README.txt

Output the symmetric difference of two sorted streams of numbers.
Examples:
list1 = [1,3,5,8]
list2 = [2,5,6,7,8]
output = [1,2,3,6,7]

input1 = [1,2,3,4,99,100]
input2 = [3,4,5,6,99]
output = [1, 2, 5, 6, 100]

Assume both given lists are strictly increasing.
Optimal answer takes O(n+m) time and constant space.

rubysoln.rb

y = [1,2,3,4,99,100]
x = [3,4,5,6,99]
r = []
while (!x.empty? || !y.empty?)
    i = x.first
    j = y.first
    if i.nil? 
        moving = (y.shift)
        puts "moving #{moving}"
        r << moving
    elsif j.nil? 
        moving = (x.shift)
        puts "moving #{moving}"
        r << moving
    elsif i < j 
        moving = (x.shift)
        puts "#{i} < #{j} moving #{moving}"
        r << moving
    elsif i > j
        moving = y.shift
        puts "#{i} > #{j} moving #{moving}"
        r << moving
    else
        shift1 = x.shift
        shift2 = y.shift
        puts "#{i} = #{j} dropping #{shift1} #{shift2}"
    end
    puts "#{i} <- #{x} #{j} <- #{y} | #{r}"         
end

# y = [1,2,3,4,99,100]
# x = [3,4,5,6,99]
# r = []
# while (!x.empty? || !y.empty?)
#     if x.first.nil? 
#         r << y.shift
#     elsif y.first.nil? 
#         r << x.shift
#     elsif x.first < y.first
#         r << x.shift
#     elsif x.first > y.first
#         r << y.shift
#     else
#         x.shift
#         y.shift
#     end
# end

in1 = [3,4,5,6,99]
in2 = [1,2,3,4,99,100](in1 + in2).sort - (in1 & in2)
SortedSet.new(in1 + in2) - (in1 & in2)

python: set(in1) ^ set(in2)

SortedSet.new(Set.new(in1) ^ Set.new(in2))