Facebook Careers Puzzle—peaktraffic

From Facebook’s Job Puzzles page:

Cliques are sets of vertices in a graph that are complete, meaning there is an edge between every pair of the vertices in the clique. This Facebook puzzle is to find maximal cliques in presumably a large but sparse data set, since the problem is NP-complete (worst-case is when the graph is dense).

I will come back and cover this in broader detail at a later time.

The following solution in Ruby passed the Facebook puzzle robot:

(peaktraffic.rb) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#!/usr/bin/env ruby
# VROOM
# Kanwei Li, 2009

# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
  puts "error: must specify a valid input file"
  exit
end
input = File.open(filename)

$build_matrix = {}
$adj_matrix = {}

while line = input.gets
  line.strip!
  next if line.empty?

  splitted = line.split("\t")
  a, b = splitted[1..2]
  unless a == b
    $build_matrix[a] ||= {}
    $build_matrix[a][b] = true

    if $build_matrix[b] && $build_matrix[b][a]
      $adj_matrix[a] ||= []
      $adj_matrix[a] << b
      $adj_matrix[b] ||= []
      $adj_matrix[b] << a
    end
  end
end

$cliques = []

def print_cliques(set, neighbors, seen)
  if neighbors.empty? && seen.empty?
    $cliques << set.sort.join(", ") if set.size > 2
  else
    possible_pivots = neighbors + seen
    pivot = possible_pivots.inject(nil) do |best, p|
      best.nil? || $adj_matrix[p].size > best.size ? best = p : best
    end
    neighbors.size.times do |i|
      n = neighbors[i]
      next if $adj_matrix[n].include?(pivot)
      neighbors[i] = nil
      print_cliques(set + [n], neighbors.compact & $adj_matrix[n], seen & $adj_matrix[n])
      seen << n
    end
  end
end
print_cliques([], $adj_matrix.keys, [])
puts $cliques.sort.join("\n") << "\n"
Posted on