Question 1

What is a segment tree and what operations does it support efficiently?

Accepted Answer

A tree data structure that supports range queries (sum, min, max) and point/range updates in O(log n) time. Built in O(n), each query/update is O(log n). A node at index i covers range [l, r]; children cover [l, mid] and [mid+1, r]. Used in competitive programming for problems like 'sum of elements in range [l, r] after point updates'.

Question 2

What is the difference between a B-tree and a B+ tree?

Accepted Answer

B+ trees store all data in leaf nodes with leaves linked for efficient range scans; B-trees store data in all nodes including internal nodes. B+ tree advantage: internal nodes only store keys (more keys per disk page = fewer I/Os). Linked leaf nodes make range queries a sequential scan. PostgreSQL and MySQL InnoDB use B+ trees. B-trees are used in some filesystems (HFS+).

Question 3

What is a Bloom filter and what are its trade-offs?

Accepted Answer

A space-efficient probabilistic data structure that tests set membership — may produce false positives but never false negatives. Bloom filter: bit array + k hash functions. Insert: set k bits. Lookup: if all k bits set → probably in set; if any 0 → definitely not. Used in databases (BigTable, Cassandra) to avoid disk I/O for keys that don't exist. False positive rate tunable via size.

Question 4

What does 'amortized O(1)' mean for dynamic array (ArrayList) appending?

Accepted Answer

While individual appends occasionally trigger O(n) resizing (doubling capacity), the average cost across n appends is O(1) — total n appends cost O(n). Doubling strategy: resize happens at sizes 1,2,4,8,... Total copies = 1+2+4+...+n = 2n. Amortized per-append cost = 2n/n = O(1). Doubling is key — linear growth (add 1 each time) would give O(n) amortized cost.

Question 5

What is a red-black tree and how does it maintain balance?

Accepted Answer

A self-balancing BST with color properties (red/black) ensuring no root-to-leaf path is more than twice as long as any other — guaranteeing O(log n) operations. Red-black rules: root is black; red nodes have black children; all paths from root to null have the same number of black nodes. Rotations and recoloring restore properties after insert/delete. Used in Java TreeMap, C++ std::map, and Linux's completely fair scheduler.

Data Structures & Algorithms — Senior Dev Interview Questions

More Senior Dev Topics

Data Structures & Algorithms at Other Levels