Skip to content
Tutorials Center
My learning

Topics

Lesson 72 of 77 ยท Practice

Practice: Data Structures, Databases and Systems Set

Practice 15 interview questions across algorithms in Python, SQL queries and system design estimates, with runnable workspaces and hidden solutions.

This second practice set covers the three areas that most technical loops test after the language basics: algorithms and data structures, SQL, and design reasoning. There are 15 questions, five in each area. Algorithm and SQL questions come with a runnable workspace, so you can write and test your own answer. Design questions are discussion questions with a small calculation you can run. Every question has a solution hidden in a "Show solution" box.

Work the same way as in the first set: give yourself about five to ten minutes per question, write the answer before looking, then compare and note what you missed. The honest limit: design answers are judgment calls. The solutions here are good answers, not the only right ones, so focus on whether you named the trade-offs.

Three areas, five questions each

Algorithms Questions 1 to 5, in Python.
SQL Questions 6 to 10, on sample tables.
Design Questions 11 to 15, with numbers.
1 / 2

Algorithms (Python)

Question 1. lower_bound(nums, target): in a sorted list, return the index of the first element greater than or equal to target, or len(nums) if there is none. It must run in O(log n).

Question 2. has_cycle(head): given the head of a singly linked list, return True if the list contains a cycle. Use O(1) extra memory.

Question 3. max_depth(root): return the number of nodes on the longest root-to-leaf path of a binary tree (0 for an empty tree).

Question 4. top_k_frequent(nums, k): return the k most frequent values. Break ties by the smaller value, so the answer is unique.

Question 5. num_islands(grid): the grid is a list of strings of "1" (land) and "0" (water). Count groups of land cells connected up, down, left or right.

The stubs below fail on purpose. Replace each body until every line says pass.

Python Algorithms workspace: questions 1 to 5

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Show solutions for questions 1 to 5
Python
import heapq
from collections import Counter

def lower_bound(nums, target):
    low, high = 0, len(nums)
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def top_k_frequent(nums, k):
    counts = Counter(nums)
    return [value for value, _ in heapq.nsmallest(k, counts.items(), key=lambda item: (-item[1], item[0]))]

def num_islands(grid):
    rows = [list(row) for row in grid]
    count = 0
    for r in range(len(rows)):
        for c in range(len(rows[0])):
            if rows[r][c] == "1":
                count += 1
                stack = [(r, c)]
                while stack:
                    y, x = stack.pop()
                    if 0 <= y < len(rows) and 0 <= x < len(rows[0]) and rows[y][x] == "1":
                        rows[y][x] = "0"
                        stack += [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
    return count

1. Binary search with a half-open range [low, high): when the middle value is too small, discard it and everything to its left; otherwise keep it as a candidate. The loop ends with low == high, the first index that can hold the target. O(log n). 2. Floyd's tortoise and hare: the fast pointer moves two steps and the slow one step; if there is a cycle they must meet. O(n) time, O(1) space; a set of visited nodes also works but uses O(n) memory. 3. Recursion on the two subtrees; the depth is one more than the deeper child. O(n) time, O(height) stack space; mention an explicit stack or BFS for very deep trees. 4. Count with a hash map (O(n)), then pick the top k by a key that sorts count descending and value ascending. A heap gives O(n log k). 5. Scan the grid; each time you find unvisited land, count an island and flood it (here with a stack, to avoid recursion limits). Copying the grid keeps the input unchanged. O(rows x columns).

Review: Complexity and Data Structure Questions, Array and String Patterns and Trees and Graphs Questions.

SQL

The workspace below creates three tables. employees has a manager_id that points to another employee; customers has a few repeated emails; orders belongs to customers.

Question 6. Find the second highest distinct salary.

Question 7. List employees who earn more than their own manager.

Question 8. Find every email address that appears more than once in customers.

Question 9. For each department, return the employees with the highest salary. Keep ties.

Question 10. List customers who have never placed an order.

Write your queries at the bottom of the TryIt. The SELECT that is already there shows the data.

SQL SQL workspace: questions 6 to 10

Press Run (or Ctrl + Enter) to see the result here.

Show solutions for questions 6 to 10
SQL
-- 6. Second highest distinct salary (NULL if there is none)
SELECT MAX(salary) AS second_highest
FROM employees
WHERE salary < (SELECT MAX(salary) FROM employees);

-- 7. Employees who earn more than their manager
SELECT e.name
FROM employees e
JOIN employees m ON m.id = e.manager_id
WHERE e.salary > m.salary
ORDER BY e.name;

-- 8. Duplicate emails
SELECT email, COUNT(*) AS times
FROM customers
GROUP BY email
HAVING COUNT(*) > 1;

-- 9. Top earners per department, ties kept
SELECT name, dept, salary
FROM (
  SELECT name, dept, salary,
         RANK() OVER (PARTITION BY dept ORDER BY salary DESC) AS rnk
  FROM employees
)
WHERE rnk = 1
ORDER BY dept, name;

-- 10. Customers with no orders
SELECT c.name
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.id
WHERE o.id IS NULL
ORDER BY c.name;

With the sample data these return: 6: 120. 7: Cleo (130 against her manager Ana's 120) and Eve (90 against Dan's 80). 8: [email protected] with 2. 9: Cleo (Eng, 130), Eve (Ops, 90), and both Gus and Hal (Sales, 95), because RANK() gives tied rows the same rank. ROW_NUMBER() would wrongly drop one of them. 10: Anya and Di.

Notes you can add in an interview. For 6, the subquery form handles duplicates and returns NULL when there is no second salary; LIMIT 1 OFFSET 1 over SELECT DISTINCT also works, and DENSE_RANK() generalizes to the Nth highest. For 7, the managers with a NULL manager are dropped by the inner join, which is what we want. For 10, NOT EXISTS is equivalent and often clearer; avoid NOT IN when the subquery column can contain NULL, because it then returns no rows.

Review: SQL: Query-Writing Interview Questions and Databases: Indexes, Normalization and Transactions.

Design reasoning

Question 11. A game has 10 million players. You need the top 100 and each player's own rank, updated live. What do you use?

Question 12. A mobile app calls POST /charge over a flaky network and retries on timeout. How do you make sure the customer is charged once?

Question 13. A cache sits in front of a database, and users sometimes see stale data after updates. What are the options and their costs?

Question 14. A chat service stores 50 million messages a day, about 200 bytes each. How much storage do you need for one year with 3 replicas?

Question 15. An API lists items newest first with ?page=2&per_page=3. New items arrive constantly. What goes wrong, and what is a better scheme?

Questions 14 and 15 have a runnable scratchpad: compute your estimate and watch pagination misbehave before you read the answers.

Python Design scratchpad: estimate and pagination

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Show solutions for questions 11 to 15

11. Leaderboard. Use a structure ordered by score, such as a sorted set (a skip list or balanced tree plus a hash map), which gives O(log n) updates, O(log n + 100) for the top 100 and O(log n) for a player's rank. A relational ORDER BY score LIMIT 100 over 10 million rows is fine with an index on score, but "my rank" via COUNT(*) WHERE score > mine becomes expensive under constant updates. Sharding by score range complicates rank, so start with one in-memory sorted structure and snapshot it to durable storage. Mention that exact live rank for everyone is rarely needed: showing "top 1%" or an approximate rank is often enough.

12. Safe retries. Make the operation idempotent with an idempotency key. The client generates a unique key per logical charge and sends it in a header on every retry. The server stores the key with the result (inside the same transaction as the charge, guarded by a unique constraint) and returns the stored result if it sees the key again. Also: the payment provider must be called with the same key, expire old keys after a day or so, and reject a reused key sent with a different request body.

13. Stale cache. Options: a short TTL (simple, bounded staleness, extra load); invalidate on write (delete the key when the row changes, but races exist if a reader refills the cache with old data just before the delete); write-through (write to cache and database together, more write latency); versioned keys (include a version in the key, so old entries are simply never read). The answer is a trade-off between freshness, complexity and database load, and some data (a profile photo) can be stale while other data (a balance) cannot.

14. Estimate. 50 million x 200 bytes is 10 GB per day, about 3.65 TB per year, and about 10.95 TB with 3 replicas. Real systems add indexes, metadata and compression, so say "roughly 11 TB, plan for 15 to 20 with overhead". That fits a modest sharded cluster, which tells you storage is not the hard part: write throughput (about 580 messages per second on average) and read patterns are.

15. Pagination. With offset pagination, items that arrive between requests shift the rows: the scratchpad shows page 2 repeating items from page 1 (ids 8 and 7 appear twice here, because two new items pushed them down). Large offsets are also slow, since the database still walks past all skipped rows. Keyset (cursor) pagination asks for "items older than the last id I saw", is stable under inserts, and uses an index seek, so it stays fast. Its cost: you cannot jump to page 50 directly, and the sort key must be unique (add a tie-breaker such as the id).

Review: System Design: The Building Blocks, System Design: Rate Limiters, Feeds and Chat and Databases: NoSQL, Caching and Scaling.

How to read your results

Mark each area separately. Five out of five in algorithms but two in design is a common profile for people who practiced on coding sites only; the fix is to explain systems out loud, with numbers. Three or fewer in SQL usually means a missing window-function or join habit, which a few hours of drills will repair. Whatever your score, redo the missed questions after a few days: seeing the solution once is recognition, solving it again is recall.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which approach finds a cycle in a linked list using O(1) extra memory?

    The fast pointer eventually laps the slow one inside a cycle, so they meet; no extra storage is needed.
  2. 2. Why use RANK() instead of ROW_NUMBER() to find the top earners per department when ties must be kept?

    ROW_NUMBER() assigns distinct numbers even to ties, which would keep only one of the tied employees.
  3. 3. A retried POST /charge must not charge twice. What is the standard fix?

    The server recognizes the repeated key and returns the stored result instead of performing the charge again.
  4. 4. What is the main advantage of keyset pagination over offset pagination for a live feed?

    It asks for rows after the last seen key, so inserts above do not shift the window and the database can seek via an index.
  5. 5. Why does NOT IN with a subquery often return no rows unexpectedly?

    x NOT IN (..., NULL) is never true under three-valued logic. Use NOT EXISTS or filter out NULLs.

Summary

  • Algorithms: binary search with a half-open range, two-pointer cycle detection, recursion for trees, counting plus a heap for top-k, flood fill for islands.
  • SQL: subquery or DENSE_RANK() for Nth highest, self-join for manager comparisons, GROUP BY ... HAVING for duplicates, RANK() to keep ties, LEFT JOIN ... IS NULL or NOT EXISTS for missing rows.
  • Design: sorted sets for leaderboards, idempotency keys for retries, TTL or invalidation for caches, estimates with units, keyset pagination for feeds.
  • Always state the cost and the trade-off.

Next: Practice: A Full Mock Interview Loop.