SWE Interview preparation

https://leetcode.com/problems/interleaving-string/ Given  s1 ,  s2 ,  s3 , find whether  s3  is formed by the interleaving of  s1  and  s2 . Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

https://leetcode.com/problems/continuous-subarray-sum/ Given a list of  non-negative  numbers and a target  integer  k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of  k , that is, sums up to n*k where n is also an  integer .   Example 1: Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6. Example 2: Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.   Note: The length of the array won't exceed 10,000. You may assume the sum of all the numbers is in the range of a signed 32-bit integer. ---

https://leetcode.com/problems/merge-two-binary-trees/ Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: Merged tree: 3 / \ 4 5 / \ \ 5 4 7   Note:  The merging process must start from the root nodes of both trees. ---

https://leetcode.com/problems/stickers-to-spell-word/ We are given N different types of stickers. Each sticker has a lowercase English word on it. You would like to spell out the given  target  string by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker. What is the minimum number of stickers that you need to spell out the  target ? If the task is impossible, return -1. Example 1: Input: ["with", "example", "science"], "thehat" Output: 3 Explanation: We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string. Example 2: Input: ["notice", "possible"], "basicbasic" Output: -1 Explanation: We ...

https://leetcode.com/problems/maximum-product-subarray/ Given an integer array  nums , find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation:  [2,3] has the largest product 6. Example 2: Input: [-2,0,-1] Output: 0 Explanation:  The result cannot be 2, because [-2,-1] is not a subarray.

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/ Design a data structure that supports all following operations in  average   O(1)  time. Note: Duplicate elements are allowed. insert(val) : Inserts an item val to the collection. remove(val) : Removes an item val from the collection if present. getRandom : Returns a random element from current collection of elements. The probability of each element being returned is  linearly related  to the number of same value the collection contains. Example: // Init an empty collection. RandomizedCollection collection = new RandomizedCollection(); // Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1); // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1); // Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2); // getRand...

https://leetcode.com/problems/design-circular-queue/ Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer". One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values. Your implementation should support following operations: MyCircularQueue(k) : Constructor, set the size of the queue to be k. Front : Get the front item from the queue. If the queue is empty, return -1. Rear : Get the last item from the queue. If the queue is empty, return -1. enQueue(value) : Insert an element into the circular queue. Re...

https://leetcode.com/problems/increasing-subsequences/ Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2.   Example: Input: [4, 6, 7, 7] Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]   Note: The length of the given array will not exceed 15. The range of integer in the given array is [-100,100]. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence. ---

https://leetcode.com/problems/largest-bst-subtree/ https://github.com/openset/leetcode/tree/master/problems/largest-bst-subtree https://www.interviewbit.com/problems/largest-bst-subtree/ Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it. Note: A subtree must include all of its descendants. Example: Input: [10,5,15,1,8,null,7] 10 / \ 5 15 / \ \ 1 8 7 Output: 3 Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3. Follow up: Can you figure out ways to solve it with O(n) time complexity? --- Related problems 124-binary-tree-maximum-path-sum 543-diameter-of-binary-tree ---

https://leetcode.com/problems/reverse-integer/ Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2 31 ,  2 31  − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. --- Intuition Catch last digit Check overflow and underflow boundary condition update ans Time Complexity : O(log n) - number of digits Space Complexity : O(1) - Constant  ---

https://leetcode.com/problems/rectangle-area/ Find the total area covered by two  rectilinear  rectangles in a  2D  plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure. Example: Input: A = -3 , B = 0 , C = 3 , D = 4 , E = 0 , F = -1 , G = 9 , H = 2 Output: 45 Note: Assume that the total area is never beyond the maximum possible value of  int . ---

https://leetcode.com/problems/remove-linked-list-elements/ Remove all elements from a linked list of integers that have value  val . Example: Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 -- Intuition Have a prev pointer If head.val == target    Set the prev to head.next else    prev = prev.next Preprocess Corner case, while head.val == target at the beginning of list -- Related problems 237-delete-node-in-linked-list ---

https://leetcode.com/problems/remove-invalid-parentheses/ Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results. Note:  The input string may contain letters other than the parentheses  (  and  ) . Example 1: Input: "()())()" Output: ["()()()", "(())()"] Example 2: Input: "(a)())()" Output: ["(a)()()", "(a())()"] Example 3: Input: ")(" Output: [""] --- Related problems 1249-minimum-remove-to-make-valid 1021-remove-outermost-parentheses --- Intuition Minimum removals => BFS Find the level at which valid sub string is found, all valid combinations are of same length, and at same level isValid helper function     if ( count++     if ) count--     if count < 0 => return false return count == 0 BFS - Q and visited set hold both valid, and invalid strings if current is valid, mark isValid, and simply poll from Q, no m...

https://leetcode.com/problems/closest-binary-search-tree-value https://www.lintcode.com/problem/closest-binary-search-tree-value/description Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286 4 / \ 2 5 / \ 1 3 Output: 4 --- Intuition Find closest node tracking the min diff Pay attention to corner case - target >= Integer.MAX_VALUE Initialize the closest node to Double.MAX_VALUE --- Time - O(n) Space - O(h) - recursive call stack best case - O(log n) - balanced BST worst case - O(n) for one sided skewed BST --- Related problems 272-closest-binary-search-tree-value-ii

https://leetcode.com/problems/compare-version-numbers/ Compare two version numbers  version1  and  version2 . If  version1  >  version2  return  1;  if  version1  <  version2  return  -1; otherwise return  0 . You may assume that the version strings are non-empty and contain only digits and the  .  character. The  .  character does not represent a decimal point and is used to separate number sequences. For instance,  2.5  is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision. You may assume the default revision number for each level of a version number to be  0 . For example, version number  3.4  has a revision number of  3  and  4  for its first and second level revision number. Its third and fourth level revision number are both  0 . Example 1: I...

https://leetcode.com/problems/most-common-word/ Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words.  It is guaranteed there is at least one word that isn't banned, and that the answer is unique. Words in the list of banned words are given in lowercase, and free of punctuation.  Words in the paragraph are not case sensitive.  The answer is in lowercase. Example: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit." banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because i...