SDE - 1

The recursive approach involves direct implementation of mathematical recurrence formula. 
F(n) = F(n-1)+F(n-2)
 

Pseudocode :

fibonacci(n):
	if(n<=1)
		return n;
	return fibonacci(n-1) + fibonacci(n-2)

This is an exponential approach. 

It can be optimized using dynamic programming. Maintain an array that stores all the calculated fibonacci numbers so far and return the nth fibonacci number at last. This approach will take O(n) time complexity and O(n) auxiliary space.

Inorder traversal requires that we print the leftmost node first and the right most node at the end. 
So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. So the steps would be : 
1. Start with the root node. 
2. Push the node in the stack and visit it's left child.
3. Repeat step 2 while node is not NULL, if it's NULL then pop the topmost node from the stack and print it.
4. Now move to node's right child and repeat step 1
5. Repeat the above steps while node is not NULL and stack is not empty

Traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, calculate the area with the popped bar as smallest bar. The current index is the ‘right index’ and index of previous item in stack is the ‘left index’. 
Following is the complete algorithm.

1) Create an empty stack.
 

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1. 
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack. 
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
 

3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

The brute force solution is to traverse the array and to search elements one by one. Run a nested loop, outer loop for row and inner loop for the column
Check every element with x and if the element is found then print “element found”. If the element is not found, then print “element not found”.
 

Efficient Approach : The idea here is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases : 
 

1. The given number > the current number: This will ensure that all the elements in the current row are smaller than the given number as the pointer is already at the right-most elements and the row is sorted. Thus, the entire row gets eliminated and continues the search for the next row. 

2. The given number < the current number: This will ensure that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continues the search for the previous column, i.e. the column on the immediate left.
 

3. The given number == the current number: This will end the search.
 

• Algorithm: 
1. Let the given element be x, create two variable i = 0, j = n-1 as index of row and column
2. Run a loop until i = n
3. Check if the current element is greater than x then decrease the count of j. Exclude the current column.
4. Check if the current element is less than x then increase the count of i. Exclude the current row.
5. If the element is equal, then print the position and end.

Algorithm:
1) Sort all points according to x coordinates.
2) Divide all points in two halves.
3) Recursively find the smallest distances in both subarrays.
4) Take the minimum of two smallest distances. Let the minimum be d. 
5) Create an array that stores all points which are at most d distance away from the middle line dividing the two sets.
6) Find the smallest distance in the created array.
7) Return the minimum of d and the smallest distance calculated in above step 6.
Time Complexity : O(n (Logn)^2)

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.