CareerCup

B+ trees (treat the numbers as keys to a table in a database).

if the goal is only to find one number in one million unsorted ones, just do linear search

otherwise, use bit array to sort, the find

You could do one of the following

1. Add all of them to a Hash table and then look up the target number. (O(n) + O(1))
2. Do linear search (if you have to look up only one number) (O(n))
3. Put then in a array, sort them and do binary search on them. (O(NlogN) + O(logN))

Make a binary search tree and traverse.

I have never tried this, but i think this approach works:

1) Write two java classes which has threads t1, t2 in each of them respectively.
2) t1- will create an expandable array (Vector) which will take 10000 elements a time.
3) t2- will search for the element in the created Vector.
4) when t1 is executing, t2 searches for the element in the created Vector.

This may fasten up things. Let me know if there will be any problem with this approach.

very good method, kind of parallel programming.

You can also use a trie, or, if you wanna get fancy, a van emde boas tree.

Again, all answers.. no question to ask. If I'm an interviewer, I will minus you guys points because you guys are making ASSumpations. (The poster all need to be clear)

Questions to ask:
Are integers repeated?
Are all integers distinct?
Do you know how many are repeated?
Are integers sequential? (if they are, you don't need stupid fancy btrees and crap)
Are integers in order? (if they are, you don't need stupid fancy btrees and crap)
Are they all random?

Knowing the above will efficienize the method to find it based on the appropriate "algorithm"
It's an overkill to do hashtable and crap if it's sequential.

The question is too easy to be straightforward (oh bsort, bsearch, btree, blah). Interviewer is looking if you are ASSuming. I'm an interviewer, btw, but.. I don't use 1 million.. I use 100 integers and see the questions they try to clarify..that's the real world.

Read 1 million integers in a Array, then sort it using Collections.sort, and do a BinarySearch to find a particular integer