Given a prefix polish notation, convert to a binary tree. Recursion All numbers must be leaf node, so when see a number, create a node and return. For an operator, recursively build left and right subtree while keep advancing the index on string. This file contains bidirectional Unicode text that may be interpreted or compiled […]
Given a list of strings. If a string is a shifted version of another, they are considered shifted strings. Group all shifted strings togethers. Observation is that “diff string” of each char is the same for group of a shifted strings. We can convert each string to diff string as the key. One tricky part […]
Given a binary tree, convert it to a doubly linked list. Recursion Each recursion returns a pair of left and right end of the list. At each node, it recurse on left and right, then tries to join current node with left/right results. Time: O(n) This file contains bidirectional Unicode text that may be interpreted […]
Given a 2D city blocks and a list of post offices coordinates. Calculate the minimum distance each block to the nearest post officies. BFS Initialize all cells to -1, meaning the distances all need to be determined. The core idea is to run BFS from each post office concurrently. This ensures that each cell will […]
Given an unsorted array, determine whether it has an increasing triplet subsequence. Invariant Walk the array and keep updating small and mid (in order) if find better one (i.e. smaller). This makes sense because (1) both value can only go down; (2) mid always greater than small. Thus when find a number greater than mid, […]
Given a triangle, find the minimum path from top to bottom. The idea is to use an array to keep track of min path to current level, which is built from previous level, walking backwards in a row. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. […]
DFS Use a stack to store nodes in topological order. Use a set to track visited node. Run dfs, where a node is pushed onto stack after all its children has been visited. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file […]
Given a list list (without knowing its length), return a random node where each node has equal probability to be picked. Reservoir Sampling Walk through the list meanwhile keep track of current result and number of nodes seen so far (cnt). Each time generate a random number in [0, cnt-1] (via rand.nextInt(cnt)). Use current node […]
Given an array with positive integers, count all subarrays that have product less than k. Two Pointers Two pointers walk the array representing current subarray. Maintain current product. If new element can join the subarray, it will introduce new subarray for each previous one, thus adding the length of subarray to the result. Otherwise, moving […]
Given a list of votes of pairs. Return top k votes up to a certain timestamp. TreeSet When need this kind floor/ceiling type of operations, considering using tree set. lower()/higher()/headSet()/tailSet() Use priority queue to find top k. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To […]
bilbo3000.wordpress.com 