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

Design Hashset

Design a HashSet without using any built-in hash table libraries. To be specific, your design should include these functions: add(value): Insert a value into the HashSet. contains(value): Return whether the value exists in the HashSet or not. remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing. Example MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // returns true hashSet.contains(3); // returns false (not found) hashSet.

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

Most Common Word

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique. Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase. Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.

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

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection. Example 1 Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Example 2 Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Note Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm?

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

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection. Example 1 Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2 Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Note Each element in the result must be unique. The result can be in any order. Solution Use binary search when one of the lists is very long and the other is short class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: if len(nums1) < len(nums2): return self.

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