SDE - 1

Approach : I approached this problem using DFS .

1) Create a boolean recursive function with parameters as root and target .
2) If we reached at the leaf node (root and !root->left and !root->right) and target-root->value==0 , return true as we
found out a path that sums up to target.
3) If root is not null , call 1) dfs with root->left and target-root->val and 2) dfs with root->right and target-root->value .
Return the OR of both these values.


TC : O(N) where N=number of nodes in the binary tree.
SC : O(N)

Approach :

1) Run a loop from i = 2 to i = min(m, n). 
2) Find the remainder for (m / i) and (n / i).
3) If both the remainders are zero, then m and n are not co-prime. 
4) If you run through the entire loop without finding an 'i' that divides both m and n, then they are co-prime.

TC : O(min(m, n)), where m and n are the two input integers.
SC : O(1)

Approach (Using DP) : This problem is a variation of LIS (longest increasing subsequence). 

1) We will sort the array according to the first element to define an order of picking pairs in the chain. 

2) Now the elements are sorted according to the first elements we need to find the longest increasing subsequence according to their second elements. 

3) We will use a ‘DP’ table of size ‘N’ to calculate the results for each index. Definition: ‘DP’[i] will store the max length pair chain ending at index ‘i’.

4) Base case: Each pair can make a valid chain of length 1 so we initialize each entry in the ‘DP’ table with value 1.

5) Transitions: If the current pair is the ending element of the chain then the maximum length of pair chain ending at this pair will be 1 + maximum ‘DP[j]’ where 0<= ‘j’ < ‘i’ and the first element of the current pair is greater than the second element of the pair having index ‘j’.

6) The final answer will be the maximum length among all the lengths we found so far in our ‘DP’ table.


TC : O(N ^ 2), where N = number of pairs
SC : O(N)

Approach (Using Recursion) : 

1) Recursively traverse the entire linked list to get the last node as a rightmost node.

2) When we return from the last recursion stack. We will be at the last node of the Linked List. Then the last node value is compared with the first node value of Linked List.

3) In order to access the first node of Linked List, we create a global left pointer that points to the head of Linked List initially that will be available for every call of recursion and the right pointer which passes in the function parameter of recursion.

4) Now, if the left and right pointer node value is matched then return true from the current recursion call. Then the recursion falls back to (n-2)th node, and then we need a reference to the 2nd node from head. So we advance the left pointer in the previous call to refer to the next node in the Linked List.

5) If all the recursive calls are returning true, it means the given Linked List is a palindrome else it is not a palindrome.


TC : O(N), where N = number of nodes in the linked list
SC : O(N)

Approach (Using DP) :

1) Create a boolean 2D array/list ‘DP’ of size (‘N+1’)*(‘K+1’) i.e. ‘DP[N+1][K+1]’.

2) If ‘K’ is equal to 0, then the answer should be ‘true’. Hence, run a loop from 0 to ‘N’ (say iterator = ‘i’):
‘DP[i][0]’ = true.

3) If ‘K’ is not zero but ‘ARR’ is empty then the answer should be ‘false’. Hence, run a loop from 1 to ‘K’ (say iterator =
‘i’):
‘DP[0][i]’ = false.

4) To fill the ‘DP’ table, run a loop from 1 to ‘N’ (say iterator = ‘i’):
4.1) Run a loop from 1 to ‘K’ (say iterator = ‘j’):
‘DP[i][j]’ = ‘DP[i-1][j]’.
4.2) If ‘j’ is greater than equal to ‘ARR[i-1]’:
‘DP[i][j]’ = ‘DP[i][j]’ OR ‘DP[i-1][j - ARR[i-1]]’.

5) Finally, return ‘DP[N][K]’.


TC : O(N*K), where N = size of the array and K = required sum
SC : O(N*K)

Approach (Using Binary Search) : 

1) Find the mid index.

2) If the value(key) being searched for is at the mid index, then return the mid index.

3) Compare values at start index, end index, and mid-index:
3.1) If the left subarray is sorted, check if the value(key) to be searched lies in the range:
a) If it does, then search space reduces between [start, (mid-1)].
b) Otherwise, the search space reduces between [(mid + 1), end]

3.2) If the right subarray is sorted, check if the value(key) to be searched lies in the range:
a) If it does, then search space reduces between [(mid + 1), end].
b) Otherwise, the search space reduces between [start, (mid -1)]

4) Repeat from step-1 until the key is found.

5) Return -1 if never found.


TC : O(log(N)), Where N = size of the array.
SC : O(1)

Static Polymorphism : Static Polymorphism is commonly known as the Compile time polymorphism. Static polymorphism is the feature by which an object is linked with the respective function or operator based on the values during the compile time. Static or Compile time Polymorphism can be achieved through Method overloading or operator overloading.

Dynamic Polymorphism : Dynamic Polymorphism or Runtime polymorphism refers to the type of Polymorphism in OOPs, by which the actual implementation of the function is decided during the runtime or execution. The dynamic or runtime polymorphism can be achieved with the help of method overriding.

If you are a user, and you have a problem statement, you don't want to know how the components of the software work, or how it's made. You only want to know how the software solves your problem. Abstraction is the method of hiding unnecessary details from the necessary ones. It is one of the main features of OOPs. 
For example, consider a car. You only need to know how to run a car, and not how the wires are connected inside it. This is obtained using Abstraction.

Collision doesn’t happen only in following two cases : 

1) All ants move in counterclockwise direction.
2) All ants move in clockwise direction.

Since every ant has two choices (pick either of two edges going through the corner on which ant is initially sitting),
there are total 23 possibilities.

Out of 23 possibilities, only 2 don’t cause collision. So, the probability of collision is 6/8 or 3/4 and the probability of
non-collision is 2/8 or 1/4.

General Tip : Before an interview for any company , have a breif insight about the company , what it does , when was
it founded and so on . All these info can be easily acquired from the Company Website itself .

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round,
like what are the projects currently the company is investing, which team you are mentoring. How all is the work
environment etc.

Tip 4 : Since everybody in the interview panel is from tech background, here too you can expect some technical
questions. No coding in most of the cases but some discussions over the design can surely happen.