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/search-insert-position/ Given a sorted array 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 may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0

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/inorder-successor-in-bst/ https://github.com/openset/leetcode/tree/master/problems/inorder-successor-in-bst https://www.lintcode.com/problem/inorder-successor-in-bst/description Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node  p  is the node with the smallest key greater than  p.val .   Example 1: Input: root = [2,1,3] , p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2: Input: root = [5,3,6,2,4,null,null,1] , p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null .   Note: If the given node has no in-order successor in the tree, return  null . It's guaranteed that the values of the tree are unique. --- Related problems 701-insert-into-binary-search-tree ---

https://leetcode.com/problems/time-based-key-value-store/ Create a timebased key-value store class  TimeMap , that supports two operations. 1.  set(string key, string value, int timestamp) Stores the  key  and  value , along with the given  timestamp . 2.  get(string key, int timestamp) Returns a value such that  set(key, value, timestamp_prev)  was called previously, with  timestamp_prev <= timestamp . If there are multiple such values, it returns the one with the largest  timestamp_prev . If there are no values, it returns the empty string ( "" ).   Example 1: Input: inputs = ["TimeMap","set","get","get","set","get","get"] , inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]] Output: [null,null,"bar","bar",null,"bar2","bar2"] Explanation:   TimeMa...

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ https://workat.tech/problem-solving/practice/two-sum-sorted Given an array of integers that is already  sorted in ascending order , find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have  exactly  one solution and you may not use the  same  element twice. Example: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. ---

https://leetcode.com/problems/split-array-largest-sum/ Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays. Note: If  n  is the length of array, assume the following constraints are satisfied: 1 ≤  n  ≤ 1000 1 ≤  m  ≤ min(50,  n ) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8] , where the largest sum among the two subarrays is only 18. --- Related problems 774-minimize-max-distance-to-gas-station 875-koko-eating-bananas 1011-capacity-to-ship-packages-within-d-days ---

https://leetcode.com/problems/single-element-in-a-sorted-array/ You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.   Example 1: Input: [1,1,2,3,3,4,4,8,8] Output: 2 Example 2: Input: [3,3,7,7,10,11,11] Output: 10   Note:  Your solution should run in O(log n) time and O(1) space. ----

https://leetcode.com/problems/integer-to-roman/ Roman numerals are represented by seven different symbols:  I ,  V ,  X ,  L ,  C ,  D  and  M . Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as  II  in Roman numeral, just two one's added together. Twelve is written as,  XII , which is simply  X  +  II . The number twenty seven is written as  XXVII , which is  XX  +  V  +  II . Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not  IIII . Instead, the number four is written as  IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as  IX . There are six instances where subtraction is used: I  can be placed bef...

https://leetcode.com/problems/search-a-2d-matrix/ Write an efficient algorithm that searches for a value in an  m  x  n  matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 3 Output: true Example 2: Input: matrix = [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] target = 13 Output: false --- Intuition Binary search between lo = 0, hi = matrix.length * matrix[0].length - 1 r = mid / matrix[0].length; c = mid % matrix[0].length; --- Time - O ( Log N) - N = R * C => O (Log (R * C)) Space - O(1) --- Second approach Start search at top right while r < matrix.length && c >= 0      if (matrix[r][c] == target)          return true      if (ma...

https://www.lintcode.com/problem/minimize-max-distance-to-gas-station/ https://leetcode.com/problems/minimize-max-distance-to-gas-station/ On a horizontal number line, we have gas stations at positions  stations[0], stations[1], ..., stations[N-1] , where  N = stations.length . Now, we add  K  more gas stations so that  D , the maximum distance between adjacent gas stations, is minimized. Return the smallest possible value of  D . Example: Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 Output: 0.500000 Note: stations.length  will be an integer in range  [10, 2000] . stations[i]  will be an integer in range  [0, 10^8] . K  will be an integer in range  [1, 10^6] . Answers within  10^-6  of the true value will be accepted as correct. --- Related problems 410-split-array-largest-sum 875-koko-eating-bananas 1011-capacity-to-ship-packages-within-d-days --- Intuition Corner cases =>     Wo...

https://leetcode.com/problems/koko-eating-bananas Koko loves to eat bananas.  There are  N  piles of bananas, the  i -th pile has  piles[i]  bananas.  The guards have gone and will come back in  H  hours. Koko can decide her bananas-per-hour eating speed of  K .  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than  K  bananas, she eats all of them instead, and won't eat any more bananas during this hour. Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back. Return the minimum integer  K  such that she can eat all the bananas within  H  hours. Example 1: Input: piles = [3,6,7,11] , H = 8 Output: 4 Example 2: Input: piles = [30,11,23,4,20] , H = 5 Output: 30 Example 3: Input: piles = [30,11,23,4,20] , H = 6 Output: 23 Note: 1 <= piles.length <= 10^4 ...

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/ Let's define a function  f(s)  over a non-empty string  s , which calculates the frequency of the smallest character in  s . For example, if  s = "dcce"  then  f(s) = 2  because the smallest character is  "c"  and its frequency is 2. Now, given string arrays  queries  and  words , return an integer array  answer , where each  answer[i]  is the number of words such that  f(queries[i])  <  f(W) , where  W  is a word in  words . Example 1: Input: queries = ["cbd"], words = ["zaaaz"] Output: [1] Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz"). Example 2: Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] Output: [1,2] Explanation: On the first query only f("bbb") < f(...