In this article, we have present some must practice "Design a Data Structure" problems. These are important problems for Coding Interviews at Google and other companies. You need to modify standard data structure to form new data structures to solve this problem efficiently.

Following are the important "Design a Data Structure" problems:

Problem 1

Design a data structure that supports the following three operations:

• Insert: Insert an element E into the data structure
• Delete: Delete a given element E (if present) from the data structure
• Get Random: Return a random element for the data structure

Hint:

Make a 2 copies of a single element and save one copy in a 1D array and the other copy in a Hash Map. Think how will you implement the operations so that it operates in constant time O(1). The time complexity of the operations will be:

• Insert: O(1)
• Delete: O(1)
• Random: O(1)

Problem 2

Design a data structure that supports the following three operations:

• Insert: Insert an element E into the data structure
• Delete: Delete a given element E (if present) from the data structure
• K product: The product of the last K inserted elements

The time complexity of the operations will be:

• Insert: O(1)
• Delete: O(1)
• Product: O(1)

Problem 3

Design a data structure that represents an Excel spreadsheet / 2D map and supports the following operations:

• Insert an element E point at point (x, y)
• Delete an element at point (x, y)
• Find the points closest to point (x, y)

Hint:

A Binary Tree data structure can be used to design this data structure and support these operations at the following time complexity:

• Insert: O(logN)
• Delete: O(logN)
• Find nearby points: O(logN)

where N is the total number of elements inserted.

Problem 4

Design a data structure where the following operations are supported:

• Insert an element E
• Delete an element E
• Find Minimum of all elements
• Find Maximum of all elements

Hint:

We can use two Binary Heaps: Minimum and Maximum Binary Heaps to design this data structure. The time complexity of the operations will be:

• Insert: O(logN)
• Delete: O(logN)
• Find Minimum: O(1)
• Find Maximum: O(1)

where N is the total number of elements.

Problem 5

Design a data structure where the following operations are supported:

• Insert an element E
• Delete an element E
• Find the most frequent element

Hint:

This data structure can be designed using Hash Map and Linked List. The time complexity of the operations will be:

• Insert: O(1)
• Delete: O(1)
• Most frequent: O(1)

Problem 6

Design a data structure where the following operations are supported:

• Insert an element E
• Delete an element E
• Find the median element

Hint:

This data structure can be designed using Binary Heap or Multi-ordered set. You will get the idea here. The time complexity of the operations will be:

• Insert: O(logN)
• Delete: O(logN)
• Median: O(1)

Problem 7

Design a data structure where the following operations are supported:

• Insert an element E
• Delete an element E
• Product of K elements in between

Hint:

This data structure can be designed using a modified balanced Binary Tree inserting elements based on time stamp. The time complexity of the operations will be:

• Insert: O(logN)
• Delete: O(logN)
• Product: O(1)

Problem 8

Design a data structure such that there are K sets of elements and the total number of elements across all K sets in N. Given an element E, we have to find the closest element to E in each of K sets.

Pre-processing of the dataset is allowed.

Hint:

This data structure requires to create bridge across the different sets. The technique to design this data structure is known as Fractional Cascading. The time complexity of the operation will be:

• Time Complexity of operation: O(logN + K)
• Space Complexity: O(N)