나는 재미있는 직업 면접 경험을 가지고 있었다. 질문은 정말 쉽게 시작되었습니다.
Q1 : 우리는 숫자가 들어있는 가방을 가지고
1,2,3, …,100. 각 숫자는 정확히 한 번 표시되므로 100 개의 숫자가 있습니다. 이제 하나의 숫자가 가방에서 무작위로 선택됩니다. 빠진 번호를 찾으십시오.
물론이 인터뷰 질문을 들었으므로 다음과 같은 라인을 따라 매우 빠르게 대답했습니다.
A1 : 음, 숫자의 합
1 + 2 + 3 + … + N이다(N+1)(N/2)(참조 : 산술 시리즈의 합을 위키 백과 ). 를 들어N = 100, 합계입니다5050.따라서 모든 숫자가 백에 있으면 합계는 정확히
5050됩니다. 하나의 숫자가 누락되었으므로 합계는 이보다 작으며 차이는 그 숫자입니다.O(N)시간과O(1)공간 에서 누락 된 숫자를 찾을 수 있습니다 .
이 시점에서 나는 내가 잘했다고 생각했지만 갑자기 질문이 예기치 않게 바뀌었다.
Q2 : 맞습니다. 이제 두 개의 숫자가 없으면 어떻게해야합니까?
나는 이전에이 변형을 보거나들은 적이 없었고, 그래서 당황했고 질문에 대답 할 수 없었다. 면접관은 내 사고 과정을 알고 있다고 주장 했으므로 예상 제품과 비교하여 더 많은 정보를 얻을 수 있거나 첫 번째 패스 등에서 정보를 수집 한 후 두 번째 패스를 수행 할 수 있다고 언급했지만 실제로 촬영 중이었습니다. 실제로 솔루션에 대한 명확한 경로를 갖는 것이 아니라 어둠 속에서.
면접관은 두 번째 방정식을 갖는 것이 실제로 문제를 해결하는 한 가지 방법이라고 말함으로써 저를 격려하려고했습니다. 이 시점에서 나는 일종의 화를 내었고 (사전 답변을 알지 못했기 때문에) 이것이 일반적인 (읽기 : “유용한”) 프로그래밍 기술인지, 아니면 단지 트릭 / 고트 카 답변인지 물었다.
면접관의 대답은 나를 놀라게했다. 3 개의 누락 된 숫자를 찾기 위해 기술을 일반화 할 수있다. 실제로 k 개의 누락 된 숫자 를 찾기 위해 일반화 할 수 있습니다 .
Qk : 가방에 정확히 k 개의 숫자가 없으면 어떻게 효율적으로 찾을 수 있습니까?
몇 달 전 이었지만 여전히이 기술이 무엇인지 알 수 없었습니다. 분명히 Ω(N)모든 숫자를 한 번 이상 스캔해야하기 때문에 시간 하한이 있지만 면접관 은 해결 기술 의 시간 및 공간 복잡성 ( O(N)시간 입력 스캔 제외)이 N이 아닌 k 로 정의되어 있다고 주장했습니다 .
따라서 여기의 질문은 간단합니다.
- Q2를 어떻게 해결 하시겠습니까?
- Q3를 어떻게 해결 하시겠습니까?
- Qk를 어떻게 해결 하시겠습니까?
설명
- 일반적으로있다 N 1 ..에서 번호 N 뿐 아니라 1..100은.
- 비트 세트 사용 , 지정된 비트 값으로 각 숫자의 존재 여부를 인코딩하므로
O(N)추가 공간의 비트를 사용 하는 명확한 세트 기반 솔루션을 찾고 있지 않습니다 . N에 비례하여 추가 공간을 확보 할 수 없습니다 . - 또한 명확한 정렬 우선 접근 방식을 찾고 있지 않습니다. 이 방법과 세트 기반 접근 방식은 인터뷰에서 언급 할 가치가 있습니다 (구현하기 쉽고 N 에 따라 매우 실용적 일 수 있습니다). 나는 성배 솔루션을 찾고 있습니다 (구현하는 것이 실용적이지 않을 수도 있지만 그럼에도 불구하고 원하는 점근 적 특성을 가지고 있음).
물론 다시 입력을 스캔해야 O(N)하지만 ( N이 아닌 k로 정의 된) 소량의 정보 만 캡처 한 다음 어떻게 든 누락 된 k 를 찾아야합니다 .
답변
다음은 Dimitris Andreou의 링크에 대한 요약입니다 .
i = 1,2, .., k 인 i 번째 거듭 제곱의 합을 기억하십시오. 이것은 방정식 시스템을 해결하는 문제를 줄입니다.
a 1 + a 2 + … + a k = b 1
a 1 2 + a 2 2 + … + a k 2 = b 2
…
a 1 k + a 2 k + … + a k k = b k
사용 뉴턴의 신원을 b를 알고, 내가 계산 할 수 있습니다
c 1 = a 1 + a 2 + … a k
c 2 = a 1 a 2 + a 1 a 3 + … + a k-1 a k
…
c k = a 1 a 2 … a k
다항식 (xa 1 ) … (xa k )을 확장하면 계수는 정확히 c 1 , …, c k 가됩니다 . Viète의 공식을 참조하십시오 . 모든 다항식 요인이 고유하게 (다항식의 고리가 유클리드 영역 임), i 는 순열까지 고유하게 결정됨을 의미합니다 .
이것은 힘을 기억하는 것이 숫자를 회복하기에 충분하다는 증거를 끝냅니다. 상수 k의 경우이 방법이 좋습니다.
그러나, k가 변할 때, c 1 , …, c k 를 계산하는 직접적인 접근법 은 엄청나게 비싸다. 예를 들어, c k 는 모든 누락 된 수, 크기 n! / (nk)!의 곱 이기 때문이다 . 이를 극복하려면 Z q 필드 에서 계산을 수행하십시오 . 여기서 q는 n <= q <2n이되도록 소수 입니다.- Bertrand의 가정에 의해 존재합니다 . 수식은 여전히 유효하며 다항식의 인수 분해는 여전히 고유하므로 증거를 변경할 필요가 없습니다. 또한 유한 필드에 대한 인수 분해 알고리즘 (예 : Berlekamp 또는 Cantor-Zassenhaus 의 알고리즘)이 필요합니다 .
상수 k에 대한 고급 의사 코드 :
- 주어진 숫자의 i 번째 거듭 제곱 계산
- 알 수없는 숫자의 i 번째 거듭 제곱의 합계를 빼기 위해 빼십시오. 합을 불러라 b i .
- B의 연산 계수에 사용 뉴턴의 정체성 난 ; 그들을 c i 라고 불러라 . 기본적으로, c 1 = b 1 ; c 2 = (c 1 b 1 -b 2 ) / 2; 정확한 공식은 Wikipedia를 참조하십시오.
- 다항식 x k -c 1 x k-1 + … + c k를 인수 분해 합니다.
- 다항식의 근은 필요한 수 a 1 , …, a k 입니다.
다양한 k의 경우, 예를 들어 Miller-Rabin을 사용하여 소수 n <= q <2n을 찾고 모든 수를 모듈로 q로 줄인 단계를 수행하십시오.
편집 :이 답변의 이전 버전은 Z q 대신 q가 소수 인 유한 특성 필드 2 (q = 2 ^ (log n))를 사용할 수 있다고 언급했습니다 . 뉴턴의 공식은 최대 k의 숫자로 나눌 필요가 있기 때문에 그렇지 않습니다.
답변
Muthukrishnan-Data Stream Algorithms : Puzzle 1 : Finding Missing Numbers 페이지를 읽으면 찾을 수 있습니다 . 찾고있는 일반화를 정확하게 보여줍니다 . 아마도 이것은 당신의 면접관이 읽은 것과 아마도 이런 질문을 제기 한 이유 일 것입니다.
이제 사람들 만 Muthukrishnan의 치료법에 포함되거나 대체 된 답변을 삭제하기 시작하면이 텍스트를 더 쉽게 찾을 수 있습니다. 🙂
또한 의사 코드 (hurray! 까다로운 수학 공식을 읽을 필요가 없습니다 :)) (감사합니다.)가 포함 된 sdcvvc의 직접 관련 답변을 참조하십시오 .
답변
우리는 숫자 자체와 사각형 을 합하여 Q2를 풀 수 있습니다. 을 .
그런 다음 문제를 줄일 수 있습니다
k1 + k2 = x
k1^2 + k2^2 = y
어디서 x그리고y 합계가 예상 값보다 얼마나 멀리 있습니다.
대체는 다음을 제공합니다.
(x-k2)^2 + k2^2 = y
그런 다음 누락 된 숫자를 확인하기 위해 해결할 수 있습니다.
답변
@j_random_hacker가 지적했듯이 이것은 O (n) 시간과 O (1) 공간에서 중복 찾기 와 매우 유사 합니다. 내 대답의 적응도 여기에서 작동합니다.
“가방”이 1 기반 A[]크기의 배열 로 표현되어 있다고 가정하면 시간과 추가 공간 N - k에서 Qk를 해결할 수 있습니다 .O(N)O(k)
먼저 배열 A[]을 k요소 별로 확장 하여 크기가 커집니다 N. 이것은이다 O(k)추가 공간. 그런 다음 다음 의사 코드 알고리즘을 실행합니다.
for i := n - k + 1 to n
A[i] := A[1]
end for
for i := 1 to n - k
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 1 to n
if A[i] != i then
print i
end if
end for
첫 번째 루프는 k추가 항목을 배열의 첫 번째 항목과 동일하게 초기화합니다 (이것은 배열에 이미 존재하는 편리한 값입니다-이 단계 후에 크기의 초기 배열에서 누락 된 항목 N-k은 확장 배열에서 여전히 누락 됨).
두 번째 루프는 확장 배열을 치환하여 요소 x가 적어도 한 번 존재하면 해당 항목 중 하나가 위치에있게합니다.A[x] 됩니다.
중첩 루프가 있지만 여전히 O(N)시간에 실행됩니다 . 스왑은 다음 i과 같은 경우에만 발생 A[i] != i하며 각 스왑은 A[i] == i이전과 같지 않은 요소를 하나 이상 설정합니다 . 이는 총 스왑 수 (따라서 while루프 본문 의 총 실행 수 )가 최대 임을 의미합니다 N-1.
세 번째 루프 i는 값 i이 차지하지 않는 배열의 인덱스를 인쇄 i합니다. 이는 누락 된 것을 의미 합니다.
답변
나는이 문제를 해결하기 위해 4 살짜리 아이에게 물었다. 그는 숫자를 정렬 한 다음 계산했습니다. 이것은 O (주방 층)의 공간 요구 사항을 가지고 있으며 많은 공이 누락 된 것처럼 쉽게 작동합니다.
답변
가장 효율적인 솔루션인지 확실하지 않지만 모든 항목을 반복하고 비트 세트를 사용하여 숫자를 설정 한 다음 0 비트를 테스트합니다.
나는 간단한 해결책을 좋아합니다. 심지어 합이나 제곱합 등을 계산하는 것보다 빠를 것이라고 믿습니다.
답변
나는 수학을 확인하지는 않았지만 Σ(n^2)계산과 같은 패스로 계산 Σ(n)하면 누락 된 두 숫자를 얻을 수있는 충분한 정보를 제공 할 것이라고 생각합니다 Σ(n^3).3이있는 경우에도 수행하십시오.
