Re:A Brutal Look at Balanced Parentheses, Computing Machines...
by skybrian on Friday February 22, 2019 @03:05PM
(#19228648)
Yes, agreed. But it does show another pitfall when it comes to using a degenerate case as an interview question: someone who doesn't know anything about parsing or stacks might solve it easily if they have a different mindset. On the other hand, half-remembering something from school could really mess you up.
[ Parent
| on HN ]
Re:A Brutal Look at Balanced Parentheses, Computing Machines...
by braythwayt on Friday February 22, 2019 @03:08PM
(#19228671)
A typical interview along these lines will get the candidate to the "single balanced parentheses" solution, then throw in multiple types of parentheses.
The whole script goes sideways if the candidates whips Perl or Ruby or whatever out, and provides a recursive regex.
Re:A Brutal Look at Balanced Parentheses, Computing Machines...
by spc476 on Saturday February 23, 2019 @01:52AM
(#19232101)
Are you talking about the interview script, or the programming script? And what if the interviewee brings out Lua and LPEG [1]:
local lpeg = require "lpeg"
local balance = lpeg.Cmt(
lpeg.P {
(
(lpeg.P(1) - lpeg.S"()[]{}<>")
+ lpeg.P"(" * lpeg.V(1) * lpeg.P")"
+ lpeg.P"{" * lpeg.V(1) * lpeg.P"}"
+ lpeg.P"[" * lpeg.V(1) * lpeg.P"]"
+ lpeg.P"<" * lpeg.V(1) * lpeg.P">"
)^0
},
function(subject,position,capture)
return position,position > #subject
end
)
print(balance:match "") -- true
print(balance:match "()") -- true
print(balance:match "((()))") -- true
print(balance:match "()()()") -- true
print(balance:match "()(())") -- true
print(balance:match "(") -- false
print(balance:match "(()") -- false
print(balance:match "({)}") -- false
print(balance:match "({})") -- true
print(balance:match "()))((") -- false
[1] http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html
Re:A Brutal Look at Balanced Parentheses, Computing Machines...
by a1369209993 on Friday February 22, 2019 @08:28PM
(#19230956)
> the candidates whips Perl or Ruby or whatever out
My first thought for is_balanced_parens was something like:
while _!="" (s'()''g or reject)
#* multiple types of parentheses *#
while _!="" (s'()''g or s'{}''g or reject)