Instacart·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Instacart software engineer interview with a meaty systems question about handling a multi-gigabyte credentials file efficiently. The problem had multiple layers and they clearly wanted to see how far you'd push the design.

Questions Asked (1)

You have a multi-gigabyte credentials file on disk, one record per line formatted as user_id, salt, and a hex password hash. The file is unsorted and can't be fully loaded into memory. Implement a validate(user_id, password) function. First, build a streaming solution that scans lines sequentially with constant memory and stops as soon as the user is found. Then propose an offline indexing strategy that maps user IDs to byte offsets so future lookups are sublinear. Walk through trade-offs, encoding/error handling, memory-mapped vs buffered I/O, and time and space complexity for both approaches.

System DesignTechnical Trade-offsAlgorithms & Data Structures

Author's notes

This one had more surface area than I expected going in.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design a streaming solution that scans the file line-by-line with constant memory, parsing each line to extract user_id, salt, and hash, and comparing the computed hash of the provided password with the stored hash. Next, propose an offline indexing strategy that builds a mapping from user_id to byte offset, enabling sublinear lookups via binary search or hash table. Finally, discuss trade-offs, encoding/error handling, I/O methods, and complexity for both approaches.

Pro tip: Emphasize the importance of using a constant-time comparison function to prevent timing attacks, and mention that the index should be built once and stored persistently to avoid rebuilding on every startup.

1. Clarify requirements and constraints

Ask about file size, expected query frequency, security requirements, and whether the file can be modified. Confirm that memory is limited and that the file is unsorted.

2. Design streaming solution

Describe reading the file line-by-line using a buffered reader, parsing each line to extract user_id, salt, and hash. For each line, if user_id matches, compute the hash of the provided password with the salt and compare using a constant-time function. Stop early if found.

3. Propose offline indexing strategy

Explain building an index that maps user_id to byte offset. This can be done by scanning the file once, recording the offset of each line, and storing the mapping in a sorted structure (e.g., sorted array or hash table) on disk or in memory if small enough. For lookups, use binary search on the sorted index or direct hash lookup, then seek to the offset and read the line.

4. Discuss trade-offs and implementation details

Compare streaming vs indexing in terms of time/space complexity, memory usage, and build time. Cover encoding (e.g., UTF-8, ASCII), error handling (malformed lines, missing users), and I/O methods (buffered vs memory-mapped). Mention that memory-mapped I/O can be efficient for random access but may have page fault overhead.

5. Summarize complexity and conclude

State time and space complexity: streaming is O(n) time, O(1) space; indexing build is O(n) time and O(n) space (or O(u) for u users), lookup is O(log u) with binary search or O(1) with hash table, plus O(1) to read the line. Conclude with recommendations based on use case.

Key Points to Mention

Constant memory streaming: read line-by-line, parse, compare, and stop early.
Offline indexing: build user_id to byte offset mapping for sublinear lookups.
Trade-offs: streaming is simple but O(n) per lookup; indexing requires upfront build but faster subsequent lookups.
Encoding and error handling: handle malformed lines, missing users, and use constant-time hash comparison.
I/O methods: buffered I/O for sequential reads, memory-mapped I/O for random access with trade-offs.
Time and space complexity: streaming O(n) time, O(1) space; indexing O(n) build, O(log u) or O(1) lookup, O(u) space.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.