Which data structure is used in redo-undo feature?

Explanation: Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first.

Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization?
(A) Circular Linked List
(B) Queue
(C) Stack
(D) Priority Queue

Answer: (B)

Explanation: Since packets need to be processed in First In First Out order, a queue can be used for synchronization.

A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

   o    Delection of the smallest element 
   o    Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?
(A) A heap can be used but not a balanced binary search tree
(B) A balanced binary search tree can be used but not a heap
(C) Both balanced binary search tree and heap can be used
(D) Neither balanced binary search tree nor heap can be used


Answer: (B)

Explanation: A self-balancing balancing binary search tree containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). See our post Find the minimum element in a Binary Search Tree for details.

Since Heap is a balanced binary tree (or almost complete binary tree), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapify (after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present. For a heap, we cannot find out in O(logn) if an element is present or not. Thanks to game for providing the correct solution.

Which data structure is best suited for converting recursive implementation to iterative implementation of an algorithm?
(A) Queue
(B) Stack
(C) Tree
(D) Graph


Answer: (B)

Explanation: Since function calls are executed in Last In First Out order, stack is the data structure for converting recursive to iterative implementation.



Which data structure is used for balancing of symbols?
(A) Stack
(B) Queue
(C) Tree
(D) Graph


Answer: (A)

Explanation: Stack is used for balancing of symbols. This is extensively used by the compiler to check for missing or additional symbols. The start of the symbol(like (, [, {) are pushed to the stack. When the end of the symbol(like ), \, }) are encountered, it is matched with the corresponding peek element of the stack. If the match is found, the element is popped, else error is flashed.


Which of the following data structures is best suited for efficient implementation of priority queue?
(A) Array
(B) Linked List
(C) Heap
(D) Stack


Answer: (C)

Which data structure is most efficient to find the top 10 largest items out of 1 million items stored in file?
(A) Min heap
(B) Max heap
(C) BST
(D) Sorted array


Answer: (A)

Explanation: Min heap of size 10 is sufficient to find the top 10 largest items. The algorithm can be given as follows:
1. Create the min heap with first 10 items.
2. For each remaining item, check if
2.1 The item is greater than the item stored in the head of the min heap.
2.1.1 If yes, replace it with this new item. Balance the min heap.
2.1.2 If no, do nothing.

At last, the min heap will contain the top 10 largest items.

Which among the following data structures is best suited for storing very large numbers (numbers that cannot be stored in long long int). Following are the operations needed for these large numbers.
(A) Array
(B) Linked List
(C) Binary Tree
(D) Hash


Answer: (B)

Explanation: The only two choices that make sense are Array and Linked List. Since array sizes are limited, they can create problems for following operations.

X = X*Y where X and Y are very large numbers.

Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?
(A) O(nLogn)
(B) O(nLogLogn)
(C) O(n)
(D) O(nLogn)


Answer: (C)

Explanation: We can build a heap of 2n elements in O(n) time. Following are the steps.

Create an array of size 2n and copy elements of both heaps to this array.

Call build heap for the array of size 2n. Build heap operation takes O(n) time.