Software Developer

A simple approach could be to use a stack. Traverse the given list and push all the nodes to a stack. Now, Traverse the list again. For every visited node, pop the topmost node from the stack and compare data of popped node with the currently visited node. If all nodes match, then the linked list is a palindrome. 
Time Complexity : O(N) 
Auxiliary Space : O(N)

A better approach would be to reverse the second half of the list. Get the middle of the linked list and reverse the second half of the linked list. 
Next, Check if the first half and second half are identical. If they are identical, return true. 
Time Complexity : O(N) 
Auxiliary Space : O(1)

The problem can be solved using the concept of sliding window. 
We scan the array from 0 to n-1, and maintain a deque to keep "promising" elements. 
At each i, we keep "promising" elements, which are potassumally max number in window [i-(k-1),i] or any subsequent window. This means :

 
1. If an element in the deque and it is out of i-(k-1), we discard them. We just need to remove from the head, as we are using a deque and elements are ordered as the sequence in the array
 

2. Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] 3.As a result, elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max element in [i-(k-1),i]
The algorithm is amortized O(n) as each element is pushed and removed once.

To solve the question using a max heap, make a max heap of all the elements of the list. Run a loop for k-1 times and remove the top element of the heap. After running the loop, the element at top will be the kth largest element, return that. Time Complexity : O(n + klogn)

The question can also be solved using a min heap. 
 

Approach :

1. Create a min heap class with a capacity of k.
 

2. When the heap reaches capacity eject the minimum number. 
 

3. Loop over the array and add each number to the heap. 
 

4. At the end, the largest k number of elements will be left in the heap, the smallest of them being at the top of the heap, which is the kth largest number.
 

The time complexity for this solution is O(N*log(K)).

To print the nodes in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable ltr is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.

Function to print level order traversal of tree : 

printSpiral(tree)
	bool ltr = 0;
	for d = 1 to height(tree)
		printGivenLevel(tree, d, ltr);
	ltr ~= ltr /*flip ltr*/

A simple approach would be to create a new arrays with size as sum of the sizes of both the arrays. Copy the elements of both the arrays in the new array and sort the array. 
A space optimised approach also exists. While traversing the two sorted arrays parallelly, if we encounter the jth second array element is smaller than ith first array element, then jth element is to be included and replace some kth element in the first array. 

Algorithm :

1) Initialize i,j,k as 0,0,n-1 where n is size of arr1 
 

2) Iterate through every element of arr1 and arr2 using two pointers i and j respectively
if arr1[i] is less than arr2[j]
increment i
else
swap the arr2[j] and arr1[k]
increment j and decrement k

3) Sort both arr1 and arr2

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.