Data Structures Interview Questions - Data Structures Interview Prep

Data structure is way of organizing and storing data in computer memory for efficient access and modification. Examples: arrays, linked lists, stacks, queues, trees, graphs, hash tables. Choice affects algorithm performance.

Array: contiguous memory, fixed/dynamic size, O(1) access, O(n) insert/delete. Linked list: non-contiguous, dynamic size, O(n) access, O(1) insert/delete. Array: better cache locality, random access. Linked list: efficient insertion/deletion, no size limit.

Time complexity describes how algorithm runtime grows with input size. Big O notation: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. Worst-case analysis.

Space complexity describes how algorithm memory usage grows with input size. Includes input space and auxiliary space. O(1) constant, O(n) linear, O(n²) quadratic. Important for memory-constrained systems.

Stack is LIFO (Last In First Out) data structure. Operations: push (add top), pop (remove top), peek (view top), isEmpty. O(1) for all operations. Uses: function calls, expression evaluation, undo/redo, backtracking.

Queue is FIFO (First In First Out) data structure. Operations: enqueue (add rear), dequeue (remove front), front, isEmpty. O(1) for all operations. Uses: task scheduling, BFS, print queues, request handling.

Binary tree is tree where each node has at most 2 children (left, right). Root at top, leaves at bottom. Height: longest path from root to leaf. Full: all nodes have 0 or 2 children. Complete: all levels filled except last.

BST is binary tree where left subtree < node < right subtree. Enables O(log n) search, insert, delete (balanced). Inorder traversal gives sorted order. Worst case O(n) if unbalanced. Self-balancing: AVL, Red-Black trees.

Tree traversals visit all nodes: Inorder (left, root, right) - sorted for BST. Preorder (root, left, right) - copy tree. Postorder (left, right, root) - delete tree. Level-order (BFS) - level by level. All O(n) time.

Hash table stores key-value pairs using hash function. O(1) average insert, search, delete. Hash function maps key to index. Collision handling: chaining (linked list), open addressing (linear/quadratic probing). Load factor affects performance.