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/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/increasing-triplet-subsequence/ Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists  i, j, k such that  arr[i]  <  arr[j]  <  arr[k]  given 0 ≤  i  <  j  <  k  ≤  n -1 else return false. Note:  Your algorithm should run in O( n ) time complexity and O( 1 ) space complexity. Example 1: Input: [1,2,3,4,5] Output: true Example 2: Input: [5,4,3,2,1] Output: false ---

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/knight-dialer/ A chess knight can move as indicated in the chess diagram below:  .              This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes  N-1  hops.  Each hop must be from one key to another numbered key. Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing  N  digits total. How many distinct numbers can you dial in this manner? Since the answer may be large,  output the answer modulo  10^9 + 7 .   Example 1: Input: 1 Output: 10 Example 2: Input: 2 Output: 20 Example 3: Input: 3 Output: 46   Note: 1 <= N <= 5000 ---

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/edit-distance/ Given two words  word1  and  word2 , find the minimum number of operations required to convert  word1  to  word2 . You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') --- Related problems 161-one-edit-distance --- Intuition Inserting character from 1 string is equival...

https://leetcode.com/problems/target-sum/ You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols  +  and  - . For each integer, you should choose one from  +  and  -  as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer. ----- Intuition Number of ways => DFS At each array index, we have two choices, + , - Terminate recursion when index == A.length * -- Can be memoized ---