3 ms·
>"Also, there was a request to derive a formal proof while Ammon watched" You were asked to drive a formal proof? Why exactly? How often is that asked at an ac
by bogomipz 10y ago
>"Also, there was a request to derive a formal proof while Ammon watched"
You were asked to drive a formal proof? Why exactly? How often is that asked at an actual tech interview?
- thaumasiotes 10y agoThe exercise was to write a regex parser. He asked me about worst-case behavior, which is an exponential number of states. He asked for a regex with worst-case behavior, which I could provide, mentioning that I knew this because the textbook I used for the project pointed it out. Behold, a worst-case regex template: (a|b)*a(a|b)^n This requires at least 2^n states in the DFA. He asked me to prove that 2^n states were required while he waited. I didn't know the proof and wasn't comfortable trying to produce it while being watched. There's no upper limit to how long producing a proof might take.
- bogomipz 10y agoYeah thats really awkward and an odd thing to ask a candidate to do while you wait. I will be sure to avoid these people. Out of curiosity what book is that DFA problem from?
- kevinclancy 10y agoNot sure what book the above poster used, but Sipser is an excellent book for learning about DFAs.
- thaumasiotes 10y agoI used the dragon book (2nd edition) - https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ https://www.amazon.com/Compilers-Principles-Techniques-Tools... That proof isn't a problem in the book; it's mentioned, with a hint for those inclined to derive it themselves, in the running text.
- bogomipz 10y agoThanks