Data structures are the building blocks of any computer program as they help in organizing and manipulating data in an efficient manner. Without data structures, the computer would be unable to understand how to follow a program's instructions properly. It also defines their relationship with one another. Arrays, Linked Lists, Stacks, Queues, and others are examples of Data Structure. Data structures also provide clarity, organization and structure to the program's code while also helping the programmer ensure that each line of code performs its function correctly. In this article, we've compiled the answers to the most frequently asked Data Structure Interview Questions so that you may better prepare for your job interview.
A data structure is a mechanical or logical way that data is organized within a program. The organization of data is what determines how a program performs. There are many types of data structures, each with its own uses. When designing code, we need to pay particular attention to the way data is structured. If data isn't stored efficiently or correctly structured, then the overall performance of the code will be reduced.
Create a free personalised study plan Create a FREE custom study plan Get into your dream companies with expert guidance Get into your dream companies with expert.. Real-Life Problems Prep for Target Roles Custom Plan Duration Flexible PlansData structures serve a number of important functions in a program. They ensure that each line of code performs its function correctly and efficiently, they help the programmer identify and fix problems with his/her code, and they help to create a clear and organized code base.
Following are some real-time applications of data structures:
The difference is that the storage structure has data stored in the memory of the computer system, whereas the file structure has the data stored in the auxiliary memory.
A stack is a data structure that is used to represent the state of an application at a particular point in time. The stack consists of a series of items that are added to the top of the stack and then removed from the top. It is a linear data structure that follows a particular order in which operations are performed. LIFO (Last In First Out) or FILO (First In Last Out) are two possible orders. A stack consists of a sequence of items. The element that's added last will come out first, a real-life example might be a stack of clothes on top of each other. When we remove the cloth that was previously on top, we can say that the cloth that was added last comes out first.
Following are some applications for stack data structure:
Some of the main operations provided in the stack data structure are:
A queue is a linear data structure that allows users to store items in a list in a systematic manner. The items are added to the queue at the rear end until they are full, at which point they are removed from the queue from the front. Queues are commonly used in situations where the users want to hold items for a long period of time, such as during a checkout process. A good example of a queue is any queue of customers for a resource where the first consumer is served first.
Following are some applications of queue data structure:
| Stack | Queue |
|---|---|
| Stack is a linear data structure where data is added and removed from the top. | Queue is a linear data structure where data is ended at the rear end and removed from the front. |
| Stack is based on LIFO(Last In First Out) principle | Queue is based on FIFO(First In First Out) principle |
| Insertion operation in Stack is known as push. | Insertion operation in Queue is known as eneque. |
| Delete operation in Stack is known as pop. | Delete operation in Queue is known as dequeue. |
| Only one pointer is available for both addition and deletion: top() | Two pointers are available for addition and deletion: front() and rear() |
| Used in solving recursion problems | Used in solving sequential processing problems |
A queue can be implemented using two stacks. Let q be the queue and stack1 and stack2 be the 2 stacks for implementing q . We know that stack supports push, pop, and peek operations and using these operations, we need to emulate the operations of the queue - enqueue and dequeue. Hence, queue q can be implemented in two methods (Both the methods use auxillary space complexity of O(n)):
1. By making enqueue operation costly:
enqueue(q, data): While stack1 is not empty: Push everything from stack1 to stack2. Push data to stack1 Push everything back to stack1.deQueue(q): If stack1 is empty then error else Pop an item from stack1 and return it2. By making the dequeue operation costly:
enqueue(q, data): Push data to stack1dequeue(q): If both stacks are empty then raise error. If stack2 is empty: While stack1 is not empty: push everything from stack1 to stack2. Pop the element from stack2 and return it.1. By making push operation costly:
push(s, data): Enqueue data to q2 Dequeue elements one by one from q1 and enqueue to q2. Swap the names of q1 and q2 pop(s): dequeue from q1 and return it.2. By making pop operation costly:
push(s,data): Enqueue data to q1pop(s): Step1: Dequeue every elements except the last element from q1 and enqueue to q2. Step2: Dequeue the last item of q1, the dequeued item is stored in result variable. Step3: Swap the names of q1 and q2 (for getting updated data after dequeue) Step4: Return the result.An array data structure is a data structure that is used to store data in a way that is efficient and easy to access. It is similar to a list in that it stores data in a sequence. However, an array data structure differs from a list in that it can hold much more data than a list can. An array data structure is created by combining several arrays together. Each array is then given a unique identifier, and each array’s data is stored in the order in which they are created.
Array data structures are commonly used in databases and other computer systems to store large amounts of data efficiently. They are also useful for storing information that is frequently accessed, such as large amounts of text or images.
There are several different types of arrays:
A linked list can be thought of as a series of linked nodes (or items) that are connected by links (or paths). Each link represents an entry into the linked list, and each entry points to the next node in the sequence. The order in which nodes are added to the list is determined by the order in which they are created.
Following are some applications of linked list data structure:
Following are different types of linked lists:
1. Singly Linked List: A singly linked list is a data structure that is used to store multiple items. The items are linked together using the key. The key is used to identify the item and is usually a unique identifier. In a singly linked list, each item is stored in a separate node. The node can be a single object or it can be a collection of objects. When an item is added to the list, the node is updated and the new item is added to the end of the list. When an item is removed from the list, the node that contains the removed item is deleted and its place is taken by another node. The key of a singly linked list can be any type of data structure that can be used to identify an object. For example, it could be an integer, a string, or even another singly linked list. Singly-linked lists are useful for storing many different types of data. For example, they are commonly used to store lists of items such as grocery lists or patient records. They are also useful for storing data that is time sensitive such as stock market prices or flight schedules.
2. Doubly Linked List: A doubly linked list is a data structure that allows for two-way data access such that each node in the list points to the next node in the list and also points back to its previous node. In a doubly linked list, each node can be accessed by its address, and the contents of the node can be accessed by its index. It's ideal for applications that need to access large amounts of data in a fast manner. A disadvantage of a doubly linked list is that it is more difficult to maintain than a single-linked list. In addition, it is more difficult to add and remove nodes than in a single-linked list.
3. Circular Linked List: A circular linked list is a unidirectional linked list where each node points to its next node and the last node points back to the first node, which makes it circular.
4. Doubly Circular Linked List: A doubly circular linked list is a linked list where each node points to its next node and its previous node and the last node points back to the first node and first node’s previous points to the last node.
5. Header List: A list that contains the header node at the beginning of the list, is called the header-linked list. This is helpful in calculating some repetitive operations like the number of elements in the list etc.
| Arrays | Linked Lists |
|---|---|
| An array is a collection of data elements of the same type. | A linked list is a collection of entities known as nodes. The node is divided into two sections: data and address. |
| It keeps the data elements in a single memory. | It stores elements at random, or anywhere in the memory. |
| The memory size of an array is fixed and cannot be changed during runtime. | The memory size of a linked list is allocated during runtime. |
| An array's elements are not dependent on one another. | Linked List elements are dependent on one another. |
| It is easier and faster to access an element in an array. | In the linked list, it takes time to access an element. |
| Memory utilization is ineffective in the case of an array. | Memory utilization is effective in the case of linked lists. |
| Operations like insertion and deletion take longer time in an array. | Operations like insertion and deletion are faster in the linked list. |
Asymptotic analysis of an algorithm defines the run-time performance as per its mathematical boundations. Asymptotic analysis helps us articulate the best case(Omega Notation, Ω), average case(Theta Notation, θ), and worst case(Big Oh Notation, Ο) performance of an algorithm.
Hashmap is a data structure that uses an implementation of a hash table data structure which allows access to data in constant time (O(1)) complexity if you have the key.
The time complexity is O(1) assuming that the hash function used in the hash map distributes elements uniformly among the buckets.
A binary tree is a data structure that is used to organize data in a way that allows for efficient retrieval and manipulation. It is a data structure that uses two nodes, called leaves and nodes, to represent the data. The leaves represent the data and the nodes represent the relationships between the leaves. Each node has two children, called siblings, and each child has one parent. The parent is the node that is closest to the root of the tree. When a node is deleted from the tree, it is deleted from both its child and its parent.
Following are some applications for binary tree data structure:
A binary search tree is a data structure that stores items in sorted order. In a binary search tree, each node stores a key and a value. The key is used to access the item and the value is used to determine whether the item is present or not. The key can be any type of value such as an integer, floating point number, character string, or even a combination of these types. The value can be any type of items such as an integer, floating point number, character string, or even a combination of these types. When a node is added to the tree, its key is used to access the item stored at that node. When a node is removed from the tree, its key is used to access the item stored at that node.
A binary search tree is a special type of binary tree that has a specific order of elements in it. It has three basic qualities:
Following are some applications for binary tree data structure:
Tree traversal is the process of visiting all the nodes of a tree. Since the root (head) is the first node and all nodes are connected via edges (or links) we always start with that node. There are three ways which we use to traverse a tree −
1. Inorder Traversal:
// Print inorder traversal of given tree. void printInorderTraversal(Node root) < if (root == null) return; //first traverse to the left subtree printInorderTraversal(root.left); //then print the data of node System.out.print(root.data + " "); //then traverse to the right subtree printInorderTraversal(root.right); >
2. Preorder Traversal:
// Print preorder traversal of given tree. void printPreorderTraversal(Node root) < if (root == null) return; //first print the data of node System.out.print(root.data + " "); //then traverse to the left subtree printPreorderTraversal(root.left); //then traverse to the right subtree printPreorderTraversal(root.right); >
3. Postorder Traversal:
// Print postorder traversal of given tree. void printPostorderTraversal(Node root) < if (root == null) return; //first traverse to the left subtree printPostorderTraversal(root.left); //then traverse to the right subtree printPostorderTraversal(root.right); //then print the data of node System.out.print(root.data + " "); >Consider the following tree as an example, then:
A deque can be thought of as an array of items, but with one important difference: Instead of pushing and popping items off the end to make room, deques are designed to allow items to be inserted at either end. This property makes deques well-suited for performing tasks such as keeping track of inventory, scheduling tasks, or handling large amounts of data.
There are two types of deque:
Following are some real-time applications for deque data structure:
Following are the key operations available deque:
Priority Queue is an abstract data type that is similar to a queue in that each element is assigned a priority value. The order in which elements in a priority queue are served is determined by their priority (i.e., the order in which they are removed). If the elements have the same priority, they are served in the order they appear in the queue.
Following are some real-time applications for priority queue:
The following table contains an asymptotic analysis of different implementations of a priority queue:
| Operations | peek | insert | delete |
|---|---|---|---|
| Linked List | O(1) | O(n) | O(1) |
| Binary Heap | O(1) | O(log n) | O(log n) |
| Binary Search Tree | O(1) | O(log n) | O(log n) |
A graph is a type of non-linear data structure made up of nodes and edges. The nodes are also known as vertices, and edges are lines or arcs that connect any two nodes in the graph.
The following are the two most common graph representations:
1. Adjacency Matrix: Adjacency Matrix is a two-dimensional array with the dimensions V x V, where V is the number of vertices in a graph. Representation is simpler to implement and adhere to. It takes O(1) time to remove an edge. Queries such as whether there is an edge from vertex 'u' to vertex 'v' are efficient and can be completed in O(1).
One of the cons of this representation is that even if the graph is sparse (has fewer edges), it takes up the same amount of space. Adding a vertex takes O(V^2). It also takes O(V) time to compute all of a vertex's neighbours, which is not very efficient.
2. Adjacency List: In this method, each Node holds a list of Nodes that are directly connected to that vertex. Each node at the end of the list is connected with null values to indicate that it is the last node in the list. This saves space O(|V|+|E|). In the worst-case scenario, a graph can have C(V, 2) edges, consuming O(V^2) space. It is simpler to add a vertex. It takes the least amount of time to compute all of a vertex's neighbours.
One of the cons of this representation is that queries such as "is there an edge from vertex u to vertex v?" are inefficient and take O (V) in the worst case.
| Breadth First Search (BFS) | Depth First Search (DFS) |
|---|---|
| It stands for “Breadth First Search” | It stands for “Depth First Search” |
| BFS (Breadth First Search) finds the shortest path using the Queue data structure. | DFS (Depth First Search) finds the shortest path using the Stack data structure. |
| We walk through all nodes on the same level before passing to the next level in BFS. | DFS begins at the root node and proceeds as far as possible through the nodes until we reach the node with no unvisited nearby nodes. |
| When compared to DFS, BFS is slower. | When compared to BFS, DFS is faster. |
| BFS performs better when the target is close to the source. | DFS performs better when the target is far from the source. |
| BFS necessitates more memory. | DFS necessitates less memory. |
| Nodes that have been traversed multiple times are removed from the queue. | When there are no more nodes to visit, the visited nodes are added to the stack and then removed. |
| Backtracking is not an option in BFS. | The DFS algorithm is a recursive algorithm that employs the concept of backtracking. |
| It is based on the FIFO principle (First In First Out). | It is based on the LIFO principle (Last In First Out). |
AVL trees are height balancing binary search trees named after their inventors Adelson, Velski, and Landis. The AVL tree compares the heights of the left and right subtrees and ensures that the difference is less than one. This distinction is known as the Balance Factor.
BalanceFactor = height(left-subtree) − height(right-subtree)
We can perform the following two operations on AVL tree:
An AVL tree can balance itself by performing the four rotations listed below:
Following are some real-time applications for AVL tree data structure:
The B Tree is a type of m-way tree that is commonly used for disc access. A B-Tree with order m can only have m-1 keys and m children. One of the primary reasons for using a B tree is its ability to store a large number of keys in a single node as well as large key values while keeping the tree's height relatively small.
A B-tree of order 4 is shown below in the image:
Following are the key properties of a B-tree data structure:
Following are real-time applications of a B-Tree data structure:
A segment Tree is a binary tree that is used to store intervals or segments. The Segment Tree is made up of nodes that represent intervals. Segment Tree is used when there are multiple range queries on an array and changes to array elements.
The segment tree of array A[7] will look like this:
Following are key operations performed on the Segment tree data structure:
Following are real-time applications for Segment Tree:
The word "Trie" is an abbreviation for "retrieval." Trie is a data structure that stores a set of strings as a sorted tree. Each node has the same number of pointers as the number of alphabet characters. It can look up a word in the dictionary by using its prefix. Assuming that all strings are formed from the letters 'a' to 'z' in the English alphabet, each trie node can have a maximum of 26 points.
Trie is also referred to as the digital tree or the prefix tree. The key to which a node is connected is determined by its position in the Trie. Trie allows us to insert and find strings in O(L) time, where L is the length of a single word. This is clearly faster than BST. Because of how it is implemented, this is also faster than Hashing. There is no need to compute a hash function. There is no need to handle collisions (like we do in open addressing and separate chaining)
Another benefit of Trie is that we can easily print all words in alphabetical order, which is not easy with hashing. Trie can also perform prefix search (or auto-complete) efficiently.
The main disadvantage of tries is that they require a large amount of memory to store the strings. We have an excessive number of node pointers for each node
Following are some real-time applications for Trie data structure:
Red Black Trees are a type of self-balancing binary search tree. Rudolf Bayer invented it in 1972 and dubbed it "symmetric binary B-trees."
A red-black tree is a Binary tree in which each node has a colour attribute, either red or black. By comparing the node colours on any simple path from the root to a leaf, red-black trees ensure that no path is more than twice as long as any other, ensuring that the tree is generally balanced.
Red-black trees are similar to binary trees in that they both store their data in two's complementary binary formats. However, red-black trees have one important advantage over binary trees: they are faster to access. Because red-black trees are so fast to access, they are often used to store large amounts of data.
Red-black trees can be used to store any type of data that can be represented as a set of values.
Every Red-Black Tree Obeys the Following Rules:
Following are some real-time applications for the Red-Black Tree data structure:
LRU cache or Least Recently Used cache allows quick identification of an element that hasn’t been put to use for the longest time by organizing items in order of use. In order to achieve this, two data structures are used:
Heap is a special tree-based non-linear data structure in which the tree is a complete binary tree. A binary tree is said to be complete if all levels are completely filled except possibly the last level and the last level has all elements as left as possible. Heaps are of two types:
#include using namespace std; class Solution public: //function that takes an array and its size as arguments int removeDuplicates(int a[],int n)< int index=0; for(int i=1;iif (a[i]!=a[index]) < //change index index++; //swap next line a[index]=a[i]; > > return index+1; > >; int main() < int T; //taking the number of test cases from user cin>>T; //running the loop for all test cases while(T--) < int N; //taking size input from user cin>>N; int a[N]; //taking array input from user for(int i=0;i>a[i]; > Solution ob; //calling the removeDuplicates in the Solution class int n = ob.removeDuplicates(a,N); //printing the array after removing duplicates for(int i=0;i" "; cout > // Tree Node struct Node < int data; Node* left; Node* right; >; //Function to store the zigzag order traversal of a tree in a list. vector zigZagTraversal(Node* root) < //creating two stacks for level traversals in both order stackst1; stack st2; //vector to store the zigzag traversal vector result; //Initialize the first stack with the root element st1.push(root); //Iterate until either of the stack is not empty while(!st1.empty() || !st2.empty())< //iterate until the first stack is not empty while(!st1.empty())< Node* temp=st1.top(); st1.pop(); result.push_back(temp->data); if(temp->left) st2.push(temp->left); if(temp->right) st2.push(temp->right); > //Iterate until the second stack is not empty while(!st2.empty())< Node* temp=st2.top(); st2.pop(); result.push_back(temp->data); if(temp->right) st1.push(temp->right); if(temp->left) st1.push(temp->left); > > return result; >//structure of the linked list struct Node < int data; Node *left; Node *right; >//function take the head of the linked list as a parameter void sortList(Node *head) < //if linked list is empty then return back if(head==NULL) return; else < Node *temp=head; Node *temp1=head; //to store count of 0s, 1s, and 2s int count0=0,count1=0,count2=0; //calculating the count of 0s, 1s, and 2s while(temp!=NULL) < if(temp->data==0) count0++; else if(temp->data==1) count1++; else count2++; temp=temp->next; > //iterating over count of 0s and filling the linked list while(count0!=0) < temp1->data=0; temp1=temp1->next; count0--; > //iterating over count of 1s and filling the linked list while(count1!=0) < temp1->data=1; temp1=temp1->next; count1--; > //iterating over count of 2s and filling the linked list while(count2!=0) < temp1->data=2; temp1=temp1->next; count2--; > > >From the above representation, we can see that there exists a cycle: 1→2→3→1
//function to run dfs for a given node in the graph int dfs(int v,vector adj[],vector &visited,vector &rec,int i,int parent) < int ans=0; visited[i]=1; rec[i]=1; for(auto x : adj[i])< if(x!=parent) < if(rec[x]) return 1; ans=dfs(v,adj,visited,rec,x,i); if(ans) return 1; >> rec[i]=0; return 0; > // Function to detect cycle in an undirected graph. // it takes adjacency list representation as an argument bool isCycle(int v, vector adj[]) < vectorvisited(v,0),rec(v,0); int ans=0; for(int i=0;i return 0; > int prec(char c) < if (c == '^') return 3; else if (c == '/' || c == '*') return 2; else if (c == '+' || c == '-') return 1; else return -1; >public: // Function to convert an infix expression to a postfix expression. string infixToPostfix(string s) < stackst; // For stack operations, we are using C++ built in stack string result; for (int i = 0; i < s.length(); i++) < char c = s[i]; // If the scanned character is // an operand, add it to the output string. if ((c >= 'a' && c = 'A' && c = '0' && c st.pop(); > // If an operator is scanned else < while (!st.empty() && prec(s[i]) > st.push(c); > > // Pop all the remaining elements from the stack while (!st.empty()) < result += st.top(); st.pop(); >return result; >//function to find maximum in each subarray using sliding window approach vector max_of_subarrays(vector arr, int n, int k) < int i=0,j=0; dequedq; dq.push_front(i++); while(i vector ans; while(i=dq.front()) < dq.pop_front(); >j++; while(!dq.empty()&&arr[dq.back()] <=arr[i]) dq.pop_back(); dq.push_back(i++); >ans.push_back(arr[dq.front()]); return ans; > Input:
Output: 3 4 5 6 7 9 12
//Function to return a list of integers denoting the node //values of both the BST in a sorted order. void inorder(Node*root,vector&v)< if(root==NULL) return; inorder(root->left,v); v.push_back(root->data); inorder(root->right,v); > vector merge(vectorv1,vectorv2)< vectorv; int n1=v1.size(),n2=v2.size(),i=0,j=0; while(iv2[j]) < v.push_back(v2[j]); j++; >else < v.push_back(v1[i]); i++; >> while(i while(j return v; > vector merge(Node *root1, Node *root2) < vectorv1,v2; inorder(root1,v1); inorder(root2,v2); return merge(v1,v2); > Input:
Output:
vector> uniqueRow(int M[MAX][MAX],int row,int col) < set> st; vector> v; for(int i=0; i v1; for(int j=0; j if(st.count(v1) == 0) < v.push_back(v1); st.insert(v1); >> return v; >int numSubarrayProductLessThanK(vector& nums, int k) < int ans=0; int pdt=1; int left=0,right=0; while(right<=nums.size()-1)< pdt*=nums[right]; while(pdt>=k and left if(right-left>=0) ans+=right-left+1;//since on adding a new element new subarrays formed is r-i+1; right++; > return ans; > The three increasing elements of the given arrays are 10, 11, and 12, which form a three-size subsequence with the highest product.
vector maxProductSubsequence(int *a , int n) < sets; long long largestOnLeft[n]; for(int i=0;i it--; largestOnLeft[i]=*it; > int m=0; long long p=INT_MIN; vector result(3); result[0]=-1; for(int i=n-1;i>=0;i--) < if(a[i]>=m) < m=a[i];>else < if(largestOnLeft[i] !=-1) < if(largestOnLeft[i]*a[i]*m >p) < p=largestOnLeft[i]*a[i]*m; result[0]=largestOnLeft[i]; result[1]=a[i]; result[2]=m; >> > > return v; >
class Solution< public: Node* partition(Node *l, Node *h)< //Your code goes here Node*temp = h; Node*tt = l; Node*first = l; while(tt != h)< if(tt->data data)< swap(first->data, tt->data); first = first->next; > tt = tt -> next; > swap(first-> data, h->data); return first; > >; void _quickSort(struct Node* l, struct Node *h) < if (h != NULL && l != h && l != h->next) < Solution ob; struct Node *p = ob.partition(l, h); _quickSort(l, p->prev); _quickSort(p->next, h); > > void quickSort(struct Node *head)
Input: 100
Output: 100-> NULL
14 -> 1 -> 20 -> NULL
class Solution < public: //Function to connect nodes at the same level. void connect(Node *p) < map> m; queue q; queue l; q.push(p); l.push(0); while(!q.empty()) < Node *temp=q.front(); int level=l.front(); q.pop(); l.pop(); m[level].push_back(temp); if(temp->left!=NULL) < q.push(temp->left); l.push(level+1); > if(temp->right!=NULL) < q.push(temp->right); l.push(level+1); > > for(map > ::iterator it=m.begin();it!=m.end();it++) < vectortemp1=it->second; for(int i=0;inextRight=temp1[i+1]; > temp1[temp1.size()-1]->nextRight=NULL; > > >; Input: N = 3
Output: 5 for N = 3, there are 5 possible BSTs:
class Solution < public: //function to calculate binomial coefficient C(n,k) long long int binomialCoefficient(long long int n, long long int k) < long long int res = 1; if (k >n - k) k = n - k; for (long long int i = 0; i < k; ++i) < res *= (n - i); res /= (i + 1); >return res; > //function to calculate Nth Catalan Number long long int catalanNumber(long long in n) < // Calculate value of 2nCn long long int C = binomialCoefficient(2*n, n); // return 2nCn/(n+1) return C/(n+1); >//Function to return the total number of possible unique BST. long long int numOfUniqueBinarySearchTrees(int n) < // find nth catalan number long long int countOfUniqueBinarySearchTrees = catalanNumber(n); // return nth catalan number return countOfUniqueBinarySearchTrees; >>;class LRUCache < private: class node_t < public: int key; int value; node_t * next; node_t * prev; >; int cap; node_t head; unordered_map tbl; void remove_node(node_t * node) < node->next->prev = node->prev; node->prev->next = node->next; > void add_node(node_t * node) < node->next = head.next; node->prev = &head; head.next = node; node->next->prev = node; > public: //Constructor for initializing the cache capacity with the given value. LRUCache(int cap): cap(cap) < // code here head.prev = &head; head.next = &head; >//Function to return value corresponding to the key. int get(int key) < // your code here unordered_map::iterator it = tbl.find(key); if(it==tbl.end()) return -1; remove_node(it->second); add_node(it->second); return it->second->value; > //Function for storing key-value pair. void set(int key, int value) < // your code here unordered_map::iterator it = tbl.find(key); if(it!=tbl.end()) < remove_node(it->second); add_node(it->second); it->second->value = value; > else < node_t * node = new node_t; node->key = key; node->value = value; add_node(node); tbl[key] = node; if(tbl.size()>cap) < auto * old_node = head.prev; tbl.erase(old_node->key); remove_node(old_node); delete old_node; > > > >;class Solution < public: bool checkDuplicatesWithinRange(vectorarr, int range) < // Creating an empty hashset unordered_setmyset; // Traversing the input array for (int i = 0; i < arr.size(); i++) < // If already present in hashset, then we found a duplicate within range distance if (myset.find(arr[i]) != myset.end()) return true; // Add this item to hashset myset.insert(arr[i]); // Remove the range+1 distant item from the hashset if (i >= range) myset.erase(arr[i-range]); > return false; > >;public class Node
int heightOfBinaryTree(Node node) < if (node == null) return 0; // If node is null then height is 0 for that node. else < // compute the height of each subtree int leftHeight = heightOfBinaryTree(node.left); int rightHeight = heightOfBinaryTree(node.right); //use the larger among the left and right height and plus 1 (for the root) return Math.max(leftHeight, rightHeight) + 1; >>
int countNodes(Node root) < int count = 1; //Root itself should be counted if (root ==null) return 0; else < count += countNodes(root.left); count += countNodes(root.right); return count; > > import java.util.HashMap; //to store a Binary Tree node class Node < int data; Node left = null, right = null; Node(int data) < this.data = data; >> public class InterviewBit < // traverse nodes in pre-order way public static void leftViewUtil(Node root, int level, HashMapmap) < if (root == null) < return; >// if you are visiting the level for the first time // insert the current node and level info to the map if (!map.containsKey(level)) < map.put(level, root.data); >leftViewUtil(root.left, level + 1, map); leftViewUtil(root.right, level + 1, map); > // to print left view of binary tree public static void leftView(Node root) < // create an empty HashMap to store first node of each level HashMapmap = new HashMap<>(); // traverse the tree and find out the first nodes of each level leftViewUtil(root, 1, map); // iterate through the HashMap and print the left view for (int i = 0; i > public static void main(String[] args) < Node root = new Node(4); root.left = new Node(2); root.right = new Node(6); root.left.left = new Node(1); root.left.left = new Node(3); root.right.left = new Node(5); root.right.right = new Node(7); root.right.left.left = new Node(9); leftView(root); >>
class InterviewBit < public int numberOfIslands(char[][] grid) < if(grid==null || grid.length==0||grid[0].length==0) return 0; int m = grid.length; int n = grid[0].length; int count=0; for(int i=0; i> > return count; > public void mergeIslands(char[][] grid, int i, int j)< int m=grid.length; int n=grid[0].length; if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1') return; grid[i][j]='X'; mergeIslands(grid, i-1, j); mergeIslands(grid, i+1, j); mergeIslands(grid, i, j-1); mergeIslands(grid, i, j+1); > >// V - total vertices // visited - boolean array to keep track of visited nodes // graph - adjacency list. // Main Topological Sort Function. void topologicalSort() < Stackstack = new Stack(); // Mark all the vertices as not visited boolean visited[] = new boolean[V]; for (int j = 0; j < V; j++)< visited[j] = false; >// Call the util function starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, stack); // Print contents of stack ->result of topological sort while (stack.empty() == false) System.out.print(stack.pop() + " "); > // A helper function used by topologicalSort void topologicalSortUtil(int v, boolean visited[], Stack stack) < // Mark the current node as visited. visited[v] = true; Integer i; // Recur for all the vertices adjacent to the current vertex Iteratorit = graph.get(v).iterator(); while (it.hasNext()) < i = it.next(); if (!visited[i]) topologicalSortUtil(i, visited, stack); >// Push current vertex to stack that saves result stack.push(new Integer(v)); >In this post, we covered the most important and frequently asked Data Structures interview questions. We've also included some pointers and tricks to help you prepare for the interview. When preparing for the product-based companies interview, keep in mind that the Data Structures interview is a critical component of the process. It is critical that you are well prepared for the interview because it will determine whether or not you are hired. As a result, it is critical to begin planning as soon as possible.
