SDE - 1

BFS can be used here. 

Algorithm: 
1. Create an empty queue Q. 
1. Find all rotten oranges and enqueue them to Q. Also, enqueue a delimiter to indicate the beginning of the next time frame.
2. Run a loop While Q is not empty
3. Do following while delimiter in Q is not reached
2. Dequeue an orange from the queue, rot all adjacent oranges. While rotting the adjacent, make sure that the time frame is incremented only once. And the time frame is not incremented if there are no adjacent oranges.
3. Dequeue the old delimiter and enqueue a new delimiter. The oranges rotten in the previous time frame lie between the two delimiters.
Time Complexity: O(N*M)
Space Complexity: O(N*M)

The brute force algorithm iterates over the array, and then iterates again for each number to count its occurrences. As soon as a number is found to have appeared more than any other can possibly have appeared, return it.
• Time complexity : O(n^2)
• Space complexity : O(1)

The efficient approach is to use Moore’s Voting Algorithm. 
Approach: 
This is a two-step process : 
• The first step gives the element that maybe the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.
• Check if the element obtained from the above step is majority element. This step is necessary as there might be no majority element.

Algorithm: 
• Loop through each element and maintains a count of majority element, and a majority index, maj_index
• If the next element is same then increment the count if the next element is not same then decrement the count.
• if the count reaches 0 then changes the maj_index to the current element and set the count again to 1.
• Now again traverse through the array and find the count of majority element found.
• If the count is greater than half the size of the array, print the element
• Else print that there is no majority element
• Time Complexity: O(n). 
• Auxiliary Space: O(1).

One approach would be to traverse the tree and for every traversed node X :
1) Find maximum sum from leaf to root in left subtree of X 
2) Find maximum sum from leaf to root in right subtree of X. 
3) Add the above two calculated values and X->data and compare the sum with the maximum value obtained so far and update the maximum value. 
4) Return the maximum value.

The time complexity of above solution is O(n2)

This question can also be solved in a single traversal of binary tree. The idea is to maintain two values in recursive calls : 
1) Maximum root to leaf path sum for the subtree rooted under current node. 
2) The maximum path sum between leaves (desired output).

For every visited node X, we find the maximum root to leaf sum in left and right subtrees of X. We add the two values with X->data, and compare the sum with maximum path sum found so far.

A direct approach is to traverse the entire linked list and calculate its length. Traverse the list again and return the (length-N+1) node. But this approach involves two traversals of the linked list. 
To further optimize the solution, the question can be solved in one traversal only. Two pointers can be used here. Steps :
1. Initialize both the slow pointer and the fast pointer to the head node.
2. First, move fast pointer to n nodes from the head node.
3. Now, move both the pointers one by one until the fast pointer reaches the end of the list.
4. Now, the slow pointer will point to the nth node from the end. This is because when we started advancing pointers 'fast' and 'slow', difference between them was of 'n' nodes which is maintained while advancing these pointers.
Return the slow pointer.
Time Complexity : O(n)

The recursive approach is to traverse the tree in a depth-first manner. The moment you encounter either of the nodes node1 or node2, return the node. The least common ancestor would then be the node for which both the subtree recursions return a non-NULL node. It can also be the node which itself is one of node1 or node2 and for which one of the subtree recursions returns that particular node.
Pseudo code :
LowestCommonAncestor(root, node1, node2) {
if(not root)
return NULL
if (root == node1 or root == node2) 
return root
left = LowestCommonAncestor(root.left, node1, node2)
right = LowestCommonAncestor(root.right, node1, node2)
if(not left)
return right
else if(not right)
return left
else
return root
}

Steps :
1. Initially, reverse the individual words of the given string one by one. 
2. Reverse the whole string from start to end to get the desired output

Steps : 
1. Sort the given array in decreasing order of destination. 
2. Create groups of K (starting from the highest floor), the cost for each group will be 2 * (max(Elements in current group)). 
3. The summation across all groups will be the answer.

It is a finite set of formal rules for generating syntactically correct sentences or meaningful correct sentences.
Constitute Of Grammar :
Grammar is basically composed of two basic elements –
Terminal Symbols –
Terminal symbols are those which are the components of the sentences generated using a grammar and are represented using small case letter like a, b, c etc.
Non-Terminal Symbols –
Non-Terminal Symbols are those symbols which take part in the generation of the sentence but are not the component of the sentence. Non-Terminal Symbols are also called Auxiliary Symbols and Variables. These symbols are represented using a capital letter like A, B, C, etc.

Token is the smallest unit in a ‘C’ program. It is each and every word and punctuation that you come across in your C program. The compiler breaks a program into the smallest possible units (Tokens) and proceeds to the various stages of the compilation.

This can be solved using recursion. The basic idea is to subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit. Keep checking for left or right child path sum equal to target sum – value at current node. 
Time complexity : o(n)

Regular Languages : A language is regular if it can be expressed in terms of regular expression.
An expression is regular if:
ɸ is a regular expression for regular language ɸ.
ɛ is a regular expression for regular language {ɛ}.
If a ∈ Σ (Σ represents the input alphabet), a is regular expression with language {a}.
If a and b are regular expression, a + b is also a regular expression with language {a,b}.
If a and b are regular expression, ab (concatenation of a and b) is also regular.

NP Problem: 
The NP problems set of problems whose solutions are hard to find but easy to verify and are solved by Non-Deterministic Machine in polynomial time. 
NP-Hard Problem: 
A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is reducible to X in polynomial time. NP-Hard problems are as hard as NP-Complete problems. NP-Hard Problem need not be in NP class.

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.