Find the smallest 3 numbers from a total of 5000 numbers

Question

Today was my interview. The question which was asked was:

Give an efficient solution to search smallest 3 numbers from a given array.

The array contains unsorted numbers which can also repeat. There are 5000 numbers in total in array.

I went step by step. I created an array of 700 numbers:

private static Integer [] numberArray = new Integer[]{  
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16
    };

I gave my first solution:

    private static Integer[] getLeastThreeNum() {
    Integer [] nums = new Integer[3];
    int count = 0;

    List<Integer> list = Arrays.<Integer>asList(numberArray);

    Set<Integer> set = new TreeSet<Integer>(list); 

    for(Iterator<Integer> itr = set.iterator(); itr.hasNext();){
        //System.out.println(itr.next());
        if(count <= 2){
            nums[count] = itr.next();
            count++;
        }else{
            break;
        }

    }

    return nums;
}

Then I gave my next solution which comprises of 3 methods: getLeastThreeNum", merge and findLeastThreeNum.

Method getLeastTheeNum, the parent method:

private static Integer[] getLeastThreeNum(){

    int total = numberArray.length,             
        startIndex = 0, 
        lastIndex = 0;

    final int range = 90; // search in 90 numbers at a time 

    boolean flag  = false;
    Integer [] rangeArrayCopy = null;
    Integer [] leastThreeNum = null;
    System.out.println("Total Numbers to be searched "+total);
    do{
        if(lastIndex == 0){ // first iteration
            lastIndex = range;  
        }else{ // next iteration
            startIndex = lastIndex;
            if((lastIndex + range) <= total){
                lastIndex += range;
            }else{ // last iteration
                lastIndex = total; 
                flag = true;
            }
        }

        // create a sub array from a given range 
        rangeArrayCopy = Arrays.copyOfRange(numberArray,startIndex,lastIndex); 
        if(leastThreeNum == null){ // for first search of least 3 numbers               
            leastThreeNum = findLeastThreeNum(rangeArrayCopy);
        }else{ 
            // merge the 3 least numbers we got with the next batch of numbers
            // and find the least 3 numbers from them
            rangeArrayCopy = merge(rangeArrayCopy,leastThreeNum); 
            leastThreeNum = findLeastThreeNum(rangeArrayCopy);
        }

    }while(flag == false);

    return leastThreeNum; 
}

Method merge:

// merges two arrays
private static Integer[] merge(Integer [] first,Integer [] second){
    Integer [] both = new Integer[first.length + second.length];

    for(int i = 0; i < first.length; i++){
        both[i] = first[i];         
        for(int j = 0; j < second.length; j++){
            both[first.length + j] = second[j];
        }
    }

    return both;
}

Method findLeastThreeNum:

private static Integer [] findLeastThreeNum(Integer [] numberArray) {
    Integer [] nums = new Integer[3];
    int count = 0;

    List<Integer> list = Arrays.<Integer>asList(numberArray);

    Set<Integer> set = new TreeSet<Integer>(list); 

    for(Iterator<Integer> itr = set.iterator(); itr.hasNext();){

        if(count <= 2){
            nums[count] = itr.next();
            count++;
        }else{
            break;
        }

    }

    return nums;
}

The method findLeastThreeNum is the same as the first solution.

In the second solution, I divide the array into sub-arrays, and then search least 3 numbers from the sub-array.

In the second solution, the steps are as follows:

1. Create the first sub-array
2. Find the least 3 numbers from the sub-array
3. Merge the 3 numbers with the next sub-array and so step 1

I thought my second solution was efficient for searching from 5000 numbers for least 3 numbers, but the interviewer was not satisfied. Can you please review my code and tell me where I can improve?

Answer 1

It's difficult to tell you where to improve. You simply over-complicated the problem. It happens to everyone, especially under the pressure of an interview situation.

Also, your logic is just sort of hard to follow. Why were you splitting it into sub-arrays? Perhaps it was a perfectly valid reason but its not clear from me just looking at the code why you would want to do this.

Your usage of a TreeSet is also something I find hard to understand.

Giving your variables more meaningful names might help somewhat. You have variables such as:

boolean flag  = false;

What is this flag for? I try to always prefix my boolean variables with 'is': isFound, isHidden, isAlive.

Integer [] both = new Integer[first.length + second.length];

This line occurs in a relatively short function so I'm able to understand that both refers to both arrays merged together. Why not name it mergedArray or something similar?

I would also try to stay away from primitive arrays:

Integer [] nums = new Integer[3];

because they are less flexible than Java's inbuilt Lists.

---

I've written my own version of the function that you might find helpful. It works on the assumption that there will always be at least 3 numbers in the given list but it would be trivial to add a check for that at the top.

public static List<Integer> getLowestThree(List<Integer> numbers)
{
    List<Integer> lowestThree = new LinkedList<>();
    lowestThree.add(numbers.get(0));
    lowestThree.add(numbers.get(1));
    lowestThree.add(numbers.get(2));
    Collections.sort(lowestThree); //sort so we always know largest is at index 2

    for ( int i = 3; i < numbers.size(); ++i)
    {        
        if ( numbers.get(i) < lowestThree.get(2) ) // if its smaller than the largest
        {
            lowestThree.remove(2);           // remove the largest
            lowestThree.add(numbers.get(i)); // add the current one
            Collections.sort(lowestThree);   // sort for the same reason as before
        }
    }

    return lowestThree;
}

Answer 2

Clarification

It's not clear from the description if the lowest 3 numbers in 1 1 2 2 3 should be 1 1 2 or 1 2 3. Note that some ambiguity in the wording of the question can be part of the interview process. It's important to ask clarifying questions, to show inquisitive thinking, attention to detail and corner cases.

Time complexity

It's important to be keenly aware of the time complexity of your proposed solution during an interview. You are expected to think about it aloud.

Both of your implementations will add all numbers in a tree set. What's the time complexity of that?

By contrast, what's the time complexity of finding the minimum value m1? And the minimum value m2 that is greater than m1? And the minimum value m3 that is greater than m3? What is the total time complexity of finding all m1 and m2 and m3? How does this compare to the time complexity of adding all numbers to a tree set? Hmmm... These are things you could think out loud during the interview, and the interviewer may even help you.

Space complexity

The same considerations apply here as well, especially because time and space are often at odds.

Adding all numbers to a tree set doubles the space used. Could you do it without extra space? That's another clarifying question for the interviewer, if you can modify the content of the input object or not.

Style

There are several style issues in the posted code:

• Why is the input type Integer[] instead of a simple int[] ?
• Use interface type instead of implementation in declarations, for example SortedSet instead of TreeSet
• Use the diamond operator <> when the compiler can infer the type parameter

Extensions

Of course, the alternative solution I hinted at, finding m1, m2, m3 will not scale well. The interviewer will inevitably extend the question to "how about finding the lowest first half", at which point the simple alternative falls apart. But that's OK. By that time, he has seen your attention to time and space complexity concerns, and even if you cannot figure out the ideal algorithm for the next step, it might be OK.

Start small, using the simplest solution that can work, even brute force is OK to begin with, and optimize one step at a time, as necessary.

So what's the trick to the next step? Do you really need to add all n numbers to a tree set to know the lowest k numbers? Or maybe a tree set of k numbers could be enough? Maybe some numbers never need to be added to the tree set during the process? For example, when you know that the highest number in the tree set is 5, do you ever need to add 712 to the tree set, or perhaps you can just skip that and move on? What's the time complexity of using a tree set of size k as opposed to that of size n? Is there another data structure that could also be interesting?

Answer 3

Starting From a Simple Base

Here's a solution in C to find the lowest three distinct numbers. It should be readily translatable to Java.

// find the smallest three numbers

int numbers[] = {  
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16
    };

#include <limits.h>

// manage three locations that store the lowest three values
inline void place_into_lowest_3(int *s1, int *s2, int *s3, int n)
{
    if (n<*s1) {*s3=*s2,*s2=*s1,*s1=n;return;}
    if (n<*s2 && n!=*s1) {*s3=*s2,*s2=n;return;}
    if (n<*s3 && n!=*s1 && n!=*s2) {*s3=n;return;}
}

int main() 
{
    int s1 = INT_MAX;
    int s2 = INT_MAX;
    int s3 = INT_MAX;
    for (int i=0;i<700;++i) {
        int n = numbers[i];
        place_into_lowest_3(&s1,&s2,&s3,n);
    }
    printf("In ascending order, smallest three are %d %d and %d.\n",s1,s2,s3);
}

The output, hopefully correct(!) is:

C:\Workarea>small.exe
In ascending order, smallest three are 1 3 and 4.
C:\Workarea>

If we're only looking for the few lowest numbers, we can simply manage our own tiny 'array' of variables.

I work on a code base of about 8 million lines of code, so I like to optimize for the simplest 'fast enough' solution, bearing in mind that people tend to read much more code than they write.

Going Further and Finding the n Smallest Numbers

Just to add a little about my thought process on this one. We have to look at all the numbers, so you're O(n) right there. We can also easily pick out the smallest number. If we want to pick out the next smallest number, then we can track smallest and next smallest, and simply shuffle the numbers if we find one smaller. The shuffling is the only slightly tricky part, as it's very easy just to end up with 1,1,1 as the three smallest numbers. Extend this one more time to pick the three smallest numbers.

Going further, if I then asked a candidate to identify the smallest n numbers, then I'd expect to see them add them to an array of the n smallest, where n could be, say, specified on the command-line.

I'd also be looking for defensive programming along the lines of checking input, using INT_MAX etc., to assure that the program cannot fail.

Here's code that manages an array of the n smallest numbers.

// find the smallest n numbers

int numbers[] = {  
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        12,32,4,1,45,1,4,45,6,34,21,6,34,7,6,34,89,12,56,78,12,45,34,78,90,12,1,
        12,43,65,87,98,21,11,29,38,37,45,1,6,72,8,56,37,82,81,91,7,61,32,87,32,
        43,98,54,12,87,45,98,76,54,32,87,3,87,6,54,21,87,19,15,27,16,47,80,16
    };

#include <limits.h>

// must initially populate array of smallest with INT_MAX
inline void place_into_lowest_n(int *smallest, int n, int v)
{
    // skip values larger than end of array
    if (v>=smallest[n-1]) return;
    for (int i=0;i<n;++i) {
        // skip values already in array
        if (v==smallest[i]) return;
        // if v smaller, insert into smallest array at i
        if (v<smallest[i]) {
            for (int j=n-1; j>i; --j) smallest[j] = smallest[j-1];
            smallest[i]=v;
            return;
        }
    }
}

#define SMALLEST_N 10

int main() 
{
    int smallest[SMALLEST_N];
    for (int i=0;i<SMALLEST_N;++i) smallest[i]=INT_MAX;

    for (int i=0;i<700;++i) {
        int n = numbers[i];
        place_into_lowest_n(smallest,SMALLEST_N,n);
    }
    printf("In ascending order, smallest %d are ",SMALLEST_N);
    for (int i=0;i<SMALLEST_N;++i) printf("%d ",smallest[i]);
    printf(".\n");
}

Output for the 10 smallest numbers is:

C:\Workarea>small-v2.exe
In ascending order, smallest 10 are 1 3 4 6 7 8 11 12 15 16 .
C:\Workarea>

Further Areas for Discussion in an Interview

How might you deal with sorting larger data than you can deal with in memory?

At what point in managing a sorted array of the n smallest numbers, might you start binary searching to see if the number should be among the n smallest?

It's kinda neat that there's so much to think about even on a really simple little problem like finding a few small numbers.