DS: Misc

Question 1

What is a Circular List?

Answer 1

A list that does not have a clear “head” or “tail”, because “tail” points to “head” effectively creating a closed loop.

Question 2

HashMap Complexity

Answer 2

On AVERAGE:
Insert: O(1)
Deleting: O(1)
Search: O(1)

In Worst Case: Above 3 are O(n).

This is wrt to Collision of Keys, all based on hashing function. Hashing key.

Question 3

Java TreeMap - when would you use it?

Answer 3

Java TreeMap is an implementation of Red-Black tree.

Map is sorted in the natural ordering of keys or the Comparator provided.

Question 4

How are Strings stored and their memory layout?

Answer 4

In memory, everything is stored in bits 0 or 1.
When using ASCII encoding, which covers all the english alphabets - we can map every character to a number and store them in 1 byte.
ASCII mapping is 0-255 (2^8).
So a string is stored as array of ASCII encoded numbers. Each character is 1 byte.

If using another encoding, then depending on number of bytes to store them.

Question 5

What is a “sub-sequence of an array”?

Answer 5

A sub-sequence of an array is a set of numbers that aren’t necessarily adjacent in the array - BUT - that are in the same order as they appear in the array.

Question 6

Binary Tree vs BST

Answer 6

Binary Tree: A tree in which, every node has at max 2 child nodes.

Binary Search Tree: A Binary Tree in which all the nodes in the left sub-tree is less than or equal to value of node itself. And all the nodes in the right sub-tree is greater than node.

                                   Node X
                                         /\
                                        /  \
                                       /    \
                             Node Y  Subtree 3
                                   /\
                                  /  \
                                 /    \
                   Subtree 1   Subtree 2

BST: Subtree 1 < Node Y < Subtree 2 < Node X < Subtree 3