Re:Ask HN: How is the job search coming along for people who...
by nephanth on Friday December 09, 2022 @01:06PM
(#33924466)
For the short story. A few years ago I was sitting a CS exam that was 3 hours of coding and then a defense where you explained what you have done on the board.
You had to compute a graph from a set of points (i think it was knn, not sure) and do stuff on it. At some point of the defense, this happened
Me: I skipped this question.
Examinator: why?
Me: If I compute it using the graph structure, it reduces to max-clique, which is np-complete. I looked for a solution using the point dara but didn't find it
Examinator: can you write an algorithm for max-clique on the board?
Me: here. This is exponential time
Examinator: it's worst case exponential time. But in this case it would have worked, you just had to try it
Me: urgh
Now I've learned my lesson: np-complete doesn't mean impossible
You had to compute a graph from a set of points (i think it was knn, not sure) and do stuff on it. At some point of the defense, this happened
Me: I skipped this question.
Examinator: why?
Me: If I compute it using the graph structure, it reduces to max-clique, which is np-complete. I looked for a solution using the point dara but didn't find it
Examinator: can you write an algorithm for max-clique on the board?
Me: here. This is exponential time
Examinator: it's worst case exponential time. But in this case it would have worked, you just had to try it
Me: urgh
Now I've learned my lesson: np-complete doesn't mean impossible