SDE - 1

Concept of indexing can be used to solve this question.

Traverse the array. For every element at index i,visit a[i]. If a[i] is positive, then change it to negative. If a[i] is negative, it means the element has already been visited and thus it is repeated. Print that element.

Pseudocode :

findRepeating(arr[], n)
{
	missingElement = 0
	for (i = 0; i < n; i++){
		element = arr[abs(arr[i])]

		if(element < 0){
			missingElement = arr[i]
			break
		}
		arr[abs(arr[i])] = -arr[abs(arr[i])]
	}
	return abs(missingElement)
}

Sorting can be used to solve this problem. Next, two -pointer technique can be applied on the sorted array.
Traverse the array and fix the first element of the triplet. Now use the Two Pointer technique to find if there is a pair whose sum is equal to x – array[i].
• Algorithm : 
1. Sort the given array.
2. Loop over the array and fix the first element of the possible triplet, arr[i].
3. Then fix two pointers, one at i + 1 and the other at n – 1. And look at the sum, 
1. If the sum < required sum, increment the first pointer.
2. Else, If the sum > required sum, Decrease the end pointer to reduce the sum.
3. Else, if the sum of elements at two-pointers == required sum, then print the triplet and break.

Time Complexity : O(nlogn)

• Make an integer matrix ‘boxes’ of dimension (3*n, 3), we will store all three rotations of each type of boxes in it.
• Generate all 3 rotations for all ‘n’ types of boxes, for simplicity we will consider ‘width’ always smaller than or equal to ‘length’. Store them in matrix ‘boxes’ such that ‘boxes[i][0]’, ‘boxes[i][1]’, ‘boxes[i][2]’ give height, width, length of ‘i’th box respectively.
• Sort the matrix ‘boxes’ in decreasing order of base area. Base area of i^th box is given by ‘boxes[i][1] * boxes[i][2]’.
• Make an integer array ‘maxHeight’ of size 3*n, where maxHeight[i] will give the maximum height of the stack if the ‘i^th’ box after sorting is the topmost box of the stack.
• Initialize an integer variable ‘result’:= 0, it will keep track of the maximum possible height of stack so far.
• Run a loop where ‘i’ ranges from 0 to 3*n-1 and for each ‘i’ perform the following steps-:
  • Assign ‘maxHeight[i]’ := ‘boxes[i][0]’.
  • Run a loop where j ranges from 0 to i-1.  If ‘boxes[j][1]’ and ‘boxes[j][2]’ is strictly greater than ‘boxes[i][1]’ and ‘boxes[i][2]’ respectively, then update ‘maxHeight[i]’ with maximum of its current value and sum of of ‘maxHeight[j]’ + ‘boxes[i][0]’.
  • Update ‘result’ with the maximum of its current value and ‘maxHeight[i]’.
• Return ‘result’

TC : O(N ^ 2),  where  ‘N’ is the number of types of boxes.

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)
The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

The idea is to traverse the given list of prices and find a local minimum of every increasing sequence. We can gain maximum profit if we buy the shares at the starting of every increasing sequence (local minimum) and sell them at the end of the increasing sequence (local maximum). 
Steps :
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as an ending index. If we reach the end, set the end as the ending index.
3. Update the solution and Increment count of buy-sell pairs. 
4. Repeat the above steps till the end is not reached.

Dijkstra's Algorithm basically starts at the source node and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
Once the shortest path between the source node and another node is found, that node is marked as "visited" and added to the path. 
The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.
Pseudocode :

function Dijkstra(Graph, source):
2: for each vertex v in Graph: // Initialization
3: dist[v] := infinity // initial distance from source to vertex v is set to infinite
4: previous[v] := undefined // Previous node in optimal path from source
5: dist[source] := 0 // Distance from source to source
6: Q := the set of all nodes in Graph // all nodes in the graph are unoptimized - thus are in Q
7: while Q is not empty: // main loop
8: u := node in Q with smallest dist[ ]
9: remove u from Q
10: for each neighbor v of u: // where v has not yet been removed from Q.
11: alt := dist[u] + dist_between(u, v)
12: if alt < dist[v] // Relax (u,v)
13: dist[v] := alt
14: previous[v] := u
15: return previous[ ]

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.