relationship_search.rb

#!/usr/bin/env ruby

# Question:
# 	If user_1 followed user_2, we will get an array item like:
#   	[id_1, id_2]
# 	Here is a sample user relationship list:
# 		[ [2, 3], [1, 4], [3, 2], [1, 3], [4, 2], [7, 2], [5, 3], [4, 1] ]
# 	If two items have two same IDs, print one of the items out.
# 	So if we print out [3, 2] and [1, 4], that should be a right result.

$rel_list = [ [2, 3], [1, 4], [3, 2], [1, 3], [4, 2], [7, 2], [5, 3], [4, 1] ]
$digit_weight = 10 ** $rel_list.flatten.max.to_s.length

# Get the weight value of the relationship.
def weight rel
	a, b = if rel[0] < rel[1]; rel else rel.reverse end
	a * $digit_weight + b
end

# Simulate to trigger the comparison event.
def compare_event e
	if e[:val] == 0
		puts e[:rel].join ','
	end
end

# The default sort algorithm in Ruby is Quick Sort, which is plenty good here.
#   Time: average O(log n) | worst n * n
# Memory: average log n    | worst n
$rel_list.sort { |a, b|
	val = weight(a) <=> weight(b)
	compare_event({ :val => val, :rel => a })
	val
}