Extremely delighted to say that I've received the intern offer from LinkedIn for the year 2023.

Here are my technical interview questions

1. You are given a balanced BST and a value X. You have to find and print the nodes whose sum is equal to X.

2. Given a length N, find the number of binary strings you can form of length N such that no two adjacent indices will have '1' in it. N can be upto 10^5.
   Eg of a valid string, N = 5, 10001, 10010, 10101, 01010, 00000, etc
   Eg of an invalid string, N = 5, 11000, 10110, 10110, 11111, 11101, etc

For the first question I gave multiple solutions

• Create an array using inorder traversal(the array becomes sorted) => now the problem is the same as 2-SUM.
  • Either do a two pointer approach [Time: O(N), Space: O(N)], or
  • Use a hashmap [Time: O(N), Space: O(N)], or
  • Binary search [Time: O(NlogN), Space: O(N)]
• While traversing the tree you can create a hashmap and check if (X - (node->val)) exists in the hashmap [Time: O(N), Space: O(N)]
• While traversing a tree since it's a BST for each node you visit you can find a node whose value is (X - (node->val)) in LogN time [Time: O(NlogN), Space: O(1)] [He asked me to write this code]

He asked me if I could do better that is Time: O(N) and Space: O(1)
I was given a hint to do it iteratively so I explained to him the approach using two pointers but for nodes.
Judging by the remaining time, I wasn't sure if I could code though, so we started the second problem.

The problem seems pretty self-explanable that we need to use Dynamic Programming.

• Transition: Either update current to 0 or to 1 so number of transitions = 2
• State: There are N indices hence N states are possible so number of states = N
• Time Complexity = O(Transition * Space) = O(N)

Code for the second problem

int dp[100005][2] = {-1}; //initialising with -1 for cache check

int rec(int cur_length = 0, int prev = 0){
	
	//base case
	if(cur_length == N)
		return 1;

	//cache check
	if(dp[cur_length][prev] != -1)
		return dp[cur_length][prev];

	if(prev == 1)
		ans = rec(cur_length+1, 0); //compulsory step since no consequtive 1
	
	else
		ans = rec(cur_length+1, 0) + rec(cur_length+1, 1);

	dp[cur_length][prev] = ans;

	return ans;
}

Time: O(N), Space: O(N) (if DP array wasn't global, for my code the space is a order of const value 10^5.