#### Fri Jul 13 2018

# Data Structure interview questions

Data structures and algorithms are an important part of programming either it for Java, C++ or any other programming language. Since data structures are core programming concept, it's mandatory for all programmers, to know basic data structures like stack, linked list, queue, array, tree, and graph. Though tree and graph are on the tough side, programmers get familiar will all these. Any list of programming job interview questions is incomplete without questions from data structures and algorithms. In this article, we will see a couple of data structure questions answers that will help you to crack the job interviews.

## Q. What is Data Structure?

**Ans.** A data structure is a group of data elements grouped together under one name. These data elements are called members. They can have different types and different lengths. Some of them store the data of the same type while others store different types of data. Data structure refers to the way data is organized and manipulated. It seeks to find ways to make data access more efficient. When dealing with the data structure, we not only focus on one piece of data but the different set of data and how they can relate to one another in an organized manner.

## Q. What are various data-structures available?

**Ans.** Data structure availability may vary by programming languages. Commonly available data structures are the list, arrays, stack, queues, graph, tree etc.

## Q. Differentiate between PUSH and POP?

**Ans.** Pushing and popping refers to the way data is stored into and retrieved from a stack.

PUSH - Data being pushed/ added to the stack.

POP - Data is retrieved from the stack, particularly the topmost data.

## Q. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?

**Ans.** Polish and Reverse Polish notations.

## Q. Which data structure is used to perform recursion?

**Ans.** The data structure used for recursion is Stack.

Its LIFO property helps it remembers its 'caller'. This helps it know the data which is to be returned when the function has to return.

System stack is used for storing the return addresses of the function calls.

## Q. What is Huffman’s algorithm?

**Ans.** It is used in creating extended binary trees that have minimum weighted path lengths from the given weights. It makes use of a table that contains the frequency of occurrence for each data element.

## Q. Why we need to do algorithm analysis?

**Ans.** A problem can be solved in more than one ways. So, many solution algorithms can be derived for a given problem. We analyze available algorithms to find and implement the best suitable algorithm.

## Q. What is a linked list?

**Ans.** The linked list is a data structure which stores the same kind of data elements but not in contiguous memory locations and size is not fixed. The linked lists are related logically.

## Q. How to find if the linked list has a loop?

**Ans.** This question has the bit of similarity with the earlier algorithm and data structure interview question. It means we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to the same node. This will only happen if the linked list has the loop.

## Q. What is a hashing technique?

**Ans.** In general, in all searching techniques, search time is dependent on the number of items. Sequential search, binary search, and all the search trees are totally dependent on the number of items and many key comparisons are involved. Hashing is a technique where search time is independent of the number of items or elements. In this technique, a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.

## Q. What are the difference between malloc() and calloc()?

**Ans.** Following are the main difference between malloc() and calloc().

calloc() function takes two parameters but malloc() function takes only one parameter.

Memory allocated by calloc() is initialized to zero while memory allocated by malloc() contains garbage value.

## Q. What is stack?

**Ans.** In data-structure, the stack is an Abstract Data Type (ADT) used to store and retrieve values in Last In First Out method.

## Q. Why do we use stacks?

**Ans.** Stacks follows LIFO method and addition and retrieval of a data item takes only Ο(n) time. Stacks are used where we need to access data in the reverse order or their arrival. Stacks are used commonly in recursive function calls, expression parsing, depth-first traversal of graphs etc.

## Q. What are the different application of stack?

**Ans.** Some of the applications of the stack are as follows - Function calls, Reversal of a string, Checking validity of an expression containing nested parentheses, Conversion of infix expression to postfix.

## Q. What is a spanning Tree?

**Ans.** A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

## Q. What is a queue?

**Ans.** A Queue is a sequential organization of data. A queue is a first in first out type of data structure. An element is inserted at the last position and an element is always taken out from the first position.

## Q. What are priority queues?

**Ans.** A priority queue is a collection of elements such that each element has been assigned a priority.

## Q. What is divide and conquer method?

**Ans.** The basic idea is to divide the problem into several subproblems beyond which cannot be further subdivided. Then solve the subproblems efficiently and join them together to get the solution for the main problem.

## Q. What are asymptotic notations?

**Ans.** Asymptotic analysis can provide three levels of mathematical binding of the execution time of an algorithm − Best case is represented by Ω(n) notation, Worst case is represented by Ο(n) notation, the Average case is represented by Θ(n) notation.

## Q. Give some examples greedy algorithms?

**Ans.** The below-given problems find their solution using the greedy algorithm approach −

Travelling Salesman Problem, Prim's Minimal Spanning Tree Algorithm, Kruskal's Minimal Spanning Tree Algorithm, Dijkstra's Minimal Spanning Tree Algorithm, Graph - Map Coloring, Graph - Vertex Cover, Knapsack Problem, Job Scheduling Problem.

## Q. What is selection sort?

**Ans.** Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted and unsorted. Then it selects the minimum element from unsorted sub-list and places it into the sorted list. This iterates unless all the elements from unsorted sub-list are consumed into sorted sub-list.

## Q. What is shell sort?

**Ans.** Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller sublist 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).

## Q. How depth-first traversal works?

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

## Q. What is a binary search tree?

**Ans.** 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 the value greater than it's parent value.

## Q. What is an AVL Tree?

**Ans.** AVL trees are height balancing binary search tree. AVL tree checks the height of left and right subtrees and assures that the difference is not more than 1. This difference is called the Balance Factor.

## Q. What is a spanning Tree?

**Ans.** A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.

## Q. What is the difference between NULL and VOID?

**Ans.** Null is actually a value, whereas Void is a data type identifier. A null variable simply indicates an empty value, whereas void is used to identify pointers as having no initial size.

## Q. What is a recursive function?

**Ans.** A recursive function is one which calls itself, directly or calls a function that in turn calls it. Every recursive function follows the recursive properties - base criteria where functions stop calling itself and progressive approach where the functions try to meet the base criteria in each iteration.

## Q. What is Fibonacci series?

**Ans.** Fibonacci Series generates subsequent number by adding two previous numbers. For example - 0 1 1 2 3 5 8 13.

## Q. What is the tower of Hanoi?

**Ans.** Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings. All rings are of different size and stacked upon each other where the large disk is always below the small disk. The aim is to move the tower of the disk from one peg to another, without breaking its properties.

Lastly, we can say that these are not only questions that you will be faced in the interviews. These are the example of the level of questions related to data structures and algorithm. It only depends on interviewers that what they want to ask and how they will examine you. The aim is to give you an idea of the type of questions and help you to understand the label of interview questions regarding the data structures and algorithm. Best of luck for the future! Thank you!

**Author:**Geekboots