Repeat Code With LeetCode — Valid Parentheses
If you add a colon and turn your face sideways, it looks like a smiley face!!!
The real motivation here was to start using a programming language other than C++, starting with something easy, but this easy problem was “hard” enough for me that I decided to cover it again in two or three parts. This will be the C++ version.
I actually encountered it before in an interview for a series C startup, and I passed, with the two caveats that I had 15 minutes but only had to explain how I would solve it. If I remember correctly, our conversation went something like this:
Me: I would use a stack. I would push to the stack every time I have an opening character, and pop from the stack every time I find a corresponding closing character
Interviewer: Fine. Let’s say you had an opening curly brace. Then you had a closing curly brace. How would you know what maps to what?
Me: Well, I suppose I could use an unordered map. It doesn’t have to be an unordered map, though…it could just be a vector of structs
This problem is basically a perfect use case for a stack, which you can think of as a….
…uh…please don’t kill me…
…a stack. A stack is a stack. It is best characterized as last in, first out, but even that takes a bit away from the metaphor. Think of a stack of plates, as Wikipedia shows us. If you want to add to a stack, you put something at the top. If you want to take elements out of the stack, you have to take from the top as well. You also have a “peek” operation, which gives you the ability to look at the top element.
Instead of just closing with “use a stack and you are good,” I thought I would share with you some of my struggles with this problem.
The Problem
Difficulty: Easy
Skills Required: Stacks
Problem Description: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
The (Rough) Solution
The above is some code I wrote that LeetCode accepted, with all of its comments and print statement glory. Here are a few things that I was thinking about:
First of all, my first implementation today failed because I did not do any kind of verification. If I saw an opening character I would push, and if I saw a closing character I would pop. This would fail on something like “[)”, as all the code would check is that there was an opening element, followed by a closing one.
Second, I did not think to use a hashmap (or unordered_map, which is a close approximation of a hashmap). Instead, I wrote a helper function that simply returned a corresponding closing character. This effectively achieved the same thing, but I can’t imagine anyone including that in a book solution.
Next were edge cases. If the size is 1, return false. If it begins with a closing character, return false.
Finally, I did some debugging (thought maybe my helper function was failing) until arriving at line 61. If you fail to obtain the correct closing character for the one you are checking, throw it out. The entire string is false.
The Cleaner Solution
The code above is a little easier to read. I wrote it some time ago. I saw it was doing a % 2 at the beginning, which I found clever, prompting me to wonder if I stole the code from someone else. Then I saw the code was using the stupid variable name “thisChar,” so it does look like my work.
To paraphrase the LeetCode explanation, the algorithm is:
- Find an opening bracket/character, push it to stack
- Find a closing bracket/character, check top element of stack. If they are the same type (as in a pair, like ()), pop off stack and keep processing. Otherwise you reject the entire thing and return false
Closing Thoughts
So…a few thoughts.
First of all, NeetCode is leaving Google to return to coding interview videos full-time. This is a good thing for us, but I cannot help but feel disappointed. The Software Engineer Prophecy wrote that a Chosen One would obtain a job at Google, then change their interview process. I may have been misreading the prophecy, though.
Second, another programming language would be useful. I have had more than a few experiences of an interviewer expecting a specific programming language.
This could double with my other blog, allowing me to gain and demonstrate basic competencies in other programming languages.
