Data Structures and Algorithms Interview Exam Questions with Answers

Data Structures and Algorithms Interview Exam Questions with Answers What is a data structure? - Correct Answers: A way of defining, storing, and retrieving data in a structural and systematic way. What is an algorithm? - Correct Answers: A step by step procedure, which defines a set of instructions to be executed in a certain order to get a desired output. Why do we do algorithm analysis? - Correct Answers: A problem can be solved in more than one way. So, many solution algorithms can be derived for a given problem. We must implement the most suitable algorithm. What are the criteria of algorithm analysis? - Correct Answers: An algorithm is generally analyzed by two factors -- *execution time* and *space required* by the algorithm. What is asymptotic analysis of an algorithm? - Correct Answers: Refers to defining the mathematical bounds/framing of an algorithms run-time performance. What are the 3 primary asymptotic notations? - Correct Answers: *Best case* - Ω(n). *Worst case* - Ο(n) notation. *Average case* - Θ(n) notation. What is a linear data structure? - Correct Answers: A data structure that contains sequentially arranged data items. The next item can be located in the next memory address. Arrays and lists are examples of linear data structures What are common operations that can be performed on data structures? - Correct Answers: *Insertion* - adding a data item. *Deletion* - removing a data item. *Traversal* - accessing and/or printing all data items. *Searching* - finding a particular data item. *Sorting* - arranging data items in a pre-defined sequence. Briefly explain the approaches to developing algorithms? - Correct Answers: *Greedy Approach* - finding solution by choosing next best option. *Divide and Conquer* - dividing the problem to a minimum possible sub-problem and solving them independently. *Dynamic Programming* - dividing the problem into a minimum number of possible problems and solving them in a combined manner. What are some examples of greedy algorithms? - Correct Answers: Traveling Salesman Prim's Minimal Spanning Tree Algorithm Kruskal's Minimal Spanning Tree Algorithm Dijkstra's Minimal Spanning tree Algorithm Graph - Map Coloring Graph - Vortex Cover Knapsack Problem Job Scheduling Problem What are some examples of divide and conquer algorithms? - Correct Answers: Merge sort Quick sort Binary search Strassen's Matrix Multiplication Closest pair (points) What are some examples of dynamic programming algorithms? - Correct Answers: Fibonacci number series Knapsack problem Tower of Hanoi All pair shortest path by Floyd-Warshall Shortest path by Dijkstra Project scheduling What is a linked-list? - Correct Answers: A linked-list is a list of data items connected with links ( pointers). What is a stack? - Correct Answers: An abstract data type used to store and retreive values in the LIFO (Last In First Out) method. Why would you want to use a stack? - Correct Answers: They use a LIFO method and retrieval of data takes on O(n) time. We use them when we need to access data in the reverse order that is was initially acquired. Commonly used in recursive function calls, expression parsing, depth first traversal of graphs. What operations can be performed on a stack? - Correct Answers: *push* - add an item to the top of the stack. *pop* - remove item from the top of the stack. *peek* - return value stored in the top item without removing it.. *isempty* - check if stack is empty. *isfull* - check if stack is full. What is a queue? - Correct Answers: An abstract data strucure that is similar to a stack. It is open at both ends and one end is used to insert data and the other is used to remove data. It follows a FIFO (First In First Out) methodology. Why do we use queues? - Correct Answers: We use them when we need to work on data items is the exact sequence of their arrival. Every operating system maintains queues of various processes. Priority queues and breadth first traversal of graphs are some examples of queues. What operations can be performed on Queues? - Correct Answers: *enqueue* - add item to the rear of the queue *dequeue* - remove item from the front of the queue *peek* - give value of front item without removing *isempty* check to see if empy *isfull* check to see if full What is a linear search? - Correct Answers: A search that attempts to find an item in a sequentially arranged data type. Compared expected data item with each of the data items in a list or array. Average case - O(n) Worst case - O(n^2). Data in target arrays/lists need not to be sorted. What is a binary search? - Correct Answers: Search selects the middle of the list or array and splits it into two parts. First the middle is compared to the target. If it is not found, then a decision must be made to continue the same procedure with either the left or right sub lists. What is a bubble sort? How does it work? - Correct Answers: A comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped out if they are not in order. Because time complexity is O(n^2), it is not suitable for large sets of data. What is insertion sort? - Correct Answers: DIvides the list into two sublists, sorted and unsorted. It takes one element at a time and finds its appropriate location in the sorted sublist and inserts it there. The output after insertion is a sorted sublist. What is selection sort? - Correct Answers: An in-place sorting technique. It divides the data set into two sublists: sorted and unsorted. Then it selects the minimum element from unsorted sublist and places it into the sorted list. This iterates unless all the elements from unsorted sublist are consumed. How are selection sort and insertion sort different? - Correct Answers: Both are sorting techniques that maintain two sub-list: sorted and unsorted. Both take one element at a time and places it into the sorted sub-list. Insertion sort works on the current element and places it in the sorted array at the appropriate location. Selection sort searches the minimum from the unsorted sub-list and replaces it with the current element in hand. What is merge sort and how does it work? - Correct Answers: Divide and conquer approach. It keeps dividing the list into smaller sub-lists until all sub-lists are only 1 element big. Then it merges them in a sorted way until all sub-lists are consumed. It has a run-time complexity of O(n log n) and it needs O(n) auxiliary space What is shell sort? - Correct Answers: 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 upto Ο(n log n). How does quick sort work? - Correct Answers: Divide and conquer. It divides list in to smaller partitions using a pivot. The values which are smaller than the pivot are arranged on the left parition and the greater values are arranged in the right partition. Each partition is recursively sorted using quick sort. What is a graph? - Correct Answers: A pictorial representation of a set of object where some pairs of objects are connected by links. The interconnected onect are represented by points called vertices, and the links that connect the vertices are called edges. How does depth first traversal work? - Correct Answers: 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. How does breadth first traversal works? - Correct Answers: Traverse a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration. What is a tree? - Correct Answers: A minimally connected graph having no loops and circuits. What is a binary tree? - Correct Answers: A special tree where each node can have only two children at maximum. What is a binary search tree? - Correct Answers: 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 it's parent value. What is tree traversal? - Correct Answers: A process to visit all nodes in a tree. Always start from root. Three ways: In-order Traversal Pre-order Traversal Post-order Traversal PRACTICE CARD Traverse a binary search tree using: In Order, Pre Order, and Post order traversals. - Correct Answers: PRACTICE CARD Traverse a binary search tree using: In Order, Pre Order, and Post order traversals. What is an AVL Tree? - Correct Answers: Height balancing binary search tree. CHecks the height of left and right sub-trees and assures that the difference is not more than 1. This is called the balance factor. BalanceFactor = heigh * (left-subtree) - heigh * (right - subtree) What is a spanning tree? - Correct Answers: Subset of a graph which has all the vertices covered with minimum possible number of edges. A spanning tee does not have cycles and it can not be disconnected. How many spanning trees can a graph have? - Correct Answers: It depends on how connected the graph is. A complete undirected graph can have maximum n^n-1 number of spanning trees, where n is the number of nodes. How kruskal's algorithm works? - Correct Answers: Treats graph as a forest and every node has an individual tree. A tree connects to another if and only if it has the least cost among all available option and does violate MST properties. How does Prim's algorithm works? - Correct Answers: Treats the nodes as a single tree and keeps on adding new nodes to the spanning tree from the given graph. What is a minimum spanning tree? - Correct Answers: A weighted graph, a minimum spanning tree is a spanning tree that has minimum weight that all other spanning trees of the same graph. What is a heap? - Correct Answers: 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. What is a recursive function? - Correct Answers: A function which calls itself, directly or calls a function that in turn calls it. each recursive function has: *base criteria* - where function stops calling itself. *progressive approach* - where the functions tries to meet the base criteria in each iteration. What is the Towers of Hanoi problem? - Correct Answers: A mathematical puzzle which consists of three tower pegs and more than one rings. all rings are of different sizes and are stacked upon each other where the lare disk is always below the smaller disk. The aim is to move the tower of disks from one peg to another without breaking its properties. What is fibonacci series? - Correct Answers: Generates subsequent number by adding two previous numbers. For example. What is hashing? - Correct Answers: A technique to convert a range of key values into a range of indexes of an array. By using hash tables, we can create an associative data storage where data index can be found by providing its keys. What is the prefix and post fix notation of (a + b) * (c + d) ? - Correct Answers: