SWE Interview preparation

https://leetcode.com/problems/fibonacci-number/ The  Fibonacci numbers , commonly denoted  F(n)  form a sequence, called the  Fibonacci sequence , such that each number is the sum of the two preceding ones, starting from  0  and  1 . That is, F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1. Given  N , calculate  F(N) .   Example 1: Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1. Example 2: Input: 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2. Example 3: Input: 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.   Note: 0 ≤  N  ≤ 30.

https://leetcode.com/problems/partition-equal-subset-sum/ Given a  non-empty  array containing  only positive integers , find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200.   Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].   Example 2: Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets. ---

https://leetcode.com/problems/max-dot-product-of-two-subsequences/ Given two arrays  nums1  and  nums2 . Return the maximum dot product between  non-empty  subsequences of nums1 and nums2 with the same length. A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  [2,3,5]  is a subsequence of  [1,2,3,4,5]  while  [1,5,3]  is not).   Example 1: Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6] Output: 18 Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2. Their dot product is (2*3 + (-2)*(-6)) = 18. Example 2: Input: nums1 = [3,-2], nums2 = [2,-6,7] Output: 21 Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2. Their dot product is (3*7) = 21. Example 3: Input: nums1 = [-1,-1], nums2 = [1,1] Output: -1 Explanation: Tak...

https://leetcode.com/problems/uncrossed-lines/ We write the integers of  A  and  B  (in the order they are given) on two separate horizontal lines. Now, we may draw  connecting lines : a straight line connecting two numbers  A[i]  and  B[j]  such that: A[i] == B[j] ; The line we draw does not intersect any other connecting (non-horizontal) line. Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line. Return the maximum number of connecting lines we can draw in this way.   Example 1: Input: A = [1,4,2] , B = [1,2,4] Output: 2 Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2. Example 2: Input: A = [2,5,1,2,5] , B = [10,5,2,1,5,2] Output: 3 Example 3: Input: A = [1,3,7,1,7,5] , B = [1,9,2,5,1] Output: 2   Note: 1 <= A.length <...

https://leetcode.com/problems/unique-binary-search-trees/ Given  n , how many structurally unique  BST's  (binary search trees) that store values 1 ...  n ? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 --- Related problems 95-unique-binary-search-trees-ii ---

https://leetcode.com/problems/unique-binary-search-trees-ii/ Given an integer  n , generate all structurally unique  BST's  (binary search trees) that store values 1 ...  n . Example: Input: 3 Output: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 --- Related problems 96-unique-binary-search-trees ---

https://leetcode.com/problems/wildcard-matching/ Given an input string ( s ) and a pattern ( p ), implement wildcard pattern matching with support for  '?'  and  '*' . '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the  entire  input string (not partial). Note: s  could be empty and contains only lowercase letters  a-z . p  could be empty and contains only lowercase letters  a-z , and characters like  ?  or  * . Example 1: Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa" p = "*" Output: true Explanation:  '*' matches any sequence. Example 3: Input: s = "cb" p = "?a" Output: false Explanation:  '?' matches 'c', but the second letter is 'a', which does not match 'b'. Example 4: ...

https://leetcode.com/problems/longest-palindromic-subsequence/ Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000. Example 1: Input: "bbbab" Output: 4 One possible longest palindromic subsequence is "bbbb". Example 2: Input: "cbbd" Output: 2 One possible longest palindromic subsequence is "bb". ---

https://leetcode.com/problems/frog-jump/ A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water. Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit. If the frog's last jump was  k  units, then its next jump must be either  k  - 1,  k , or  k  + 1 units. Note that the frog can only jump in the forward direction. Note: The number of stones is ≥ 2 and is < 1,100. Each stone's position will be a non-negative integer < 2 31 . The first stone's position is always 0. Example 1: [0,1,3,5,6,8,12,17] There are a total of 8 stones. The first stone at the 0th unit, second stone at the 1st unit, third stone at the 3rd unit, and so on... The last stone at...

https://leetcode.com/problems/longest-arithmetic-sequence/ Given an array  A  of integers, return the  length  of the longest arithmetic subsequence in  A . Recall that a  subsequence  of  A  is a list  A[i_1], A[i_2], ..., A[i_k]  with  0 <= i_1 < i_2 < ... < i_k <= A.length - 1 , and that a sequence  B  is  arithmetic  if  B[i+1] - B[i]  are all the same value (for  0 <= i < B.length - 1 ).   Example 1: Input: [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3. Example 2: Input: [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10]. Example 3: Input: [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5].   Note: 2 <= A.length <= 2000 0 <= A[i] <= 10000 ---

https://leetcode.com/problems/word-break-ii/ Given a  non-empty  string  s  and a dictionary  wordDict  containing a list of  non-empty  words, add spaces in  s  to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = " catsanddog " wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [   "cats and dog",   "cat sand dog" ] Example 2: Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3: Inpu...

https://leetcode.com/problems/n-th-tribonacci-number/ The Tribonacci sequence T n  is defined as follows:  T 0  = 0, T 1  = 1, T 2  = 1, and T n+3  = T n  + T n+1  + T n+2  for n >= 0. Given  n , return the value of T n . Example 1: Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 Example 2: Input: n = 25 Output: 1389537 Constraints: 0 <= n <= 37 The answer is guaranteed to fit within a 32-bit integer, ie.  answer <= 2^31 - 1 . --- Intuition Similar to Fibonacci series F(N) = F(N - 1) + F(N - 2) + F(N - 3) We just need last three entries, no need for full DP table ---- Time - O(n) Space - O(1) --- Related problems climbing-stairs ---

https://leetcode.com/problems/climbing-stairs/ You are climbing a stair case. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note:  Given  n  will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step --- Intuition How can we reach stair n One step from n - 1 or Two steps from n - 2 # ways to reach n = # ways to reach (n -1) + # ways to reach (n - 2) F(n) = F(n - 1) + F(n -2) Recursion with memoization. We do not need all past entries, just two last ones are sufficient - constant space -- Time - O(n) Space - O(1) -- Related problems min-cost-climbing-stairs