An onsite implementation question from a startup.

Question

The system maintains a table with 150 pages, and each page contains 1.5 million records hashed with users’ birth date. Each record includes information of username, nickname, birth date, hometown and title. We are required to write a C++ program that transforms this table into another one, which has 100 pages and is hashed with username. What’s the best algorithm in terms of both space efficiency and time efficiency?

Answer 1

Your best bet is probably a linear translation.

Answer 2

This is not really a C++ or algorithm question, but one on data storage / structure. The objective is create data structures that allow for fastest access with least amount of duplicated data (that's why the problem statement has large values).

I suggest creating a table of records with an additional ID field.

Next, create indices that contain the record ID. This allows you to use different fields as keys when locating records.

In C++, you could use a std::map:

std::map<HashType, Record_ID_Type> index;

For a database, I would let the database create indices for fields I wanted to index.