Operational OS Data Structures Interview Questions & Answers:

1. What is a complexity of linear search, binery search?

In linear search each element in the array should be checked
until the required element got searched whereas in binary
search array is divided into two and required element is
searched

2. What is AVL tree?

An AVL tree is a self-balancing binary search tree, and it
was the first such data structure to be invented.In an AVL
tree, the heights of the two child subtrees of any node
differ by at most one. Lookup, insertion, and deletion all
take O(log n) time in both the average and worst cases,
where n is the number of nodes in the tree prior to the
operation. Insertions and deletions may require the tree to
be rebalanced by one or more tree rotations.

3. Explain real world example of polymorphism and encapsulation?

Rael world example fo polymorphism can be start machnism of
bike, inwhich u wil hav same method start() but it may be
either by kick start or button start.
N example for encapsulation can be a stack or queue doesn't
matter how it is implented internally with linked list or array

4. What is difference between the run time polymorphism and compile time poly morphism and about virtual function?

Compile time polymorphism(Static polymorphism) means
basically those language structure which will cause the
compiler to produce code at the compile-time. That is, the
compiler is well aware that what code is to be generated at
the compile-time itself: Ex: overloading of operators,
functions.

Run time Polymorphism(Dynamic Polymorphism)means that the
compiler is unaware what code is to be generated so it binds
the possible code and let the program decide it at the
run-time itself.Ex: the virtualness of a class member or the
entire class itself.

5. Why enum can not be used directly with printf function?

enum is not an basic data type like int,float and all it is
a user defined data type, and printf function works only
with basic data type, we 've overload printf function to
make it work for user defined data types :)

6. What is R-B tree?

A red black tree is a binary tree where
1. every node has color.
2. root node is always black
3. the child of a black node is either black or red
4. both the child nodes of every red node must be black
5. all the leaves must be black

7. What is the different between B-tree and B+ tree?

It's all about branching factor. Because of the way B+-Trees store records (called "satellite information") at the leaf level of the tree, they maximize the branching factor of the internal nodes. High branching factor allows for a tree of lower height. Lower tree height allows for less disk I/O. Less disk I/O theoretically means better performance
In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only.
A B+ - Tree is in the form of a balanced tree in which every path from the root of the tree to a leaf of the tree is the same length.
Each nonleaf node in the tree has between [n/2] and n children, where n is fixed.
B+ - Trees are good for searches, but cause some overhead issues in wasted space.

8. Tell me how to search an element in sorted linked list with time complexity is O(log n)?

we can use the binary search algorithm for this problem because this searching algorithm has O(log n) performance in both worse and average case.

9. Do you know how to find the number of possible tree in the given tree?

number of possible tree = (2 power n) - n.
for example:
A tree contain three node.
so n=3.
possible tree = 8 - 3 = 5.

10. Tell me why do tree always takes o(log n) time?

Tree always takes o(log n) time because tree has height is
(log n).