Coding · Design a structure
In-memory contact manager with prefix search
- Reported once
- Medium
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Build an in-memory contact manager. add(firstName, lastName, phone) stores a contact and returns its numeric id, starting at 1. remove(id) deletes a contact and returns whether it existed. search(prefix) returns every contact whose first name, last name or phone number starts with the prefix, ignoring case, each shown as first name, last name and phone separated by spaces, in the order the contacts were added. A contact that matches through more than one field appears once, and an empty prefix returns nothing. The per-search cost should depend on the prefix length and the number of matches, not on the number of contacts. A candidate report lists it as a machine coding round: add or update contacts, then search by first name, last name or phone number, partial or complete and case insensitive, with the total count shown, in memory only and checked by unit tests. This version merges the three searches into one that matches any of the fields, and has remove in place of update.
Restated in our own words, not a quote from CRED or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would settle the contract before drawing classes. Is a match a prefix of one field, or could it be any word inside the name? Is search case insensitive? What do I return, ids or formatted contacts, and in what order? If a contact matches through both its first and last name, does it appear twice? Does it need removal, and what happens to ids afterwards? Is it single threaded and memory only, as the prompt says?
My assumptions: a match is a prefix of the first name, the last name or the phone, ignoring case; results come back once each in the order the contacts were added, and their count is the length of the list; an empty prefix matches nothing; ids start at 1 and are never reused; there is no persistence, and one thread uses it. The report lists update as well, which I would treat as remove followed by add.
Brute force
Say the obvious answer and why it is too slow.
Keep the contacts in an array. add pushes a new entry. search lowercases the prefix and scans every contact, testing whether the first name, last name or phone starts with it, and collects the hits in array order. remove deletes the entry. It is correct, short and easy to unit test, and a good starting point to say out loud.
Each search costs O(N * p) for N contacts and a prefix of length p, even when only two contacts match. With a million contacts and a search per keystroke that is millions of string comparisons every time, and most of them fail on the first character. Sorted arrays per field with binary search fix the lookups but make add and remove O(N) because of shifting, and the three result lists still have to be merged and de-duplicated.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(N * p) per search over N contacts and a prefix of length p
- Time
- O(L) for add and remove of keys with total length L, O(p + r) for search
- Space
- O(total key length) for the trie and the id sets
The pattern is a trie whose nodes remember which contacts pass through them. A trie turns "which keys start with this prefix" into one walk down the prefix, and the only question is what to read when the walk ends. Instead of collecting the whole subtree, store at every node the set of contact ids whose key passes through that node. After walking the prefix, that set is exactly the answer, so search is O(p + r) for a prefix of length p and r results.
All three fields of a contact go into the same trie, lowercased: the first name, the last name and the phone. A search for a prefix is meant to match any of the three fields, so the node reached by that prefix holds the union, and the Set removes duplicates when a contact matches through two fields. Empty fields are skipped.
Order comes for free. Ids are handed out in increasing order and a JavaScript Set iterates in insertion order, so each node's set lists ids in the order the contacts were added, and deleting an id never disturbs the others. The results need no sorting.
Removal needs care because the keys of one contact can share path nodes. First delete the id from every node along all of its keys. Only then prune bottom-up, walking each key again and deleting nodes whose set is now empty; pruning while still removing would delete a node that a second key of the same contact is about to visit. The price of the design is memory: every key character adds an id to a set, so space is the total length of all keys. In an interview I would split the trie into its own PrefixIndex class and keep the contacts in a store; the code here keeps them together to stay short.
Walk it through
A dry run on the example, step by step.
| Operation | Result | Note |
|---|---|---|
| add Asha Rao 98100 | 1 | keys asha, rao, 98100 |
| add Ravi Asher 98255 | 2 | asher shares as with asha |
| add Meera Rao 77001 | 3 | rao node now holds 1, 3 |
| search as | ids 1, 2 | first name and last name |
| search RAO | ids 1, 3 | lowercased, last names |
| search 98 | ids 1, 2 | two phones |
| search 982 | ids 2 | narrowed to one phone |
| remove 1 | true | id 1 leaves every path |
| search as | ids 2 | only Ravi remains |
| search zz | none | walk falls off the trie |
| remove 1 | false | already gone |
Three contacts go in. Asha Rao gets id 1, Ravi Asher id 2 and Meera Rao id 3. Searching as walks two nodes and finds ids 1 and 2: Asha through her first name and Ravi through his last name, Asher. Searching RAO is lowercased first and finds 1 and 3 through the last name. The prefix 98 finds the two phones starting with 98, and 982 narrows it to id 2.
Then remove 1 deletes id 1 from every node on its paths and prunes the nodes that became empty. The same search for as now returns only Ravi, a search for zz returns nothing because the walk falls off the trie, and a second remove of id 1 returns false. The table shows ids in the result column to fit the page; the code returns the formatted contact strings.
The code
Runnable JavaScript, checked against test cases.
class ContactManager {
constructor() {
this.root = { next: new Map(), ids: new Set() };
this.contacts = new Map();
this.nextId = 1;
}
keysOf(contact) {
return [contact.first, contact.last, contact.phone].map((field) => field.toLowerCase()).filter((key) => key !== "");
}
add(first, last, phone) {
const id = this.nextId++;
const contact = { first, last, phone };
this.contacts.set(id, contact);
for (const key of this.keysOf(contact)) {
let node = this.root;
for (const ch of key) {
if (!node.next.has(ch)) node.next.set(ch, { next: new Map(), ids: new Set() });
node = node.next.get(ch);
node.ids.add(id);
}
}
return id;
}
remove(id) {
const contact = this.contacts.get(id);
if (contact === undefined) return false;
this.contacts.delete(id);
const keys = this.keysOf(contact);
for (const key of keys) {
let node = this.root;
for (const ch of key) {
node = node.next.get(ch);
node.ids.delete(id);
}
}
for (const key of keys) {
const path = [];
let node = this.root;
for (const ch of key) {
const child = node.next.get(ch);
if (child === undefined) break;
path.push([node, ch]);
node = child;
}
for (let i = path.length - 1; i >= 0; i--) {
const [parent, ch] = path[i];
if (parent.next.get(ch).ids.size > 0) break;
parent.next.delete(ch);
}
}
return true;
}
search(prefix) {
const key = prefix.toLowerCase();
if (key === "") return [];
let node = this.root;
for (const ch of key) {
node = node.next.get(ch);
if (node === undefined) return [];
}
return [...node.ids].map((id) => {
const c = this.contacts.get(id);
return c.first + " " + c.last + " " + c.phone;
});
}
}
function run(ops, args) {
const book = new ContactManager();
return ops.map((op, i) => (i === 0 ? null : book[op](...args[i])));
}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.
Edge cases
What to test before you say you are done.
An empty prefix returns an empty list by definition, and a prefix longer than every key falls off the trie and returns an empty list too. A contact with an empty last name is still found by its first name and phone, since empty fields are never inserted. A contact whose first and last names are equal, like Rao Rao, is indexed twice but appears once, because the ids sit in sets.
- Removing an unknown or already removed id: returns false and changes nothing.
- Ids after removal: they are never reused, so the order of the remaining results stays the order of adding.
- Mixed case: keys and prefixes are lowercased the same way, so ASH finds Asha.
- Phone formats: the phone is stored as typed, so a prefix like +91 matches only if it was entered with it; normalising is a follow-up.
- Two contacts with the same name: they get different ids and both appear.
Follow-ups to expect
Where the interviewer pushes next.
- How would you rank the results, for example most recently used first, and cap them at ten?
- How would you also match a word in the middle of a name, or the last digits of a phone?
- How would you cut the memory when there are millions of contacts?
- How would you make it safe for many concurrent readers and one writer?
- How would you persist the contacts and rebuild the index on startup?
Where candidates slip
The mistakes this problem punishes.
The common design slip is one trie per field with the three result lists concatenated, which returns a contact twice when two fields match and loses the added order. Another is storing ids only at the end of a key and gathering the subtree on each search, which makes a short prefix as slow as a scan.
Others: pruning nodes while the contact still has other keys to remove, which crashes on a shared path; comparing without lowercasing both sides; reusing ids after a remove so the order breaks; returning the live set instead of a fresh array so callers can corrupt the index; and testing only the happy path, when a machine-coding round expects unit tests for removal, duplicates and empty input.
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
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.