Company questionsGroundworkRazorpay

Machine coding · Caches and stores

In-memory database

  • Reported once
  • Strategy
  • Facade
  • Specification
  • 1 source

One candidate write-up. Treat it as a single data point.

The prompt
Build a small in-memory database as a machine-coding exercise. The reported brief gives no schema or query detail, so assume tables with typed columns, insert, select, update and delete with simple filters, and one index that speeds up equality lookups. Bad input should fail with a clear error and leave the stored data unchanged.

Restated in our own words, not a quote from Razorpay or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

The source gives almost no detail, so the first job is to pin down scope out loud. Questions to ask: which column types are needed, and are nulls allowed? Is there a primary key or unique constraint? What does a filter look like: a list of comparisons that must all hold, or also OR and nesting? Are joins, ordering, limits or aggregates expected? How many indexes, what kind, and can one be created after data exists? Is a text query language needed, or is a method API fine? Do we need transactions, persistence or concurrent access?

Assumed scope: three column types (int, string, bool), every column required, no primary key. A filter is a list of conditions with a column, an operator and a value, all of which must hold. Operators are equality, inequality and the four orderings. One hash index per table, created at any time. A method API, no text parser. Out of scope: joins, ordering, transactions, persistence and threads.

Entities and relationships

Who owns what, and who talks to whom.

  • Database is the facade. It owns tables by name and exposes createTable and table.
  • Table owns the schema, the rows (a Map from an internal row id to a row object), an optional index and the operations insert, select, update and delete. It also records the access path used by the last query in lastPlan.
  • HashIndex maps one column's values to the set of row ids that hold that value. The table keeps it in step with every write.
  • TYPES is a lookup of one validator function per column type.
  • OPERATORS is a lookup of one comparison function per operator string.
  • Condition is a plain object with a column, an operator and a value.

Relationships: a database has many tables, a table has many rows and at most one index, and a table uses TYPES to validate values and OPERATORS to evaluate conditions.

The design

The class map, the main flow and the patterns that earn their place.

Class map of the in-memory databaseThe table owns rows and the index. Types and operators are lookups that the table consults.
DatabasecreateTable, tableTableinsert, select, updateTYPESint, string, bool checksOPERATORS= != < <= > >=Row storerow id to rowHashIndexvalue to row idshas manyownskeeps in stepvalidates withfilters with123
  1. A database holds tables by name.
  2. A table stores rows in a map from an internal row id to the row.
  3. Every write also updates the one optional index so lookups stay correct.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

The table is the only place where rows and the index live, and everything that can vary is a lookup table. Column types are entries in TYPES and operators are entries in OPERATORS. That is the Strategy pattern reduced to a map from name to function: adding a float type or a "like" operator is one entry and touches nothing else. A condition is a small object evaluated against a row, which is the Specification idea, and a filter is simply a list of them that must all hold. Database is a thin facade that hides how tables are stored.

Rows are stored in a Map keyed by an increasing internal id that is never reused, so the index can refer to a row without holding the row itself. The index is a HashIndex: value to Set of ids. Creating it walks the existing rows once.

  1. insert validates the whole row first (unknown column, wrong type, missing column), then assigns the next id, stores a copy and adds the id to the index if there is one.
  2. select, update and delete all start from matching(where). It first checks every column name, operator name and condition value type, so a typo or a string compared with an int fails loudly rather than matching nothing, and select checks the projected column names the same way. update and delete require the list of conditions, so leaving it out cannot wipe a table by accident. It then asks candidates for ids: if some condition is an equality on the indexed column it takes the index lookup, otherwise every row id. Finally it applies every condition to those candidates and sorts the ids, so the index is only a pre-filter and results are identical with or without it. lastPlan records which path ran so a demo can show the index being used.
  3. select returns copies, optionally projected to the requested columns, so callers cannot change stored rows behind the index.
  4. update validates the new values before touching any row, so a bad value changes nothing. It computes the matching ids before mutating, then for each row removes the old index entry, applies the change and adds the new entry. Computing the ids first also means a row whose changed column no longer matches the filter is not revisited.
  5. delete removes each matching row and its index entry and returns the count.

A scan tests all n rows and an indexed equality lookup tests only the k rows in one bucket, and both then sort the matching ids. A hash index cannot serve a range filter, so those still scan; an ordered structure would be needed to change that. There is no atomicity across rows beyond validating up front. With threads the minimum is a read-write lock per table, and real databases use versioned rows.

The code

Runnable JavaScript, with the checks it passes.

razorpay-in-memory-database.js
const TYPES = {
  int: (value) => Number.isInteger(value),
  string: (value) => typeof value === "string",
  bool: (value) => typeof value === "boolean",
};

const OPERATORS = {
  "=": (a, b) => a === b,
  "!=": (a, b) => a !== b,
  "<": (a, b) => a < b,
  "<=": (a, b) => a <= b,
  ">": (a, b) => a > b,
  ">=": (a, b) => a >= b,
};

class HashIndex {
  constructor(column) {
    this.column = column;
    this.buckets = new Map();
  }
  add(id, row) {
    const value = row[this.column];
    if (!this.buckets.has(value)) this.buckets.set(value, new Set());
    this.buckets.get(value).add(id);
  }
  remove(id, row) {
    const ids = this.buckets.get(row[this.column]);
    ids.delete(id);
    if (ids.size === 0) this.buckets.delete(row[this.column]);
  }
  lookup(value) {
    return [...(this.buckets.get(value) || [])];
  }
}

class Table {
  constructor(name, schema) {
    this.name = name;
    this.schema = schema;
    this.rows = new Map();
    this.nextId = 1;
    this.index = null;
    this.lastPlan = "scan";
  }
  validate(values, partial) {
    for (const [column, value] of Object.entries(values)) {
      if (!Object.hasOwn(this.schema, column)) throw new Error("unknown column " + column);
      if (!TYPES[this.schema[column]](value)) throw new Error("column " + column + " expects " + this.schema[column]);
    }
    if (partial) return;
    for (const column of Object.keys(this.schema)) {
      if (!Object.hasOwn(values, column)) throw new Error("missing column " + column);
    }
  }
  createIndex(column) {
    if (!Object.hasOwn(this.schema, column)) throw new Error("unknown column " + column);
    this.index = new HashIndex(column);
    for (const [id, row] of this.rows) this.index.add(id, row);
  }
  insert(values) {
    this.validate(values, false);
    const id = this.nextId++;
    const row = { ...values };
    this.rows.set(id, row);
    if (this.index) this.index.add(id, row);
    return id;
  }
  candidates(where) {
    const probe = this.index && where.find((c) => c.column === this.index.column && c.op === "=");
    if (probe) {
      this.lastPlan = "index:" + probe.column;
      return this.index.lookup(probe.value);
    }
    this.lastPlan = "scan";
    return [...this.rows.keys()];
  }
  matching(where) {
    if (!Array.isArray(where)) throw new Error("where must be a list of conditions");
    for (const condition of where) {
      if (!Object.hasOwn(this.schema, condition.column)) throw new Error("unknown column " + condition.column);
      if (!Object.hasOwn(OPERATORS, condition.op)) throw new Error("unknown operator " + condition.op);
      if (!TYPES[this.schema[condition.column]](condition.value)) {
        throw new Error("column " + condition.column + " expects " + this.schema[condition.column]);
      }
    }
    return this.candidates(where)
      .filter((id) => where.every((c) => OPERATORS[c.op](this.rows.get(id)[c.column], c.value)))
      .sort((a, b) => a - b);
  }
  select(where = [], columns = null) {
    const ids = this.matching(where);
    for (const column of columns || []) {
      if (!Object.hasOwn(this.schema, column)) throw new Error("unknown column " + column);
    }
    return ids.map((id) => {
      const row = this.rows.get(id);
      if (!columns) return { ...row };
      return Object.fromEntries(columns.map((column) => [column, row[column]]));
    });
  }
  update(where, changes) {
    this.validate(changes, true);
    const ids = this.matching(where);
    for (const id of ids) {
      const row = this.rows.get(id);
      if (this.index) this.index.remove(id, row);
      Object.assign(row, changes);
      if (this.index) this.index.add(id, row);
    }
    return ids.length;
  }
  delete(where) {
    const ids = this.matching(where);
    for (const id of ids) {
      if (this.index) this.index.remove(id, this.rows.get(id));
      this.rows.delete(id);
    }
    return ids.length;
  }
}

class Database {
  constructor() {
    this.tables = new Map();
  }
  createTable(name, schema) {
    if (this.tables.has(name)) throw new Error("table exists " + name);
    for (const type of Object.values(schema)) {
      if (!Object.hasOwn(TYPES, type)) throw new Error("unknown type " + type);
    }
    const table = new Table(name, schema);
    this.tables.set(name, table);
    return table;
  }
  table(name) {
    if (!this.tables.has(name)) throw new Error("no table " + name);
    return this.tables.get(name);
  }
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

  1. How would you support a range filter on the indexed column, and which structure replaces the hash map?
  2. How would you add a unique constraint or a primary key, and what must an update that changes the key check before it writes anything?
  3. How would you support several indexes and choose between them when a query has two indexed equality conditions?
  4. How would you add order by, limit and a count aggregate without changing how update and delete find their rows?
  5. How would you add transactions with rollback, and what would you record so that a failed update can be undone?

Where candidates slip

The mistakes this problem punishes.

  • Validating while mutating, so a bad value half way through an update leaves some rows changed and others not.
  • Forgetting to maintain the index on update and delete, which gives stale hits or misses rows after a change.
  • Letting the index decide the result instead of only narrowing candidates, so a query with an indexed equality plus another condition ignores the second one.
  • Returning the stored row objects, which lets callers edit data without the index knowing.
  • Letting a typo in a column or operator name silently match nothing, and accepting the string "40" for an int column.
  • Looking up user supplied names with plain property access, so an operator or column called constructor slips through as valid. Check own properties only.
  • Writing a query parser first and running out of time before the tables, types and index work.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Now make it stick

Sketch the class map on the whiteboardRun a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Read these chapters first