Functional Requirements (FRs)

• You have a search engine that gives results based on the search queries being done by the users. You need to build an autocomplete system to help users with query suggestions. Your system will get access to the actual queries being done by users through a data stream. This data should be used to power the suggestions.
• The autocomplete system should return the top 10 query suggestions whenever a user starts typing.
• Prefix-based autocomplete: All the query suggestions should have the keyword typed by the user as their prefix.
• The top suggestions should be determined based on the popularity of the searches done by the user.
• Assume all search queries are done using lowercase English alphabets and there are no special characters or digits.

Non-Functional Requirements (NFRs)

• Daily-active users (DAU): 100M.
• Requests to autocomplete system: 20x of DAU.
• Latency should be very low.
• The suggestions can be stale by at most an hour.
• The system should be highly available and scalable.

How to solve the problem?

• General:
  • Note everything you are discussing or thinking of in the text editor.
  • Draw everything that your interviewer needs to visualize on the whiteboard.
  • Be cognizant of how much time you've left and pace yourself (as required) so as to cover things that the interviewer wants to see you do based on the FRs and NFRs that were finalized.
• Step 1: Think about the functional and non-functional requirements.
  • In an interview, the FRs and NFRs won't be provided.
  • You need to have a discussion with your interviewer to finalize these.
  • This step should take around 10-15 mins.
• Step 2: For senior developers:
  • Note down the metric estimations.
  • The metrics would generally include read and write QPS, latency, storage, memory, bandwidth, etc.
• Step 3: (Optional) Note down the APIs that you would need to support the functional requirements. Do it only if you've time.
• Step 4: High-level design:
  • Propose and draw a very high-level design.
  • This design might have flaws and bottlenecks.
  • This design should just give a very high-level idea of the overall system.
• Step 5: Deep-dive into the design:
  • Come up with the bottlenecks in the initial design and iteratively come up with a better design addressing the bottlenecks and trade-offs.
  • Update the design on the whiteboard as you are solving the bottlenecks.
  • Try to come up with multiple solutions for certain bottlenecks and mention the trade-offs and the reasons why you are picking up one over the others. If you don't have time, just mention them but don't note them.
  • If the interviewer asks, mention the DB schema as well. While practicing, make sure to add the DB schema.
• Step 6: Overview:
  • Try to give an overview of the entire design specifically talking about the major decisions taken.