D ATA S T R U C T U R E S

• Data Structure(DS) is a way the information is organized in computer memory

• Types:
• Primary DS
Basic constants
Pointers
• Secondary DS
Linear DS => Array, Stack, Queues, Linked list
Non- linear DS => Trees, Graph
 APPLICATION OF DATA STRUCTURES
STACK:
• Stack is used in undo operations in word document
• Evaluation of expressions
• Used to implement queues, array etc.
QUEUE:
• Printing a document in printer.
• Priority queues are used in scheduling jobs based on priority
• Circular queues in round robin scheduling.
LINKED LIST:
• Website linked to one another
• Dynamic memory management
 APPLICATION OF DATA STRUCTURES
TREE:
• Used in File structure.(i.e.,) Directory traversal.
• Used in efficient searching using B+ tree index.
• Autocomplete feature based on prefixes.
• Tree data structure also is used in DBMS. child table will reference the parent
table
• BSP(Binary Space Partitioning) tree is used in 3D video games, collision
detection of robots.
GRAPH:
• Google maps: Uses GPS(Graph is used)
• Broadcasting in Network
• Social networking
 APPLICATION OF DATA STRUCTURES
ARRAY:
• Used in CPU scheduling. In CPU scheduling queues are used. Queues are
implemented by using arrays.
• Used in matrix operations
TRIE:
• Efficient information retrieval DS
Bloom filter:
• URL shortening
• Identify malicious URL
Google chrome uses bloom filter to identify malicious URL
• It is a space efficient DS used by google's bigtable, apache cassandra,
postgresql to increase the performance of db query operation
 IMPORTANT QUESTIONS
• How many stacks are required to implement a Queue
Two
Consider two stacks S1 and S2. Whenever elements are to be enqueued,
push those elements in S1. If we want to dequeue some elements, pop the
elements from S1 and push it into S2. Then dequeue required elements.
• Implement a queue using Linked List
Initially head and tail pointer points to first node of linked list. When element
is to be enqueued, insert in the first node and increment the tail pointer and so
on. Whenever new element is inserted, it is inserted in a node where tail
pointer points, and tail pointer incremented. If element is to be removed, it
should be removed in front and head pointer is incremented.
 IMPORTANT QUESTIONS
• Is it possible to implement array using a stack?
Yes
Consider two stacks S1 and S2. Here two pointers are used to the set of
input values. 1st pointer points to 1st element. 2nd pointer points to last
element.
Push the element pointed by 1st pointer in S1 and increment 1st pointer.
Push the element pointed by 2nd pointer in S2 and decrement 2nd pointer
and so on until all elements are accessed.
Then pop elements from S1 one by one and push into S2. Finally pop all
elements from S2.
 IMPORTANT QUESTIONS
• Array and Linked list –Accessing, Dynamic size, Ease of insertion/deletion in linked list
• Stack and array – Difference is Accessing and different data items in stack
• Structure and array – Difference
• When is binary search algorithm best applied? When elements are sorted
• The height of a BST is given as h. Consider the height of the tree as the no. of edges in the
longest path from root to the leaf. The maximum no. of nodes possible in the tree is? 2h+1 -1
• How do you find middle of a linked list?
• How do you find nth node from end of a linked list?
• How do you find nth node from end of a linked list?
• How do you find the reverse of a single linked list?
• How do you find the number of times a value occur in linked list?
• How do you find the intersection point of two linked list?
• How do you remove duplicates in linked list?
SET:
• It is a DS which is unordered collection of values
• It does not display the duplicate values.
HASHING:
• It is a DS which is used for Storing and retrieving of data quickly from the hash
table.
• Hash function is used to implement it.
 IMPORTANT QUESTIONS
• Given a Binary Search Tree (BST), print its values in ascending order
 Perform In order traversal
• Is it possible to find a loop in a Linked list ?
Yes
• What is the type of the algorithm used in solving the 8 Queens problem?
Backtracking
• Translate infix expression into its equivalent post fix expression: (AB)*(D/E)
(AB)*(D/E) = [AB]*[DE/] = ABDE/*
• What are priority queues?
It is a collection of elements such that each element has been assigned a priority when it is
inserted in queue.
De-queue is performed based on the priority of elements.
• Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing priorities.
• TREE:
• Non linear DS which have hierarchical relationship with data items
• Each node have any number of child.
• Full binary tree: Every non-leaf node have exactly 2 children and all leaf node are on same level
• Complete binary tree: Every non-leaf node have exactly 2 children and all leaf node are on
same level
• Extended binary tree: conversion of binary tree into complete binary tree
BINARY TREE:
• It is a tree in which has either empty nodes or has exactly two children
• BINARY SEARCH TREE:
• Value of left child of node is smaller
• Value of right child of node is larger
 IMPORTANT
Define preorder traversal
QUESTIONS
i)Process the root node
ii)Process the left subtree
iii)Process the right subtree
Define postorder traversal
i)Process the left subtree
ii)Process the right subtree
iii)Process the root node
Define in order traversal
i)Process the left subtree
ii)Process the root node
iii)Process the right subtree
Define level order traversal
Traverse the tree level by level
 IMPORTANT QUESTIONS
• A linear list of elements in which deletion can be done from one end (front) and
insertion can take place only at the other end (rear) is known as a ? Queue
• What is mean by dequeue?
double ended queue.
Insertion and Deletion can be performed at both ends
• The data structure required for Depth First Search on a graph is? Stack
• The data structure required for Breadth First Search on a graph is? Queue
• In linked list implementation of a queue, where does a new element be
inserted? At the tail of linked list
• In linked list implementation of a queue, front and rear pointers are tracked.
Which of these pointers will change during an insertion into a NONEMPTY
queue? Rear pointer will be changed
 IMPORTANT QUESTIONS
• Every full binary tree is also a complete binary tree
• In a full binary tree, every internal node has exactly two children. A full binary tree
with 2n+1 nodes contains n internal nodes
• The no of external nodes in a full binary tree with n internal nodes is? n+1
• Convert Infix to postfix conversion. (A+B) * (C-D) +1 => AB+CD-1+*
• In full binary search tree every internal node has exactly two children. If there are 100 leaf
nodes in the tree, how many internal nodes are there in the tree? 99
• Suppose a complete binary tree has height h>0. The minimum no of leaf nodes possible in
term of h is? 2h -1
• The height of a binary tree is the maximum number of edges in any root to leaf
path. The maximum number of nodes in a binary tree of height h is: 2h+1 -1
• How do you print nodes at k distance from the root?
• How do you find the size of the tree(i.e.,) No. of nodes in a tree?
• How do you find the mirror image of the tree?
• How do you find the maximum depth of the tree?
 IMPORTANT QUESTIONS
• In which data structure, elements can be added or removed at either end, but not
in the middle? dequeue
• Which one is faster? A binary search of an ordered set of elements or a
sequential search ?
• A variant of the linked list in which none of the node contains NULL pointer is?
Drawbacks of linked list?
• The linked list pointers do not provide an efficient way to search an item in the
linked list
• Linked lists are not suitable to for the implementation of Binary search
• In worst case, the number of comparison need to search a singly linked list of
length n for a given element is O(n)
TIME COMPLEXITY OF SORTING ALGORITHMS

Algorithm Best case Average case Worst case

Bubble sort O(n) O(n^2) O(n^2)
Insertion sort O(n) O(n^2) O(n^2)
Selection sort O(n^2) O(n^2) O(n^2)
Merge sort O(nlogn) O(nlogn) O(nlogn)
Quick sort O(nlogn) O(nlogn) O(n^2)
Heap sort O(nlogn) O(nlogn) O(nlogn)
• A sorting technique is called stable if it maintains the relative order of
occurrence of non-distinct elements
• Stable sorting algorithm? Merge sort algorithm, Radix sort
• Which sorting does not performs comparison? Counting sort, Radix sort
• For merging two sorted lists of size m and n into sorted list of size m+n, we
require comparisons of O(m+n)
• Refer
• Careerride.com
• Carrercup.com
• Careerarm.com
• Geeksforgeeks.org
for more interview questions