Skip to main content
All Questions

Implement Trie

Medium

Design a data structure that efficiently stores and retrieves strings. Specifically, implement a Trie (Prefix Tree) with the following operations:

  • insert(String word): Inserts a string word into the trie.
  • search(String word): Returns true if the string word is present in the trie (i.e., was inserted before), and false otherwise.
  • startsWith(String prefix): Returns true if there is any string in the trie that starts with the given prefix, and false otherwise.

Example

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

Constraints

  • All inputs are guaranteed to be lowercase English letters (a-z).
  • The length of the input string is in the range [1, 2000].
  • The total number of calls to insert, search, and startsWith is at most 3 * 10^4.

Interview experiences

4 shared
Amazon · a month ago
"In DSA it was focusing on Design DSA style problem, then i have HLD and LLD interviews. Design DSA: Implement Trie for recent searches usecase LLD: Bookmyshow style ticket booking system HLD: Design Link preview feature, similar to what's found in Slack or Whatsapp"
Software Engineer · Senior / L5
R
RBC Capital Markets · 4 months ago
"It was an easy interview, first is the introductions, then they give you about 15-20 mintues to solve the valid parentheses question. Then the rest is behavioural"
Software Engineer · Intern
F
Fresh Prep · a year ago
"The interview process for the Full Stack Developer role consisted of a take-home assessment followed by a final interview round. The take-home focused on practical software development and gave me an opportunity to demonstrate my coding approach, problem-solving skills, and ability to structure a solution independently. The final interview covered a mix of computer science fundamentals, technical problem-solving, and questions about my previous development experience. We discussed topics such as data structures and algorithms, object-oriented programming, databases, APIs, and general software engineering concepts. There were also questions about projects I had worked on and the technical decisions I made. Overall, the process was fairly well structured and provided a good balance between practical coding and theoretical knowledge. The interviewers were professional, and the final round allowed me to explain my reasoning and discuss my experience in more depth."
Software Engineer · Entry Level / L3
Goldman Sachs · a year ago
"It was overall good experience. Except you have 4 rounds continuously. What went well? Asking them solid questions and being able to come up with a working solution. What didn’t go well? Not preparing enough for system design as a DevOps Engineer."
DevOps · Mid Level / L4

Related courses

Course

Machine Learning Engineer Interview Prep

Land your dream machine learning role at Meta, Google, Amazon, Apple, Microsoft, Nvidia, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Explore ML system design, core concepts, coding, behavioral interviews, and more.

Course

Data Engineering Interview Prep

Land your dream data engineering role at Meta, Google, Amazon, Microsoft, Walmart, DoorDash, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Practice data modeling, pipeline design, SQL, coding, behavioral interviews, and more.