SDE - 1

Sort the array and return second last element.

I started with a basic brute force approach by counting the number of 0’s,1’s,2’s. Let the count be x,y,z then we can traverse again and fill x nodes as 0 , y nodes as 1 and z nodes as 2.
Then the interviewer asked me to optimize the solution
Next comes the efficient solution
Iterate through the linked list. Maintain 3 pointers named zero, one, and two to point to current ending nodes of linked lists containing 0, 1, and 2 respectively. For every traversed node, we attach it to the end of its corresponding list. Finally, we link all three lists. To avoid many null checks, we use three dummy pointers zero, one and two that work as dummy headers of three lists.

First solution using extra space:
1) We can make a set of integer.
2) Traverse the linked list and store the values in set.
3) After traversal the set will contain all those elements which are unique.
4) We can then copy those elements back to the linked list.

The interviewer asked me to optimize and asked me the complexity.

So second optimised solution:
1) Traverse the linked list.
2) If the current data is the same as the next node then delete the next node.
3) Before deleting a node, we need to store the next pointer of the node

Tip 1 : Be accurate and give real-life examples
Tip 2 : Try to include interviewer in discussion

Tip 1 : Draw the diagram and explain logic.

1. Start from the root.
2. Compare the searching element with root, if less than root, then recurse for left, else recurse for right.
3. If the element to search is found anywhere, return true, else return false.

Initially all vertex are unvisited so visited[i] will be false for all i and as no path is yet constructed so distance[i] will be infinity or you can take any value like -1 and set predecessor[i] as -1 for all i.

Now the first vertex to be visited is sourse and distace of Source to source is 0 hence visited[source] = true
distance[source]=0.
queue.push(source).

while there are vertices in the queue:
1.Read a vertex u from the queue
2.For all adjacent vertices of u :
if visited[adj[u][i] ] is false (where adj is a vector containing adjascency list)
- make it true
put distance [adj[u][i]]=distance[i]+1
predecessor[adj[u][i]]=u

queue.push(adj[[u][i]])

if(adj[u][i]==destination then return true so we get distance of vertex i from source vertex from distance array and immediate predecessor of vertex i from predecessor array we get length of path from source to any vertex in O(1) time from distance array and printing path from source to any vertex we use predecessor array which takes O(V) time in worst case
thus complexity of the algorithm is O(V+E) with Auxiliary space O(V).