Shi is a fresh graduate majoring in electronics, but he has read a lot of books on Internet and programming in his spare time and wants to work in BAT Internet Company.
Before xiao Shi in the BAT three interview has failed two, today xiao Shi went to BAT in the last interview.
After a brief introduction, the interviewer gave Shi a question.
[Interview site]
Title: How to find the first 1000 largest numbers in a billion?
Shi: I can use divide-and-conquer, which is similar to partition in quicksort. If you pick a random number t, and partition the entire array, you get two parts, the first part is greater than t, and the second part is less than t.
If the number of partitions in the previous section is greater than 1000, then continue to search for partitions in the previous section. If the number in the first part is less than 1000, partition the second part to find the remaining number.
First, the partition process, time is O (n). We spent N for the first partition, halved the amount of data for the second partition, so it only cost N /2, and n/4 for the third partition, and so on. And n + n/2 + n/4 +… It’s obviously less than 2n, so the asymptotic time of this method is only order n.
(Note: the time complexity calculation here is only a simplified calculation version, the real rigorous mathematical proof can refer to the correlation analysis in introduction to algorithms.)
Half a minute passed.
For a moment, Steve panicked.
He recalled the details of a bitmap lecture lu had given him. An idea came to me.
Xiao Shi drew a picture on the paper.
After understanding the algorithm, Xiao Shi’s code is also very fast to write, in a short time to write:
/** * @author on 2018/10/14. */ public class TopN {private int parent(int n) {return(n - 1) / 2; } private int left(int n) {return2 * n + 1; } private int right(int n) {return2 * n + 2; Private void buildHeap(int n, int[] data) {private void buildHeap(int n, int[] data) {for(int i = 1; i < n; i++) { int t = i; / / adjust the heapwhile(t != 0 && data[parent(t)] > data[t]) {
int temp = data[t];
data[t] = data[parent(t)];
data[parent(t)] = temp;
t = parent(t);
}
}
}
// 调整data[i]
private void adjust(int i, int n, int[] data) {
if(data[i] <= data[0]) {
return; Int temp = data[I]; data[i] = data[0]; data[0] = temp; Int t = 0;while( (left(t) < n && data[t] > data[left(t)])
|| (right(t) < n && data[t] > data[right(t)]) ) {
if(right(t) < n &&data [right(t)] < data[left(t)]) {// Temp = data[t]; data[t] = data[right(t)]; data[right(t)] = temp; t = right(t); }else{// replace the left child temp = data[t]; data[t] = data[left(t)]; data[left(t)] = temp; t = left(t); Public void findTopN(int n, int[] data) {public void findTopN(int n, int[] data) {buildHeap(n, data); // adjust the following numberfor(int i = n; i < data.length; i++) { adjust(i, n, data); }} // Print the array public voidprint(int[] data) {
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + ""); } System.out.println(); }}Copy the codeThe interviewer takes a look.
Xiao Shi skillfully introduced his own project, due to full preparation, Xiao Shi chat with ease. Several questions asked by the interviewer were also explained in detail.
After Shi left, the interviewer wrote his comments in the system:
【 Meet Teacher Lu 】
Small history to go back to school hum a song on the road in the campus, just met Lu teacher.
Xiao Shi told Teacher Lu about the interview.
Xiao Shi: I got a lot of insight. Although I have done topN problems at ordinary times, I have less time to know divide-and-conquer. But you still have to analyze it on a case-by-case basis, and it’s much faster to use the heap for this kind of big data.
The author of this article is my good friend Xin Ge. The link to the article is as follows:
How to find the top 1000 numbers in a billion