# Implement Trie — coding interview question

Aced (formerly Exponent) publishes a public search API over its indexed pages; the guide is at https://www.aced.io/agents/agent-access.

Source: https://www.aced.io/questions/3441/implement-trie
Source observed: 2026-11-04T22:49:39.484Z
Last checked: 2026-11-04T22:49:39.484+00:00
Indexed: 2026-11-06T20:55:46.61+00:00

---

# Implement Trie

**Difficulty:** Medium  
**Category:** Data Structures & Algorithms; Coding  
**Reported last asked:** 15 days ago  
**Interview experiences:** 26+ interviews are associated with this question.  
**Roles:** Software Engineer, DevOps, Data Engineer, Machine Learning Engineer  
**Companies:** Amazon, Fresh Prep, Goldman Sachs, Apple, Oracle, Meta

We provide this coding interview question for designing a data structure that efficiently stores and retrieves strings. Implement a **Trie**, also called a prefix tree, with these operations:

- `insert(String word)`: Insert `word` into the trie.
- `search(String word)`: Return `true` when `word` is present because it was inserted previously; otherwise return `false`.
- `startsWith(String prefix)`: Return `true` when at least one stored string begins with `prefix`; otherwise return `false`.

A Trie is a tree-like structure in which each node represents one character. Searching traverses the relevant character branches, making the structure suitable for auto-completion, dictionary lookups, and spell checking.

## Example

```text
insert("apple")
search("apple") -> true
search("app") -> false
startsWith("app") -> true
insert("app")
search("app") -> true
```

## Constraints

- All inputs contain only lowercase English letters (`a-z`).
- Each input string has length `[1, 2000]`.
- The total number of calls to `insert`, `search`, and `startsWith` is at most `3 * 10^4`.

## Interview experiences

We have three shared interview experiences connected to this question:

- [Amazon — Software Engineer, Senior / L5](https://www.aced.io/experiences/amazon-senior-software-engineer-interview-4930a7), 15 days ago: the contributor described a DSA design problem involving Implement Trie for a recent-searches use case, followed by HLD and LLD interviews. The same interview included a BookMyShow-style ticket-booking design and a link-preview feature similar to Slack or WhatsApp.
- [Fresh Prep — Software Engineer, Entry Level / L3](https://www.aced.io/experiences/fresh-prep-software-engineer-interview-9d2dd8), a year ago: the contributor described a take-home assessment followed by a final interview covering computer-science fundamentals, technical problem solving, data structures and algorithms, object-oriented programming, databases, APIs, prior projects, and technical decisions.
- [Goldman Sachs — DevOps, Mid Level / L4](https://www.aced.io/experiences/goldman-sachs-devops-interview-c7acbc), a year ago: the contributor described four continuous rounds and noted that producing a working solution and asking solid questions went well; insufficient system-design preparation was a difficulty.

## Related questions

- [Implement mutex](https://www.aced.io/questions/7283/implement-mutex)
- [Implement DFS traversal.](https://www.aced.io/questions/7314/implement-dfs-traversal-algorithm)
- [Implement BFS traversal.](https://www.aced.io/questions/6639/implement-bfs-graph-traversal)

## Related courses

### [Machine Learning Engineer Interview Prep](https://www.aced.io/courses/ml-engineer)

![Machine Learning Engineer Interview Prep](https://images.ctfassets.net/x78yjrjc11pq/6UfkHxUyLQVfDHSfLNQtWa/1be1539a65b4f6f15201f5b573c0a578/ML_Engineer_Interview_Prep_Course.jpeg?w=800&h=800&fm=webp&q=75)

We prepare candidates for machine-learning roles at Meta, Google, Amazon, Apple, Microsoft, Nvidia, and other top companies through mock interviews, frameworks, and advice from senior candidates. Topics include ML system design, core concepts, coding, and behavioral interviews.

### [Data Engineering Interview Prep](https://www.aced.io/courses/data-engineering)

![Data Engineering Interview Prep](https://images.ctfassets.net/x78yjrjc11pq/5XoOCgXlGqN2fa1zaroNWd/9a2e23df48a212bc00d352873feb2d6a/Data_Engineer_Interview_Prep_Hero_Image.jpg?w=800&h=800&fm=webp&q=75)

We prepare candidates for data-engineering roles at Meta, Google, Amazon, Microsoft, Walmart, DoorDash, and other top companies. Topics include data modeling, pipeline design, SQL, coding, and behavioral interviews.

## Practice controls

The question includes Question, Solution, and Community tabs. The coding workspace includes Editor and Share views, plus Output, Test Results, and Console tabs. Sign-up is required to run code: [Sign up to run code](https://www.aced.io/signup?src=lesson).

[Upgrade for detailed company stats](https://www.aced.io/upgrade?src=questions)

### Aced interview-preparation areas

We provide interview courses and practice resources covering Product Management, Forward Deployed Engineering, Engineering Management, Software Engineering, System Design, Data Science, Machine Learning, Data Engineering, AI Engineering, Investment Banking, Generative AI, Security Engineer, TPM, Solutions Architect, UX / Product Design, and BizOps & Strategy. We also provide Loops, Experiences, Questions, Practice, coaching, resume review, salary negotiation, job referrals, resources, and related services.

---

[Read this page’s summary](https://www.aced.io/agents/api/public/v1/page-tldr?url=https%3A%2F%2Fwww.aced.io%2Fquestions%2F3441%2Fimplement-trie&trace=t_679ff9ab98f3)

## Ask a follow-up about this page

Need a more specific answer? Ask the exact question you have. It returns a fresh, cited answer from Aced (formerly Exponent)’s knowledge base. No account or API key required.

Open this URL with your own question, URL-encoded. Include your question in q. All research inputs are optional; no account or setup.

`GET https://www.aced.io/agents/agent/faq?q={question}&trace=t_679ff9ab98f3`

[Tool guide and examples](https://www.aced.io/agents/agent-access) · [OpenAPI](https://www.aced.io/agents/api/public/v1/openapi.json) · [Page TLDR form](https://www.aced.io/agents/agent-tools/page-tldr?url=https%3A%2F%2Fwww.aced.io%2Fquestions%2F3441%2Fimplement-trie). Opening a form does not execute a tool.