The idea: you store the previous states of your work (which are limited to a specific number) in the memory in such an order that the last one appears first.
This can’t be done just by using arrays.
That is where the Stack comes in handy.
A real-life example of Stack could be a pile of books placed in a vertical order.
In order to get the book that’s somewhere in the middle, you will need to remove all the books placed on top of it.
This is how the LIFO (Last In First Out) method works.
Here’s an image of stack containing three data elements (1, 2 and 3), where 3 is at the top and will be removed first:Basic operations of stack:Push — Inserts an element at the topPop — Returns the top element after removing from the stackisEmpty — Returns true if the stack is emptyTop — Returns the top element without removing from the stackCommonly asked Stack interview questionsEvaluate postfix expression using a stackSort values in a stackCheck balanced parentheses in an expressionQueuesSimilar to Stack, Queue is another linear data structure that stores the element in a sequential manner.
The only significant difference between Stack and Queue is that instead of using the LIFO method, Queue implements the FIFO method, which is short for First in First Out.
A perfect real-life example of Queue: a line of people waiting at a ticket booth.
If a new person comes, they will join the line from the end, not from the start — and the person standing at the front will be the first to get the ticket and hence leave the line.
Here’s an image of Queue containing four data elements (1, 2, 3 and 4), where 1 is at the top and will be removed first:Basic operations of QueueEnqueue() — Inserts element to the end of the queueDequeue() — Removes an element from the start of the queueisEmpty() — Returns true if queue is emptyTop() — Returns the first element of the queueCommonly asked Queue interview questionsImplement stack using a queueReverse first k elements of a queueGenerate binary numbers from 1 to n using a queueLinked ListA linked list is another important linear data structure which might look similar to arrays at first but differs in memory allocation, internal structure and how basic operations of insertion and deletion are carried out.
A linked list is like a chain of nodes, where each node contains information like data and a pointer to the succeeding node in the chain.
There’s a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.
Linked lists are used to implement file systems, hash tables, and adjacency lists.
Here’s a visual representation of the internal structure of a linked list:Following are the types of linked lists:Singly Linked List (Unidirectional)Doubly Linked List (Bi-directional)Basic operations of Linked List:InsertAtEnd — Inserts given element at the end of the linked listInsertAtHead — Inserts given element at the start/head of the linked listDelete — Deletes given element from the linked listDeleteAtHead — Deletes first element of the linked listSearch — Returns the given element from a linked listisEmpty — Returns true if the linked list is emptyCommonly asked Linked List interview questionsReverse a linked listDetect loop in a linked listReturn Nth node from the end in a linked listRemove duplicates from a linked listGraphsA graph is a set of nodes that are connected to each other in the form of a network.
Nodes are also called vertices.
A pair(x,y) is called an edge, which indicates that vertex x is connected to vertex y.
An edge may contain weight/cost, showing how much cost is required to traverse from vertex x to y.
Types of Graphs:Undirected GraphDirected GraphIn a programming language, graphs can be represented using two forms:Adjacency MatrixAdjacency ListCommon graph traversing algorithms:Breadth First SearchDepth First SearchCommonly asked Graph interview questionsImplement Breadth and Depth First SearchCheck if a graph is a tree or notCount number of edges in a graphFind the shortest path between two verticesTreesA tree is a hierarchical data structure consisting of vertices (nodes) and edges that connect them.
Trees are similar to graphs, but the key point that differentiates a tree from the graph is that a cycle cannot exist in a tree.
Trees are extensively used in Artificial Intelligence and complex algorithms to provide an efficient storage mechanism for problem-solving.
Here’s an image of a simple tree, and basic terminologies used in tree data structure:The following are the types of trees:N-ary TreeBalanced TreeBinary TreeBinary Search TreeAVL TreeRed Black Tree2–3 TreeOut of the above, Binary Tree and Binary Search Tree are the most commonly used trees.
Commonly asked Tree interview questionsFind the height of a binary treeFind kth maximum value in a binary search treeFind nodes at “k” distance from the rootFind ancestors of a given node in a binary treeTrieTrie, which is also known as “Prefix Trees”, is a tree-like data structure which proves to be quite efficient for solving problems related to strings.
It provides fast retrieval, and is mostly used for searching words in a dictionary, providing auto suggestions in a search engine, and even for IP routing.
Here’s an illustration of how three words “top”, “thus”, and “their” are stored in Trie:The words are stored in the top to the bottom manner where green colored nodes “p”, “s” and “r” indicates the end of “top”, “thus”, and “their” respectively.
Commonly asked Trie interview questions:Count total number of words in TriePrint all words stored in TrieSort elements of an array using TrieForm words from a dictionary using TrieBuild a T9 dictionaryHash TableHashing is a process used to uniquely identify objects and store each object at some pre-calculated unique index called its “key.
” So, the object is stored in the form of a “key-value” pair, and the collection of such items is called a “dictionary.
” Each object can be searched using that key.
There are different data structures based on hashing, but the most commonly used data structure is the hash table.
Hash tables are generally implemented using arrays.
The performance of hashing data structure depends upon these three factors:Hash FunctionSize of the Hash TableCollision Handling MethodHere’s an illustration of how the hash is mapped in an array.
The index of this array is calculated through a Hash Function.
Commonly asked Hashing interview questionsFind symmetric pairs in an arrayTrace complete path of a journeyFind if an array is a subset of another arrayCheck if given arrays are disjointThe above are the top eight data structures that you should definitely know before walking into a coding interview.
If you are looking for resources on data structures for coding interviews, look at the interactive & challenge based courses: Data Structures for Coding Interviews (Python, Java, or JavaScript).
For more advanced questions, look at Coderust 3.
0: Faster Coding Interview Preparation with Interactive Challenges & Visualizations.
If you are preparing for a software engineering interviews, here’s a comprehensive roadmap to prepare for coding Interviews.
Good luck and happy learning! :).. More details