January 8th, 2005

  • evan

a cs problem for y'all

So I've downloaded a bunch of this LJ friends data. For each user, I have a list of the other users they're linked to. Internally on LJ, these users are attached to numeric user ids, but these ids are not exposed in the data. It'd be nice to have the user ids because they correlate with the time someone joined LJ and that'd be interesting to study, but it would seem I'm out of luck. BUT, it turns out there is bit of information: these lists of users are sorted in order of user ids.

So the question: given a set of user lists, each of which contains a list of users ordered by userid, write an algorithm that tells me the overall ordering of these users. (I can't get back the actual user ids, of course, because there are potentially users I have no data for. And it's possible there are multiple solutions for a given input; I just need one.)

(PS: email me if you want the answer.)