Maximum Xor of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai< 231. Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28. Solution (prefix hashset - less efficient) Time: O(N) Space: O(1) class Solution: def findMaximumXOR(self, nums: List[int]) -> int: # 0bxxxxxx - 0b L = len(bin(max(nums))) - 2 max_xor = 0 for i in range(L-1, -1, -1): max_xor <<= 1 print("max_xor:", bin(max_xor) ) # set the rightmost bit to 1 curr_xor = max_xor | 1 print("curr_xor:", bin(curr_xor) ) # highest (L-i) bits prefixes = {num >> i for num in nums} print("prefixes:", [bin(p) for p in prefixes] ) # as long as there exists a p that makes curr_xor^p > 0 # Update max_xor, if two of these prefixes could result in curr_xor.

by lek tin in "algorithm" access_time 2-min read

Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9]. Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000. Solution (iterative) class Solution: def lexicalOrder(self, n: int) -> List[int]: res = [0 for i in range(n)] curr = 1 for i in range(n): res[i] = curr # lower digits if curr * 10 <= n: curr *= 10 # higher digits else: # if curr is greater than n, we reverse it by /10 if curr >= n: curr //= 10 curr += 1 # if curr becomes X00000, we need to get rid of the trailing 0's while curr % 10 == 0: curr //= 10 return res # Input: n = 50 # Output: [1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,32,33,34,35,36,37,38,39,4,40,41,42,43,44,45,46,47,48,49,5,50,6,7,8,9] Solution (recursion) Recursion

by lek tin in "algorithm" access_time 1-min read

K Th Smallest in Lexicographical Order

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n. Note: 1 ≤ k ≤ n ≤ 10^9. Example Input: n: 13 k: 2 Output: 10 Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10. Solution class Solution: def findKthNumber(self, n: int, k: int) -> int: if n < k or k < 1: return 0 if n < 10: return k curr = 1 k -= 1 while k > 0: leap, prev, next = 0, curr, curr+1 while prev <= n: # update leap leap += min(n+1, next) - prev prev *= 10 next *= 10 if leap <= k: curr += 1 print(leap, "<= k; curr =", curr) k -= leap else: curr *= 10 print(leap, "> k; curr =", curr) k -= 1 return curr # Input: n=1300, k=50 # order: [1,10,100,1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,101,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,102,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,103,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,104,1040,1041,1042] # Output: # 412 > k; curr = 10 # 111 > k; curr = 100 # 11 <= k; curr = 101 # 11 <= k; curr = 102 # 11 <= k; curr = 103 # 11 <= k; curr = 104 # 11 > k; curr = 1040 # 1 <= k; curr = 1041 # 1 <= k; curr = 1042

by lek tin in "algorithm" access_time 2-min read

Implement Trie Prefix Tree

Implement a trie with insert, search, and startsWith methods. Example Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // returns true trie.search("app"); // returns false trie.startsWith("app"); // returns true trie.insert("app"); trie.search("app"); // returns true Note You may assume that all inputs are consist of lowercase letters a-z. All inputs are guaranteed to be non-empty strings. Solution Java class Trie { class TrieNode { private TrieNode[] children; private final int R = 26; private boolean isWord; public TrieNode() { children = new TrieNode[R]; } public boolean containsKey(char ch) { return children[ch -'a'] !

by lek tin in "algorithm" access_time 3-min read

Add and Search Word Data Structure Design

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter. Example addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note You may assume that all words are consist of lowercase letters a-z. Solution

by lek tin in "algorithm" access_time 1-min read