# DSA Day-29

Hey Guys!!!

We have covered the basics of each data structures along with their practice links and personal notes. We will be doing self-evaluation on the topics covered till now.

Round -1

- Which of the following involves arranging the records in logical order?

A. Merging

B. Sorting

C. Traversing

D. Searching

2. Which of the following is a set of data values and associated operations that are specified accurately, independent of any particular implementation?

A. Stack

B. Tree

C. Abstract Data Type

D. Graph

3. The post order traversal of a binary tree is DEBFCA. Find out the pre order traversal

A. ABFCDE

B. ADBFEC

C. ABDECF

D. ABDCEF

4. In a graph if e =(u,v) means

A. u is adjacent to v but v is not adjacent to u

B. e begins at u and ends at v

C. u is processor and v is successor

D. both b and c

5. Worst case time complexity of quick sort is

A. O(n²log7)

B. O(nlogn)

C. O(n²)

D. O(logn)

6. Which design strategy stops the execution when it find the solution otherwise starts the problem from top

A. Back tracking

B. Divide and conquer

C. Branch and Bound

D. Dynamic programming

7. Prims algorithm is based on ____________ method.

A. Divide and conquer method

B. Dynamic programming

C. Greedy method

D. Branch and bound

8. Testing of a program consists of 2 phases which are ______________ and ___________.

A. Average case and worst case

B. Time complexity and space complexity

C. Validation and checking errors

D. Debugging and profiling

9. A list which displays the relationship of adjacency between elements is said to be

A. linear

B. non linear

C. linked list

D. trees

10. Which of the following sorting algorithm is of divide-and-conquer type?

A.Bubble sort

B. Quick sort

C. Insertionsort

D. All of above

Round -2

- https://www.interviewbit.com/problems/bst-iterator/
- https://www.interviewbit.com/problems/merge-k-sorted-lists/
- https://www.interviewbit.com/problems/palindrome-list/
- https://www.interviewbit.com/problems/vertical-order-traversal-of-binary-tree/
- https://www.interviewbit.com/problems/level-order/

Round -3

- N different couple go to cinema with 2N different seats. They take their place randomly. You could make swap operations. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.
- Given a array where each element is maximum +-k index away from it’s sorted position, find an algorithm to sort such array.
- find out all the elements in a sorted integer array whose value is equal to index of the array. O(logn) solution is expected.
- let’s say you’re given an arbitrary list of relations r1 and r2 from objects in a set of arbitrary size. find the size of th largest subset with the property that no two are related. for e.g., given set S = {a,b,c,d,e,f} and relations {a,d}, {b,c}, {a,c}, {a,e}, find the subset of S such that no two a connected.
- reverse the doubly linked list without using extra space
- How would you handle collision during hashing?
- Design and implement a calculater that can calculate expressions like: + 2 4 * 8 ( + 7 12) ( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) (PS:all items are space delimetered.)
- Sort a stack using only one other stack and no recursion.
- Create a LRU Cache.
- Is heap completely sorted?

**Answers**

- B
- C
- C
- D
- C
- A
- C
- D
- A
- B

Good luck! Stay tuned for the final segment of the series.