News for hackers. Stuff that matters.
Re:Triplebyte expands its recruiting platform beyond YC, sig... by thaumasiotes on Friday March 10, 2017 @12:24AM (#13836587)
The 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.

Re:Triplebyte expands its recruiting platform beyond YC, sig... by bogomipz on Friday March 10, 2017 @08:15AM (#13838304)
Yeah 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?

Re:Triplebyte expands its recruiting platform beyond YC, sig... by thaumasiotes on Friday March 10, 2017 @11:27AM (#13839766)
I used the dragon book (2nd edition) - 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.

Re:Triplebyte expands its recruiting platform beyond YC, sig... by bogomipz on Friday March 10, 2017 @03:13PM (#13841705)
Thanks
Re:Triplebyte expands its recruiting platform beyond YC, sig... by kevinclancy on Friday March 10, 2017 @11:10AM (#13839630)
Not sure what book the above poster used, but Sipser is an excellent book for learning about DFAs.