최근에 한 인터뷰에서 “10 억 개의 숫자 중 100 개의 가장 큰 숫자를 찾는 프로그램을 작성하십시오”라는 질문을 받았습니다.
나는 O (nlogn) 시간 복잡성으로 배열을 정렬하고 마지막 100 숫자를 취하는 무차별 대입 솔루션 만 제공 할 수있었습니다.
Arrays.sort(array);
면접관은 더 나은 시간 복잡성을 찾고 있었지만 몇 가지 다른 솔루션을 시도했지만 그에 대답하지 못했습니다. 더 나은 시간 복잡성 솔루션이 있습니까?
답변
100 개의 가장 큰 숫자의 우선 순위 큐를 유지하고 큐에서 가장 작은 숫자 (큐의 헤드)보다 큰 숫자가 발생할 때마다 큐의 헤드를 제거하고 새 번호를 추가 할 때마다 10 억 개의 숫자를 반복 할 수 있습니다. 대기열에.
편집하다:
Dev가 지적했듯이 우선 순위 대기열이 힙으로 구현되면 대기열에 삽입하는 것이 복잡합니다.O(logN)
최악의 경우 billionlog2(100) 보다 더 나은 것을 습니다.billionlog2(billion)
일반적으로 N 숫자 집합에서 가장 큰 K 숫자가 필요한 경우 복잡도는 O(NlogK) 보다 큽니다 O(NlogN). 이는 K가 N에 비해 매우 작을 때 매우 중요합니다.
EDIT2 :
이 알고리즘의 예상 시간은 각 반복마다 삽입이 발생하거나 발생하지 않을 수 있으므로 매우 흥미 롭습니다. i 번째 숫자가 큐에 삽입 될 확률은 랜덤 변수가 i-K동일한 분포의 랜덤 변수 보다 클 확률입니다 (처음 k 개의 숫자가 큐에 자동으로 추가됨). 주문 통계 ( link 참조 )를 사용하여이 확률을 계산할 수 있습니다 . 예를 들어, 숫자가에서 임의로 균일하게 선택되었다고 가정하고 {0, 1}(iK 중) i 번째 숫자의 예상 값은 i (i-k)/i이고 임의 변수가이 값보다 클 확률은 다음과 같습니다.1-[(i-k)/i] = k/i 있습니다.
따라서 예상되는 삽입 수는 다음과 같습니다.
예상 실행 시간은 다음과 같이 표현할 수 있습니다.
( k첫 번째 k요소로 대기열을 생성 한 다음 n-k비교 및 위에서 설명한 예상 삽입 횟수는 각각 평균을 취합니다.log(k)/2 시간 )
에 N비해 매우 큰 K경우이 표현은보다 훨씬 더 가깝 n습니다 NlogK. 이것은 질문의 경우와 같이 10 억 회에 비해 매우 작은 반복 후에도 숫자가 대기열에 삽입 될 가능성이 매우 적다는 점에서 다소 직관적입니다.
답변
인터뷰에서 이것이 요청되면 인터뷰어는 아마도 알고리즘에 대한 지식뿐만 아니라 문제 해결 과정을보고 싶을 것입니다.
설명은 매우 일반적이므로 문제를 명확하게하기 위해이 숫자의 범위 나 의미를 물어볼 수 있습니다. 이렇게하면 면접관에게 깊은 인상을 줄 수 있습니다. 예를 들어이 숫자가 특정 국가 (예 : 중국)의 연령을 나타내는 경우 훨씬 쉬운 문제입니다. 살아있는 사람이 200보다 늙지 않다는 합리적인 가정하에, 200 (아마도 201) 크기의 int 배열을 사용하여 한 번의 반복으로 같은 나이를 가진 사람들의 수를 계산할 수 있습니다. 여기서 색인은 나이를 의미합니다. 이 후 100 가장 큰 숫자를 찾는 케이크 조각입니다. 그런데이 알고를 카운팅 정렬 이라고 합니다 .
어쨌든, 질문을보다 구체적이고 명확하게하는 것은 인터뷰에서 당신에게 좋습니다.
답변
O (n)이 걸리는 숫자를 반복 할 수 있습니다
현재 최소값보다 큰 값을 찾을 때마다 크기가 100 인 순환 큐에 새 값을 추가하십시오.
해당 순환 대기열의 최소값은 새로운 비교 값입니다. 그 대기열에 계속 추가하십시오. 가득 찬 경우 큐에서 최소값을 추출하십시오.
답변
나는 이것이 ‘알고리즘’으로 태그되어 있다는 것을 깨달았지만 아마도 ‘인터뷰’로 태그되어야하기 때문에 다른 옵션을 던져 버릴 것입니다.
10 억 숫자의 출처는 무엇입니까? 데이터베이스 인 경우 ‘값 desc 한도 100으로 테이블 순서에서 값 선택’을 수행하면 작업이 매우 훌륭하게 수행됩니다. 사투리 차이가있을 수 있습니다.
이것은 일회성입니까, 아니면 반복 될 것입니까? 반복한다면 얼마나 자주? 일회성이고 데이터가 파일에 있으면 ‘cat srcfile | 정렬 (필요에 따라 옵션) | head -100 ‘은 컴퓨터가이 사소한 일을 처리하는 동안 지불해야하는 생산적인 작업을 신속하게 수행하게합니다.
반복되는 경우, 상위 100 개를 지속적으로보고 할 수 있도록 초기 답변을 얻고 결과를 저장 / 캐시하는 적절한 접근 방식을 선택하는 것이 좋습니다.
마지막으로이 고려 사항이 있습니다. 초급 직업을 찾고 괴짜 관리자 또는 미래의 동료와 인터뷰하고 있습니까? 그렇다면 상대 기술 장단점을 설명하는 모든 방법을 사용할 수 있습니다. 좀 더 관리적인 직업을 찾고 있다면, 솔루션의 개발 및 유지 보수 비용에 관심이있는 관리자처럼 접근하여 “정말 감사합니다”라고 말하고 면접관이 CS 퀴즈에 중점을두고 싶다면 떠나십시오. . 그와 당신은 거기에 많은 발전 가능성이 없을 것입니다.
다음 인터뷰에서 더 나은 행운을 빕니다.
답변
이에 대한 나의 즉각적인 반응은 힙을 사용하는 것이지만 한 번에 모든 입력 값을 유지하지 않고 QuickSelect를 사용하는 방법이 있습니다.
200 크기의 배열을 만들고 처음 200 개의 입력 값으로 채 웁니다. QuickSelect를 실행하고 낮은 100을 버리고 100 개의 빈 공간을 남겨 둡니다. 다음 100 개의 입력 값을 읽고 QuickSelect를 다시 실행하십시오. 전체 입력을 100 개씩 배치 할 때까지 계속하십시오.
마지막에는 상위 100 개의 값이 있습니다. N 값의 경우, 대략 N / 100 배 정도 빠른 선택을 실행했습니다. 각 Quickselect는 상수의 약 200 배이므로 총 비용은 상수의 2N 배입니다. 이것은이 설명에서 100으로 배선하려는 매개 변수 크기에 관계없이 입력 크기가 선형으로 보입니다.
답변
빠른 선택 알고리즘 을 사용 하여 (순서별) 인덱스 [billion-101]에서 숫자를 찾은 다음 숫자를 반복하여 해당 숫자보다 큰 숫자를 찾을 수 있습니다.
array={...the billion numbers...}
result[100];
pivot=QuickSelect(array,billion-101);//O(N)
for(i=0;i<billion;i++)//O(N)
if(array[i]>=pivot)
result.add(array[i]);
이 알고리즘 시간은 다음과 같습니다. 2 XO (N) = O (N) (평균 사례 성능)
Thomas Jungblut 와 같은 두 번째 옵션 은 다음과 같습니다.
힙 사용 MAX 힙을 빌드하면 O (N)가 걸리고, 상위 100 개의 최대 숫자는 힙 맨 위에 오게됩니다. 힙 (100 XO (Log (N)))에서 힙을 가져 오면됩니다.
이 알고리즘 시간은 다음과 같습니다 .O (N) + 100 XO (Log (N)) = O (N)
답변
다른 quickselect 솔루션이 다운 보트되었지만 quickselect가 크기가 100 인 큐를 사용하는 것보다 솔루션을 더 빨리 찾게된다는 사실은 여전히 남아 있습니다. Quickselect의 예상 실행 시간은 2n + o (n)입니다. 아주 간단한 구현은
array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
if(array[i]>r)
add array[i] to result
평균 3n + o (n) 비교가 필요합니다. 또한, quickselect가 배열에서 가장 큰 100 개의 항목을 가장 오른쪽에있는 100 개의 위치에 남겨둔다는 사실을 사용하여보다 효율적으로 만들 수 있습니다. 실제로, 실행 시간은 2n + o (n)으로 향상 될 수 있습니다.
이것이 최악의 경우는 아니지만 예상되는 피벗 선택 전략을 사용하여 예상되는 문제가 있습니다 (예 : 임의로 21 요소를 선택하고 피벗으로 21 요소의 중간 값을 선택). 비교 횟수는 다음과 같습니다. 임의로 작은 상수 c에 대해 최대 (2 + c) n의 높은 확률로 보장 c.
실제로 최적화 된 샘플링 전략 (예 : 임의로 샘플 sqrt (n) 요소를 선택하고 99 번째 백분위 수를 선택)을 사용하면 임의로 작은 c에 대해 실행 시간을 (1 + c) n + o (n)으로 줄일 수 있습니다. (K라고 가정하면, 선택 될 요소의 수는 o (n)입니다).
반면, 크기가 100 인 큐를 사용하려면 O (log (100) n) 비교가 필요하며 100의 로그베이스 2는 대략 6.6입니다.
크기 N의 배열에서 K가 가장 큰 K 요소를 선택하는보다 추상적 인 의미 에서이 문제를 생각하면 K = o (N)이지만 K와 N 모두 무한대로 이동하면 빠른 선택 버전의 실행 시간은 다음과 같습니다. O (N) 및 큐 버전은 O (N log K)가되므로 이런 의미에서 quickselect도 무조건 우수합니다.
의견에 따르면 대기열 솔루션은 임의의 입력에서 예상 시간 N + K log N에서 실행됩니다. 물론, 무작위 입력 가정은 질문에서 명시 적으로 언급하지 않는 한 절대 유효하지 않습니다. 대기열 솔루션은 임의의 순서로 배열을 순회하도록 만들 수 있지만, 이로 인해 전체 입력 배열을 치환하거나 길이가 N 인 새로운 배열을 할당 할뿐만 아니라 난수 생성기에 대한 N 호출의 추가 비용이 발생합니다. 무작위 지수.
문제로 인해 원래 배열의 요소를 이동할 수없고 메모리 할당 비용이 높아서 배열 복제가 옵션이 아닌 경우 이는 다른 문제입니다. 그러나 실행 시간 측면에서 이것은 최상의 솔루션입니다.
