Interview@X Company Data Structures – Part 1

My friend attended the Interview process at X company. He shared his experiences, his interview rounds and other information with me. Just thought of sharing the same information with the world.

His interview was scheduled@10 O’clock. The interview process was rapid and smooth. As soon as he reached the place he was called for the interview. He went through 3 rounds and was judges in 3 competencies i.e. Core Java, Data Structures and Puzzles.

I will put all the questions sent by him in few parts. I will start discussion with Data Structure questions as it will need least amount of googling for me :):).

There were very few simple questions from Data Structures side (I think, they were not looking for some super humans like Amazon, Google search :) ).

Que 1. You have given a link list, find the nth element of the element from the last…

If input to the method is 2nd element, then D should be output of the method or program.

Ans: To solve this it is required to identify the end of the list and then traverse back from end. Or there should some other pointer which could suggest the element when other pointer has reached to end of the list.

As stated above there are 2 pointers required which will point to the start of the link list at the start.

Now Leading pointer will move to n-1 place first.

After this will move the leading pointer and lagging pointer in the list until leading pointer reaches to null.

Next step

So Leading pointer has reached to Null and lagging pointer has reached to the output of the program.

Pseudo Code

   1: Struture Node{

   2:     char data;

   3:     Node *next;

   4: }

   5:  

   6: char findNFromLast(int n){

   7:     Node leadingPointer = Head;

   8:     Node laggingPointer = Head;

   9:     

  10:     for(int i =0 ; i < n-1; i++){

  11:         leadingPointer = leadingPointer->next;

  12:     }

  13:     

  14:     for(;leadingPointer->Next !=null;){

  15:         leadingPointer = leadingPointer->next;

  16:         laggingPointer = laggingPointer->next;

  17:     }

  18:     

  19:     return(laggingPointer->data);

  20:  

  21: }

This looks very simple and straight forward question. Complexity of the solution is o(n)… N is the number of nodes in the link list.

Disclaimer: This may not be the best optimal solution, if you guys have better solution then let me know.