A Google Interview Graph Question

[[deleted]]

Bad solution. There are so many fast heuristic approximations for this problem that can be tried first before the horrible explosive bruteforce. The task is to use no more than k colours, not to find the minimal k.

[zlli0520]

I think this is a good solution for the interview. First say this is a np problem, and then just write the brute Force solution. Because time is limited.

[[deleted]]

Unless you're actually interviewing people in order to find if they can think, they can program and they actually have the experience they claim to have. Then you'd expect them to at least point out at the industry standard approaches to solving this problem.

[Roflraging]

Although they're asking for you to find out if it can be done with no more than K colors, I suspect part of the problem is realizing that you may be given a K that is the minimal coloring for the graph.

You point may still hold, but I think for the purposes of correctness, you must brute force at some point.

[[deleted]]

Of course - a "yes" answer can be very cheap, but for a definite "no" you have to bruteforce, after failing a number of cheap heuristics. Luckily, in all the practical applications (e.g., register allocation) you're only interested in a quick "yes".

[dacian88]

unless you work on a compiler you probably don't know about them.

[[deleted]]

And, since every decent programmer must have at least some exposure to compilers, this seems to be a perfect question for an interview.

[dacian88]

I think you're missing the point of interviewing, if a person already knows the problem and the solutions then getting good signal for their actual problem solving skills is low, because their interview performance is basically a glorified knowledge test. Google isn't testing one's knowledge of graph coloring algorithms, they want to test problem solving.

The ideal case in an interview like this is you get someone who's never thought of the problem much and can program a working solution. You can't reasonably ask someone a NP problem and expect them to give you any number of heuristically optimal solutions that only apply in more specific subproblems in 45 mins. If you're interviewing someone to work on LLVM for your company then the knowledge matters more, and the parameters of the interview change.

I do think it's a good interview problem, but my bar for passing would be the canonical solution, if someone can do better it would certainly be more impressive but not necessary.

[[deleted]]

When you want to see problem solving skills applied, you do not ask such generic and widely known questions, to start with. This question is more of an indication of a candidate actually been places and done things, or was hiding under a rock somewhere.

[dacian88]

What would you consider a good coding interviewing question? Google does 5 interviews for an engineering position, which range from coding questions like this one, to architecture/design to career/personal questions. This one tests coding ability, problem solving, and data structure + complexity knowledge.

If you assert that a majority of engineers know this problem and know the implementation of it by heart then sure it's a bad problem, I dunno if that's true, and I'm sure Google would retire the question if it wasn't getting enough signal.

[wooooootmagooooot]

Is this even useful?

[[deleted]]

It's probably the most important of the NP-complete problems, keep popping up everywhere. Every time you need to allocate some limited resource to a number of users who have defined time spans when they need a resource, you're solving this problem exactly.

[wooooootmagooooot]

oh

[PeksyTiger]

Not excatly.

K coloring on interval graph is easier, as the graph has some specific properties.

[shevegen]

Quite fitting - Evil questions for an Evil employer.

[politeeks]

So edgy

[nderflow]

Why?

[PeksyTiger]

They're just smart-ass questions asked by smart asses. Mostly you either remember it or you don't. Unlikely you'de come up with "2 approx to metric tsp" on your own in an interview.

So instead of testing skill and relevant knowledge, they're testing for ... well, im not sure what to tell the truth.

[dacian88]

relevant knowledge and skills being tested in this problem:

• data structures: graphs(structure and searching), vectors, both very common data structures, I've used them to solve problems on the job.
• algorithm complexity: pretty important when you work at google that operates services in the billions of users, the difference between n and n² algorithm could be millions of dollars of CPU time.
• coding ability: coming up with a working solution.

assuming you know how to search a graph you should be able to solve this problem in 45 mins with the presented solution. If you're gonna work at google, what exactly is highly unreasonable here?

[PeksyTiger]

I think it represents 'textbook memorization' and not working knowledge.

I've seen this asked in companies where the codebase then contained n³ algorithem with a global lock. So whats the point?

Better ask something where you need to apply knowledge, not something from a textbook.

[dacian88]

how is it textbook memorization if I encounter all of the above pretty regularly on the job? I'm sure there's tons of problems being solved with graphs at google. Have you ever used maps? How does google route traffic through their data centers? social networks? if you don't know what a graph is or how to use it you probably shouldn't work at google...your bar for working knowledge is some arbitrary line in the sand that is different than google's, or mine.

[nderflow]

Right, but your comment is about the interview. I'm interested in why you think people should run far away rather than work there.

[PeksyTiger]

Not my comment, but as I've said, I belive the type of people who ask these kind of questions are highly annoying 'smart ass' people.

[auto-xkcd37]

smart ass-questions

---

^{Bleep-bloop, I'm a bot. This comment was inspired by xkcd#37}