The Technical Interview Question I Bombed
Posted by Kevin Tran on 2020-09-04
Identifying skills I need to work on
Valid Parenthesis.
This was the question I had for one of my technical interviews that I absolutely bombed. I realized that I needed to get better at algorithm problems after this. The unfortunate truth about the indutry is that whiteboarding and technical problems are still a huge part of the interview process. Although I don't think these accurately depict whether or not a candidate can actually do the job, in most cases.
These have been the bane of my job applying existence. I can build full stack web apps but I am terrible at whiteboarding. I have slowly started to try and get more comfortable but the wide range of questions that could possibly be asked is a large task. it is a bit hard to find where toeven start. But I'm trying. I want to document my process with this and hopefully talking about the solutions to some problems I practice will help me get a better understanding.
Here are the instructions for this particular problem, and I will dissect what everything is doing line by line in a way that makes sense to me and maybe others in the future.
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "(]"
Output: false
And here is the solution:
var isValid = function(s) {
let stack = []
let map = {
'[': ']',
'(': ')',
'{': '}'
}
for (let i = 0; i < s.length; i++) {
let c = s[i]
if (map[c]) {
stack.push(map[c])
} else if (c !== stack.pop()) {
return false
}
}
return !stack.length
};
We start by declaring the function and the parameter. Next we declare a variable to hold parenthesis which we add and remove from, aka our stack. We also declare a variable of a map/hash of the key/value pairs of parenthesis that we will use to compare as we are iterating through the string.
var isValid = function(s) {
let stack = []
let map = {
'[': ']',
'(': ')',
'{': '}'
}
We will then start a manual for loop, starting at the beginning of the string, for as long as i is less than the length of s, and increment by 1. Next to improve readability we will store s at the index of i (s[i]) into a variable c.
for (let i = 0; i < s.length; i++) {
let c = s[i]
The if statement we will check if the s value at index of i exists in the map as a key. If it does exist we will add that value to our stack.
if (map[c]) {
stack.push(map[c])
The else if will run if the s value at index of i does not exist. We will check if the s value at the index of i does not equal the removed last element of the stack. If they do not equal each it will return false for the inputted string.
} else if (c !== stack.pop()) {
return false
Finally we return the opposite of the length of the stack which is 0 so it will evaluate to true. If we get to this point it means that we have been able to successfully iterate through the entire string.
return !stack.length
I find that just finding answers for these types of problems don't help unless I actually break it down step by step. I hope that this breakdown has helped you as much as it helped me.