DSA (Revision + Self Evaluation)

Hey Everyone! So, after 21 days of DSA where we covered arrays, strings, linked lists, hashmaps, stacks and queues… I’ve decided to give you a small self evaluation test where I have tried including previously asked placement questions.

Section1: MCQ

1. If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is :

A) Less than 1

B) Less than n

C) Less than m

D) Less than n/2

2. Which of these are core interfaces in the collection framework. Select the one correct answer.

A) Tree

B) Linked List

C) Stacks

D) Map

3. If the array is already sorted, then the running time for merge sort is: ?

A) O(1)

B) O(n*logn)

C) O(n)

D) O(n²)

4. How would you make the middle node of a doubly linked list to the top of the list?
Let assume “X” is the middle node

A) X->next->prev = x->prev x->prev->next = x->next x->next = head head->prev=x

B) x->next = head head->prev=x

C) X->next->prev=x->next x->prev->next = x->prev x->next = head head->prev=x

D) None of the above

5. Assume single linked list pseudo code as follows?

struct Node {
data
next
}
record List {
Node firstNode
}

function1(List list) {
obsoleteNode = list.firstNode; list.firstNode = list.firstNode.next; free obsoleteNode;
}

function2(node node) {
obsoleteNode = node.next; node.next= node.next.next; free obsoleteNode;
}

function3(Node node,Node newNode) {
newNode.next = node.next;node.next= newNode
}

function4(List list, Node newNode) {
newNode.next = list.firstNode; list.firstNode = newNode;
}

A) function1 removes the first node

B) function2 removes the node past this one

C) function3 inserts newNode after node

D) function4 inserts newNode after current first node

6. What does the following function do if S is an array used to implement a stack?

float peep (float S[], int *t, int i)
{  
float val;
if( (*t-i+1) > 0)
{ 
val = S[*t-i+1];
return val;
}
} 

A) Returns the ith value from top of the stack

B) Returns the value at the top of the stack

C) Compilation Error

D) Returns the value at the ith position of the array

7. Let the following circular queue can accommodate maximum six elements with the following data
front = 2 rear = 4
queue = _______; L, M, N, ___, ___
What will happen after ADD O operation takes place?

A) front = 2 rear = 5 queue = ______; L, M, N, O, ___

B) front = 3 rear = 5 queue = L, M, N, O, ___

C) front = 3 rear = 4 queue = ______; L, M, N, O, ___

D) front =2 rear =4 queue = L,M,N,P,______

8. We need to implement a queue using a circular array. If DATA is a circular array of CAPACITY elements, and rear is an index into that array, what will be the index for the element after rear?

A) (rear + 1) % CAPACITY

B) rear + (1 % CAPACITY)

C) rear % (1 + CAPACITY)

D) (rear % 1) + CAPACITY

9. Convert the infix to postfix for A-(B+C)*(D/E)

A) ABC+DE/*-

B) ABC-DE/*-

C) ABC-DE*/-

D) None of the above

10. The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum

A) Three nodes

B) Two nodes

C) One node

D) Any number of nodes

Section2: Coding

1. https://www.interviewbit.com/problems/largest-number/
2. https://www.interviewbit.com/problems/add-two-numbers-as-lists/
3. https://www.interviewbit.com/problems/rain-water-trapped/
4. https://www.interviewbit.com/problems/remove-duplicates-from-sorted-array/
5. https://www.interviewbit.com/problems/window-string/

All the above questions are previously asked by different companies for placements. So, solve these questions on your own before moving to solutions part.

Hope this could be helpful. If you want me to post more such self-evaluations, please leave a response saying ‘Need more self evaluations’ so that I know that you guys are interested.

Good Luck!!!

Solutions for MCQs

1. A
2. D
3. B
4. A
5. C
6. A
7. A
8. D
9. A
10. C

Visit us on:

https://instagram.com/placementprep_aryagswm?igshid=1d5oaojdprbwy