Data Structure
Interview Questions

• Array: Fixed-size, contiguous memory allocation, constant-time access, and O(1) time complexity for random access. However, resizing is difficult and time-consuming.
• Linked List: Dynamic size, non-contiguous memory allocation, efficient insertion and deletion, but requires sequential traversal for access.

• Stack: Follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the same end (top).
• Queue: Follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.

A binary tree is a hierarchical data structure consisting of nodes where each node has at most two children, referred to as the left child and the right child. The topmost node is called the root, and nodes with no children are called leaves.

• Binary Tree: Simply a hierarchical tree structure with each node having at most two children.
• Binary Search Tree (BST): A binary tree with the additional property that the left subtree of a node contains only nodes with values less than the node, and the right subtree contains only nodes with values greater than the node.

Hashing is the process of converting input data (keys) into a fixed-size array index through a hash function. It provides a fast and efficient way to search, insert, and delete elements in data structures like hash tables.

• Insertion (average case): O(1)
• Deletion (average case): O(1)
• Search (average case): O(1)
• However, in the worst case, these operations can have a time complexity of O(n), where n is the number of elements.

• Breadth-First Search (BFS): Explores all the vertices at the current depth before moving on to the next level. Uses a queue.
• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Uses a stack (or recursion).

Dynamic programming is a technique used to solve problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once, storing the results to avoid redundant computations. It is often used for optimization problems.

Asymptotic analysis of an algorithm defines the run-time performance as per its mathematical boundations. Asymptotic analysis helps us articulate the best case(Omega Notation, Ω), average case(Theta Notation, θ), and worst case(Big Oh Notation, Ο) performance of an algorithm.

Following are the key operations available deque:

• insertFront(): This adds an element to the front of the Deque.
• insertLast(): This adds an element to the rear of the Deque.
• deleteFront(): This deletes an element from the front of the Deque.
• deleteLast():This deletes an element from the front of the Deque.
• getFront(): This gets an element from the front of the Deque. 
• getRear(): This gets an element from the rear of the Deque. 
• isEmpty(): This checks whether Deque is empty or not.
• isFull(): This checks whether Deque is full or not.

• A variable is stored in memory based on the amount of memory that is needed. Following are the steps followed to store a variable:
  • The required amount of memory is assigned first.
  • Then, it is stored based on the data structure being used.
• Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on requirements in real-time.