Menu Close

Data structures interview questions

What is data?

  • Data is a set of values of qualitative or quantitative variables about one or more persons or objects.
  • Data is any set of characters that is gathered and translated for some purpose, usually analysis

What is information?

  • A quantitative measure data is called information.
  • The results of processed data(such as formatting and printing) by giving the input depends on requirement is called information.

What is Algorithm?

  • Algorithm is a set of rules used to specify how a work is to be executed upon, in order to get the expected results.
  • An algorithm is a finite list of instructions, most often used in solving problems or performing tasks.

What are the characteristics of Algorithm?

  1. Unambiguous: Algorithm should be clear. Each of its steps and their inputs/outputs should be clear.
  2. Input: An algorithm should have well-defined inputs.
  3. Output: An algorithm should produce well-defined outputs.
  4. Finiteness: A well defined algorithm terminates after a finite number of steps.
  5. Independent: These step-by-step directions should be independent of any programming code.

What is Abstract Data type?

  • Abstract Data type (ADT) is for objects whose behavior is defined by a set of functions.
  • ADT only mentions what operations are to be performed but not how these operations will be implemented.
  • Function prototype is called ADT of that function.

What is Data structure?

  • A data structure is a particular way of organizing data in a computer so that it can be used effectively.
  • Data structures have wide scope of usage in Computer Science, Data analytics and Software Engineering.

What is Flowchart?

  • A diagrammatic representation of an algorithm.
  • It is using different types of boxes and symbols.
  • The operation to be performed is written on the box.
  • All symbols are interconnected by arrows to indicate the flow of information and processing.

What is time complexity?

  • Time consumed by an algorithm in order to perform the given task.
  • The amount of time taken by programmer to design a problem solution in the form of algorithm.
  • The time complexity of the program is the amount of time taken by system to solve a problem.
  • Mathematically expressed as,
    • T(P) = C + TP(I)
    • Where C is compile time
    • TP(I) is the execution time.

What is space complexity?

  • The amount of memory required in order to complete the task.
  • Space complexity components are
    • Instruction space
    • Data space
    • Stack space.

What is Big-oh notation?

  • Big-oh notation is represented by symbol ‘O’.
  • It is a method that defines the upper bound of algorithm’s running time.
  • Using this notation, user can calculate the longest time taken by algorithm.

What is linear data structure?

  • A data structure in which the elements are connected one to another.
  • Array, Stack, Queue and Linked Lists are examples of Linear data structures.

What is Stack?

  • A stack is a linear data structure that stores a set of elements in a sequential manner.
  • In stack new elements can be inserted and existing elements are deleted from the same end called “TOP”.

Write the functionality of Stack?

  • Push(): Insert an element into Stack
  • Pop(): Remove element from Stack
  • Traverse(): Display list of stack elements
  • isEmpty(): Check the stack is empty or not
  • isFull(): Check the stack is Full or not
  • Peek(): Returns the top element but not remove.

What are the applications of Stack?

  1. Infix expression evaluation
  2. Towers of Hanoi problem
  3. DFS graph traversal

What is recursion?

  • Function calling itself is called recursion.
  • It is the application of Stack.
  • Recursion function execution follows LIFO flow.

What is Queue?

  • Queue is a linear data structure.
  • A queue is an ordered collection of items in which new items inserted from the REAR and existing items delete from FRONT.
  • FRONT location is fixed in linear queue.

Define Linked List?

  • Linked list is a linear data structure used to store similar data in memory.
  • The elements in liked list are not use adjacent memory locations.
  • Linked list is a collection of elements called Nodes.
  • Every node has two fields Data and Link.

What is circular single linked list?

  • A circular single linked list in which the link filed of last node points to the first node of the same list.
  • In circular linked list, there is no NULL link to indicate the end of list.

What is double linked list?

  • It is a linear data structure.
  • In a double linked list, every list of element has both a reference to the next element and reference to the previous element.
  • Double linked list is bi-directional.
  • We can traverse the data in both the directions hence we can perform operations bit easy compare to single linked list.

What is circular queue?

  • Circular queue is introduced to overcome the drawback of Linear queue.
  • In linear queue, all elements need to move in forward direction after deleting an element because the FRONT pointer is fixed.
  • In Circular queue, both FRONT and REAR pointer move in clockwise direction to perform queue operations easily.

What is Towers of Hanoi problem?

  • “Towers of Hanoi” is a classical example of recursion problem.
  • In this problem, there are three towers named as source, auxiliary and destination.
  • The source tower consists of 2 or more disks of different sizes where each disk rest on the one just large than it.
  • The task is to move all the disks from source to destination without violating rules.
    • At a time, only one disk may be moved.
    • Larger disk should not be placed on top of smaller disk.
    • For the purpose of intermediate storage of disks, only auxiliary tower should be used.

What is Tree?

  • Tree is a non-linear data structure represented in a hierarchical manner.
  • A tree can be said to be a binary tree if it contains at most two children.
  • It contains a finite set of elements called Nodes which are connected each other using finite set of lines called Branches.

What is hash table?

  • Hash table is a data structure of fixed size that is used to store the dictionary pairs.
  • Hashing is a technique that makes use of a hash function for mapping pairs to the corresponding position in a hash table.

What is Graph?

  • A Graph defined as G=(V,E) where,
  • V is the set of elements called Nodes or Vertices or Points.
  • E is the set of Edges of the graph defined with a unique pair(U,V) of nodes.
  • Here (U, V) pair denotes that there is an edge from node U to node V.

What is directed and undirected graph?

  • A graph in a non-linear data structure.
  • A graph in which nodes are connected with edges.
  • If every edge is directed to node is called Directed Graph.
  • If every edge is undirected to node is called undirected Graph.

What is DFS?

  • Depth First Search is a Graph traversal in which we start from a given vertex V in the graph. We mark this vertex as visited. Now any of the unvisited vertexes adjacent to V is visited.
  • This process is continued until no new node can be visited.
  • Now we backtrack from the path to visit unvisited vertices if any left.
  • Stack is used to keep track of all nodes adjacent to a vertex.

What is BFS?

  • Breadth First Search is a Graph traversal in which we start with given vertex V and visit all the nodes adjacent to V from left to right.
  • Queue Data structure is used to keep track of all adjacent nodes.
  • The first node visited then whose successors are visited.

What is Minimal spanning tree?

  • A minimum spanning tree is a spanning tree which is not cyclic.
  • The weights with the edges and the total weight of the tree(the sum of weights) is at a minimum.

How prim’s algorithm works?

  • The node of the graph added to the tree at each point is the node which is adjacent to a node with minimum weight.
  • The arc of minimum weight becomes a tree arc connecting the new node of the tree.
  • When all the nodes of the graph have been added to the tree, a minimum spanning tree has been constructed for the Graph.

What is Expression tree?

  • Expression tree is a binary tree that is used to store and represent the arithmetic expressions.
  • It consists of leaf nodes and internal nodes.
  • The operands(constants or values) are represented as leaf nodes.
  • The operators represented as internal nodes.

What is adjacency list?

  • In adjacency list representation of a Graph, G=(V,E), each vertex of a graph represented by an adjacency list.
  • The adjacency list corresponding to vertex ‘I’ contains all vertices that are adjacent to ‘I’ in G.
  • In adjacency list representation, each adjacency list is maintained as a chain so it is called linked adjacency list representation.

What is Spanning tree?

  • A spanning tree for a connected, undirected graph, G=(V,E) is a sub graph of G that is an undirected tree and contains all vertices of G.
  • It should not create a cycle like Graph.

What are the algorithms used to find Minimum spanning tree?

  1. Prim’s algorithm
  2. Kruskal’s algorithm

What is sorting?

  • Sorting is a technique of organizing the data of arranging the records either in ascending order or descending order.
  • It is very easy and efficient to perform searching the data is stored in order.

What is Linear search?

  • A linear search is a sequential search.
  • It is a method for finding an element within the array or list.
  • It sequentially checks each element of the list with the element to be searched until a match is found.

What is Binary search?

  • Binary search compares the element to be searched with the mid location element of the array.
  • If the element is equal to mid location element, it returns the location as element found.
  • If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found.
  • If the search ends with the remaining half being empty, the target is not in the array.

What is Hash search?

  • Hash table is used in hash search algorithm.
  • Hash table with a specific size is used to store elements with index.
  • One of the most common approaches is to search for item into a value that is used to index into an indexed hash table.

What is AVL Tree?

  • Named after their inventor Adelson, Velskii & Landis.
  • AVL tree is a balanced binary search tree.
  • AVL tree uses rotations for balancing the nodes.
  • It uses balance factor to rotate the tree to balance.

What are the AVL rotations?


What is Red-Black Tree?

  • In computer science, a red–black tree is a kind of self-balancing binary search tree.
  • Each node stores an extra bit representing color, used to ensure that the tree remains approximately balanced during insertions and deletions.
  • The red black tree satisfies all the properties of the binary search tree but there are some additional properties which were added in a Red Black Tree.
  • The height of a Red-Black tree is O(Logn) where (n is the number of nodes in the tree).

What are the Rules of Red-Black Tree?

  1. Every node has a color either red or black.
  2. Root of tree is always black.
  3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
  4. Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

What is B tree?

  • B Tree is a specialized m-way tree that can be widely used for disk access.
  • A B-Tree of order m can have at most m-1 keys and m children.
  • One of the main reasons of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.

Explain the Rules of B-Tree?

  • Every node in a B-Tree contains at most m children.
  • Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
  • The root nodes must have at least 2 nodes.
  • All leaf nodes must be at the same level.
  • It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes.

What are B+ trees?

  • A B+ tree is an N-ary tree with a variable but often large number of children per node.
  • A B+ tree consists of a root, internal nodes and leaves.
  • The root may be either a leaf or a node with two or more children.
  • A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.