Problem
This problem was asked by Nest.
Create a basic sentence checker that takes in a stream of characters and determines whether they form valid sentences. If a sentence is valid, the program should print it out.
We can consider a sentence valid if it conforms to the following rules:
The sentence must start with a capital letter, followed by a lowercase letter or a space.
All other characters must be lowercase letters, separators (
,
,;
,:
) or terminal marks (.
,?
,!
,‽
).There must be a single space between each word.
The sentence must end with a terminal mark immediately following a word.
Step 1: Understand the problem
One of the biggest mistakes that people make in this kind of problem is to rush in. The premise of this problem seems simple enough, so they jump in without considering the nuance. What is the nuance here?
Consider the input. It’s a stream. What does this mean for your problem:
You will only get your input one step at a time. You can’t get 3 chars at once as you would with a string
Similarly, new input will overwrite the old one. Since we want to track the sentence seen so far, we want to remember this.
The more advanced people might have caught this immediately. However, this kind of framing is helpful to you as well. Remember, communication is one of the major aspects you’re evaluated in during your interviews. By explicitly calling out this observation you will show off both your communication and technical knowledge. For interviews, follow the mantra: If you see something, say something.
Step 2: Identity methodology
We have to identify how to approach a problem. Here is everything we know so far:
We get our input one character at a time
Our sentence becomes valid or invalid based on how the new character interacts with the input we have seen so far.
There are multiple possible ways for the rules to interact with each other. For example, we might have a space or a lowercase after an uppercase letter.
Depending on the current character and state, a different set of rules will apply.
This should help you notice something. We need some way to track what kind of input we had last. With that, we can determine what state given our new input. Is there a system we can use to effectively capture this constant state changing? Turns out there is. And using that will help us solve this problem easily.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.