> The second was to write a recursive permutation generator using dynamic programming which is no easy task. I got totally stumped in the moment by that one. At the end of the interview I asked the interviewer “This problem seems a little steep for a phone interview. Do you often write recursive algorithms at Payment Processing Company?” He replied “No, we don’t use recursion.” “How about permutations? When have you used those?” He answered “Our algorithms have no need for permutations. Most of the engineers here work on user interfaces and infrastructure.”
This is absolutely hilarious, and has happened to me a bunch of times interviewing at large corps. Although I wish I had the balls to do what Jared does here, which is ask the interviewer if they ever even _used_ dynamic programming on the job.
Like, I get that some jobs are algorithms intensive. I've worked in such jobs myself. On the job, I had a lot of resources to help me - access to textbooks like CLRS and Wikipedia, so that building an algorithm and coming up with it's big O was mostly straightforward. But we've never had the CEO come and say "I need a O(n) algorithm stat for this problem _text dump of hard DP problem_".