SWE Interview preparation

https://leetcode.com/problems/robot-return-to-origin/ There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot  ends up at (0, 0)  after it completes its moves. The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false. Note : The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.   Example 1: Input: moves = "UD" Output: true Explanation : The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true. Example 2:

https://leetcode.com/problems/lemonade-change/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a queue to buy from you, and order one at a time (in the order specified by  bills ). Each customer will only buy one lemonade and pay with either a  $5 ,  $10 , or  $20  bill.  You must provide the correct change to each customer, so that the net transaction is that the customer pays $5. Note that you don't have any change in hand at first. Return  true  if and only if you can provide every customer with correct change.   Example 1: Input: [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true. Example 2: Input: [5,5,10] Output: true Example 3: Input: [10,10] Output: false Example 4: Input: [5,5,10,10,20] Output: false Explana

https://github.com/openset/leetcode/tree/master/problems/find-leaves-of-binary-tree https://leetcode.com/problems/find-leaves-of-binary-tree/ https://www.lintcode.com/problem/find-leaves-of-binary-tree/description Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.   Example: Input: [1,2,3,4,5]     1 / \ 2 3 / \ 4 5 Output: [[4,5,3],[2],[1]]   Explanation: 1. Removing the leaves  [4,5,3]  would result in this tree: 1 / 2   2. Now removing the leaf  [2]  would result in this tree: 1   3. Now removing the leaf  [1]  would result in the empty tree: [] ----- Intuition Need info from both left, and right child to determine if current node is leaf node Post Order DFS Consider looking up the tree from below where the level is determined as the height from below  Terminate recursi

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e.,   [0,1,2,4,5,6,7]  might become   [4,5,6,7,0,1,2] ). Find the minimum element. The array may contain duplicates. Example 1: Input: [1,3,5] Output: 1 Example 2: Input: [2,2,2,0,1] Output: 0 Note: This is a follow up problem to  Find Minimum in Rotated Sorted Array . Would allow duplicates affect the run-time complexity? How and why? ---- Intuition Standard binary search with unknown target while (lo <= hi) when lo == hi => infinite loop => terminate Need to determine where pivot (minimum element) is relative to mid if (nums[mid] < nums[hi])     => mid to hi is strictly increasing     => search in lower half     => mid is min, potential ans, cannot discard     => hi = mid else if (nums[mid] > nums[hi])     => pivot is somewhere between mid and hi     => mid is higher element, disca

https://leetcode.com/problems/employee-importance/ You are given a data structure of employee information, which includes the employee's   unique id , their  importance value   and their  direct   subordinates' id. For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is  not direct . Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates. Example 1: Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1 Output: 11 Explanation: Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importanc

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ Given an array of integers   nums   and a positive integer   k , find whether it's possible to divide this array into   k   non-empty subsets whose sums are all equal.   Example 1: Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: True Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.   Note: 1 <= k <= len(nums) <= 16 . 0 < nums[i] < 10000 . --- --- Intuition If the sum of all elements in array % k != 0     return false DFS on all combinations, and keep track of sums      Terminate on last index .. reached here only if all sums are valid             return true     for (i = 0... k)          if (sums[i] + nums[index] <= target)               sums[i] += nums[index]               if (dfs(nums, sums, index + 1, target))                    return true               sums[i] -= nums[index]     return false This tries all combinations Can optimize Sort

https://leetcode.com/problems/matchsticks-to-square/ Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used  exactly  one time. Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has. Example 1: Input: [1,1,2,2,2] Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1. Example 2: Input: [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks. Note: The length sum of the given matchsticks is in the range of  0  to  10^9 . The length of the given matchstick array will not exceed

https://leetcode.com/problems/shortest-word-distance/ https://www.lintcode.com/problem/shortest-word-distance/description https://github.com/openset/leetcode/tree/master/problems/shortest-word-distance Given a list of words and two words  word1  and  word2 , return the shortest distance between these two words in the list. Example: Assume that words =  ["practice", "makes", "perfect", "coding", "makes"] . Input: word1 = “coding” , word2 = “practice” Output: 3 Input: word1 = "makes" , word2 = "coding" Output: 1 Note: You may assume that  word1   does not equal to   word2 , and  word1  and  word2  are both in the list. --- Intuition We just need access to closest indexes for word1, word2 We can get that as soon as we find first matches of word1 and word2 Traverse left to right, and save index1, index2 if we find a match if (index1 != -1 && index2 != -1) {     ans = min(ans, abs(index1 - index2)) } ---