To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
We’ve all seen the memes,
Regex bad. Regex hard to read WAWAWA…(trust me this is related to FSMs)
What if I told you that Regex isn’t that bad, you just haven’t learned it correctly? This is a pity because Regexs are one of the most important Tools in a Software Engineers’ arsenal. I have used them extensively in my journey to achieve great performance at a cheap cost. To understand Regex, it is important to take a step back and learn about their little brother, Finite State Machines. Which is what we will be covering today.
Hope you’re ready for this because this going to be a great time.
Key Points
What is a Finite State Machine- I could give you the technical definition, but that wouldn’t really help anyone. I like to think of FSMs as a very specific variant of directed graphs. The Nodes are the possible states of your program. The edges (transition conditions) tell you which states are reachable from a current state.
Where would FSMs be good- FSMs are fantastic in any place where you can spot a few rules to filter your input by. For eg., I once used FSMs (Regex) to filter through large amounts of text to get a much smaller corpus, on which I ran more expensive AI algorithms. You can also use FSMs in cases where your system is defined by a set of rules.
Components of an FSM- A Finite State Machine requires 5 elements-
Don’t be scared of the Math terms and Greek Letters. It’s a lot more intuitive than it looks. The Alphabet is just the input domain i.e the kinds of inputs that your Machine will process. S0 is just the state your program will start in (like how your computer starts on the desktop). The state transitions simply tell you how what the next state for your program will be, given the current state and an input symbol. The final states are merely the states that your machine will accept as ‘Finished’/’Acceptable’.
Getting good with FSMs- Take it slow and steady. The reason that people struggle with Regex/FSMs is that half the time they can’t even spot them. Other times they get impatient and don’t work through constructing the machines in a calm and methodical manner.
My first suggestion is to work on the theoretical aspect. I’m linking a fantastic intro to FSMs by a YouTube channel called Neso Academy below. They have a lot of great videos on Theoretical Computer Science. Go over their content. You can also Google more questions involving FSMs and such concepts to get better.
Coding FSMs- You will also need to get better at programming FSMs. This is not super hard. As you work on the theoretical FSM questions, also create end-to-end codes simulating them. The code should be self-contained, starting from the correct initial starting State, and terminating the program when you hit accepting/final states. Take a look at this coding interview solution for an example.
A special Challenge- You’re surrounded by systems/processes that can be modeled by FSMs. See if you can do that, and send me your models. We’ll create a few community posts with that. Try to get as creative as you can. Bonus points if you can also provide code (in a language of your choice) to simulate it. Super impressive ones will get 1 month of this newsletter, completely free (no credit card information needed).
I look forward to seeing how creative y’all can be. Enjoy the video below. Neso Academy is a goldmine for Computer Science concepts. Would recommend checking them out.
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 50% off for upto a whole year.
This is a limited-time offer, that I’m running to celebrate my almost 50 questions completed. Take advantage of it by clicking the button above.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Math Mondays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75