Software Job - Interview Question

Today, I was searching for some technical articles and stumbled upon this interview question from Amazon, for which I could immediately think about some good solution. Here's the question:

We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?

I read an answer from some guy, who said to sort the numbers first and then loop through and find the number. I thought that was inefficient way of doing that. My answer is as below:

1) - Calculate the sum of all numbers stored in the array of size 51. 
2) - Subtract the sum from (52 * 53)/2   -- Formula : n (n+1)/2.

The result of subtraction is the answer for this question.

Any other solutions that you know of?!?!?!

11 comments:

  1. Replies
    1. Tks very much for your post.

      Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

      You also find all interview questions at link at the end of this post.

      Source: Download Ebook: Ultimate Guide To Job Interview Questions Answers:

      Best rgs

      Delete
  2. Better than sort one, but inferior to yours sum of series.

    Create one more boolean array of length 52.
    Iterate over first array, for each number encountered mark its position in second array as true i.e., if you encounter 4 mark 4th element in second array as true.

    Finally iterate over second array and find which one is false.
    So just 2 iterations overall, but memory consumption is more.

    ReplyDelete
    Replies
    1. The solution you proposed is almost the same as 'sorting and looping through'.

      After I wrote this post, I created an alternative solution using 'bitset' operator. This logic is useful not just for 1 missing number (as in the above logic), but also for multiple missing numbers. Here's the link: http://java-bytes.blogspot.com/2012/02/missing-number.html

      Delete
  3. Thanks for the article, excellent stuff.
    I have seen interesting Interview Questions and Answers here.

    ReplyDelete
  4. Thank you for this post.its very informative...
    Yatiken Software

    ReplyDelete
  5. Its very beneficial blog. this is very useful for everyone. Want a more latest job vacancies update. Visit Here

    ReplyDelete
  6. Tks very much for your post.

    Avoid surprises — interviews need preparation. Some questions come up time and time again — usually about you, your experience and the job itself. We've gathered together the most common questions so you can get your preparation off to a flying start.

    You also find all interview questions at link at the end of this post.

    Source: Interview Questions & Answers:

    Best rgs

    ReplyDelete
  7. Thanks for your informative post on Java application development. This open source platform assists software developers to create stunning mobile application with ease. Further, they can make use of this platform at free of cost. J2EE Training in Chennai

    ReplyDelete
  8. The expansion of internet and other business intelligence leads to large volume of data. Industries are looking for talented professionals to maintain and process huge volume of data with latest tools available in the market. Taking Hadoop Training in Chennai | Big Data Training in Chennai will ensure better career prospects for talented professionals.

    ReplyDelete