Instacart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Did a coding round for a Software Engineer role at Instacart. The whole thing was basically one big object-oriented design problem that kept growing in scope. More layers than I expected for what looked like a straightforward file system question.

Questions Asked (1)

Design an in-memory file storage service that supports adding files, copying files, querying file sizes, and searching files by prefix and suffix. Files are identified by a full path string and have an integer size. Later parts add user ownership with storage capacity limits and a capacity update operation that evicts files when needed.

System DesignAlgorithms & Data StructuresData Modeling

Author's notes

This started simple enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then design a data model that supports efficient operations for each API. Use a trie for prefix search and a suffix trie or reversed trie for suffix search, and for the eviction part, maintain a min-heap or ordered structure to track files by size or timestamp. Discuss trade-offs and potential optimizations.

Pro tip: Demonstrate awareness of real-world constraints: mention that in-memory storage is limited, so eviction policies must be efficient and consider concurrency if multiple users access the service. Also, discuss how to handle path normalization and duplicate file names.

1. Clarify Requirements and Scope

Ask questions to understand expected scale, file size ranges, frequency of operations, and whether paths are case-sensitive. Confirm if eviction should be based on file size, insertion time, or other criteria.

2. Design Core Data Structures

Propose a hash map for O(1) file lookup by path, a trie for prefix search, and a reversed trie for suffix search. For eviction, consider a min-heap keyed by size or a balanced BST for ordered access.

3. Define APIs and Operations

Outline methods for addFile(path, size), copyFile(src, dest), getSize(path), searchByPrefix(prefix), searchBySuffix(suffix), and later addUser(userId, capacity), updateCapacity(userId, newCapacity). Explain how each operation interacts with the data structures.

4. Handle Eviction and Capacity Management

Describe how to track total storage per user and trigger eviction when capacity is exceeded. Discuss eviction policy (e.g., LRU, largest files first) and how to efficiently find and remove files to free space.

5. Discuss Trade-offs and Optimizations

Compare alternative approaches (e.g., suffix array vs. reversed trie) and their time/space complexities. Mention potential concurrency control, persistence, and scalability considerations.

Key Points to Mention

Use of trie for efficient prefix search and reversed trie for suffix search, with O(L) time where L is query length.
Hash map for O(1) file lookup by full path, ensuring fast add, copy, and size queries.
Eviction strategy: min-heap or balanced BST to track files by size or timestamp, enabling efficient removal when capacity is exceeded.
Handling of user ownership: per-user storage tracking and capacity limits, with eviction scoped to the user's files.
Trade-offs between different data structures: e.g., trie vs. hash map for prefix search, and heap vs. sorted list for eviction.
Considerations for concurrency, path normalization, and potential memory overhead of maintaining multiple indexes.

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