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.

SOP statements

During one of my friend's interview few questions were asked about SOP statements. Those are as follows.

How do you write message on standard output?

This is very trivial question and most of the Java developer have used SOPs several times while writing code,  debugging code or providing additional information to the user.

System.out.println("Write SOP Here");

In eclipse type Syso, and press CTRL+Enter, it will expand it to System.out.println. This was the very simple question to answer.

Sequel of the first question was, What do these components represent?

Few of us may know and few may not. So lets have a look on each of them.

There are 3 component of the statement.

System

System class can neither be instantiated nor be overridden as its default constructor which is marked as private. This class provide few utility important utility methods.

Out

Out is the final and static instance of the PrintStream class. It is instantiated with the application and remain unchanged and log the data on the configuration of the system. PrintStream class belongs to java io package.

Println

println is a method which flushes data and appends a New line character to printstream instance.

Sometime this information is not sufficient to answer this question efficiently. There is one more question that struck to my mind.

java.io have many other write streams also, so why was PrintStream chosen to write data on standard output?

Many of us may not know the answer. Lets start with what java doc has to say about it.

A PrintStream adds functionality to another output stream, namely the ability to print representations of various data values conveniently. Two other features are provided as well. Unlike other output streams, a PrintStream never throws an IOException; instead, exceptional situations merely set an internal flag that can be tested via the checkError method. Optionally, a PrintStream can be created so as to flush automatically; this means that the flush method is automatically invoked after a byte array is written, one of the println methods is invoked, or a newline character or byte ('\n') is written.

As it does not throw any exception and data flushes after certain amount of bytes. This class provides suitable mechanism to use as a standard output stream to display all stack in exceptional scenarios as well.

After writing this entry my own fundamentals have improved about SOP and its components. I hope it helped you as well.

Disclaimer: All the material here is the result of research and understanding of other material. If there is some content which is either incorrect or inappropriate to the context of the article I am always open for discussion.