SDE - 1

It was a dp problem. Firstly I used recursion to solve it.

static int count(int S[], int m, int n)
{

// If n is 0 then there is 1 solution
// (do not include any coin)
if (n == 0)
return 1;

// If n is less than 0 then no
// solution exists
if (n < 0)
return 0;

// If there are no coins and n
// is greater than 0, then no
// solution exist
if (m <= 0)
return 0;

// count is sum of solutions (i)
// including S[m-1] (ii) excluding S[m-1]
return count(S, m - 1, n) +
count(S, m, n - S[m - 1]);
}

It was an exponential solution ie TC - 2^n

We then used an array which reduced TC to n^2

static long countWays(int S[], int m, int n)
{
//Time complexity of this function: O(mn)
//Space Complexity of this function: O(n)

// table[i] will be storing the number of solutions
// for value i. We need n+1 rows as the table is
// constructed in bottom up manner using the base
// case (n = 0)
long[] table = new long[n+1];

// Initialize all table values as 0
Arrays.fill(table, 0); //O(n)

// Base case (If given value is 0)
table[0] = 1;

// Pick all coins one by one and update the table[]
// values after the index greater than or equal to
// the value of the picked coin
for (int i=0; i for (int j=S[i]; j<=n; j++)
table[j] += table[j-S[i]];

return table[n];
}

It was a basic DP problem and the interviewer wanted to see my solution building approach.
I started of by using recursion. which took exponential time.

L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.

I then used an array to build the optimal approach by comparing the previous occurring array elements with the current one.

public int lengthOfLIS(int[] nums) {

int m = nums.length;

if(m==0)return 0;

int[] dp = new int[m+1];

Arrays.fill(dp,1);

int max = Integer.MIN_VALUE;

for(int i=0;i {
//System.out.println(Arrays.toString(dp));
for(int j=0;j 
if(nums[j] dp[i]=Math.max(dp[i],dp[j]+1);

}

max = Math.max(max,dp[i]);

}
return max;
}

For Binary search tree, while traversing the tree from top to bottom the first node which lies in between the two numbers n1 and n2 is the LCA of the nodes, i.e. the first node n with the lowest depth which lies in between n1 and n2 (n1<=n<=n2) n1 < n2. So just recursively traverse the BST in, if node’s value is greater than both n1 and n2 then our LCA lies in the left side of the node, if it’s is smaller than both n1 and n2, then LCA lies on the right side. Otherwise, the root is LCA (assuming that both n1 and n2 are present in BST).

Algorithm: 

1. Create a recursive function that takes a node and the two values n1 and n2.
2. If the value of the current node is less than both n1 and n2, then LCA lies in the right subtree. Call the 
recursive function for the right subtree.
3. If the value of the current node is greater than both n1 and n2, then LCA lies in the left subtree. Call the 
recursive function for the left subtree.
4. If both the above cases are false then return the current node as LCA

Tip 1 : Always prepare your projects well enough.
Tip 2 : You should be aware of the basics of tech stack used in your projects.
Tip 3 : Prepare basics of SQL. Basic joins and where clause queries should be prepared well.