Data Structures Interview Questions

Finding the right career path is hard and creates a lot of anxiety about how to select the right path. Don’t worry! To land your dream job we have brought you Data Structures questions for interview which will help you pass the toughest of Data Structures interview. We have compiled the questions on various topics like ArrayList, Blocking Queue, Stack, etc. Prepare with these Data Structures interview questions, and answers and pursue your career.

  • 4.5 Rating
  • 10 Question(s)
  • 10 Mins of Read
  • 7654 Reader(s)

Advanced

An ArrayList is a collection of homogenous data types stored in contiguous memory locations. An ArrayList can be sorted using Collections.sort() method. This works fine as long as the ArrayList is made up of Strings. In case the ArrayList is made of custom object – Employee  - in our case, we need to do a few more things

  • Create a class that implements the Comparator interface. This interface provides the compare() method which compares two arguments for order. It returns a negative integer if the first argument is less than second, zero if the two are equal, else a positive value. The inputs to this method will two employee objects that need to be compared. Inside the method write the logic to fetch the first name from the objects and compare them.
  • In the Main class where theCollections.sort is called also pass the object of above-created class e.g. Collections.sort(<arraylist obj>, new <object of a class implementing comparator>)
  • In case you want an option to sort theArrayList by first name or last name then you can create another class implementing Comparator which sorts the objects based on lastname. In the main method based on the preference, you can pass the desired comparator class in a sort method.
  • Another way to sort theArrayList is to implement Comparable interface. This interface provides a compareTo() method which takes in an object to be compared as input. Extend the Employee class to implement this interface and override the compareTo method to compare the objects based on the first name. As you can see, this approach is less flexible as compared to the one for using Comparator.

A singly linked LinkedList is uni-directional with each node pointing to the next node. One of the ways to traverse the list and print it in reverse order in a single go is with the help of the Stack data structure.

A stack data structure follows Last In First Out (LIFO) order i.e. the last element to be pushed to the stack would be the first element that will be popped out. To print the linked list in reverse order we simply traverse the list and push each element to the stack. Once traversal is complete we need to pop out each element from the stack until no more element is left. Since the element that gets added last will be the first one to be popped out, the elements will be printed in reverse order.

Finding the middle element in a LinkedList is another common problem. To solve it we need to use two pointers. One pointer will be moved by one element at a time, while the other pointer will be moved two elements at a time. This way when the second pointer reaches the end of the linked list, the position where the first pointer would be, in the middle of the linked list.

An ArrayList is a homogenous collection of elements. The elements are placed in contiguous memory locations. Unlike an array which is of fixed size, ArrayList is dynamic in nature i.e. its size automatically grows when new elements get added to it.

It is part of Java’s Collection framework and implementation of its List interface.

A thread-safe collection is one that operates in the desired manner even when multiple threads are operating on it in parallel. An ArrayList is not threadsafe by default. It means that in a multi-threaded environment with multiple threads adding or removing elements from ArrayList at the same time, extra care needs to be taken to ensure that transactions are atomic in nature and do not interfere with one another. This can be done by synchronizing the ArrayList. There are two ways to achieve this:

  • One is to usesynchronizedList() method from Collections API – This method returns a threadsafe version of the original list. However, when iterating this threadsafe list, we should manually synchronize it as well.
  • Another way is to useCopyOnWriteArrayList. It is a thread-safe variant of ArrayList API and doesn’t require explicit synchronization while traversal. All mutative operations like add, remove, etc are implemented by creating a separate copy of the underlying array.

In the above example, the first non-repeating character is ‘l’. As can be seen, we need to iterate over each element of the String and maintain a count of the number of times each unique character appears. In addition, we also need to maintain the order in which element occurs so that the first non-repeating character can be determined. For this scenario, we can use a LinkedHashMap.

A linkedhashmap is similar to hashmap – so it essentially stores data as key-value pair - with the additional feature that it maintains the order of insertion of elements. It can alternatively also maintain the order of access to elements. The keys in the map are unique.

To solve the above problem, we iterate the string starting from the first element. For each character, we check if the element already exists in the map or not. Each new character is added to linkedhashmap (which maintains insertion order) with count 1. If the element already exists, the count is updated. Once the string traversal is complete, we have the unique elements as well as their count in linkedhashmap.

To find first non-repeating we now iterate over linkedhashmap and find the key that has a count greater than 1. Since this map maintains the order of insertion of elements, the first such key found would be the answer.

A HashMap is an unordered collection of key-value pairs. Each key in the hashmap must be unique. The underlying implementation can be considered to be an Array of Buckets/Nodes where each Node represents a LinkedList.

When an element is added to a Hashmap, the hashcode of the key is generated using Hashing. Hashing is the process of converting an object to an integer form. Using the hashcode, the bucket where the key should go to is determined. The list at that bucket is then traversed to determine if the key already exists or not. If the key doesn’t exist, the element is added to the LinkedList, else the existing key’s value is updated.

In our case, a key is an object of the employee class. To use employee object as a key we need to ensure that it can be looked up and its uniqueness can be determined. To achieve this we need to override hashcode() and equals() method.

The hashcode() should be written such that the same key will always go to the same bucket. Fro this we can concatenate first name and last name and return hashcode of a concatenated string. In the bucket, the equals() method is used to compare if the two employee objects are the same or not. For this, we can compare the objects both first and last names for equalness.

One of the key points to note is that if hashcode of two objects is the same, they might or might not be equal. But if the two objects are equal then their hashcode must be same.

Intermediate

A linked list is a data structure in which elements are linked to each other using pointers. Each element or node consists of a data field and reference to the next node in the list. Unlike an ArrayList, the elements are not stored in contiguous memory locations. The entry point to the linked list is called head and has the reference to the first node in the list. The last node in the list has reference to null.

A linked list is a linear data structure. A linear data structure is one in which data is arranged in an orderly fashion with the elements attached adjacently to each other. A non-linear data structure is one in which elements are arranged in a hierarchical fashion, creating a relationship among the elements. Some of the examples of the nonlinear data structure are tree and graph.

An ArrayList is essentially an array with elements placed in contiguous memory locations. This makes it much faster when doing get (search) and set (update) operations. However, inserts and deletions are much faster in a LinkedList is no resizing of the list needs to take place as well as no copying of content to a new list is needed in case the previous one gets full. In addition, the linked list is dynamic in nature and memory is allocated when required.

An ArrayList is a collection of homogenous data types stored in contiguous memory locations while a LinkedList is a collection of data elements linked to each other using pointers. Since pointers are used the elements are not required to occupy contiguous memory locations. Let’s see how this arrangement affects searching, insertion and deletion of data.

  • Insertion and Deletion of elements is much easier in a LinkedList. This is because when a new node is added or existing node removed, only the pointers need to be rearranged. No shifting of data is required. However, when an element is added in the mid of anArrayList or removed from the middle, all the remaining elements need to be rearranged resulting in higher cost of operation.
  • Searching, however, is faster is anArrayList as the elements are stored in contiguous memory locations and can be looked up without having to traverse the entire list. In the case of a LinkedList, the entire list needs to be traversed until the element being searched for is found.

Hence if the application involves a number of reads than writes an ArrayList is suitable otherwise a LinkedList.

A singly LinkedList is one in which the node contains two fields – data – the actual content and – address – link to the next node. Though this type of list occupies less memory, it can be traversed in one direction only. A doubly LinkedList is one in which the node contains data and address of previous as well as the next node. This type of list can be traversed in both directions.

Consumer Producer problem is one in which we have two independent entities – a producer and a consumer sharing a common buffer/queue. Producer writes data to the queue while Consumer consumes from it. The problem is that if queue is full then the producer should wait for space to become available before writing to it while if the queue is empty, the consumer should wait for data to become available before starting to read again.

In a traditional queue, if the queue is full and the producer tries to add more elements to it, it will throw an exception. On the other hand, if the queue is empty and the consumer tries to read from it, it will throw an exception again. This is where Blocking Queue is of help.

Blocking Queue is a part of the java.util.concurrent package. It is a type of Queue with the additional feature of blocking if the queue is full or empty. A thread trying to add/enqueue an element to an already full queue is blocked until another thread makes space for it by removing/dequeuing an element from the queue. Similarly, a thread trying to dequeue an element from an empty queue is blocked until another thread adds an element to the queue. Hence in this way, it helps solve the Consumer Producer problem.

The various implementations of BlockingQueue are:

  • LinkedBlockingQueue
  • PriorityBlockingQueue
  • SynchronousBlockingQueue

The stack is a linear data structure that follows First In Last Out (FILO) or Last In First Out (LIFO) order. The first element pushed to the stack is the last element to be popped out. Both push() and pop() methods operate at one end of the stack i.e. Top.  Both push and pop operations operate in constant time i.e. O(1). The stack is said to be in underflow state when empty and overflow state when full. In addition, it is a collection of homogenous data types only.

A queue, on the other hand, follows First in First Out (FIFO) order i.e. an element that is enqueued or added to the queue first is the first one to be dequeued or removed. The insertion of elements happens at one end of the queue while the removal of elements happens at the other end. A queue, however, is also a linear data structure and a collection of similar data types only. The enqueue and dequeue operations run in constant time i.e. O(1).

Some of the applications of the stack are in reversing a string and top-down depth-first parsing in a Natural Language Processing task. A queue, on the other hand, can be used for breadth-first search or serving requests on a shared resource like printer etc.

In this case, we need to iterate over words in the paragraph (separated by space). As we iterate we need to maintain unique elements in the paragraph along with their count. A simple HashMap is well suited for this scenario.

A HashMap is a part of the Java Collections framework and implements the Map interface. Elements are stored as key-value pair. Each key in the map will be unique. Order of insertion of elements is however not maintained. To access a value in a hashmap one must know the corresponding key. If the key is known, it allows us to store an object or retrieve it in constant time – O (1).

To solve the above problem we first split the paragraph by space into a string array. Next, we iterate over elements in this array and check if the element is already present in hashmap or not. If element is not found, then a new entry is created in a hashmap with count 1, else if the element is found then the corresponding count is updated.

Once the array has been traversed we have unique elements as well as their count on the map. Now we simply need to traverse the hashmap and output each as well as corresponding value. This will give us the unique element is the paragraph as well as the number of times it occurred.

Description

Data Structure is a way of collecting and organizing, processing, and storing data. It is basically used to reduce the space and time complexities of different tasks.

Every individual will have a dream to work with the best and the well-known companies. If you are planning to enter the world of Data Structure or considering switching to this extremely in-demand career then Data Structure will be the right choice. Top notch companies like Amazon, Microsoft, and Google are looking for a candidates who are skilled enough. The average salary for a professionals like Data Scientist gets an average salary of an $117,345 per year. But many of us have no idea of what of kind of interview questions you can expect in the data structure interview. Don’t worry we have got you the top most asked data structure questions for an interview.

Data structure interview questions and answers for freshers here will increase your confidence and will help you attend interview. Prepare better with these commonly asked data structure interview questions for freshers or experience which will help you to face the toughest of interviews more confidently.

Treat your next Data Structure interview as  an entrance to success. Give it your best and get the job. Wish you all the luck and confidence.

Read More
Levels