A PDF version of the problem is available for easier reading and reference: Download link

We provide a minimal parser skeleton for your convenience. Implement all TODOs. You may modify any existing code or start from scratch if you prefer.

A database can be viewed as a table with multiple columns and rows. Each row is a record. If you find it confusing, please view the example below.

In this problem, your task is to simulate a tiny in-memory database over a predefined table with a fixed subset of SQL. SQLs follow the exact templates below.

Table (predefined)

TABLE people (
  id   INT,
  name TEXT,
  age  INT,
  city TEXT
)

• Columns are exactly: id, name, age, city.

Statements

• INSERT: insert one row

INSERT INTO people VALUES (INT, 'TEXT', INT, 'TEXT');

• UPDATE: set a column to a literal; optional single-condition WHERE

UPDATE people SET col = LIT [WHERE col = LIT];

• DELETE: optional single-condition WHERE

DELETE FROM people [WHERE col = LIT];

• SELECT: select rows from table in descending order; if equal, output in any order; optional single-condition WHERE

SELECT col FROM people [WHERE col = LIT] ORDER BY col DESC;

Literals & tokens

• col: one of id, name, age, city
• INT: an integer
• TEXT, LIT: a string of A-Z, a-z, 0-9

Execution

• Start with an empty database.
• Execute statements in order.
• Print the result of every SELECT.

Input

• Line 1: integer Q as the number of statements.
• Next Q lines: SQL statements, each ending with ; (must follow the templates).

Output

For each SELECT:

1. Print a line with the number of result rows R (after filtering).
2. Then print R lines: the single selected column per row.
   • INT as decimal; TEXT without quotes.

Sample

Input

10
INSERT INTO people VALUES (1, 'ALICE', 20, 'NY');
INSERT INTO people VALUES (2, 'BOB', 21, 'SF');
INSERT INTO people VALUES (3, 'CAROL', 20, 'NY');
UPDATE people SET name = 'HUANCHEN' WHERE id = 2;
SELECT name FROM people ORDER BY id DESC;
SELECT name FROM people WHERE age = 20 ORDER BY name DESC;
DELETE FROM people WHERE city = 'NY';
SELECT id FROM people ORDER BY age DESC;
INSERT INTO people VALUES (4, 'DAVE', 22, 'LA');
SELECT city FROM people WHERE id = 4 ORDER BY city DESC;

Output

3
CAROL
HUANCHEN
ALICE
2
CAROL
ALICE
1
2
1
LA

Explanation Step-by-step state (only showing rows after each mutating statement):

1. Insert (1, ALICE, 20, NY)

   [(1, 'ALICE', 20, 'NY')]

2. Insert (2, BOB, 21, SF)

   [(1, 'ALICE', 20, 'NY'), (2, 'BOB', 21, 'SF')]

3. Insert (3, CAROL, 20, NY)

   [(1, 'ALICE', 20, 'NY'), (2, 'BOB', 21, 'SF'), (3, 'CAROL', 20, 'NY')]

4. Update name = 'HUANCHEN' where id = 2

   [(1, 'ALICE', 20, 'NY'), (2, 'HUANCHEN', 21, 'SF'), (3, 'CAROL', 20, 'NY')]

5. SELECT name FROM people ORDER BY id DESC;

   • No WHERE, so all rows.
   • Selected column is name, but order by id (because the query says ORDER BY id DESC).
   • Sort rows by id descending: ids 3, 2, 1 → names: CAROL, HUANCHEN, ALICE

   • Output:

     3
     CAROL
     HUANCHEN
     ALICE

6. SELECT name FROM people WHERE age = 20 ORDER BY name DESC;

   • Filter: age = 20 → rows [(1, 'ALICE', 20, 'NY'), (3, 'CAROL', 20, 'NY')]
   • Order by name descending: [CAROL, ALICE]

   • Output:

     2
     CAROL
     ALICE

7. Delete where city = 'NY' → remove ids 1 and 3

   [(2, 'HUANCHEN', 21, 'SF')]

8. SELECT id FROM people ORDER BY age DESC;

   • Only row [(2, HUANCHEN, 21, SF)]
   • Order by age desc (just one row), select id → 2

   • Output:

     1
     2

9. Insert (4, DAVE, 22, LA)

   [(2, 'HUANCHEN', 21, 'SF'), (4, 'DAVE', 22, 'LA')]

10. SELECT city FROM people WHERE id = 4 ORDER BY city DESC;

    • Filter id = 4 → [(4, DAVE, 22, LA)]
    • Order by city desc (single row), select city → LA

    • Output:

      1
      LA

Code Skeleton

You are allowed to change other places in the code.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

enum class Type { INT, TEXT };
struct Value {
  Type type;
  int int_val;
  std::string str_val;
};
typedef std::vector<Value> Row;

struct Where {
  std::string col;
  std::string lit;
};

class MiniSQL {
public:
  MiniSQL() {
    // TODO: Initialize the database if needed
  }

  void insert(const std::vector<std::string> &values) {
    // TODO: Implement insertion logic
    // std::cerr << "Inserting values: ";
    // for (const auto &value : values) {
    //   std::cerr << value << " ";
    // }
    // std::cerr << std::endl;
  }

  void update(const std::string &col, const std::string &lit) {
    // TODO: Implement update logic
    // std::cerr << "Updating column " << col << " to " << lit << " for all
    // rows."
    //           << std::endl;
  }

  void update(const std::string &col, const std::string &lit,
              const Where &pred) {
    // TODO: Implement update logic
    // std::cerr << "Updating column " << col << " to " << lit << " where "
    //           << pred.col << " = " << pred.lit << "." << std::endl;
  }

  void _delete() {
    // TODO: Implement delete logic
    // std::cerr << "Deleting all rows from people." << std::endl;
  }

  void _delete(const Where &pred) {
    // TODO: Implement delete logic
    // std::cerr << "Deleting rows where " << pred.col << " = " << pred.lit <<
    // "."
    //           << std::endl;
  }

private:
  std::vector<Row> _data;

  static Value _parse(const std::string &lit) {
    if (lit.front() == '\'' && lit.back() == '\'')
      return Value{Type::TEXT, 0, lit.substr(1, lit.size() - 2)};
    else
      return Value{Type::INT, std::stoi(lit), ""};
  }

  // TODO: Add more private methods as needed
};

int main() {
  int q = 0;
  std::cin >> q;
  std::cin.ignore();

  MiniSQL db;
  for (int i = 0; i < q; ++i) {
    std::string command;
    std::getline(std::cin, command);
    assert(command.back() == ';');
    command.pop_back();

    std::vector<std::string> tokens;
    std::istringstream stream(command);
    std::string token;
    while (stream >> token)
      tokens.push_back(token);

    if (tokens[0] == "INSERT") {
      // INSERT INTO people VALUES (INT, 'TEXT', INT, 'TEXT');
      assert(tokens[1] == "INTO");
      assert(tokens[2] == "people");
      assert(tokens[3] == "VALUES");

      std::vector<std::string> values;
      values.push_back(tokens[4].substr(1, tokens[4].size() - 2)); // id
      values.push_back(tokens[5].substr(0, tokens[5].size() - 1)); // name
      values.push_back(tokens[6].substr(0, tokens[6].size() - 1)); // age
      values.push_back(tokens[7].substr(0, tokens[7].size() - 1)); // city

      assert(tokens.size() == 8);
      db.insert(values);
    } else if (tokens[0] == "UPDATE") {
      // UPDATE people SET col = lit [WHERE col = lit];
      assert(tokens[1] == "people");
      assert(tokens[2] == "SET");

      std::string col = tokens[3];
      assert(tokens[4] == "=");
      std::string lit = tokens[5];

      if (tokens.size() > 6) {
        assert(tokens[6] == "WHERE");
        std::string where_col = tokens[7];
        assert(tokens[8] == "=");
        std::string where_lit = tokens[9];
        Where pred{where_col, where_lit};

        assert(tokens.size() == 10);
        db.update(col, lit, pred);
      } else {
        assert(tokens.size() == 6);
        db.update(col, lit);
      }
    } else if (tokens[0] == "DELETE") {
      // DELETE FROM people [WHERE col = lit];
      assert(tokens[1] == "FROM");
      assert(tokens[2] == "people");

      if (tokens.size() > 3) {
        assert(tokens[3] == "WHERE");
        std::string where_col = tokens[4];
        assert(tokens[5] == "=");
        std::string where_lit = tokens[6];
        Where pred{where_col, where_lit};

        assert(tokens.size() == 7);
        db._delete(pred);
      } else {
        assert(tokens.size() == 3);
        db._delete();
      }
    } else if (tokens[0] == "SELECT") {
      // TODO: Implement SELECT command parsing
    } else
      assert(false);
  }
  return 0;
}

1. After Insert (1, 'ALICE', 20, 'NY')

[(1, 'ALICE', 20, 'NY')]

2. After Insert (2, 'BOB', 21, 'SF')

[(1, 'ALICE', 20, 'NY'), (2, 'BOB', 21, 'SF')]

3. After Insert (3, 'CAROL', 20, 'NY')

[(1, 'ALICE', 20, 'NY'), (2, 'BOB', 21, 'SF'), (3, 'CAROL', 20, 'NY')]

4. After Update name = 'HUANCHEN' where id = 2

[(1, 'ALICE', 20, 'NY'), (2, 'HUANCHEN', 21, 'SF'), (3, 'CAROL', 20, 'NY')]

5. Result of SELECT name FROM people ORDER BY id DESC;

Sorted by id descending: 3, 2, 1 → names CAROL, HUANCHEN, ALICE.
Row count: 3.

6. Result of SELECT name FROM people WHERE age = 20 ORDER BY name DESC;

Filtered to age = 20: ids 1 and 3 → ALICE, CAROL.
Ordered by name descending: CAROL, ALICE.
Row count: 2.

7. After Delete where city = 'NY' (remove ids 1 and 3)

[(2, 'HUANCHEN', 21, 'SF')]

8. Result of SELECT id FROM people ORDER BY age DESC;

Only row is id 2 (age 21).
Row count: 1.

9. After Insert (4, 'DAVE', 22, 'LA')

[(2, 'HUANCHEN', 21, 'SF'), (4, 'DAVE', 22, 'LA')]

10. Result of SELECT city FROM people WHERE id = 4 ORDER BY city DESC;

Filtered to id = 4 → LA.
Row count: 1.