09:18 pm, 8 Jan 05

### and the algorithm is...

I don't even need to write pseudocode for my answer, because the algorithm has a name.

Put each user list into a graph, with edges in list L from user L

Topo sort¹ is O(v+e). I think

This could make a fun interview question because there's two sides to it: there is recognizing that the problem of representing the merged posets is a graph, and then on top of that knowing topological sort. But for weaker / less theory-heavy candidates you can see how well they do with manual solutions. And I like it 'cause it's actually a real problem. I'll implement it later, maybe tomorrow, and tell you what I find.

1 I admit I looked this one up to be sure I wasn't missing something, though it's obvious if you think for a sec.

**Topological sort!**I can't believe I stared at this for so long and didn't see it.Put each user list into a graph, with edges in list L from user L

_{i}to user L_{i+1}, and then use topo sort.Topo sort¹ is O(v+e). I think

**dan_erat**'s answer (the only person who submitted one, too) would work but it looks slow.This could make a fun interview question because there's two sides to it: there is recognizing that the problem of representing the merged posets is a graph, and then on top of that knowing topological sort. But for weaker / less theory-heavy candidates you can see how well they do with manual solutions. And I like it 'cause it's actually a real problem. I'll implement it later, maybe tomorrow, and tell you what I find.

1 I admit I looked this one up to be sure I wasn't missing something, though it's obvious if you think for a sec.

dan_erat1. Select a vertex that has in-degree zero.

2. Add the vertex to the sort.

3. Delete the vertex and all the edges emanating from it from the graph.

which seems like it's what I was doing. Anyway, drunk now and

scsiis playing Katamari Damacy, which is way too distracting for me to ponder CS stuff.evan(And that game is so awesome!)

evandan_eratI wouldn't have gotten it as quickly (or at all?) in a job interview setting — I suck at writing code when people are watching and I'm under tight time constraints. During a mini-crisis on Thursday, I could barely write simple text-processing Python code with a co-worker hovering over my shoulder and telling me what to do. From observing others, I get the feeling that I'm not alone in this regard. :)

xaosenkosmosloganbevanSecond smallest integer: I was just reading about this for some reason, so I feel like an expert. The easy answer is STL does it for you. I think implementing partial sort can be done by finding the smallest element, swapping it into A[0], then finding the smallest element in A[1..n]. In general, if n's the size of the array and k is the element you want, it's O(nk). There are more efficient approaches with the same general strategy that have the same big-O. The really cool solution for larger k is to do it with heaps, but maybe this is a different post.

If I were asked this on an interview I'd probably begin by asking the interviewer if they were more interested in the general solution or if they wanted me to try to find the smallest two "manually" (by tracking them both). Both are interesting interview questions, though they measure different things.

Some people are really good at this stuff. My friend

erin_earlblew me the away the other day with a solution to a problem like one of these.## k-th smallest

Perhaps I am wrong, but all that you're doing with the second smallest integer is the select procedure, which is well known to be O(n). For more details, you can look up how to find the median of a list in linear time in CLR..martJust for laughs, here's a really lame way to do it quickly in Perl.

Go through each retrieved list in turn, and for each pair create two entries in a hashtable for the relationship in each direction, 1 for "higher" and -1 for "lower". Once you've made a gi-huge hash of all of the relationships, use the standard Perl

`sort`

function to sort based on the relationships given in the table, returning zero if any combinations come up that don't have an answer.You can solve almost anything with a huge hashtable.

;)mart(Quickly as in quick to write, not quick to run. I'm not sure what kind of sort Perl's

`sort`

does, so I'm not sure what big-O you'd be talking about.)cpm