Shantibhushan Naik

Tag: pickup

  • Maintaining relationship – common friends

    I was posed a very trivial question from one of my friends recently. It picked my interest, since I could not readily solve it, and I had the inkling that there is a better, simple solution for this problem.

    The problem was, let’s say I have a table of users as below
    User's table data

    And these users have friends as below

    User's friends data or more easier to read as User's friends data

    Now, the trivial task was find common friends for users 1, and 5, hence naturally the answer should be

    User 1 : Woody’s friends, and User 5 : Andy’s friends  are

    Woody's friends and Andy's friends

    So, the question I had was what could be the best SQL query that would be return me this result?

    Woody and Andy's common friends

    I thought of 2 different SQL queries

    SELECT f.fid, u.name 'Woody and Andy\'s common friends' FROM
    (SELECT f.`fid` FROM friends f
    WHERE f.`uid` IN (1,5)
    GROUP BY f.`fid` HAVING COUNT(f.`fid`) > 1) f INNER JOIN user u ON (u.uid=f.fid)

    -or- another one was

    SELECT f.fid, u.name 'Woody and Andy\'s common friends' FROM
    (SELECT a.fid FROM
    (SELECT * FROM friends f
    WHERE f.`uid`=1) a INNER JOIN
    (SELECT * FROM friends f
    WHERE f.`uid`=5) b ON (a.fid=b.fid)) f INNER JOIN user u ON (u.uid=f.fid)

    Both seem to work, but is there any elegant way of getting common friends in a much simpler SQL query? At this moment, I logically find first SQL query more intuitive since all it does is pickup friends who appear more than once when users are 1 and 5. The second SQL query seems plain brute force approach.

  • Merging pre-sorted lists

    A while ago, I came across an interesting problem. We have 3 different sorted queues (entries were sorted by time), out of which we had to pickup the smallest time, and send the first arrived entry out of those 3 queues in sequence.

    Q1 Q2 Q3
    2 3 1
    5 4 6
    7 6 9
    8 10 11

    As you can see, all queues (Q1, Q2, Q3) are already sorted, but on application side we have to pickup entries across all queues in sorted order and process them. So the entries should be processed in 1, 2, 3, 4, 5, … 11 sequence. Frankly this is merging of already sorted lists, and a person from computer science background should already know this. But I don’t come from such background, and the solution one of my friends gave was plain amazing.

    The solution was pickup first entry from each queue, compare them, choose the smallest and process it first.

    Q1 Q2 Q3 Smallest
    2 3 1 1

    Thus, here 1 is processed first. Now pickup next entry from queue where smallest was found (Q3 in this example), so now the next comparison becomes like this

    Q1 Q2 Q3 Smallest
    2 3 6 2

    The smallest is 2, so this is processed and next entry from Q1 was picked-up

    Q1 Q2 Q3 Smallest
    5 3 6 3

    And so on… giving us

    Q1 Q2 Q3 Smallest
    2 3 1 1
    2 3 6 2
    5 3 6 3
    5 4 6 4
    5 6 6 5
    7 6 6 6
    7 10 6 6
    7 10 9 7
    8 10 9 8
    10 9 9
    10 11 10
    11 11

    A simple, and elegant solution, isn’t it? Is there any other better alternative?

  • Pickup problem

    Who needs a pickup now?
    Photobucket - Video and Image Hosting