SDE - 1

Approach :
1) The idea is to do reverse inorder traversal of BST. Keep a count of nodes visited.
2) The reverse inorder traversal traverses all nodes in decreasing order, i.e, visit the right node then centre then left and continue traversing the nodes recursively.
3) While doing the traversal, keep track of the count of nodes visited so far.
4) When the count becomes equal to n, stop the traversal and print the key.

//Pseudo Code : 

void nthLargestInBST(TreeNode*root , int n, int&cnt)
{
if(!root || cnt>=n)
return;

cnt++;
nthLargestInBST(root->right,n,cnt);
if(cnt==n)
{
cout<<"Nth largest element in BST = "}

TC : O(h+n) where h=height of the tree and n is given
SC : O(h)

Approach 1 :
1) To check if a tree is height-balanced, get the height of left and right subtrees. 
2) Return true if difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.

//Pseudo Code
int height(TreeNode*root)
{
if(!root)
return 0;
return 1+max(height(root->left) , height(root->right));
}

bool isBalanced(TreeNode*root)
{
if(!root)
return true;
int leftHt=height(root->left);
int rightHt=height(root->right);
if(isBalanced(root->left) and isBalanced(root->right) and abs(leftHt-rightHt)<=1)
return true;
return false;
}

TC : O(N^2) where N=number of nodes in the Binary Tree
SC : O(N)


Approach 2 (Time Efficient ) :
1) Above implementation can be optimized by calculating the height in the same recursion rather than calling a height() function separately .
2) Then check if the answer is already false or not if it is already false, then simply return 0 .
3) Else return the height of the node . 

//Pseudo Code : 

bool ans;

int checkBalance(TreeNode* root)
{
if(!root)
return 0;
if(!ans) // if Answer is already False then return it.
return 0;
int leftSubTree = checkBalance(root->left);
int rightSubTree = checkBalance(root->right);
if(abs(leftSubTree-rightSubTree) > 1)
{
ans = false;
}

return 1 + max(leftSubTree, rightSubTree);
}

bool isBalanced(TreeNode* root){
ans = true;
int temp = checkBalance(root);
return ans;
}

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

Answer : 

Zombie Process : A process which has finished the execution but still has entry in the process table to report to its parent process is known as a zombie process. A child process always first becomes a zombie before being removed from the process table. The parent process reads the exit status of the child process which reaps off the child process entry from the process table.

Orphan Process : A process whose parent process no more exists i.e. either finished or terminated without waiting for its child process to terminate is called an orphan process.
In the following code, parent finishes execution and exits while the child process is still executing and is called an orphan process now.
However, the orphan process is soon adopted by init process, once its parent process dies.

Approach : I solved it using 2-pointers and keeping a track of the frequency of the elements encountered in a freq array of size 26

Steps :
1) Initiliase a freq array of size 26 where a=0, b=1 ...,z=25 .
2) Let s be our string and n = s.size()
3) Do , freq[s[0]]++;
4) Keep 2 pointers start and end where initially start=0 and end=1 also maintain a answer variable ans where initially ans=0
5) Now run a loop till end=1 and startfreq(26,0);
freq[s[0]-'a']++;
int start=0 , end=1 ;
int ans=1;
while(end=1 and start {
freq[s[start]-'a']--;
start++;
}
freq[s[end]-'a']++;
}
ans=max(ans,end-start+1);
end++;
}
return ans;
}

This was a preety standard Binary Search Question and I had solved this question before on platforms like LeetCode and CodeStudio . I was asked this question to test my implementation skills and how well do I handle Edge Cases .

Approach :
1) The idea is to find the pivot point, divide the array in two sub-arrays and perform binary search.
2) The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only element for which next element to it is smaller than it.
3) Using the above statement and binary search pivot can be found.
4) After the pivot is found out divide the array in two sub-arrays.
5) Now the individual sub – arrays are sorted so the element can be searched using Binary Search.

TC : O(Log(N))
SC : O(1)

Approach 1 (Naive Solution ) : 
One by one calculate sum of all sub-arrays possible and check divisible by K. 

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

Approach 2 (Efficient Solution) :

Observe : Let sum(i,j)=subarray sum from arr[i] to arr[j] (both inclusive) (arr[i]+arr[i+1]...+arr[j])

Now for sum(i,j) to be divisible by k , th following condition must hold :

sum(0,j)%k=sum(0,i-1)%k

Keeping the above points in mind , let's design an efficient algo for this problem : 

Algorithm :

1) Make an auxiliary array of size k as Mod[k] . This array holds the count of each remainder we are getting after dividing cumulative sum till any index in arr[].

2) Now start calculating cumulative sum and simultaneously take it’s mod with K, whichever remainder we get increment count by 1 for remainder as index in Mod[] auxiliary array. 

3) Sub-array by each pair of positions with same value of ( cumSum % k) constitute a continuous range whose sum is divisible by K.

4) Now traverse Mod[] auxiliary array, for any Mod[i] > 1 we can choose any two pair of indices for sub-array by (Mod[i]*(Mod[i] – 1))/2 number of ways . 

5) Do the same for all remainders < k and sum up the result that will be the number all possible sub-arrays divisible by K.

//Pseudo Code :

int subarraysDivByK(vector& arr, int k) 
{
int n=arr.size();
vectormod(k,0); 
int cumu=0;
for(int i=0; i1)
ans+=(mod[i]*(mod[i]-1)/2);
}
return ans+mod[0];

}

TC : O(N) where N=size of the array
SC : O(k)

Approach :
The idea is to follow the recursive approach for solving the problem i.e. start searching for the element from the root. 

1) If there is a leaf node having a value less than N, then element doesn’t exist and return -1.
2) Otherwise, if node’s value is greater than or equal to N and left child is NULL or less than N then return the node value.
3) Else if node’s value is less than N, then search for the element in the right subtree.
4) Else search for the element in the left subtree by calling the function recursively according to the left or right value.

TC : O(h) where h=Height of the Binary Tree
SC : O(h)

Approach :

Some key points about a Hash Map : 

1) HashMap is the data structure used to store key-value pairs, where the average retrieval time for get() and insert() operations is constant i.e. O(1).

2) Hashmap uses the array of Singly Linked List internally.

3) The array is called the buckets and at every bucket(i-th index of the array) holds a pointer to head of the Singly Linked List.

4) Every Linked List Node has fields called the ‘KEY’, ‘VALUE’ and certainly the pointer to the next node.

5) For every entry of a key, we try to generate a ‘unique value’ pointing to the bucket where it can be stored. It can also be said that we try to find an index against every key that needs to be inserted or updated in the array/buckets.

6) If we know which bucket to look at, then we can make the operations, ‘INSERT’ , and ‘GET’ in the constant time since fetching a value or updating a value at a known index in an array is a constant time operation.

7) To calculate the index against every key that needs to be inserted we use hashing algorithms. The values thus computed are called Hash Values. This hash value serves as the location or index of the bucket.


Functions to be implemented:

1. INSERT(VALUE) :

We will first compute the hash value or location in the buckets where the key needs to be inserted using any of the hashing algorithms available. 

In case the location doesn’t have a list already, we make it as the head or if the location already contains a list(case of collision) we insert the new key at the head.

To make sure that every insert operation happens in constant time, we keep a threshold of 0.7(less than 1) over the load factor. If the load factor exceeds the threshold value, we run a rehash function. 

loadFactor = (size * 1.0) / buckets.size()

The load factor is defined to be the total load that is being put on the buckets. We try to keep it less than or equal to 0.7 to maintain the operations performed are constant. 

RE_HASH(): This function basically increases the total bucket size by either a factor of multiple of 2 or by the power of 2 and every KEY present is inserted into the updated buckets(you may read more about it on the internet).



2. DELETE(VALUE):

It works in a similar way we discussed above for the insert function. 



3. SEARCH(KEY):

Generate the hash value against the key to be searched and get the bucket corresponding to the key by taking modulo with the total bucket size.



TC : O(1) , All the functions take constant time. Hence, the overall Time Complexity is O(1).
SC : O(N) , where ‘N’ is the number of elements in the HashMap.