Algo Advance

Leetcode 857 Minimum Cost to Hire K Workers There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker. We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules: Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group. Every worker in the paid group must be paid at least their minimum-wage expectation. Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted. Constraints: n == quality.length == wage.length 1 <= k <= n <= 10^4 1 <= quality[i], wage[i] <= 10^4 Analysis: The first step is to get the wage/quality ratio.  Let focus on a small size first: we have two people only, (q1, r1) and (q...

Priority_queue (pq) is a powerful data structure that is very suitable for questions requires order or ranks, such as Top K problems. Especially, whenever it requires the k smallest or biggest elements during the a scanning, pq could be very convenient to use. In C++,  1. the default order inside a pq is decreasing, or the largest one is the on the top; 2. even though its name having a queue, the built-in function for the top element is pq.top(); 3. the elements inside a pq are not strictly sorted, it is more like a heap; 4. when pop out or push in one element, the pq (or heap) can automatically adjust the positions of its elements based on the relative magnitude of the element. Top K elements: 1. find the k smallest elements in an array priority_queue<int> pq; for(auto &a : array) { pq.push(a); if(pq.size() > k) pq.pop(); } 2. find the k largest elements in an array priority_queue<int, vector<int>, greater<int>> pq; for(auto &a : array) {...

Breadth-first Search - Middle Level - Question 1 Leetcode 1162  As Far from Land as Possible Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|. Constraints: n == grid.length n == grid[i].length 1 <= n <= 100 grid[i][j] is 0 or 1 Analysis: One way to solve this problem is that: for each water position, we run a bfs search to the find the shortest distance to the land. Then the get the maximum of these shortest distances. The time complexity is O(n^4), which is too large to this question. Alternatively, we can start with all lands, then do a bsf search. The last find water should have the largest distance to the land. The time complexity ...

Breadth-first Search - Easy Level - Question 1 Leetcode 101  Binary Tree Level Order Traversal Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). Constraints: The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000 Analysis: This question is pretty-straightforward: starting with the root, then layer-by-layer goes down.  1. If use a queue, need to know the number of nodes in the current nodes; 2. for each node at one layer, record the node value, then save its child leaves if exist. See the code below: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> res; if(!root) return res; queue...

Breadth-first Search - Example Leetcode 200  Number of Islands Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'. Analysis: The BFS method is straightforward: once we find a position with value of '1', then we can start the layer-by-layer expansion. To avoid redundant scan, we need to label the positions visited. Once the search is done, the count of island is updated by adding one. For the four direction expansion, a trick is used in the for loop, to short the code. See the code below: class Solution { public: int numIslands(vector<vector<char>>& grid) { if(!grid.size() || !grid.f...

Breadth-first Search (BFS) is one of the well-known brute-force search algorithms which has been widely used. The basic idea is just like its name: do the searching by expansion. Staring with the sources, the expansion diffuses layer by layer. In contrast, another common search algorithm is Depth-first Search (DFS) which focuses on one route first until reaching the end, then starts the next possible route. So one way to understand BFS is that: BFS searches all the possible routes at the same time. And for each route, BFS usually makes the same amount of progress. In the middle of the search, once a route becomes invalid, it can be dropped right away. So for BFS, 1. the minimum distance can be obtained since the shortest routes can be always found before other routes; 2. to avoid redundant search, need to make sure each position (state) is only searched once. [DFS also needs this]. 3. a queue is usually used for the search, to easier realize the layer-by-layer expansion. Example Easy L...

Dynamic Programming - Medium Level - Question 1 Leetcode 91 Decode ways A message containing letters from A-Z can be encoded into numbers using the following mapping: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into: "AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06". Given a string s containing only digits, return the number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer. Constraints: 1 <= s.length <= 100 s contains only digits and may contain leading zero(s). Analysis: We can define f(i) as the number of...

Binary Search - Interview Questions - Question 1 Minimum steps to find a baseball One baseball has been placed at one spot in an m * n matrix, and we want to quickly find the location of the baseball. For each move (can pick up any locations), the only thing we know is that we are getting closer or further from the baseball comparing to the previous position. A Boolean helper API is provided for this information: helper(x1, y1, x2, y2), where (x1, y1) is the former position and (x2, y2) the current position. When helper(x1, y1, x2, y2) is true, it means closer; false for further. Design an algorithm to find the location. Analysis: Suppose the baseball is at (x0, y0), and the matrix size is known as m * n. If we are on the top side of the matrix above X = x0, then every move down would get us closer to the target; if we are at the down side below X = x0, then every move up gets us closer too. The horizontal direction can give us the similar results. So we can  reduce the 2D problem ...

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...

Dynamic Programming - Example Leetcoce 70  Climbing Stairs You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Constraints: 1 <= n <= 45 Analysis: Think about this question, when n = 10, how many ways to finish the 10th step? Ahh, not easy to count directly, but if we know the number of ways to finish the 9th step and 8th step, then we should know the number of ways to finish the 10th step (This is recursion!!!), which is the sum of them.  Why sum? Because these are the only two different ways for the last climb to finish the 10th step, one is 1 step from the 9th, the other is 2 steps from the 8th. To generalize the question, how about to the nth step? If we define the number of ways to finish the nth step as f(n), then the number of ways for (n-1)th is f(n-1), for (n-2)th is f(n-2), and, f(n) = f(n-1) + f(n-2) How many ways to finish the first step? 1 How many w...

The dynamic programming (dp) is one of the most intriguing realm in algorithm. The main purpose for dp is to avoid redundant calculations. One of the keys to achieve this is to solve the same problem with a smaller size. Once the same question with the smaller size is solved, the results can be stored and re-used directly when meet with the same problem again. The populate word for dp is state, which means exactly the same question but different sizes (so the real idea behind dp is recursion, but with memoization). The state essentially is an abstract of the question to be solved. How to correctly define the state is one of two main difficulties for dp.  The correct state means: 1. the state can fully describe the question to be solved; 2. the state transition formula can be derived based on the state definition. The other difficulty is initialization. The initial states usually mean the question with very smaller sizes, so the results can be obtained without complex calculations. ...

Binary Search - Medium Level - Question 1 Leetcode 33  Search in Rotated Sorted Array There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity. Constraints: 1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 All values of nums are unique. nums is guaranteed to be rotated at some pivot. -10^4 <= target <= 10^4 Analysis: This question is quite popular in interview. Binary search should be the way to reach O(logn) time complexity, but t...

Binary Search - Easy Level - Question 1 Leetcode 278 First Bad Version You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. Constraints: 1 <= bad <= n <= 2^31 - 1 Analysis: The n value could be very large, so the naïve way to go back one by one is too slow. One observation is that: if the xth version is good, then all the previous versions before x are good as well. So it is suitable for the binary search. So we can make a guess first, then can s...

Binary Search - Example Leetcode 35  Search Insert Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Constraints: 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums contains distinct values sorted in ascending order. -10^4 <= target <= 10^4 Analysis: The array is sorted, so we just need to run a routine binary search. Make a guest first, then based on the guessed result, we can adjust the search range. See the code below: class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size(); while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } return left; } }; If you know t...

Recursion - Hard Level - Question 1 Leetcode 761 Special Binary String Special binary strings are binary strings with the following two properties: The number of 0's is equal to the number of 1's. Every prefix of the binary string has at least as many 1's as 0's. You are given a special binary string s. A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string. Return the lexicographically largest resulting string possible after applying the mentioned operations on the string. Constraints: 1 <= s.length <= 50 s[i] is either '0' or '1'. s is a special binary string. Analysis: One way to solve this problem is to find all the 'special binary strings', and then just sort them reversely, and then concatenate them together. The problem becomes how to break the input s...

Binary search may be one of the most intuitive algorithms: when the search space is sorted, then we can make a guess first (usually the middle in the range of [left, right)) to see whether the "guessed" value fits the condition or not. Based on the result with the "guessed" value,  we can adjust the search range by removing either the first half or the second half. Some key points: 1. The search space may be an abstract one. The basic understanding is that: if the "middle" value is Okay, and all the values smaller (or larger) than it are also Okay, then we can consider to use binary search; 2. In some special cases, binary search is NOT always the most efficient method for sorted data (for example, two sum problem with a sorted array); 3. The boundary conditions are tricky to handle. The template of the lower_bound index (the index of the first element equal to the target if exists; or the index of the first element (maybe the end of the array) larger than...

Recursion - Medium Level - Question 1 Leetcode 50  Pow(x, n) Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). Constraints: -100.0 < x < 100.0 -2^31 <= n <= 2^31-1 -10^4 <= x^n <= 10^4 Analysis: If n == 0, then it always return 1; If n == 1, it returns x. For other n, consider the positive n first (since the negative value can be calculated with the positive ones). If n is even, then pow(x, n) can be rewritten as pow(x, n/2) * pow(x, n/2); if odd, pow(x, n/2) * pow(x, n/2) * x. One of the key steps is that we just need to calculate pow(x, n/2) once, for the rest calls (or the second time to this question), just re-use the calculated results. One corner case is pow(x, INT_MIN), which will cause overflow if simply timing with (-1). Some details need to take. See the code below: class Solution { public: double myPow(double x, int n) { // the nagative case (handled the corner case) if(n<0) return 1.0/(x*myPow(x, -(n+1)))...

Recursion - Easy Level - Question 1 Leetcode 504 Base 7 Given an integer num, return a string of its base 7 representation. Constraints: -10^7 <= num <= 10^7 Analysis: 1. if abs(num) < 7, return to_string(num). For example, 0 ->  "0",  -1 -> "-1", 1 -> "1", etc. 2. otherwise, we just need to consider (num/7) and (num%7). The second part can be converted to a string directly (need to pay attention to the negative values. For example, -8. num%7 == -1, but we just need "1" actually. So need to use the abse(num%7)). The first part can be calculated recursively. See the code below: class Solution { public: string convertToBase7(int num) { // base if(abs(num) < 7) return to_string(num); // converging return convertToBase7(num/7) + to_string(abs(num%7)); } }; Upper Layer

Recursion - Example Leetcode 231  Power of Two Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2^x Constraints: -2^31 <= n <= 2^31 - 1 Analysis: One way is to think about this question recursively: if n%2 == 1, then n must not be power of 2; if not, then we just need to consider whether (n/2) is a power of 2 or not. This is exactly the "same question with a smaller size"! It is trivial to figure out the base cases: if n == 0, return false; if n == 1, return true. See the code below: class Solution { public: bool isPowerOfTwo(int n) { // base cases if(n == 0) return false; if(n == 1) return true; // converging if(n%2 == 1) return false; return isPowerOfTwo(n/2); } }; If interested, there are some other ways to solve this problem. For example, using bit manipulation, we can have the following solution: class ...

Recursion - Interview Questions - Question 1 If needed, you can read the Recursion Basics first. Please describe the recursion concept to a 5 years old? Suggested Answers: One: Russian dolls. If you open it, then there is "the same" but "smaller" one, until you reach to the most inside one. Two: Thinking about that you are sitting at the last row of a very large class room. The rows of seats have been defined as starting with the one most close to the front chalkboard (1, 2, 3, ...). The question to ask is which row you are sitting now.  Your can count it from the first row until to your row; but a different way is that: "if the row number of the one before mine is x, then my row is (x + 1)". Then the same procedure can be run until reaching the first row, which can return 1 easily. Then it can be used to return the row numbers for all the rest rows (including yours). Upper Layer

Recursion is one of the most important concepts in algorithm. Once you understand it, it is quite fair to say that you may have mastered almost "half" of the algorithm. Recursion is based one an obvious fact: computers can do repetitive operations in a much faster way than human beings. In practice, to avoid infinite loop, the terminating condition has to be clear. Thus, the size of the problem to be solved has to become smaller (Neither the same Nor larger) for every recursive call, which eventually converges to the base case.  The base cases usually have very small sizes which can return the results trivially. To sum up, some key points: a). base cases with trivial returns; b). the same question but a shrinking size. Question List Upper Layer

Who wants to read these notes? 1. the one who wants to learn algorithm; 2. the one who has a planned interview in a short amount of time, such as one month later; 3. purely out of curiosity; 4. all the rest. The primary purpose for these posts is to help anyone who wants to learn algorithm in a short amount of time and be ready for coding interviews with tech companies, such as, Amazon, Facebook, Microsoft, etc. Before you start, you are expected to already know:  1. the fundamentals of at least one programming language; 2. the fundamentals of data structures. If you do not have these basics, it is better to "google and read" some intro docs, which should NOT take large amount of time. Of course, you can always learn whenever see a "unknown" data structure or line in the codes. Remember, "google and read" is always one of keys to learning. Common algorithms: 1. Recursion 2. Binary search 3. Dynamic programming 4. Breadth-first search 5. Depth-first search...