Data Structure Interview Questions | Page 2


Question 11:

What is best case, average case and worst case time complexity of binary search algorithm?

The best case, average case and worst case time complexity of binary search is listed below:

  Best Case Average Case Worst Case
Binary Search O(1) O(logn) O(logn)
Question 12:

What is the worst case time complexity of insert operation in Red Black Tree?

The worst case time complexity of insert operation in Red Black Tree is O(nlogn).

Question 13:

What is binary search tree?

Binary Search Tree is a binary tree which has the holds properties:

  1. The left subtree of a node contains the nodes with keys less than the node’s key.
  2. The right subtree of a node contains the nodes with keys greater than the node’s key.
  3. Each node can have at max two child nodes.

For example:

Binary Search Tree

Question 14:

What is the worst case time complexity of delete operation in Red Black Tree?

The worst case time complexity of delete operation in Red Black Tree is O(nlogn).

Question 15:

How many nodes does a perfect binary tree of level n has?

A perfect binary tree of level n has 2n+1 - 1 nodes.


Question 16:

What is the worst case time complexity of search operation in Red Black Tree?

The worst case time complexity of search operation in Red Black Tree is O(nlogn).

Question 17:

How many leaf nodes does a perfect binary tree of level n has?

A perfect binary tree of level n has 2n nodes.

Question 18:

Heapsort can be used as the auxiliary sorting routine in radix sort, because it operates in place. What do you think?

The auxiliary sorting routine in radix sort needs to be stable, meaining that numbers with the same value appear in the output array in the same order as they do appear in the input array. Heapsort is not stable. It does operate in place, meaning that only a constant number of elements of the input array are ever stored outside the array.

Question 19:

What is circular linked list?

A circular linked list is an implementation of linked list in which last node has reference to the first node as shown below:

Circular Linked List

Doubly Circular Linked List

Question 20:

What is priority queue?

A priority queue is a queue in which 

  • elements are inserted in the order of arrival with associated priority
  • elements with highest priority is processed first from the queue.

For example: Let us say we have various activities that has to be processed by particular department. When any activity comes to the department it has priority associated with it. When department starts processing it, it first checks the priority associated with activities and process the activity with highest priority. If two activity has same priority it process one which arrived first.

Share interview questions

Comments

Comments
comments powered by Disqus

Navigation

Social Media