Hacker News Reader

Comment by elteto | Hacker News Reader

Funny, I just went through a pre-screen assessment for one of the big ones and it was not one but _two_ DP problems. I could have probably come up with a slow solution using recursion and a bit more of time, but was given only 90 minutes. And I thought to myself, what exactly did they learn about _me_ after this exercise? Absolutely nothing, except that I can't solve DP problems on the spot. What a waste of time.

And the funny thing is, I work as an embedded developer and actually have to look up a topic or two from CLR at least once a year for work stuff (which is not very common). But DP? I've never needed it or used it. Why the emphasis in it then?

It feels a lot like software interviewing is just a bunch of rain dances and cargo culting and those that know the dance get through the hoop. I guess I'll have to order Elements of Rain Dancing from Amazon and get to practicing.

View on HN

I have yet to find an interview process that works better than RPI (Rob's Pairing Interview)[1] plus a day-in-the-life[2].

It gives both the employer and the candidate a chance to evaluate each other in context.

As an employer, you get to see how the candidate performs on two different real-world tasks, as well as how they interact with existing employees.

As an employee, you get to see what the company is really like to work with. No amount of whiteboarding can deliver that.

And at the end of the day, if that relationship feels good, both parties can choose to continue onwards towards full employment.

On the other hand, computer science trivia, by which I mean "implement Dijkstra or quicksort on a whiteboard", is a very poor means indeed by which to test for the ability to do real-world work in a real-world context.

Sure, it's valuable to have a broad understanding of algorithms and data structures. But whiteboard interviews on those types of problems only tests how well you would do competing in an ACM (Association for Computing Machinery) challenge, not how well you can deal with "here is a totally new-to-you problem that lacks a precise solution, now work productively with a team to solve it under the constraints of an operating business"

[1] https://builttoadapt.io/the-developer-hiring-process-is-brok...

[2] https://blog.jonrshar.pe/2016/Dec/05/pivotal-interviews.html

This is absolutely horrible.

"We believe coding is a social activity. In fact, we’re testing you to see how social you can be around coding."

It's worth understanding that Pivotal are hiring for a work environment that is almost entirely pair-programming, with teams of 2 to 8 engineers that rotate pairs almost every day. With that in mind, it's absolutely critical that Pivotal consider the social side of candidates while pairing.

That makes the process less suitable for other types of working environments.

It seems to me that "programming" there means glorified devops and the primary goal is a headcount of young compliant workers to show off to investors.

Probably activity is valued higher than progress.

They are certainly not looking for Knuth, who would likely fail the interview.

Yes, I think Pivotal are not looking for Knuth. Most companies don't need Knuth to be successful. That said, individual brilliance is not at odds with the other skills Pivotal are looking for.

The other statements don't ring true for me, but I understand it's just your viewpoint.

Unless your business goal is to advance computer science research, why would you want to hire Knuth and why would he want to work for you?

Why should he fail the interview? He's exceptional at talking through complex algorithms, and I've never heard of him being particularly anti-social.

Yeah, it would be okay if they were talking about coding at that specific organisation.

But the generalisation is just stupid.

How is it horrible?

I'd be absolutely drained and miserable after pair programming for an entire day. It's not an environment I would consider when looking for a job.

The best interview I ever had was similar, the largest chunk of it was me and my boss whiteboarding out a problem together, he had the marker. We were solving a problem that I'd be solving on the product, and that he had implemented on a previous project at a different employer. It just felt great.

These were my personal favourite as well. After both interviews I left feeling very enthusiastic about working at Pivotal. Both interviews felt extremely collaborative, and in both cases I actually _enjoyed_ my time, rather than feeling stressed as had happened in more "typical" interview processes.

For the day-in-the-life, I got to work on real problems that I would be solving, in the manner of working that Pivotal espouses, with the colleagues I would be working with, in the environment that I would be working in.

I think that these interviews are particularly suited to Pivotal's model of working (in particular the pair-programming) and are probably less suitable elsewhere.

Unrelated: I absolutely heart your username.

Stripe is similar, I found it so refreshing when I learned this: https://www.quora.com/What-is-the-engineering-interview-proc...

I feel your pain. I did exactly one dynamic programming algorithm (in the string matcher for Hyperscan) and was pretty inordinately pleased with myself for doing it, but we built dozens of algorithms in that project and that was the only case of DP that I recall.

But I expect to go into interviews and have people demand a different rain dance, now that everyone is talking about DP. They like mugging people with 'so big it has to be out of core' stuff, which is a good way of finding out who went to the right grad school algorithms course. :-)

I think I only saw DP-based algorithms 3 times in 12 years of working and reading open source code. Two of them were boring textbook-based implementations. One algorithm was original, and came from 80s - it's from Emacs source code, with comments like "do not touch", "here be dragons", etc.

Yes, the code involving the DP algorithm I put in had a bug in it - not from the DP algorithm itself but the assumptions that fed into it - which went undetected for some time because of how complex the DP algorithm was and how hard it was to evaluate. It only caused a minor performance quirk (not a actual semantic error) so was hard to find.

A cautionary tale about being overly clever-clever I suppose.

I don't do well on on the spot programming interviews. studying doesn't help. I can identify what needs to be done almost always, but implementing it in front of someone in only 40 mins? I need to practice that I guess. In the end as you said, I am constantly wondering what being able to regurgitate a memorized problem tells them about me (nothing) and why they don't care about my past experience, projects, successes and ratings. However, this is what every software interview is now

> I need to practice that I guess.

You are right about that, at least according to that article here:https://news.ycombinator.com/item?id=18942572

That guy trained on a well known website to solving minor coding issues and then (that's the important part) practised solving them in mock interviews to real persons.

Maybe that could help you.

Neither does this famous guy [1]. All these interviews do is waste a lot of time and generate a lot of false negatives.

You can practice all you want to get better, but no one in the corporate world is saying "I need you to code bubble sort, and I need in the next 45 minutes" and then proceeds to stand over your shoulder the entire time.

[1] https://twitter.com/dhh/status/834146806594433025

For big companies that have a ton of applicants, the false-negative rate probably doesn't matter all that much. They need a quick way to narrow the field.

As for wasting a lot of time, what more reliable method is there that takes less time than a leetcode-style problem? Surely there are more reliable methods, they probably don't take 30 minutes or less though.

I see a disturbing trend every time one of these articles comes up. It seems all these companies are doubling down on these absurd interviews. Making them harder and harder to get in.

DP is the epitome of how absurd these interviews have become and now people are getting asked 2 of these questions in pre-assestment stage.

I view it as industry moving the marker higher and higher for cult and loyalty marks and seeing if they get a steady manpower influx inline with their needs.

Jokes on them when they stop getting good devs and start getting good shortterm greedy puzzle solvers.

Hyuck hyuck hyuck

It's especially horrifying when you see all the people who devote their time to learning the rain dance instead of actually useful skills. People on /r/csMajors or /r/cscareerquestions who will say with a straight face, (well, as much as one can virtually) "you only need a data structures and algorithms class" or the generic "just grind leetcode" as a response for any perceived inadequacy. I wonder how many of these people make their job only to realize they have no experience and no interest in the actual content of their job.

I have a theory that dynamic programming problems have become more popular in part because the lower hanging fruit — reverse a linked list, is this a palindrome? — have become widely known and practiced via books and sites like hackerrank.

DP problems represent the next rung of the ladder, are somewhat less familiar. And most importantly, satisfy an interviewer’s possibly sadistic impulses by presenting a problem that has an easy 2^n solution. ;)

Sarcasm aside, I think this is just the inevitable result of the systemisation and gaming of the whiteboard interview.

Both of those have pretty easy recursive solutions. I don't think you are required to pass all the unit tests in order to move forward and doubt the most optimal DP solution was really required. I got similar (as in recursive with DP optimization possible) questions in my real interviews.

I completely agree with you that solving a DP problem for a job interview shows next to nothing about the candidate, that asking a DP problem as an interview problem is cargo culting/rain dancing/etc. On the other hand, I believe DP is fundamental algorithm that comes up again and again and is the equivalent in importance to the simplex method but for millennials and gen-[xyz]'ers.

Among the problems it solves are:

* Shortest path in a graph (aka Bellman-Ford's method) [1], A* path finding [2]

* Approximate string matching [3]

* Viterbi algorithm for hidden Markov models [4]

* Earley parser [5] for context free grammar parsing

* Dynamic time warping [6]

* Finding the base of a strong generating set for permutation groups [7]

I'm consistently surprised that DP crops up in so many places. While most people won't be required to implement the above list in their day-to-day programming life, it's quietly in the background as a fundamental algorithm.

Dynamic programming is one of the few algorithms that, in a "natural" way, reduces a problem that is naively exponential to one that is polynomial. For example, try counting where 2^T random walkers lands in an array starting from the middle after T time steps. Naively, this would require 'simulation' of 2^T but with DP you can do this in O(T^2) (assuming addition of atomic integer types is "free" and there's no overflow on count) using DP (by summing a 'count' of random walkers at each time step, at each bucket in the array).

[1] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

[2] https://en.wikipedia.org/wiki/A*_search_algorithm

[3] https://en.wikipedia.org/wiki/Approximate_string_matching

[4] https://en.wikipedia.org/wiki/Viterbi_algorithm

[5] https://en.wikipedia.org/wiki/Earley_parser

[6] https://en.wikipedia.org/wiki/Dynamic_time_warping

[7] https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorith...

When I went to graduate school, I took two algorithms classes. The first was general, and the second more targeted. For both classes, dynamic programming regularly was needed.

I think they ask about it on interviews because it’s basucally a proxy for “did you get good grades in graduate level courses”. At a top school, undergrad courses should be close enough. Of course, they could just look at your transcript, but maybe you cheated.

Which is sort of silly if you didn't PhD in CS, but rather say, mathematics, where your courses hit you with numerical methods for PDEs, linear algebra, optimization, etc.

But then they use the same interview questions for somebody who finished school 10 years ago and hasn't touched DP since then.

This also makes them convenient tools for age discrimination

> But DP? I've never needed it or used it. Why the emphasis in it then

There are people who did only the multiple choice questions and moved on to the video conf interview. At least they can skip DP question for some people, so probably not an emphasis.

Regardless of whether or not it’s a good measuring stick to see who to hire (it’s probably not), I feel like DP is something that ought to be in a professional programmer’s toolbox.

I’m an embedded developer too, and I end up reaching for DP every year or two. I think I probably use it _more_ because I’m in embedded: if I was willing to accept harder to analyze memory requirements and runtime performance, which I almost always am outside of embedded, most things I’ve solved with DP I could have more swiftly solved by composing algorithms and data structures from the standard library.

I agree, it is a tool box thing. I either did not know of or forgot the term "dynamic programming," but I use memoization regularly, and have used it as short cuts on recursive calls. Accidental dynamic programming. Heck, the first time I heard of the collatz conjecture, my toy playing around with it memoized the results.

> Absolutely nothing, except that I can't solve DP problems on the spot

It's an IQ test.

It measures cognitive intelligence. Does it predict overall success? No.

IQ tests themselves are a bad predictor for performance, and skewed by access to resources. So maybe it is similar? That's not a good thing though.

For the dp problem, you need to have experience with dp problems, experience with general algorithm problems (from the acm-like programming challenge side specifically), and generally be good at applying those in new situations. Unless that's your actual previous work, it doesn't measure intelligence in any way.

IQ tests are one of the best-known predictors of performance in any occupation.

> The validity of IQ as a predictor of job performance is above zero for all work studied to date, but varies with the type of job and across different studies, ranging from 0.2 to 0.6

Best know doesn't mean good. Any occupation also fails:

> for minimally-skilled activities, athletic strength (manual strength, speed, stamina, and coordination) are more likely to influence performance.

https://en.m.wikipedia.org/wiki/Intelligence_quotient

Also, that's a predictor for "any" job. You can do better if you know exactly what job you're interested in. Do a sample of work that's very close to the real one and you'll have a better prediction.

Reply on news.ycombinator.com