Unbalanced Expression

For the most part, interviews have always gone easy for me which is curious because I have an almost uncontrollable fear of social settings. I'm generally so consumed by the anticipation of the event that when the meeting eventually takes place my technical reflexes take over. This is both a blessing and a curse: technical questions and topics are not a problem when in this state but a vague question about personality and past experiences tends toward meaningless rambling about nonsense. Social prowess notwithstanding I've come out on top more times than not in these adventures... until recently.

I interviewed at a startup company where there were two technical questions that I had trouble with. Incidentally, the 'who we are' and 'who are you' portions actually went much better than usual - I do love irony. In either case, the first question was related to querying billions of bytes of data to provide quasi real-time behavior to users. The question was intentionally vague leaving much open to interpretation and I pared it down as much as my experience supported: what is unique in the data, what are the time constraints, what about false negatives/positives, caching, backend structure, and so on. In the end I just came to the conclusion that I could not provide the design details that they were looking for and said so. This took about fifteen minutes and they did not seem too discouraged with my ultimate conclusion.

The second question was direct and significantly less open-ended - this is the part that really threw me for a loop. The question was this: 'Solve the following expression using any language you want'.

(((1+3)*7)+((((3-1)/(1+3))*8)))

Me: "Use eval in ruby or python"
Them: "Good. You can't use eval"
Me: "I'm not too familiar, but a Lisp interpreter?"
Them: ... confused, unexpected looks ...
Me: "Nah, that is incorrect Lisp format, never mind"
Them: "Yeah, that's not exactly proper Lisp format. What else?"

I asked if the expression would always be balanced and that we only had to deal with binary operators. The answer was yes on both counts so I started drawing stacks on the whiteboard roughing out what would work. Eventually, I presented the following Ruby solution:

---

$ops = []
$vars = []

OPS = ['(', ')', '+', '-', '/', '*']

def push_op op
    $ops.push op
    if op == ')'
        $ops.pop
        v2 = $vars.pop
        v1 = $vars.pop
        op = $ops.pop
        v = eval("#{v1} #{op} #{v2}")
        $vars.push v
        $ops.pop
    end
end 

def push_var v
    $vars.push v
end

$stdin.gets.chomp.split(//).each do |c|
    if OPS.include? c
        push_op c
    else 
        push_var c
    end
end
 
puts $vars.pop

---

(the eval part was agreed to be hand-waving for a more complex case statement)

The immediate reply was: "Nope. You've missed a fundamental flaw for this class of equations". So I went back and did the entire equation by hand and realized that the solution would not support the unary operation of (). That is, something like ((1+2)) would end up with my solution popping from an empty stack. So, I injected the fix and claimed that the problem was solved for balanced and valid equations. Here is the fix.

---

def push_op op
    $ops.push op
    if op == ')'
        $ops.pop
        if $ops[-1] == '('
            $ops.pop
            return
        end
        v2 = $vars.pop
        v1 = $vars.pop

---

Again, the reply was that I was missing the real fundamental problem with this type of equation. I asked if this particular solution exhibited the flaw they were talking about and they claimed it did. I was stuck at that point and ultimately left the interview with the sense that I failed some basic understanding of mathematical equations. When I got home, I typed up my solution and ran the input they provided and the output was exactly as I had expected (the same as an eval call). I wrote my follow-up email to the company thanking them for the interview but I also attached my script with sample run indicating that I stood by my solution from that afternoon.

What do you think... did I missing something obvious or were they looking for my ability to stand my ground when I had the best solution? They never conceded that I actually had the correct answer; in fact, they indicated that I should take it home and consider what I was missing.

So, yeah. I'm still a bit off-balance from that experience.