32 Advanced Data Structures Interview Questions (ANSWERED) To Smash Your Next Programming Interview

A normal tree has no restrictions on the number of children each node can have. A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.

There are three different types of binary trees:

• Full binary tree: Every node other than leaf nodes has 2 child nodes.
• Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
• Perfect binary tree: All nodes have two children and all leaves are at the same level.

Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize data hierarchically.

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data or key, and it may or may not have a child node. The first node of the tree is called the root. Leaves are the last nodes on a tree. They are nodes without children.

A stack is a recursive data structure, so it's:

• a stack is either empty or
• it consists of a top and the rest which is a stack by itself;

Arrays are:

• Finite (fixed-size) - An array is finite because it contains only limited number of elements.
• Order -All the elements are stored one by one , in contiguous location of computer memory in a linear order and fashion
• Homogenous - All the elements of an array are of same data types only and hence it is termed as collection of homogenous

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. Hash tables implement an associative array, which is indexed by arbitrary objects (keys). A hash table uses a hash function to compute an index, also called a hash value, into an array of buckets or slots, from which the desired value can be found.

A Heap is a special Tree-based data structure which is an almost complete tree that satisfies the heap property:

• in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
• In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

A common implementation of a heap is the binary heap, in which the tree is a binary tree.

A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority.

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

A graph is a common data structure that consists of a finite set of nodes (or vertices) and a set of edges connecting them. A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.

Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).

Linked lists are very useful when you need :

• to do a lot of insertions and removals, but not too much searching, on a list of arbitrary (unknown at compile-time) length.
• splitting and joining (bidirectionally-linked) lists is very efficient.
• You can also combine linked lists - e.g. tree structures can be implemented as "vertical" linked lists (parent/child relationships) connecting together horizontal linked lists (siblings).

Using an array based list for these purposes has severe limitations:

• Adding a new item means the array must be reallocated (or you must allocate more space than you need to allow for future growth and reduce the number of reallocations)
• Removing items leaves wasted space or requires a reallocation
• inserting items anywhere except the end involves (possibly reallocating and) copying lots of the data up one position

A dynamic array is an array with a big improvement: automatic resizing.

One limitation of arrays is that they're fixed size, meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

• A singly linked list

• A doubly linked list is a list that has two references, one to the next node and another to previous node.

• A multiply linked list - each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set(e.g., by name, by department, by date of birth, etc.).
• A circular linked list - where last node of the list points back to the first node (or the head) of the list.

Queue can be classified into following types:

• Simple Queue - is a linear data structure in which removal of elements is done in the same order they were inserted i.e., the element will be removed first which is inserted first.

• Circular Queue - is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called Ring Buffer. Circular queue avoids the wastage of space in a regular queue implementation using arrays.

• Priority Queue - is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value

• In case of max-priority queue, the element will be deleted first which has the largest priority value
• In case of min-priority queue the element will be deleted first which has the minimum priority value.
• De-queue (Double ended queue) - allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end.

• Input restricted deque - In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends.

• Output restricted deque - In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends.

A Binary Heap is a Binary Tree with following properties:

• It’s a complete tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
• A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

            10                      10
         /      \               /       \  
       20        100          15         30  
      /                      /  \        /  \
    30                     40    50    100   40

Binary search tree is a data structure that quickly allows to maintain a sorted list of numbers.

• It is called a binary tree because each tree node has maximum of two children.
• It is called a search tree because it can be used to search for the presence of a number in O(log n) time.

The properties that separates a binary search tree from a regular binary tree are:

• All nodes of left subtree are less than root node
• All nodes of right subtree are more than root node
• Both subtrees of each node are also BSTs i.e. they have the above two properties

• Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is O(n).
• Searching for a given value in the queue requires iterating until you find it. So search is O(n).
• Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is O(1).
• Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `O(1).

The space complexity of a datastructure indicates how much space it occupies in relation to the amount of elements it holds. For example a space complexity of O(1) would mean that the datastructure alway consumes constant space no matter how many elements you put in there. O(n) would mean that the space consumption grows linearly with the amount of elements in it.

A hashtable typically has a space complexity of O(n).

Graph:

• Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them
• Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph)
• Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices
• Could be directed or undirected (which would apply to all edges in the graph)

Tree:

• A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG))
• Vertices are more commonly called "nodes"
• Edges are directed and represent an "is child of" (or "is parent of") relationship
• Each node (except the root node) has exactly one parent (and zero or more children)
• Has exactly one "root" node (if the tree has at least one node), which is a node without a parent
• Has to be connected
• Is acyclic, meaning it has no cycles: "a cycle is a path AKA sequence of edges and vertices wherein a vertex is reachable from itself"
• Trees aren't a recursive data structure

Because they help manage your data in more a particular way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants.

Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections.

More practically you should:

• Use a queue when you want to get things out in the order that you put them in (FIFO)
• Use a stack when you want to get things out in the reverse order than you put them in (LIFO)
• Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists:

• In Array:
• insert() operation can be implemented by adding an item at end of array in O(1) time.
• getMax() operation can be implemented by linearly searching the highest priority item in array. This operation takes O(n) time.
• deleteMax() operation can be implemented by first linearly searching an item, then removing the item by moving all subsequent items one position back.

• In a Binary Heap:
• getMax() can be implemented in O(1) time,
• insert() can be implemented in O(log n) time and
• deleteMax() can also be implemented in O(log n) time.

This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node.

In an in-order traversal, first the left sub-tree is traversed, then the root is visited, and finally the right sub-tree is traversed.

One simple way of solving this problem is to start with an empty doubly linked list. While doing the in-order traversal of the binary tree, keep inserting each element output into the doubly linked list. But, if we look at the question carefully, the interviewer wants us to convert the binary tree to a doubly linked list in-place i.e. we should not create new nodes for the doubly linked list.

This problem can be solved recursively using a divide and conquer approach. Below is the algorithm specified.

• Start with the root node and solve left and right sub-trees recursively
• At each step, once left and right sub-trees have been processed:
  • fuse output of left subtree with root to make the intermediate result
  • fuse intermediate result (built in the previous step) with output from the right sub-tree to make the final result of the current recursive call

AVL trees are height balancing binary search tree. It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. This allows us to search for an element in the AVL tree in O(log n), where n is the number of elements in the tree.

The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N)) // BalanceFactor(N) belongs to the set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations:

• Left Rotation,
• Right Rotation,
• Left Right Rotation,
• Right Left Rotation.

A tree is said to be balanced only when all three conditions satisfy:

• The left and right subtrees height differ by at most one
• The left subtree is balanced
• The right subtree is balanced

Height-balancing requirement:

• A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1.
• A tree is height-balanced if all of its nodes are height-balanced.

In a balanced BST, the height of the tree is log n where n is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto n which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time O(n) that shall be avoided.

Balanced BST maintains h = O(log n) so all operations run in O(log n) time.

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of key, value pairs, such that each possible key appears at most once in the collection. Associative array can be implemented as:

• Hash table
• Self-balancing binary search tree
• Unbalanced binary search tree
• Association list

Hash tables are O(1) average and amortized time complexity case complexity, however it suffers from O(n) worst case time complexity (when you have only one bucket in the hash table, then the search complexity is O(n)). A hashtable typically has a space complexity of O(n).

Hash tables suffer from O(n) worst time complexity due to two reasons:

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time (for linked lists)
2. Once a hash table has passed its load balance - it has to rehash (create a new bigger table, and re-insert each element to the table).

However, it is said to be O(1) average and amortized case because:

1. It is very rare that many items will be hashed to the same key if you chose a good hash function and you don't have too big load balance.
2. The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)