Given a list of words and a line width, justify the lines such that pack as much lines into one line as possible with at least one space in between (cannot exceeds line width). Evenly pad the remaining line space with white spaces. For the last line, left justify the remaining words and pad the […]
Given an input string s and a number k. Find the longest substring of s such that each character in the substring occurs at least K times. Divide and Conquer Solution This is the divide and conquer solution. The idea at its core is that for the given segment of substring [l, r], count occurrence […]
Merge Intervals First sort the intervals based on starting point. (Using Collections.sort(intervals, new Comparator() { @Override public int compare(Interval i1, Interval i2) { return i1.start – i2.start; } });). Then walk through the intervals and either insert a new one or merge with previous one. Time: O(nlogn), sorting. Note that timing is worse if merge […]
Given a flight matrix (N x N), where flight[i][j] representing whether there’s a flight from city i to city j, and a days matrix (N x K), where days[i][j] representing the number of days can stay in city i at week j. Week one start at city 0. Need to find out the maximum number […]
Post-Order Traversal (Iterative) This is a powerful framework to do backtracking iteratively. Think about it. Backtracking is essentially post-order traversal where leaf nodes are visited first while information propagate back up. There are some key ideas: Use a stack to store nodes need to be visited. Use an auxiliary pointer (head) points to the […]
Given two binary tree, determine whether two trees are the same with same structure and values. Recursion Solution Each recursion call first checks whether two current nodes have the same value and structure. If yes, it recurse on both of their left child and both of their right child in tandem. Time: O(n), visit each […]
Given a cell phone key pad where each number is associated with a list of letters. For the given number string, find all letter combinations of that number string. EPI 6.7 Letter Combinations (DFS Solution) Enumeration like this best solve with recursion. This is the DFS solution. The idea is carry current string and result […]
Binary Tree Consecutive Sequence II (Backtracking Solution) Given a binary tree, find the longest consecutive sequence in the binary tree. Note that it can be any direction, rather than only from parent to child as in its previous problem. The idea is to use backtracking. Brush up on backtracking. It it recursion which does recursion […]
Binary Tree Longest Consecutive Sequence (DFS Solution) The idea is to traverse the binary tree with DFS, meanwhile carry the current consecutive length so far. Also pass in the target, which is current_value + 1 to child recursion call, so that child can compare itself to the target: (1) if child is consecutive, increment the […]
Given N flowers. One flower blooms per day. Array flowers[i] gives the flower position (1-based) blooms at i + 1th day. Find the first day where there are k not bloomed flowers between two flowers already bloomed. [Optimal]Two Pointers/Sliding Window Solution Put in another word, we need to find two flowers such that all the […]
bilbo3000.wordpress.com 