## Top DataStructure Questions

###### Q (1): Explain Runtime Analysis of Algorithm

#### Big O Notation

*Big O Notation*is used to describe the upper bound of a particular algorithm. Big O is used to describe worst case scenarios

#### Little O Notation

*Little O Notation*is also used to describe an upper bound of a particular algorithm; however, Little O provides a bound that is not asymptotically tight

#### Big Ω Omega Notation

*Big Omega Notation*is used to provide an asymptotic lower bound on a particular algorithm

#### Little ω Omega Notation

*Little Omega Notation*is used to provide a lower bound on a particular algorithm that is not asymptotically tight

#### Theta Θ Notation

*Theta Notation*is used to provide a bound on a particular algorithm such that it can be "sandwiched" between two constants (one for an upper limit and one for a lower limit) for sufficiently large values

###### Q (2): Explain Linked List and it's type

### Linked List

- A
*Linked List*is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. **Singly-linked list**: linked list in which each node points to the next node and the last node points to null**Doubly-linked list**: linked list in which each node has two pointers, p and n, such that p points to the previous node and n points to the next node; the last node's n pointer points to null**Circular-linked list**: linked list in which each node points to the next node and the last node points back to the first node- Time Complexity:
- Access:
`O(n)`

- Search:
`O(n)`

- Insert:
`O(1)`

- Remove:
`O(1)`

- Access:

###### Q (3): Explain Stack Data Structure

### Stack

- A
*Stack*is a collection of elements, with two principle operations:*push*, which adds to the collection, and*pop*, which removes the most recently added element **Last in, first out data structure (LIFO)**: the most recently added object is the first to be removed- Time Complexity:
- Access:
`O(n)`

- Search:
`O(n)`

- Insert:
`O(1)`

- Remove:
`O(1)`

- Access:

###### Q (4): Explain Queue Data Structure

### Queue

- A
*Queue*is a collection of elements, supporting two principle operations:*enqueue*, which inserts an element into the queue, and*dequeue*, which removes an element from the queue **First in, first out data structure (FIFO)**: the oldest added object is the first to be removed- Time Complexity:
- Access:
`O(n)`

- Search:
`O(n)`

- Insert:
`O(1)`

- Remove:
`O(1)`

- Access:

###### Q (5): Explain Tree Data Structure

### Tree

- A
*Tree*is an undirected, connected, acyclic graph

### Binary Tree

- A
*Binary Tree*is a tree data structure in which each node has at most two children, which are referred to as the*left child*and*right child* **Full Tree**: a tree in which every node has either 0 or 2 children**Perfect Binary Tree**: a binary tree in which all interior nodes have two children and all leave have the same depth**Complete Tree**: a binary tree in which every level*except possibly the last*is full and all nodes in the last level are as far left as possible

###### Q (6): What is Binary Search Tree?

### Binary Search Tree

- A binary search tree, sometimes called BST, is a type of binary tree which maintains the property that the value in each node must be greater than or equal to any value stored in the left sub-tree, and less than or equal to any value stored in the right sub-tree
- Time Complexity:
- Access:
`O(log(n))`

- Search:
`O(log(n))`

- Insert:
`O(log(n))`

- Remove:
`O(log(n))`

- Access:

<img src="/img/data_structure/BST.png?raw=true" alt="Binary Search Tree" width="400" height="500">

###### Q (7): What is Trie Data Structure?

### Trie

- A trie, sometimes called a radix or prefix tree, is a kind of search tree that is used to store a dynamic set or associative array where the keys are usually Strings. No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the String associated with that node, and the root is associated with the empty String.

###### Q (8): What is Fenwick Tree?

### Fenwick Tree

- A Fenwick tree, sometimes called a binary indexed tree, is a tree in concept, but in practice is implemented as an implicit data structure using an array. Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each element of the array contains the pre-calculated sum of a range of values, and by combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated
- Time Complexity:
- Range Sum:
`O(log(n))`

- Update:
`O(log(n))`

- Range Sum:

###### Q (9): What is Segment Tree?

### Segment Tree

- A Segment tree, is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point
- Time Complexity:
- Range Query:
`O(log(n))`

- Update:
`O(log(n))`

- Range Query:

###### Q (10): What is Heap?

### Heap

- A
*Heap*is a specialized tree based structure data structure that satisfies the*heap*property: if A is a parent node of B, then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the entire heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node - Time Complexity:
- Access Max / Min:
`O(1)`

- Insert:
`O(log(n))`

- Remove Max / Min:
`O(log(n))`

- Access Max / Min:

<img src="/img/data_structure/heap.png?raw=true" alt="Max Heap" width="400" height="500">