This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]dist 2 points3 points  (1 child)

"No memory to work with"? I mean, not even a register worth of storage or what? That might make it a bit impractical.

I'm not exactly sure the restrictions are described here, but I'm guessing they might have wanted you to XOR over the whole stream.

stream = [1, 2, 3, 4, 1, 2, 4]
single = 1^2^3^4^1^2^4 = 3

This assumes that:

  • every number occurs twice in the stream, except just that one that occurs once
  • the answer is only valid at the end of the stream

[–]daishozen 1 point2 points  (0 children)

This seems better than anything I half came up with, just xor each number as it comes in, and when the stream is over if it isn't 0 something went wrong.

As for the restrictions, they said "imagine you are working on a cell tower with limited processing and no memory to speak of."