Skip to content

Instantly share code, notes, and snippets.

@sunapi386
Created March 16, 2016 17:48
Show Gist options
  • Save sunapi386/980c0abee81b8432dc82 to your computer and use it in GitHub Desktop.
Save sunapi386/980c0abee81b8432dc82 to your computer and use it in GitHub Desktop.
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.
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
@sunapi386
Copy link
Author

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))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment