SWE Interview preparation

Negative numbers in sorted array Given a sorted array of integers, find the number of negative numbers. Expected Time Complexity: O(log n) Examples Array: [-5, -3, -2, 3, 4, 6, 7, 8] Answer: 3 Array: [0, 1, 2, 3, 4, 6, 7, 8] Answer: 0 --- Intuition Sorted array => binary search Find last index of number matching condition If does not match condition - switch search space to other half if matches condition - save, and reduce search space in current half --- Complexity Time - O(log N) Space - O(1) - iterative --- ---

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: fal...

https://leetcode.com/problems/letter-case-permutation/ Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create. Examples: Input: S = "a1b2" Output: ["a1b2", "a1B2", "A1b2", "A1B2"] Input: S = "3z4" Output: ["3z4", "3Z4"] Input: S = "12345" Output: ["12345"] Note: S  will be a string with length between  1  and  12 . S  will consist only of letters or digits. --- Related problems 77-combinations 46-permutations 47-permutations-ii ---

https://leetcode.com/problems/count-and-say/ The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1  is read off as  "one 1"  or  11 . 11  is read off as  "two 1s"  or  21 . 21  is read off as  "one 2 , then  one 1"  or  1211 . Given an integer  n  where 1 ≤  n  ≤ 30, generate the  n th  term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit. Note: Each term of the sequence of integers will be represented as a string.   Example 1: Input: 1 Output: "1" Explanation: This is the base case. Example 2: Input: 4 Output: "1211" Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and val...

https://leetcode.com/problems/shuffle-the-array/ Given the array  nums  consisting of  2n  elements in the form  [x 1 ,x 2 ,...,x n ,y 1 ,y 2 ,...,y n ] . Return the array in the form   [x 1 ,y 1 ,x 2 ,y 2 ,...,x n ,y n ] .   Example 1: Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x 1 =2, x 2 =5, x 3 =1, y 1 =3, y 2 =4, y 3 =7 then the answer is [2,3,5,4,1,7]. Example 2: Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1] Example 3: Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]   Constraints: 1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3 Accepted 11,047 Submissions 11,992 ---  Time - O(N) Space - O(N) ---

https://leetcode.com/problems/k-diff-pairs-in-an-array/ Given an array of integers and an integer  k , you need to find the number of  unique  k-diff pairs in the array. Here a  k-diff  pair is defined as an integer pair (i, j), where  i  and  j  are both numbers in the array and their  absolute difference  is  k . Example 1: Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs. Example 2: Input: [1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5). Example 3: Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1). Note: The pairs (i, j) and (j, i) count as the same pair. The length of the array won't exceed 10,000. All the integers in the given input belong to the ra...

https://leetcode.com/problems/binary-tree-tilt/ Given a binary tree, return the tilt of the  whole tree . The tilt of a  tree node  is defined as the  absolute difference  between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the  whole tree  is defined as the sum of all nodes' tilt. Example: Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1 Note: The sum of node values in any subtree won't exceed the range of 32-bit integer. All the tilt values won't exceed the range of 32-bit integer. --- Intuition We need info from left, right child to compute answer for current node Post Order DFS seems appropriate Increment the ans by Math.abs(dfs(node.left) - dfs(node.right)) return sum of all includes - left + right + self for parent to process in post order --- Time ...

https://leetcode.com/problems/convert-bst-to-greater-tree/ Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 Note:  This question is the same as 1038:  https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ --- Related problems 1038-binary-search-tree-to-greater-sum --- Time - O(N) Space - O(N) --

https://leetcode.com/problems/factorial-trailing-zeroes/ Given an integer  n , return the number of trailing zeroes in  n !. Example 1: Input: 3 Output: 0 Explanation:  3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation:  5! = 120, one trailing zero. Note:  Your solution should be in logarithmic time complexity. --- Intuition - Count number of 5 factors in n Time - O( Log N base 5) ---

https://leetcode.com/problems/palindrome-number/ Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome. Follow up: Coud you solve it without converting the integer to a string?

https://leetcode.com/problems/max-stack/ https://github.com/openset/leetcode/tree/master/problems/max-stack https://www.lintcode.com/problem/max-stack/description Design a max stack that supports push, pop, top, peekMax and popMax. push(x) -- Push element x onto stack. pop() -- Remove the element on top of the stack and return it. top() -- Get the element on the top. peekMax() -- Retrieve the maximum element in the stack. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one. Example 1: MaxStack stack = new MaxStack(); stack.push(5); stack.push(1); stack.push(5); stack.top(); -> 5 stack.popMax(); -> 5 stack.top(); -> 1 stack.peekMax(); -> 5 stack.pop(); -> 1 stack.top(); -> 5 Note: -1e7 <= x <= 1e7 Number of operations won't exceed 10000. The last four operations won't be called when stack is empty. --- Related problems 155-min-stack ---

https://leetcode.com/problems/two-city-scheduling/ There are  2N  people a company is planning to interview. The cost of flying the  i -th person to city  A  is  costs[i][0] , and the cost of flying the  i -th person to city  B  is  costs[i][1] . Return the minimum cost to fly every person to a city such that exactly  N  people arrive in each city. Example 1: Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city. Note: 1 <= costs.length <= 100 It is guaranteed that  costs.length  is even. 1 <= costs[i][0], costs[i][1] <= 1000

https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/ Tic-tac-toe is played by two players  A  and  B  on a  3  x  3  grid. Here are the rules of Tic-Tac-Toe: Players take turns placing characters into empty squares (" "). The first player  A  always places "X" characters, while the second player  B  always places "O" characters. "X" and "O" characters are always placed into empty squares, never on filled ones. The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal. The game also ends if all squares are non-empty. No more moves can be played if the game is over. Given an array  moves  where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which  A  and  B  play. Return the winner of the game if it exists ( A  or  B ), in...