SWE Interview preparation

https://leetcode.com/problems/coin-change-2/ You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.   Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. Example 3: Input: amount = 10, coins = [10] Output: 1   Note: You can assume that 0 <= amount <= 5000 1 <= coin <= 5000 the number of coins is less than 500 the answer is guaranteed to fit into signed 32-bit integer -- Intuition At every position we have 2 choices, use the coin or do not use the coin DFS with 1. use the coin, reduce remainder by coins[i], do not use the coin i + 1, remainder Memo 2D for the index, and remainin...

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/maximum-sum-circular-subarray/ Given a  circular array   C  of integers represented by  A , find the maximum possible sum of a non-empty subarray of  C . Here, a  circular array  means the end of the array connects to the beginning of the array.  (Formally,  C[i] = A[i]  when  0 <= i < A.length , and  C[i+A.length] = C[i]  when  i >= 0 .) Also, a subarray may only include each element of the fixed buffer  A  at most once.  (Formally, for a subarray  C[i], C[i+1], ..., C[j] , there does not exist  i <= k1, k2 <= j  with  k1 % A.length = k2 % A.length .)   Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3 Example 2: Input: [5,-3,5] Output: 10 Explanation:   Subarray [5,5] has maximum sum 5 + 5 = 10 Example 3: Input: [3,-1,2,-1] Output: 4 Explanation:   Subarray [2,-1,3] has...