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

Minimum Number of Refueling Stops

A car travels from a starting position to a destination which is target miles east of the starting position. Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas. The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.

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

Design Hashmap

Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions: put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value. get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

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

Design Circular Deque

Design your implementation of the circular double-ended queue (deque). Your implementation should support following operations: MyCircularDeque(k): Constructor, set the size of the deque to be k. insertFront(): Adds an item at the front of Deque. Return true if the operation is successful. insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful. deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.

by lek tin in "algorithm" access_time 3-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

Flatten 2d Vector

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext. Example Vector2D iterator = new Vector2D([[1,2],[3],[4]]); iterator.next(); // return 1 iterator.next(); // return 2 iterator.next(); // return 3 iterator.hasNext(); // return true iterator.hasNext(); // return true iterator.next(); // return 4 iterator.hasNext(); // return false Notes Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases.

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

Utf 8 Validation

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules: For 1-byte character, the first bit is a 0, followed by its unicode code. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10. This is how the UTF-8 encoding would work: Char. number range | UTF-8 octet sequence (hexadecimal) | (binary) --------------------+--------------------------------------------- 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

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

Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”. One of the benefits of the circular queue is that we can make use of the spaces in front of the queue.

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

Decode String

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k.

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

Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'.

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