Data structures and algorithm questions are important part of any
programming job interview, be it a Java interview, C++ interview or any other
programming language. Since data structures is core programming concept, its
mandatory for all programmers, to know basic data structures like stack, linked
list, queue, array, tree and graph. Though tree and graph are on tough side, I
still see programmers to get familiar will all these. Any list of programming job interview questions
is incomplete without questions from data structures and algorithms. Similarly while
going on questions from data structure you may get some programming exercise as
well e.g. swapping numbers without temp variable
. Linked
list and arrays are favorite topics in any data structure interview, questions
like reversing linked list, traversing linked list or deleting nodes from
linked list, which involves algorithm and data structures are quite common.
Similarly, finding duplicates in array, finding missing numbers, sorting arrays
are very popular. You can also expect questions from stack, queue, array,
linked list, tree, graph and HashMap are most common in any data structure
interview. In this tutorial, we will see
couple of data structure questions answers from these topic. Let us know, if
you have any interesting questions from data structures and algorithm, which
you faced during any Java interviews.

##
__Data Structures and Algorithm Interview
Questions for Java Programmers__

This is combined list of questions from various data structure e.g.
array, linked list, stack or queue. It includes some coding questions as well,
which gel with data structures.

**Question 1 : How to find middle element of linked list in one pass?**

One of the most popular question from data structures and algorithm,
mostly asked on telephonic interview. Since many programmer know that, in order
to find length of linked list we need to first traverse through linkedlist till
we find last node, which is pointing to null, and then in second pass we can
find middle element by traversing only half of length. They get confused when
interviewer ask him to do same job in one pass. In order to find middle element
of linked list in one pass you need to maintain two pointer, one increment at
each node while other increments after two nodes at a time, by having this
arrangement, when first pointer reaches end, second pointer will point to
middle element of linked list. See this trick to find middle element of linked list in
single pass for more details.

**Question 2 : How to find if linked list has loop ?**

This question has bit of similarity with earlier algorithm and data
structure interview question. I mean we can use two pointer approach to solve
this problem. If we maintain two pointers, and we increment one pointer after
processing two nodes and other after processing every node, we are likely to
find a situation where both the pointers will be pointing to same node. This
will only happen if linked list has loop.

**Question 3 : How to find 3rd element from end in a linked list in one pass?**

This is another frequently asked linked list interview question. This
question is exactly similar to finding middle element of linked list in
single pass. If we apply same trick of maintaining two pointers and
increment other pointer, when first has moved upto 3rd element, than when first
pointer reaches to the end of linked list, second pointer will be pointing to
the 3rd element from last in a linked list.

**Question 4 : In an integer array, there is 1 to 100 number, out of one is duplicate, how to find ?**

This is a rather simple data structures question, especially for this
kind of. In this case you can simply add all numbers stored in array, and total
sum should be equal to n(n+1)/2. Now just subtract actual sum to
expected sum, and that is your duplicate number. Of course there is a brute
force way of checking each number against all other numbers, but that will
result in performance of O(n^2) which is not good. By the way this trick will
not work if array have multiple duplicates or its not numbers forming
arithmetic progression. Here is example of one way to find duplicate number in array.

**Question 6 : How to reverse String in Java ?**

This is one of my favorite question. Since String is one of
the most important type in programming, you expect lot of question related to
String any data structure interview. There are many ways to reverse Sting in
Java or any other programming language, and interviewer will force you to solve
this problem by using without API i.e. without using reverse() method of StringBuffer. In
follow-up he may ask to reverse String using recursion as well. See 3 ways to reverse String in Java
to learn reversing String using both loops and recursion in Java.

**Question 7 : Write a Java program to sort a array using Bubble Sort algorithm?**

I have always send couple of questions from searching and sorting in data
structure interviews. Bubble sort is one of the simplest sorting algorithm but
if you ask anyone to implement on the spot it gives you an opportunity to gauge
programming skills of a candidate. See How to sort array using Bubble Sort in
Java for complete solution of this datastrucutre interview question.

**Question 8 : What is difference between Stack and Queue data structure ?**

One of the classical datastrucutre interview question. I guess every one
know, No? Any way main difference is that Stack is LIFO(Last In First Out) data
structure while Queue is a FIFO(First In First Out) data structure.

**Question 9 : How do you find duplicates in array if there is more than one duplicate?**

Sometime this is asked as follow-up question of earlier datastrucutre
interview question, related to finding duplicates in Array. One way of solving
this problem is using a Hashtable or HashMap data structure.
You can traverse through array, and store each number as key and number of
occurrence as value. At the end of traversal you can find all duplicate numbers,
for which occurrence is more than one. In Java if a number already exists in HashMap then calling get(index) will
return number otherwise it return null. this property can be used to insert or
update numbers in HashMap.

**Question 10 : What is difference between Singly Linked List and Doubly Linked List data structure?**

This is another classical interview question on data structure, mostly
asked on telephonic rounds. Main difference between singly linked list and doubly
linked list is ability to traverse. In a single linked list, node only points
towards next node, and there is no pointer to previous node, which means you
can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows
you to navigate in both direction in any linked list.

**Question 11 : Write Java program to print Fibonacci series ?**

This is not a data structures question, but a programming one, which many
times appear during data structure interview. Fibonacci series is a mathematical
series, where each number is sum of previous two numbers e.g. 1,1, 2, 3, 5, 8,
13, 21. Interviewer is often interested in two things, a function which returns
nth number in Fibonacci series and solving this problem using recursion in
Java. Though, its easy question, recursion part often confuses beginners. See
this link to find nth Fibonacci number in Java.

**Question 12 : Write Java program to check if a number is palindrome or not?**

This is similar to previous question, not directly related to data
structures, but quite popular along with other questions. A number is called
palindrome, if reverse of number is equal to number itself. Interviewer ask to
solve this problem without taking help from Java API or any open source
library. Any way it’s simple question, you can use division operator (/) and
remainder operator (%) to solve this question. Just remember, division operator
can be used to get rid of last digit e.g. 1234/10 will give you 123, and
modulus operator can give you last digit e.g. 1234%10 will return 4. By the
way, here is a Java program check if number is
palindrome or not.

**Question 13 : What is binary search tree?**

This is a data structure question from Tree data structures. Binary
Search Tree has some special properties e.g. left nodes contains items whose
value is less than root , right sub tree contains keys with higher node value
than root, and there should not be any duplicates in the tree. Apart from
definition, interview can ask you to implement binary search tree in Java and questions
on tree traversal e.g. IN order, preorder, and post order traversals are quite
popular data structure question.

**Question 14 : How to reverse linked list using recursion and iteration?**

This is another good question on data structures. There are many
algorithm to reverse linked list and you can search of them using google. I am
thinking of writing another blog post to explain linked list reversal and will
share with you later.

**Question 15 : Write a Java program to implement Stack in Java?**

You can implement Stack by using array or linked list. This question
expect you to implement standard method provided by stack data structure e.g. push() and pop(). Both push() and pop() should be
happen at top of stack, which you need to keep track. It’s also good if you can
implement utility methods like contains(), isEmpty() etc. By
the way JDK has java.util.Stack class and you can check it’s code to get an
idea. You can also check Effective Java book, where
Josh Bloch has explains how an incorrect implementation of stack can cause memory leak in Java.

That's all on this list of data structure interview questions and
answers. This is one topic, which is always asked in any programming interview,
doesn't matter if you are C, C++, or Java developer, basic knowledge of data
structure like array, linked list, stack, queue, tree are must to clear any
programming interview.

## 22 comments :

Great post Javin! Really helpful.

I was recently asked following questions in interviews. I have found answers via Google search, but it would be great to know your comments on these questions.

1. Write your own HashMap/Hashtable implementation in Java

2. How to implement your own LinkedList (without using any Java API)

@Heisenberg, Thanks for sharing those questions, they are real good. You can implement HashMap by using Array, because only provide constant time access, if you know index. Key is to writing hash function to minimize collision. Similarly, you can implement linked list by creating some class e.g. Node, which holds data and keep track of next node. By the way, I will try to blog answers in more details.

Hi Javin, Gr8 artcile once again regarding second question ( How to find if linked list has loop ?), I want to add the following thing...

1) To determine if linked list has a loop or not..

You can detect it by simply running two pointers through the list. Start the first pointer A on the first node and the second pointer B on the second node.

Advance the first pointer by one every time through the loop, advance the second pointer by two. If there is a loop, they will eventually point to the same node. If there's no loop, you'll eventually hit the end with the advance-by-two pointer.

Consider the following loop:

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

^ |

| |

+------------------------+

Starting A at 1 and B at 2, they take on the following values:

A B

= =

1 2

2 4

3 6

4 8

5 4

6 6

Because they're equal, and B should always be beyond A (because it's advancing by two as opposed to the advance-by-one behaviour of A), it means you've discovered a loop.

The pseudo-code will go something like this:

def hasLoop (pointer nodeA):

# nodeA is first element

# Empty lest has no loops.

if nodeA == NULL: return false

# Set nodeB to second element.

nodeB = nodeA.next

# Until end of list with nodeB.

while nodeB != NULL:

# Advance nodeA by one, nodeB by two (with end-list check).

nodeA = nodeA.next

if nodeB.next == NULL: return false

nodeB = nodeB.next.next

# If same, we have a loop.

if nodeA == nodeB: return true

endwhile

# Exited without loop maens no loop.

return false

enddef

2) The second query is to the point at which loop started...

Once you know a node within the loop, finding the first node is easy.

Leave one pointer A on that node and advance the other B by one. Then use a third node C, initially set to the head.

Then you just advance B continuously. If you find it equal to C, then C is the start of your loop. On the other hand, if B ends up wrapping around to A again, then C is before your loop.

In that case, advance C and B by one and keep going. Eventually, C will enter the loop and be met by B, at which point you're done.

(C goes this way).

C ->> A (this is where A and B

| | first met).

v v

head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

^ |

| |

+------------------------+

(B runs through this loop, every time

it reaches A, you advance C; when it

reaches C, that's your first loop node).

Javin Regarding Q3 (How to find 3rd element from end in a linked list in one pass)

One approach could be in terms of pseudo ode could also be

The first node in you list I am assuming is called head.

So set a pointer to head, we'll call it current

Node current = head;

Then make another pointer that points three positions ahead

Node threeAhead = head.next.next.next;

Then write a loop that first checks to see if threeAhead.next is null, if it is not:

threeAhead = threeAhead.next;

curr = curr.next;

When threeAhead.next becomes null, you are three positions from the end with current.

so finally if you know what the length of the list is before you start,

node = first;

for (i = 0; i < length - N_FROM_END; i++) {

node = node.next;

}

result = node.value

In java ..java.util.LinkedList: linkedList.get(linkedList.size() - 3)

but if you don't now the length..

nodes = new Node[N_FROM_END];

node = first;

for (i = 0; node != null; i++) {

nodes[i % N_FROM_END] = node;

node = node.next;

}

result = nodes[i % N_FROM_END].value

or something like that. (Check the boundary conditions ... and account for the list length being less than N_FROM_END.)

@Saral Saxena, Great comment and thanks for your pseudo code, I see it helps. I will try to cover question of detecting linked list with loop, may be another post. Once again, thanks for adding value.

Javin

@Javin and Saral, can u guys please have a look if below method is correct for Queation 2 (loop detection in linkedlist)

public static void isListInLoop(LinkedList.Node head, Node tail) {

LinkedList.Node nodeA = head.next();

LinkedList.Node nodeB = head.next().next();

int counter = 0;

while(nodeB.next() != null) {

if( nodeA.equals(nodeB) )

break;

nodeB = nodeB.next();

}

System.out.println("Loop detected...");

}

For Question 3 another solution could be (with java.util.LinkedList),

public static void get3rdElementFromEnd () {

java.util.LinkedList ll = new java.util.LinkedList();

ll.add("A");

ll.add("B");

ll.add("C");

ll.add("D");

ll.add("E");

ll.add("F");

ll.add("G");

int threeAhead=0, threeBack=0;

System.out.println("ll.size = "+ll.size());

if(ll.size() > 3) {

for(String s : ll) {

threeAhead++;

if(threeAhead > 3 )

threeBack++;

}

int i = threeAhead - threeBack;

System.out.println("-- i = "+i);

if( i == 3 ) {

System.out.println("Third Element From End = "+ll.get(threeBack));

}

}

}

Please comment if this solution is not perfect at any point.

Hi guys, recently in an interview I was asked how would you reverse a linked list? I answered that I would have a new list, iterate the original linked list and add elements of this list at head of new list. Interviewer was not convinced with my answer. Anyway I thought of writing a program to prove this...here is complete program.

package example.datastructure;

public class LinkedlistExample {

public static void main(String[] args) {

Node head = new Node();

for (int i =3;i<=10;i++)

{

insertAtTail(head, new Node(""+i, null));

}

for (int i =2;i>0;i--)

{

insertAtHead(head, new Node(""+i, null));

}

traverseList(head);

reverseList(head);

traverseList(head);

deleteNode(head, "10");

traverseList(head);

}

/*

* Add element at tail of list.

* */

static void insertAtTail(Node head, Node node)

{

if (head.next == null)

{

head.next=node;

System.out.println("Linked list is empty insertAtLast");

return;

}

Node lastNode = head.next;

while(lastNode.next!=null)

{ lastNode=lastNode.next;

}

lastNode.next=node;

}

/*

* delete a node matching data.

* */

static void deleteNode(Node head, String data)

{

if (head.next == null)

{

System.out.println("Linked list is empty in deleteNode");

return;

}

Node lastNode = head.next;

Node previousNode = head;

while(lastNode!=null)

{

if(lastNode.data.equals(data))

{

break;

}

previousNode = lastNode;

lastNode=lastNode.next;

}

previousNode.next=lastNode.next;

}

/*

* Add element at head of list

* */

static void insertAtHead(Node head, Node node)

{

if (head.next == null)

{

head.next=node;

System.out.println("Linked list is empty insertAtHead");

return;

}

node.next=head.next;

head.next=node;

}

static void traverseList(Node head)

{

Node lastNode = head.next;

if (head.next == null)

{

System.out.println("Linked list is empty in traverseList");

}

System.out.print("Data: ");

while(lastNode!=null)

{

System.out.print(" " + lastNode.data);

lastNode=lastNode.next;

}

System.out.println();

}

/*

* Reverse a linked list.

* */

static void reverseList(Node head) {

if (head.next == null)

{

System.out.println("Linked list is empty in reverseList");

}

/*

* Create a linked list by adding elements of original list at head of new list.

* */

Node newHead = new Node();

Node lastNode = head.next;

Node tempNode;

while(lastNode!=null)

{

tempNode = lastNode;

lastNode=lastNode.next;

tempNode.next=newHead.next;

newHead.next=tempNode;

}

head.next = newHead.next;

}

}

class Node

{

String data;

Node next;

Node()

{}

Node(String data, Node next)

{

this.data=data;

this.next= next;

}

}

Output:

Linked list is empty insertAtLast

Data: 1 2 3 4 5 6 7 8 9 10

Data: 10 9 8 7 6 5 4 3 2 1

Data: 9 8 7 6 5 4 3 2 1

Please suggest if anything wrong in this code.

Thanks,

Prashant

Some more codes..1) Find middle element 2) find nth element 3) Find and remove loop in list

package example.datastructure;

public class LinkedlistExample {

public static void main(String[] args) {

Node head = new Node();

for (int i =3;i<=10;i++)

{

insertAtTail(head, new Node(""+i, null));

}

for (int i =2;i>0;i--)

{

insertAtHead(head, new Node(""+i, null));

}

findMiddleElement(head);

findNthElementfromlast(head,4);

// Create , detect and remove loop from list

head = new Node();

createListHavingLoop(head);

findAndRemoveLoopNode(head);

traverseList(head);

}

static void removeLoopNode(Node loopNode, Node head)

{

Node node1 = head;

Node node2 = null;

while (true)

{

node2 = loopNode;

while (node2.next != loopNode && node2.next != node1)

{

node2 = node2.next;

}

if (node2.next == node1)

{

break;

}

else

{

node1= node1.next;

}

}

node2.next=null;

}

static void findAndRemoveLoopNode(Node head)

{

if (head.next == null)

{ System.out.println("Linked list is empty findLoopNode");

return;

}

Node currentNode = head.next;

Node startNode=head;

Node lastNode=head.next.next;

while(lastNode!=null)

{

currentNode = currentNode.next;

if (lastNode.next != null)

{

lastNode = lastNode.next.next;

}

if(lastNode == currentNode)

{

startNode = startNode.next;

System.out.println("Loop Node is :" + currentNode.data);

removeLoopNode(currentNode, head);

return;

}

}

System.out.println("Loop node does not exist");

}

static void createListHavingLoop(Node head)

{

Node node1= new Node("1", null);

Node node2= new Node("2", null);

Node node3= new Node("3", null);

Node node4= new Node("4", null);

Node node5= new Node("5", null);

Node node6= new Node("6", null);

Node node7= new Node("7", null);

Node node8= new Node("8", null);

Node node9= new Node("9", null);

Node node10= new Node("10", node4);

insertAtTail(head, node1);

insertAtTail(head, node2);

insertAtTail(head, node3);

insertAtTail(head, node4);

insertAtTail(head, node5);

insertAtTail(head, node6);

insertAtTail(head, node7);

insertAtTail(head, node8);

insertAtTail(head, node9);

insertAtTail(head, node10);

}

static void findNthElementfromlast(Node head, int nthFromLast)

{

if (head.next == null)

{ System.out.println("Linked list is empty findNthElementfromlast");

return;

}

Node currentNode = head.next;

Node tempNode=head;

Node lastNode = null;

for (int i=1; i<=nthFromLast;i++)

{

tempNode = tempNode.next;

}

lastNode=tempNode;

while(lastNode.next!=null)

{

if (lastNode.next != null)

{ lastNode = lastNode.next;}

currentNode = currentNode.next;

}

System.out.println(nthFromLast + " element from last is : " + currentNode.data);

}

static void findMiddleElement(Node head)

{

if (head.next == null)

{ System.out.println("Linked list is empty findMiddleElement");

return;

}

int length = 0;

Node middleNode = head;

Node lastNode= head.next;

while(lastNode!=null)

{

length++;

if(length % 2 == 0)

{

middleNode = middleNode.next;

}

lastNode = lastNode.next;

}

if (length %2 ==1)

{

middleNode = middleNode.next;

}

System.out.println("Middle element is : " + middleNode.data);

}

}

Thanks,

Prashant

We can have one more way to solve the first question :: using queue.

We can maintain a queue and insert the element as we encounter in the linked list. While we are inserting elements, we need to make sure that queue represent the middle element at the beginning. We can do this as follows ::

Inserting 3 elements out of n at first allows us to appreciate that it will be the second element which will be middle element(atleast because we have considered only 3 elements while inserting into queue). Now we will remove the first element (as queue structure)inserting next two elements. Now we have 5 elements and for sure we know we can make out the middle element will be at greater position than previously encountered one. So that's it. We will proceed with this till the end of list. By this we do not have to spend extra overhead maintaining pointers.

For the question on identifying the duplicate in the array containing numbers 1 to 100, the difference in actual and expected sums may not give you the duplicate.

For instance, if I have an array containing three elements in the range 1-3, with 2 being the duplicate, i.e., the array is 1, 2 and 2, then the actual sum is 5 and the expected sum is 6. The difference is 1, which isn't the duplicate element.

You could use a hashmap, with the numbers 1-100 as keys and their count as values. When a key is updated twice, then that is the duplicate element. Thus, the problem of locating a duplicate element can be solved in O(n) time, but may take O(n) space.

In one of interview with Credit Suisse, I was asked to that which data structure will you use to represent and OrderBook in financial market? I wasn't sure, but I replied that Binary tree will be better choice because Orders are always sorted on time, in a particular price bracket for a particular instrument. Can any one please advise on below question, Though I think I tried in hard, still want to know expert opinions.

Can you also suggest Which data structure is suitable for parking lot, imagine you have millions of parking lots?

@Vishnu, I think binary tree is right choice to implement a LIMIT order book, where order can match either to exact price or better price, which is lower than specified for buy orders and higher than specified for sell orders. For that reason, you need to navigate to tree, whose node should be price, but they should also contain Queue of Orders to maintain time priority. In short, your Orderbook should look like:

class OrderBook{

private Map<Instrument, Tree<Node(Price, Queue<Orders>>> book;

}

In one interview i was asked to write a function to print below. input to the function is 3.

*

* * *

* * * *

Which data-structure should I use to detect deadlock between threads? This was asked as write a routine to detect deadlock from a pool of threads to me in a Java interview.

Given a string S, and a list of strings of positive length, F1,R1,F2,R2,...,FN,RN, proceed to find in order the occurrences (left-to-right) of Fi in S and replace them with Ri. All strings are over alphabet { 0, 1 }. Searching should consider only contiguous pieces of S that have not been subject to replacements on prior iterations. An iteration of the algorithm should not write over any previous replacement by the algorithm.

Input sample:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will contain a string, then a semicolon and then a list of comma separated strings.eg.

10011011001;0110,1001,1001,0,10,11

Output sample:

For each line of input, print out the string after substitutions have been made.eg.

11100110

For the curious, here are the transitions for the above example: 10011011001 => 10100111001 [replacing 0110 with 1001] => 10100110 [replacing 1001 with 0] => 11100110 [replacing 10 with 11] => 11100110

HI gyuz, I want to check the two strings are matching 70% or not. Can anyone help me out?

can you help me:

Consider the file named cars.txt, each line in the file contains information about a

car (Year, Company, Manufacture, ModelName, Type ).

1) Read the file.

2) Add each car which is represented using one line of the file to a singular link

list. Use an object of the following class.

Class node

{

int year;

stringCompany;

stringManufacture;

stringModelName;

stringType;

Char Owner;

node next;

}

3) After creating your list do the following:

a. Print how many cars owned by the person (B)?

b. Print how many cars are on the file (you need to count the link list

nodes)?

c. Print everything about all the cars that have been manufactured on

2012 on a new file called 2012Cars.

d. Print all companies’ names on a new file called company. Note do

not repeat the company name.

e. Print all the cars that has been Manufactured by Toyota in a new file

called Toyota. Note, we need to print only the ModleName.

f. Delete the first car in the list that manufactured by Honda and print

the file again. Name the file Honda.

g. Delete the last car in the list. Print the result in a new file called

CarLast. h. Print the Manufacture and the modelName of all trucks in the list

Print the result in a new file called Trucks.

ans of q4 is not correct.

ans would be

int[] o = {1,2,3,4,5,6,2,8,9,10};

int[] n = new int[o.length+1];

for(int i= 0; i < o.length; i++){

n[o[i]]++;

}

for(int i= 0; i < o.length; i++){

System.out.println("no of "+ o[i] + " is "+ n[o[i]]);

}

For Question number nine if we just have to find the Duplicate values and not their occurance below code is sufficient:

import java.util.HashSet;

import java.util.Set;

public class DuplicateFinder

{

public Set getDuplicateValues(T[] arr)

{

Set duplictes = new HashSet();

Set hashSet = new HashSet(arr.length);

for(int i=0; i< arr.length; i++) {

if(!hashSet.add(arr[i])) {

duplictes.add(arr[i]);

}

}

return duplictes;

}

/**

* @param args

*/

public static void main(String[] args) {

DuplicateFinder duplicateStringFinder = new DuplicateFinder();

Set duplicateStrings = duplicateStringFinder.getDuplicateValues(new String[]{"a", "b", "c", "d","d","a"});

System.out.println("Duplicate strings are:" + duplicateStrings.toString());

DuplicateFinder duplicateIntFinder = new DuplicateFinder();

Set duplicateIntegers = duplicateIntFinder.getDuplicateValues(new Integer[]{1,2,3,4,1,4,5,5,5});

System.out.println("Duplicate integers are:" + duplicateIntegers.toString());

}

}

Regarding Q-2

we can do it by storing the next pointer values of each node , if any duplicate comes then it's a loop.

or

we can also do with two pointers in O(n). simply say one slow pointer and one fast pointer. slow pointer will increase one time where as fast pointer will increase twice. so if we get fastpointer==slowpointer then there is loop , and if fastpointer==null then no loop that's it.

## Post a Comment