Data Structures Interview Questions and Answers Data Science

This is one of the most frequently asked data structures coding questions and answers for freshers in recent times.

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.

Expect to come across this, one of the most important data structures interview questions for experienced professionals in web development, in your next interviews.

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.

A must-know for anyone looking for top data structures interview questions, this is one of the frequently asked data structures interview questions and answers for freshers.

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.

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.

One of the most frequently posed DS interview questions and answers, be ready for this conceptual question.

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.

This is a common, yet one of the most important data structures and algorithms interview questions and answers for experienced professionals, don't miss this one.

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.