Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I was asked a question in an interview the other day, the question was:

"You have an array list of numbers from 1 to 100, the problem is that one number is missing. How would you find that number?"

This is a mock of the question. The code seems to work.

Could you guys give me some feedback?

    private int count;

public void find() {
    //prep for question
    List<Integer> ints = new ArrayList();
    for (int i = 0; i < 100; i++) {
        ints.add(i);
    }
    ints.remove(67);

    //find the missing number
    for (Integer i : ints) {
        if (i != count) {
            System.out.println(count);
            count++;
        }
        count++;
    }
}

//Output = 67

share|improve this question
    
as sky said you can count list size(). If you want know the missing number, use a TreeSet instead of List , then parse it with Jeremy K finder –  cl-r Nov 12 '12 at 10:44
add comment

4 Answers

up vote 11 down vote accepted

This is a very common question.Your algorithm is not correct.

The Rule is, find the sum of the numbers in the array and then subtract it from the the sum of numbers from 1 - 100. That is the missing the number you get.

Sum of natural number from 1 to N is NX(N+1)/2

share|improve this answer
add comment

I'm no Java guru but some things to consider might be:

  1. Seperate the UI display from the find algorithm i.e. don't have System.out.println in the method.

  2. Supply the array list as a parameter to a method. So I would probably think the top level method to do this match might be something like

    public Integer getMissingValue(ArrayList source) { // code }

    This way you could re-use the code in different contexts and even write some unit tests for it with varying values.

  3. You code assumes the array list is sequential 1 - 100 does it not? I don't see that stated in the question. If the supplied list was in a random order I don't think your answer would work.

  4. Make sure you read the question properly. It states integers 1 - 100. You have accounted for integers 0 - 99

  5. In an interview question like this I would always consider writing it using TDD. Interviewers like to see unit tests even if they don't ask for it. It shows you care about testing your code and also potentially shows good thought processes into the way you might take a problem.

share|improve this answer
add comment

If the list is ordered like in your example you could do something like:

for (int i = 0; i < ints.size(); ++i) {
    if (i + 1 != ints.get(i)) {
        return i + 1;
    }
}

The value will always be 1 more than the index (since you start at 1 and not 0) except for the missing number and the numbers that occur after it (which will be 2 ahead of the index). So you just return the first occurrence where it fails.

If the list is out of order, you could sort it first and then do the above.

Another option, which doesn't matter if the list is sorted or not, is to use sets. Explained here. Although this is probably overkill for only 1 missing element.

share|improve this answer
add comment

Well this is a well known 'brain teaser', and your solution is incorrect. You assume (and test by that assumption), that the input is ordered. Since this isn't mentioned in the question, the algorithm is incorrect - fix it first.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.