You are using an outdated browser. Please update your browser for a better user experience.

Spell Check Design Question

(This above is Tamil btw, couldn't find turkish example in time :( )

Your a software engineer working on Turkish spell checking software for Huawei phones. Your team currently uses a bit array to store the entire Turkish language's lexicon. This bit array is queried to check if a given word exists in the Turkish lexicon. Your job is to improve the space and time complexity for its querying algorithm.

Quesion 1: What is the current time and space complexity of using this bit array?

Question 2: Why is your current team's approach bad?

Question 3: Design a data structure that improves your teams querying algorithm

Question 4: Why is using a hashmap not feasible?

Question 5: What is the disadvantage of the data structure you used?

This is a design question. Your being tested on your ability to analyze a real world problem and articulate your thought process. Even if you don't have an inital idea off the bat, your thought process is most important. If you get completely stuck, search for the information and be able to readily adapt to new information

Hint 1: A hashmap isn't the answer but its a good start

Hint 2: Try to figure this out on your own at first, but if your stuck look up the specific data structure needed (its very easy to look up). Don't copy the code, but just read the wikipedia entry and try to write the code yourself

Hint 3: Using a bit array is the right idea. But think of inefficencies. Do we have to store every possible turkish word? Can we even store every word? What are alternatives ways to represent this lexicon?

Extra info :

  • Turkish is an agglutinative language which means you can form infinite words by composing numerous inflections.
  • Phones are sensitive to disk space and latency because it creates bad user experiences