Data Structures and Algorithms

Data structures and algorithms are the foundation of software application. Software professionals and developers need to have good knowledge of data structures and algorithms to develop efficient software code and programs. Data Structures and Algorithms address the requirements of data representation, storage and processing.

Common data structures include List, array, Linked List, Tree and graph. Most used algorithms are for searching and sorting of data.

Q.1 What is meant by a data structure?

A data structure as per its name is structuring of data to address the requirement of efficient and effective data representation, storage and processing. A data structure is simply an organization of data like consecutive data storage is done by array data structure and random storage can be done by tree data structure.

Report This Question

Q.2 What is the use of a data structure

A data structure is useful in performing operations on data: Data addition, removal, searching, sorting and accessing

Report This Question

Q.3 What refers to an algorithm?

An algorithm is a list of instructions to execute for achieving a specified output against provided inputs.

Report This Question

Q.4 What is the reason for conducting algorithm analysis?

Algorithm analysis is performed to know the performance of different algorithms to solve a specific problem and select the one, which best address the requirement either in terms of space or compute resource needed.

Report This Question

Q.5 Explain what you understand by asymptotic analysis of an algorithm.

Asymptotic analysis defines the mathematical limits of run-time performance of an algorithm. It results in providing the worst, average and best case for an algorithm performance.

Report This Question

Q.6 Detail the various asymptotic notations

3 levels of asymptotic notations are provided fort an algorithm: Best case (or Ω(n) notation), Average case (or Θ(n) notation) and Worst case (or Ο(n) notation)

Report This Question

Q.7 What do you understand by linear and non-linear data Structures?

As per nomenclature, linear data structure which stores data consecutively or forms a sequence, example includes queue, array, list, linked list and stacks. Whereas non-linear do not store data consecutively and their example include tree and graph.

Report This Question

Q.8 Define an array data structure

An array is a data structure which store data consecutively in adjacent memory locations. Each element can be read / written by the index number which may start from 0 or 1 for the first element, as per the programming language. For example in C language: array_sample[10]

Report This Question

Q.9 What is referred by a multidimensional array data structure?

A multidimensional array data structure is similar to an array but instead of storing a single list of elements, it is able to store elements in different lists also called as dimension. An array is said to be single dimension data structure. To access elements in a multidimensional array data structure, multiple index numbers are needed to read / write data. For example in C language a 2-D array: array_sample[10][15] Multidimensional array data structure is used to store number of data belonging to different grouping or dimension. 2D array is used to store tabular data (both row and column)

Report This Question

Q.10 What is a linked list?

A linked list is a both a linear and non-linear data structure whose elements are not stored in contiguous memory location but each element or node connects to next one by pointers. Each element in a linked list is called a node and has two parts – data to store and pointer to connect to next one. The last node pointer stores NULL to indicate end of the list. The first node is also called as head or head node. Node as needed are allocated from memory and not allocated during definition as in an array.

Report This Question

Q.11 What are variations of linked list

Linked list varies as per requirement and can be circular (last node instead of NULL, points to first node) and doubly linked list (each node has two pointers to point to the next node and previous node for forward/ backward traversal).

Report This Question

Q.12 What is more efficient array or linked list

Linked list is more efficient because of memory space utilization (array allocate all memory space as defined though may not be used but in linked list memory space to be used, is allocated) and quick insertion / deletion (in linked list the node is reached and pointers re-assigned with deallocation of node but in array whole array is copied to new smaller or bigger memory space and older one is deallocated)

Report This Question

Q.13 How will you explain the stack data structure?

Stack is a linear data structure but addition or removal of data is done at single end - called the top. It is used for LIFO (Last-In-First-Out) related requirement wherein, the first element added, will be deleted in last just like a making a pile of books one over other.

Report This Question

Q.14 What are PUSH and POP operations of a stack data structure?

PUSH and POP are operations done on a stack data structure only. PUSH operation refers to adding data element to the stack which is added to the top of the stack and POP operation removes or accesses the data element at top of the stack data structure.

Report This Question

Q.15 Illustrate the various types of notations, as: Infix, Prefix and Postfix

The different notations are about placement of operators with operands, when operators are in-between their operands it is infix (as A+B), when operators are before their operands it is prefix (+ A B) and if operators are after their operands it is postfix (A B+)

Report This Question

Q.16 Transform the expression: (A + B) * (C - D) to postfix notation

The postfix notation is generated by placing operators after the operands as per sequence in the original expression and is transformed as: (AB+) * (CD-) then finally: AB+CD-*

Report This Question

Q.17 What do you understand by the queue data structure?

A queue data structure is similar to stack with addition of data elements is done at one end called as REAR and removal of data elements is done at other end called as FRONT. It addresses FIFO (First-In-First-Out) related requirement wherein, the first element added , will be deleted in first just like a queue of people in bank or airport, first one in the queue is addressed first and query resolved.

Report This Question

Q.18 What is a dequeue?

Dequeue expands to double-ended queue hence, it is an queue with addition and removal of data elements done in both ends of the queue i.e. front and rear.

Report This Question

Q.19 Explain priority queue

A priority queue is queue with priority being assigned to each element. High priority elements are processed first.

Report This Question

Q.20 Define the tree data structure

The tree data structure is similar to a tree in which a node or first node is called as root and it, remaining nodes are linked to it and are called children nodes. The group of children nodes are nonempty sets also called as sub-tree with root node in them is placed at the top with remaining as children node of the sub-tree. The tree data structure hence, is also recursive.

Report This Question

Q.21 What are the various types of tree data structure?

6 types of tree data structure are present and which are: General Tree, Forests, Binary Tree, Binary Search Tree, Expression Tree and Tournament Tree.

Report This Question

Q.22 What is the use of queue data structure?

A queue data structure is used to address FIFO related requirements like maintaining process priority by operating system, customer query resolution, etc.

Report This Question

Q.23 Explain the operations on queues

A queue data structure has operations for adding data element in rear of the queue (called enqueue), removing data element from front (called dequeue), accessing the element at front (called peek) and checking whether the queue is full or empty.

Report This Question

Q.24 Explain linear searching

Linear searching is the searching of a data value amongst the data elements of an data structure by comparing it with every data element starting from the first one and consecutively comparing with next one. It's worst case complexity is Ο(n2) and average is Ο(n).

Report This Question

Q.25 Illustrate the working of binary search algorithm

The binary search is applicable for sorted lists or arrays. The algorithm involves selecting the middle value of the list which is divided in 2 parts and again search is done in those part if the middle value is not the value to be searched.

Report This Question

Q.26 How does bubble sort work?

The Bubble sort algorithm sorts by comparing adjacent element and swap them as per sort order. Sorting goes on till all elements are compared with rest. Its time complexity is Ο(n2).

Report This Question

Q.27 Explain the working of insertion sort

The insertion sort algorithm sorts by dividing the list into 2 sub-lists of sorted and non-sorted lists. Then, the algorithm selects an element in sorted list and places it in correct sort order thus, sorting this list. Iteratively the algorithm sorts all elements of non-sorted sub-list and places it in sorted sub-list as per sort order.

Report This Question

Q.28 How does the selection sort, works?

The selection sort algorithm performs sorting by dividing the list into 2 sub-lists of sorted and non-sorted lists. Then, the algorithm selects a minimum value element from non-sorted and puts it into sorted list as per sort order. Iteratively the algorithm sorts all elements from non-sorted list.

Report This Question

Q.29 Differentiate amongst the insertion and selection sort algorithm?

Both insertion and selection sort algorithm are similar in working but they differ as selection sort searches the minimum from the unsorted sub-list while insertion sort uses the current element in hand.

Report This Question

Q.30 How does merge sort works?

Merge sort algorithm divides the list into smaller sub-list till single element list remains. After which, these lists are merged as per sort order till sub-list is present. The run-time complexity of merge sort algorithm is Ο(n log n)

Report This Question

Q.31 Explain the shell sort algorithm?

Shell sort is very similar to insertion sort but it divides the list into smaller sub-list based on some gap variable and then each sub-list is sorted using insertion sort. In best cases, it can perform up to Ο(n log n).

Report This Question

Q.32 Illustrate the working of quick sort algorithm?

Quick sort uses divide and conquer approach by dividing the input list into small lists smaller 'partitions' using 'pivot'. The values which are smaller than the pivot are arranged in the left partition and greater values are arranged in the right partition. Each partition is recursively sorted using quick sort.

Report This Question

Q.33 What is a graph data structure?

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

Report This Question

Q.34 Explain the working of depth first traversal in a graph data structure?

Depth First Search algorithm (DFS) traverses a graph in a depth-wise motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.

Report This Question

Q.35 How breadth first traversal works?

Breadth First Search algorithm (BFS) traverses a graph in a breadth-wise motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.

Report This Question

Q.36 Define a binary tree data structure?

A binary tree has a special condition that each node can have two children at maximum.

Report This Question

Q.37 What is a binary search tree data structure?

A binary search tree is a binary tree with a special provision where a node's left child must have value less than its parent's value and node's right child must have value greater than its parent value.

Report This Question

Q.38 What is the formula to find maximum nodes in a binary tree having a height of k?

The formula is to find maximum nodes in a binary tree with height as k, is: 2k+1-1 where k >= 1

Report This Question

Q.39 Explain the main attributes of a B Tree data structure?

In a B tree of order m, 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 and all leaf nodes must be at the same level.

Report This Question

Q.40 What is the mathematical representation of a graph data structure?

A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices and E(G) represents the set of edges which are used to connect these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex relationship among them instead of having parent-child relations.

Report This Question

Q.41 Describe Path in a graph data structure?

A Path is the sequence of adjacent vertices connected by the edges with no restrictions.

Report This Question

Q.42 Explain cycle in a graph data structure?

A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path cannot be visited twice

Report This Question

Q.43 What is a Circuit in a graph?

A Circuit can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex may be repeated.

Report This Question

Q.44 Select the data structure suitable for DFS of a graph data structure

Stack is suitable for DFS of a graph.

Report This Question

Q.45 Which data structure is apt for BFS of a graph data structure?

Queue is apt for BFS of a graph.

Report This Question

Q.46 Describe a spanning tree data structure?

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. A spanning tree does not have cycles and it cannot be disconnected.

Report This Question

Q.47 Explain the working of Kruskal's algorithm?

This algorithm treats the graph as a forest and every node it as an individual tree. A tree connects to another only and only if it has least cost among all available options and does not violate MST properties.

Report This Question

Q.48 Describe minimum spanning tree (MST) data structure?

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight that all other spanning trees of the same graph.

Report This Question

Q.49 Describe a heap data structure?

Heap is a special balanced binary tree data structure where root-node key is compared with its children and arranged accordingly. A min-heap, a parent node has key value less than its child’s and a max-heap parent node has value greater than its child’s.

Report This Question

Q.50 Explain the process of hashing?

Hashing is a technique to convert a range of key values into a range of indexes of an array. By using hash tables, we can create associative data storage where data index can be found by providing its key values.

Report This Question