Data Structures Interview Questions

Question 1: How to find middle element of linked list 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 the first pointer reaches the end, the second pointer will point to a middle element of the linked list

public class LinkedListTest {

public static void main(String args[]) {
//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
LinkedList.Node head = linkedList.head();
linkedList.add( new LinkedList.Node(“1”));
linkedList.add( new LinkedList.Node(“2”));
linkedList.add( new LinkedList.Node(“3”));
linkedList.add( new LinkedList.Node(“4”));

//finding middle element of LinkedList in single pass
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;

while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}

if(length%2 == 1){
middle = middle.next();
}

System.out.println(“length of LinkedList: ” + length);
System.out.println(“middle element of LinkedList : ” + middle);

}

class LinkedList{
private Node head;
private Node tail;

public LinkedList(){
this.head = new Node(“head”);
tail = head;
}

public Node head(){
return head;
}

public void add(Node node){
tail.next = node;
tail = node;
}

public static class Node{
private Node next;
private String data;

public Node(String data){
this.data = data;
}

public String data() {
return data;
}

public void setData(String data) {
this.data = data;
}

public Node next() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public String toString(){
return this.data;
}
}
}

Output:
length of LinkedList: 4
the middle element of LinkedList: 2

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

This question has a bit of similarity with the 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 the same node.
This will only happen if a linked list has a loop or cycle.

* Java class to represent linked list data structure.

public class LinkedList {

privateNode head;

public LinkedList() {

this.head = new Node(“head”);

}

publicNode head() {

returnhead;

}

public void appendIntoTail(Node node) {

Node current = head;

// find last element of LinkedList i.e. tail

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

current= current.next();

}

// appending new node to tail in LinkedList

current.setNext(node);

}

* If singly LinkedList contains Cycle then following would be true 1) slow and

* fast will point to same node i.e. they meet On the other hand if fast will

* point to null or next node of fast will point to null then LinkedList does

* not contains cycle.

publicbooleanisCyclic() {

Node fast = head;

Node slow = head;

while(fast != null && fast.next != null) {

fast= fast.next.next;

slow= slow.next;

// if fast and slow pointers are meeting then LinkedList is cyclic

if (fast == slow) {

returntrue;

}

returnfalse;

}

@Override

public String toString() {

StringBuildersb = new StringBuilder();

Node current = head.next();

while(current != null) {

sb.append(current).append(“–>”);

current= current.next();

}

sb.delete(sb.length() – 3, sb.length()); // to remove –> from last node

return sb.toString();

}

publicstaticclass Node {

private Node next;

private String data;

public Node(String data) {

this.data = data;

}

public String data() { return data; }

public void setData(String data) { this.data = data;}

public Node next() { return next; }

public void setNext(Node next) { this.next = next; }

@Override

public String toString() {

return this.data;

}

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

If we apply the same trick of maintaining two-pointers and increment another pointer, when first has moved up to the 3rd element, then when the first pointer reaches the end of the linked list, the second pointer will be pointing to the 3rd element from last in a linked list.

Sometimes, interviewers can also generalize this problem and ask him to find the kth element from the tail, end, or last. Just use the same logic, replace 3 with k and you can solve the problem.

// Simple Java program to find n'th node from end of linked list

class LinkedList {

Node head; // head of the list

/* Linked List node */

class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

/* Function to get the nth node from the last of a

linked list */

void printNthFromLast(int n)

{

int len = 0;

Node temp = head;

// 1) count the number of nodes in Linked List

while (temp != null) {

temp = temp.next;

len++;

}

// check if value of n is not more than length of

// the linked list

if (len < n)

return;

temp = head;

// 2) get the (len-n+1)th node from the beginning

for (int i = 1; i < len - n + 1; i++)

temp = temp.next;

System.out.println(temp.data);

}

/* Inserts a new Node at front of the list. */

public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/*Driver program to test above methods */

public static void main(String[] args)

{

LinkedList llist = new LinkedList();

llist.push(20);

llist.push(4);

llist.push(15);

llist.push(35);

llist.printNthFromLast(4);

}

} //

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 structure question, especially for this kind of. In this case, you can simply add all numbers stored in an array, and the 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 the performance of O(n^2) which is not good.

By the way, this trick will not work if an array has multiple duplicates, or it’s not numbered forming an arithmetic progression.

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class CheckDuplicatesInJavaArray {

public static void main(String args[]) {

String[] withDuplicates = new String[] {“one”,”two”,”three”,”one”};

String[] withoutDuplicates = new String[] {“one”,”two”,”three”};

System.out.println(“Checking array with duplicate using brute force: ” + bruteforce(withDuplicates));

System.out.println(“Checking array without any duplicate using brute force: ” + bruteforce(withoutDuplicates));

System.out.println(“Checking array with duplicate using Set and List: ” + checkDuplicateUsingSet(withDuplicates));

System.out.println(“Checking array without any duplicate using Set and List: ” + checkDuplicateUsingSet(withoutDuplicates));

System.out.println(“Checking array with duplicate using Set and List: ” + checkDuplicateUsingAdd(withDuplicates));

System.out.println(“Checking array without any duplicate using Set and List: ” + checkDuplicateUsingAdd(withoutDuplicates));

}

* brute force way of checking if array contains duplicates in Java

* comparing each element to all other elements of array

* complexity on order of O(n^2) not advised in production

public static boolean bruteforce(String[] input) {

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

for (int j = 0; j < input.length; j++) {

if (input[i].equals(input[j]) && i != j) {

return true;

}

return false;

}

* detect duplicate in array by comparing size of List and Set

* since Set doesn’t contain duplicate, size must be less for an array which contains duplicates

public static boolean checkDuplicateUsingSet(String[] input){

List inputList = Arrays.asList(input);

Set inputSet = new HashSet(inputList);

if(inputSet.size()< inputList.size())

return true;

}

return false;

}

* Since Set doesn’t allow duplicates add() return false

* if we try to add duplicates into Set and this property

* can be used to check if array contains duplicates in Java

public static boolean checkDuplicateUsingAdd(String[] input) {

Set tempSet = new HashSet();

for (String str : input) {

if (!tempSet.add(str)) {

return true;

}

return false;

}

Output:

Checking array with duplicate using brute force: true

Checking array without any duplicate using brute force: false

Checking array with duplicate using Set and List: true

Checking array without any duplicate using Set and List: false

Checking array with duplicate using Set and List: true

Checking array without any duplicate using Set and List: false

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

public class SinglyLinkedList {    private Node head;  // Head is the first node in linked list    public void append(T data){        if(head == null){            head = new Node(data);            return;        }        tail().next = new Node(data);    }     private Node tail() {        Node tail = head;             // Find last element of linked list known as tail        while(tail.next != null){            tail = tail.next;        }              return tail;         }     @Override    public String toString(){        StringBuilder sb = new StringBuilder();        Node current = head;        while(current != null){           sb.append(current).append("-->");           current = current.next;        }            if(sb.length() &gt;=3){            sb.delete(sb.length() - 3, sb.length());             // to remove --> from last node        }             return sb.toString();    }    /**      * Reverse linked list using 3 pointers approach in O(n) time      * It basically creates a new list by reversing direction, and      * subsequently insert the element at the start of the list.      */    public void reverseIteratively() {        Node current = head;        Node previous = null;        Node forward = null;             // traversing linked list until there is no more element        while(current.next != null){                     // Saving reference of next node, since we are changing current node            forward = current.next;                     // Inserting node at start of new list            current.next = previous;            previous = current;                     // Advancing to next node            current = forward;        }             head = current;        head.next = previous;    }     /*     * Reverse a singly linked list using recursion. In recursion Stack is     * used to store data.        * 1. Traverse linked list till we find the tail,      * that would be new head for reversed linked list.     */    private Node reverseRecursively(Node node){       Node newHead;            //base case - tail of original linked list       if((node.next == null)){           return node;       }       newHead = reverseRecursively(node.next);            //reverse the link e.g. C->D->null will be null              node.next.next = node;       node.next = null;           return newHead;    }      public void reverseRecursively(){        head = reverseRecursively(head);    }      private static class Node {        private Node next;        private T data;        public Node(T data) {            this.data = data;        }        @Override        public String toString() {            return data.toString();        }    } }                                  DATA STRUCTURE SPECIFIC INERVIEW QUESTIONS:

1. Array Coding and Data Structures Interview Questions

An array is the most fundamental data structure, which stores elements at a contiguous memory location. It is also one of the darling topics of
interviewers and you will hear a lot of questions about an array in any INTERVIEW e.g. reversing an array, sorting the array, or searching elements on the array.

The key benefit of an array data structure is that it offers fast O(1) search if you know the index, but adding and removing an element from an array is slow because you cannot change the size of the array once it’s created.

In order to create a shorter or longer array, you need to create a new array and copy all elements from old to new.

The key to solving array-based questions is having a good knowledge of array data structure as well as basic programming constructors such as loop, recursion, and fundamental operators.

Here are some of the popular array-based coding interview questions for your practice:

How do you find the missing number in a given integer array of 1 to 100?
How do you find the duplicate number on a given integer array?
How do you find the largest and smallest number in an unsorted integer array?
How do you find all pairs of an integer array whose sum is equal to a given number?
How do you find duplicate numbers in an array if it contains multiple duplicates?
How are duplicates removed from a given array in Java?
How is an integer array sorted in place using the quicksort algorithm?
How do you remove duplicates from an array in place?
How do you reverse an array in place in Java?
How are duplicates removed from an array without using any library?

These questions will not only help you to develop your problem-solving skills but also improve your knowledge of array data structure.

2. Linked List Programming Interview Questions

A linked list is another common data structure that complements the array data structure. Similar to the array, it is also a linear data structure and
stores elements in a linear fashion.

However, unlike the array, it doesn’t store them in contiguous locations; instead, they are scattered everywhere in memory, which is connected to each other using nodes.

A linked list is nothing but a list of nodes where each node contains the value stored and the address of the next node.

Because of this structure, it’s easy to add and remove elements in a linked list, as you just need to change the link instead of creating the array, but the search is difficult and often requires O(n) time to find an element in the singly linked list.

It also comes in varieties like a singly linked list, which allows you to traverse in one direction (forward or reverse); a doubly linked list,
which allows you to traverse in both directions (forward and backward);
and finally, the circular linked list, which forms a circle.

If you take one node from a linked list, the remaining data structure is still a linked list, and because of that, many linked list problems have
simpler recursive solutions than iterative ones.

Here are some of the most common and popular linked list interview questions and their solutions:

How do you find the middle element of a singly linked list in one pass?
How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle?
How do you reverse a linked list?
How do you reverse a singly linked list without recursion?
How are duplicate nodes removed in an unsorted linked list?
How do you find the length of a singly linked list?
How do you find the third node from the end in a singly linked list?
How do you find the sum of two linked lists using Stack?

These questions will help you to develop your problem-solving skills as well as improve your knowledge of the linked list data structure.

3. String Coding Interview Questions

Along with array and linked list data structures, a string is another popular topic on programming job interviews. I have never participated in a
coding interview where no String interview questions were asked.

A good thing about the string is that if you know the array, you can solve string-based questions easily because strings are nothing but a character array.

So all the techniques you learn by solving array-based coding questions can be used to solve string programming questions as well.

Here is my list of frequently asked string coding questions from programming job interviews:

How do you print duplicate characters from a string?
How do you check if two strings are anagrams of each other?
How do you print the first non-repeated character from a string?
How can a given string be reversed using recursion?
How do you check if a string contains only digits?
How are duplicate characters found in a string?
How do you count a number of vowels and consonants in a given string?
How do you count the occurrence of a given character in a string?
How do you find all permutations of a string?
How do you reverse words in a given sentence without using any library method?
How do you check if two strings are a rotation of each other?
How do you check if a given string is a palindrome?

These questions help improve your knowledge of string as a data structure. If you can solve all these String questions without any help then you are in good shape.

4. Binary Tree Coding Interview Questions

So far, we have looked at only the linear data structure, but all information in the real world cannot be represented in linear fashion,
and that’s where tree data structure helps.

Tree data structure is a data structure that allows you to store your data in a hierarchical fashion. Depending on how you store data, there are different types of trees, such as a binary tree, where each node has, at most, two child nodes.a

Along with its close cousin binary search tree it’s also one of the most popular tree data structures. Therefore, you will find a lot of questions based on them, such as how to traverse them, count nodes, find depth, and check if they are balanced or not.

A key point to solving binary tree questions is a strong knowledge of theory, e.g. what is the size or depth of the binary tree, what is a leaf, and
what is a node, as well as an understanding of the popular traversing
algorithms, e.g. pre-, post-, and in-order traversal.

Here is a list of popular binary tree-based coding questions from software engineer or developer job interviews:

How is a binary search tree implemented?
How do you perform preorder traversal in a given binary tree?
How do you traverse a given binary tree in preorder without recursion?
How do you perform an inorder traversal in a given binary tree?
How do you print all nodes of a given binary tree using inorder traversal without recursion?
How do you implement a postorder traversal algorithm?
How do you traverse a binary tree in postorder traversal without recursion?
How are all leaves of a binary search tree printed?
How do you count a number of leaf nodes in a given binary tree?
How do you perform a binary search in a given array?

5. Miscellaneous Coding Interview Questions

Apart from data structure-based questions, most of the programming job interviews also ask algorithm, design, bit manipulation, and general
logic-based questions, which I’ll describe in this section.

It’s important that you practice these concepts because sometimes they become tricky to solve in the actual interview. Having practiced them
before not only makes you familiar with them but also gives you more confidence in explaining the solution to the interviewer.

How is a bubble sort algorithm implemented?
How is an iterative quicksort algorithm implemented?
How do you implement an insertion sort algorithm?
How is a merge sort algorithm implemented?
How do you implement a bucket sort algorithm?
How do you implement a counting sort algorithm?
How is a radix sort algorithm implemented?
How do you swap two numbers without using the third variable?
How do you check if two rectangles overlap with each other?
How do you design a vending machine?

Tech Studio Online