Skip to main content
Software Engineering

Return to Answer

added 114 characters in body
Source Link
Ewan
Ewan
  • 79.9k
  • 5
  • 83
  • 179

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Edit. Downvoters : This is a published textbook O(n) solution to the exact problem stated in the OP.

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Edit. Downvoters : This is a published textbook O(n) solution to the exact problem stated in the OP.

added 244 characters in body
Source Link
Ewan
Ewan
  • 79.9k
  • 5
  • 83
  • 179

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.

Edit. Ahh it seems for 4 there is a different approach than XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Source Link
Ewan
Ewan
  • 79.9k
  • 5
  • 83
  • 179

As with all standard questions the solution is to google them before the interview.

This question and variations have a very definite 'correct' answer involving XORing all the numbers. Its supposed to show you understand indexes in databases or something. So zero points for any 'might work but not what it says on the paper' answer im afriad.

On the plus side there is a finite set of these questions a few hours revision will make you look like a genius. Just remember to pretend you are working it out in your head.