This blog is a part of my “15 days cheat sheet for hacking technical interviews at big tech companies”. In this blog, we are going to solve two coding interview questions using state machines. I hope these examples help you to understand the state machine problem-solving method as well as how powerful it is to solve the problems containing many complex cases.

Background:

A finite state machine (FSM) is an abstraction used to design algorithms. It maps a finite number of states to other states via transitions. A state machine can only be in one state at any given moment.

Steps to handle a coding interview question using FSM:

• Identify all types of input data.
• Identify all possible states for the FSM.
• Identify the valid transitions between states for given inputs.
• Draw the finite state machine diagram.
• Follow the FSM diagram to implement the algorithm.

Sample Interview questions:

Question 1: Implement atoi which converts a string to an integer.
Full description: https://leetcode.com/problems/string-to-integer-atoi/Example:" -42" => -42"4193 with words"=> 4193"words and 987" => 987

In this question, there are three types of input data we need to handle with: blank characters (space), sign characters (+ or -) and digit characters (0->9). We start with the initial state 1. For blank characters, the state is kept at 1, for sign characters we move to a state 2, for digit characters we move to a state 3. Continuing to identity the valid transitions in state 2 and 3, we have the following diagram.

With the diagram, we can come up with the following algorithm:

Problem 2: Validate if a given string can be interpreted as a decimal number.
Full description: https://leetcode.com/problems/valid-number/Example:"0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => true" -90e3 " => true" 1e" => false"e3" => false" 6e-1" => true" 99e2.5 " => false"53.5e93" => true" --6 " => false"-+3" => false"95a54e53" => false

The concerned input types are: blank characters (space), sign characters (+ or -), digit characters (0->9), eand .We start with the initial state 1 and expand to different states to build up the below FSM diagram.

If the input is ended in state 3, 5, 8 or 9, it is a valid number. The rest are middle states and they will give the False output.

The below is my implementation for the FSM diagram.

Conclusion

Using state machine helps to avoid so many nested if-else statements in your code and make the code much simpler.