After learning ArrayLists and LinkedLists I started learning about another fundamental data structure from the Code with Mosh Data Structures & Algorithms Course. I highly recommend this course for anyone who wants to ace their coding interview.
This particular structure is called a stack, where basically it operates in a FILO algorithm: the first object you put in, the last one it is removed(First In, Last Out). It is sort of like one of those tennis ball cans where you can only remove the items from the top.
Stacks are very useful when you want to implement something about the order of strings and or numbers. For example, you may want to try to code a method that takes a particular string and returns the string, except in reverse order.
These past few days I encountered this interview question where you have to code a method that takes a string and checks if the string is balanced or not. All that matters is the order and the content of the brackets. For example, “[]”, “[<a>b]” and “[][]{<>}” are all balanced and “[“, “[<]>” and “[]][]” are all not balanced.
I started by implementing a method that returns whether it is balanced for only a particular bracket. It’s very simple: convert the string into a character array, iterate over the array and push every opening bracket character into the stack, and when encountered with a closing bracket check pop the outmost character on the stack. If there are no more characters, then set the boolean IsBalanced to false. At the end of the for loop we check one more time, and if none of the if-statements report a false IsBalanced then it will be true.
I soon realized that doing the same algorithm for multiple types of brackets is essentially the same thing! This is a very important problem-solving strategy called relaxing a constraint: we remove a constraint in order to get a feel for a smaller type of problem. Once we solve that problem, we are able to tackle the actual, harder problem.
The algorithm indeed works, though I used four if-loops to complete the method 😅
If you want to see my GitHub files for this question then here is the link: