SDE - 1

The idea is to take hold some planes in the middle, send some planes back and get the fuel to get the main plane fueled again. 
Let the three air plane be X, Y and Z. Let total circumference be 300 Units. So every plane can run 150 units.
Let X be the plane that will go around the world.
After 1/6th of the circumference (50 units), Y passes 1/3rd of its fuel to Z and returns (Y has fuel left to travel exactly 50 units).
Now Z has fuel left for 150 units (Completely filled). At 1/4th of the distance around the world, Z has fuel for 125 units and X has fuel for 75 units. Z completely fills the tank of X which is now able to fly to a point 3/4 of the way around the world.
Now Z has fuel for 50 units. Z now has only 1/3 of its fuel (can travel 50 units) left which is not enough to get back to the airport. But Y reaches it in time in order to refuel it, and both Y and Z air plane are the able to return safely to the airport.
Both Y and Z gets refuelled and fly towards X. Again Y refuels Z and returns to the to be refuelled. Z reaches X at the point where it has flown 3/4 around the world. This time Y and Z come from other direction so that the distance left is 1/4. (If they had come clockwise earlier, they come anti-clockwise this time).
All 3 aircraft can safely return to the home base

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.

The number of rows or columns to be printed for given n will be 2*n – 1. 
We will print the matrix in two parts. First, print the upper half from rows from 0 to floor((2*n – 1)/2) and then second half from floor((2*n – 1)/2) + 1 to 2*n – 2. 
Now for each row, print it in three parts. First part is decreasing sequence which will start from n and decrease by 1 in each iteration. The number of iterations will be equal to row number, the second part is a constant sequence where constant is n – i and it will be print 2*n – 1 – 2 * row number, and the third part is increasing sequence which is nothing but opposite of the first sequence. 
For lower half, observe, it is a mirror image of upper half (excluding middle row). So, simply run a loop of the upper half from (2*n – 1)/2 to 0.

A two-pointer approach can be used for this question. Maintain two indexes. Initialize the first index left as 0 and second index right as n-1, where n is size of the array .
While left < right , do the following : 
a) Keep incrementing index left while arr[left] =0 
b) Keep decrementing index right while arr[right]=1 
c) If left < right then exchange arr[left] and arr[right]

The brute force solution is to use two loops. The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.
Time Complexity: O(N2) 
Auxiliary Space: O(1)

The above approach can be optimized using stack data structure. 
Steps :
Push the first element to stack.
Pick rest of the elements one by one and follow the following steps in loop : 
1. Mark the current element as next.
2. If stack is not empty, compare top element of stack with next.
3. If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
4. Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
Finally, push the next in the stack.
After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

A binary tree or a bst is typically used to store numerical values. The time complexity in a bst is O(log(n)) for insertion, deletion and searching. Each node in a binary tree has at most 2 child nodes.

Trie is an ordered tree structure, which is used mostly for storing strings (like words in dictionary) in a compact way. In a trie, every node (except the root node) stores one character. By traversing up the trie from a leaf node to the root node, a string can be constructed. By traversing down the trie from the root node to a node n, a common prefix can be constructed for all the strings that can be constructed by traversing down all the descendant nodes (including the leaf nodes) of node n.

DFS can be used to solve this problem. The idea is to place queens in different columns one by one, starting from the leftmost column. As we cannot place 2 queens in the same column, when we place the queen in the nth column and if its valid position, dfs again starting n+1 th column and try placing the next queen in all the rows of n+1th column and find a valid position. If no valid queen row found in n+1th row, backtrack and go to nth column, and change the queen position to the next row and repeat the process.

The key observation in the problem is three points form a triangle only when they don’t lie on the straight line, that is an area formed by the triangle of these three points is not equal to zero. 
Area of Triangle = (1/2)*(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) 
The above formula is derived from shoelace formula.
So we will check if the area formed by the triangle is zero or not.

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.