Data Structures Fundamentals
Interview Questions

To implement a stack using a linked list, define a Node class with value and next attributes. Implement a Stack class with a head pointer for the linked list. The push operation creates a new node and adjusts the head pointer to point to this new node. The pop operation checks if the stack is empty, then retrieves the value at the head, and adjusts the head pointer to the next node.

Arrays have a fixed size and offer constant time access. They are allocated in contiguous memory. Linked lists are dynamic, allowing efficient insertions/deletions. They are allocated as nodes dispersed in memory, accessible in linear time. Arrays are suitable when the size is known, and random access is needed. Linked lists fit scenarios with frequent insertions or deletions.

The data structure uses a hash map for indexing values and a dynamic array for storing them. Insertion and deletion use the map, giving O(1) operations on average when amortized. The array ensures constant time access, as hash maps might not inherently provide such functionality without a paired structure.

Utilize two stacks: `stack_in` for enqueue operations and `stack_out` for dequeue. For enqueue, push elements to `stack_in`. For dequeue, if `stack_out` is empty, transfer all elements from `stack_in`. Pop from `stack_out` to enqueue.

A binary search tree (BST) is useful if sorted data access and range-based operations are frequent. Unlike hash tables, which lack inherent ordering, BSTs can perform in-order traversal to easily fetch sorted elements, supporting range queries efficiently.

Hash tables provide average O(1) access and modification times but lack inherent ordering. They’re ideal for fast lookups. Binary heaps are tree-like structures used in priority queues, supporting O(log n) inserts and removals, and are ideal when you need ordered priority access.

Initialize three pointers: prev, curr, next. Iterate through the list, setting next to curr.next, updating curr.next to prev, moving prev to curr, and curr to next. Continue until the end of the list is reached. Finally, set head to prev.

AVL trees keep track of the balance factor, which is the height difference between left and right subtrees, maintaining a balance factor of -1, 0, or 1. After insertions or deletions, rotations (single or double) like left-right or right-left are applied to restore balance.

Collisions can be handled via chaining, where each bucket points to a linked list of entries. Open addressing places an entry at another location if a collision occurs, with strategies like linear probing (checking subsequent positions), quadratic probing (using quadratic function), and double hashing (using a secondary hash function).

Implement a hashmap for O(1) access to nodes and a doubly linked list to track usage order. When a key is accessed, move it to the head of the list. On reaching capacity, evict the tail node. Each operation (get/put) is O(1).

Due to the balanced nature of red-black trees, insert, delete, and search operations perform in O(log n) time. Insertions and deletions require adjustments through rotations and color changes to maintain balance, ensuring the tree remains approximately balanced regardless of operations.

A trie is implemented as a tree with each node representing a character. Words are stored by traversing from root to leaf following character nodes. Each node has a children array (or hash map) storing pointers to child nodes, supporting fast prefix searches.