SDE - 1

Approach : 
1) Calculate sizes of given two linked lists. 

2) If sizes are same, then calculate sum using recursion. Hold all nodes in recursion call stack till the rightmost node, calculate the sum of rightmost nodes and forward carry to the left side. 

3) If size is not same, then follow below steps: 
a) Calculate difference of sizes of two linked lists. Let the difference be diff 

b) Move diff nodes ahead in the bigger linked list. Now use step 2 to calculate the sum of the smaller 
list and right sub-list (of the same size) of a larger list. Also, store the carry of this sum. 

c) Calculate the sum of the carry (calculated in the previous step) with the remaining left sub-list of a 
larger list. Nodes of this sum are added at the beginning of the sum list obtained the previous step.

TC : O(m+n) where m=Length of Linked List 1 and n=Length of Linked List 2
SC : O(m+n)

Approach :

The approach is as follows:
1) Get the max sum path for the left subtree.
2) Get the max sum path for the right subtree.
3) Select the one with the max sum from both and insert current node's data into it.
4) Return the updated path.


Algorithm:

list ‘MAXPATHSUM’('ROOT'):

1) If the root is NULL: return empty list.
2) Initialize ‘LEFTPATH’ = ‘MAXPATHSUM’('ROOT'->left).
3) Initialize ‘LEFTPATH’ = ‘MAXPATHSUM’('ROOT'->right).
4) Append 'ROOT' -> data to both the lists.
5) Find the sum of both lists.
6) Return the list with the greater sum.

TC : O(N+H^2), where ‘N’ is the number of nodes in the Binary tree and ‘H’ is the height of the binary tree. 
SC : O(N)

Answer : 
The answer is O(n). In each step we need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that we need to traverse all elements to find the minimum.

This was one of the most challenging problems I faced in all these rounds combined . It was based on Dynamic Programming and Trees . There is a technique called Binary Lifting that I cam across while solving problems on LeetCode and CodeStudio . This question was actually a direct implementation of this technique .

Steps : 
Given we can have at most 2^20 th ancestor of a node

1) Initialise a 2D ancestor matrix where ancestor[node][i] = stores the 2^i th ancestor of the node in the binary tree

2) Recursively fill the ancestor table in a Top-Down manner.

3)Once the ancestor table is filled , run a loop from i=19 to i=0 and check if 2^i <= k .

4) If 2^i<=k , then node=ancetor[node][i] and do k-=2^i 

5) If at any point node==-1 , simply return -1

6) Finally return the answe node 


TC : O(log(N))
SC : O(N)

//Psuedo Code : 

int n;
vectoradj[50001];
int ancestor[50001][20]; //ancestor[node][i] := stores the 2^i ancestor of node 
void calcAncestor(int node , int par)
{
ancestor[node][0]=par;
for(int i=1; i<20; i++)
{
if(ancestor[node][i-1]!=-1)
ancestor[node][i]=ancestor[ancestor[node][i-1]][i-1];
else
ancestor[node][i]=-1;
}

for(auto child : adj[node])
{
if(child!=par)
calcAncestor(child,node);
}
}

TreeAncestor(int N, vector& par) 
{
n=N;
for(int i=0; i= 0; i--)
{ 
int num = (1<= num)
{ 
node = ancestor[node][i];
k -= num; 
if(node == -1) return -1; 
}
}

return node;
}

Approach 1 (Naive) :

The naive approach runs three loops and check one by one that sum of three elements is zero or not. If the sum of three elements is zero then print elements otherwise print not found.

Algorithm: 

1) Run three nested loops with loop counter i, j, k.

2) The first loops will run from 0 to n-3 and second loop from i+1 to n-2 and the third loop from j+1 to n-1. The loop counter represents the three elements of the triplet.

3) Check if the sum of elements at i’th, j’th, k’th is equal to zero or not. If yes print the sum else continue.

TC : O(N^3) where N=size of the array
SC : O(1)


Approach 2 (Using Hash Map - Time Efficient) :

This involves traversing through the array. For every element arr[i], find a pair with sum “-arr[i]”. This problem reduces to pair sum and can be solved in O(n) time using hashing.

Algorithm: 

1) Create a hashmap to store a key-value pair.

2) Run a nested loop with two loops, the outer loop from 0 to n-2 and the inner loop from i+1 to n-1

3) Check if the sum of ith and jth element multiplied with -1 is present in the hashmap or not

4) If the element is present in the hashmap, print the triplet else insert the j’th element in the hashmap.

TC : O(N^2)
SC : O(N)


Approach 3 (Using Sorting - Time as well as Space Efficient) :

For every element check that there is a pair whose sum is equal to the negative value of that element.

Algorithm: 

1) Sort the array in ascending order.

2) Traverse the array from start to end.

3) For every index i, create two variables l = i + 1 and r = n – 1

4) Run a loop until l is less than r if the sum of array[i], array[l] and array[r] is equal to zero then print the triplet and break the loop

5) If the sum is less than zero then increment the value of l, by increasing the value of l the sum will increase as the array is sorted, so array[l+1] > array [l]

6) If the sum is greater than zero then decrement the value of r, by increasing the value of l the sum will decrease as the array is sorted, so array[r-1] < array [r].

TC : O(N^2)
SC : O(1)

Answer : 

1) For sorting nearly sorted data , Insertion Sort is the best as it adapts to O(n) time when the data is nearly sorted.

2) Bubble sort is fast, but insertion sort has lower overhead.

3) Shell sort is fast because it is based on insertion sort.

4) Merge sort, heap sort, and quick sort do not adapt to nearly sorted data.

Insertion sort provides a O(n^2) worst case algorithm that adapts to O(n) time when the data is nearly sorted. One would like an O(n·lg(n)) algorithm that adapts to this situation; smoothsort is such an algorithm, but is complex. Shell sort is the only sub-quadratic algorithm that is also adaptive in this case.

Iterative(Without using stack):

1) Initialize three pointers prev as NULL, curr as head and next as NULL.

2) Iterate through the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next
// Now change next of current
// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next

3)Finally the prev pointer contains our head , i,e. ,head=prev .

TC : O(n) where n=length of the Linked List
SC: O(1)


Recursive:

1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer

TC:O(n)
SC:O(n)


Iterative(Using Stack):

1) Store the nodes(values and address) in the stack until all the values are entered.
2) Once all entries are done, Update the Head pointer to the last location(i.e the last value).
3) Start popping the nodes(value and address) and store them in the same order until the stack is empty.
4) Update the next pointer of last Node in the stack by NULL.

TC: O(n)
SC:O(n)

Approach 1 : Recursive Inorder Traversal
Steps : 
1) The Inorder Traversal of a BST traverses the nodes in increasing order. 
2) The idea is to build an inorder traversal of BST which is an array sorted in the ascending order. 
3) Now the answer is the k - 1th element of this array.

TC : O(N) where N=number of nodes in the BST
SC : O(N)

Approach 2 : Iterative Inorder Traversal
Steps :
1) The above recursion could be converted into iteration, with the help of stack. 
2) This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.

TC : O(H) where H=height of the tree
SC : O(H)

Answer : 
1) FCFS (First Come First Serve) is a type of OS scheduling algorithm that executes processes in the same order in which processes arrive. 
2) In simple words, the process that arrives first will be executed first. It is non-preemptive in nature.
3) FCFS scheduling may cause the problem of starvation if the burst time of the first process is the longest among all the jobs. 
4) Burst time here means the time that is required in milliseconds by the process for its execution. 
5) It is also considered the easiest and simplest OS scheduling algorithm as compared to others. 
6) Implementation of FCFS is generally managed with help of the FIFO (First In First Out) queue.

Answer : 
1) It is generally a situation where the CPU performs less productive work and more swapping or paging work. 
2) It spends more time swapping or paging activities rather than its execution. 
3) By evaluating the level of CPU utilization, a system can detect thrashing. 
4) It occurs when the process does not have enough pages due to which the page-fault rate is increased. 5) It inhibits much application-level processing that causes computer performance to degrade or collapse.