developer tip

주어진 40 억 중 하나가 아닌 정수 찾기

copycodes 2020. 9. 30. 11:02
반응형

주어진 40 억 중 하나가 아닌 정수 찾기

인터뷰 질문입니다.

40 억 개의 정수가있는 입력 파일이 주어지면 파일에 포함되지 않은 정수를 생성하는 알고리즘을 제공하십시오. 1GB 메모리가 있다고 가정합니다. 메모리가 10MB 만있는 경우 수행 할 작업을 수행하십시오.

내 분석 :

파일 크기는 4 × 10 9 × 4 바이트 = 16GB입니다.

외부 정렬을 할 수 있으므로 정수의 범위를 알 수 있습니다. 내 질문은 정렬 된 큰 정수 세트에서 누락 된 정수를 감지하는 가장 좋은 방법은 무엇입니까?

내 이해 (모든 답변을 읽은 후) :

32 비트 정수에 대해 이야기하고 있다고 가정합니다. 2 ^ 32 = 4 * 10 9 개의 고유 한 정수가 있습니다.

사례 1 : 1GB = 1 * 10 9 * 8 비트 = 80 억 비트 메모리가 있습니다.

솔루션 : 하나의 고유 한 정수를 나타내는 1 비트를 사용하면 충분합니다. 정렬 할 필요가 없습니다. 이행:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

사례 2 : 10MB 메모리 = 10 * 10 6 * 8 비트 = 8 천만 비트

솔루션 : 가능한 모든 16 비트 접두사에 대해 2 ^ 16 개의 정수 = 65536 개가 있으며 2 ^ 16 * 4 * 8 = 2 백만 비트가 필요합니다. 65536 개의 버킷을 빌드해야합니다. 최악의 경우 40 억 개의 정수가 모두 동일한 버킷에 속하기 때문에 각 버킷에 대해 모든 가능성을 포함하는 4 바이트가 필요합니다.

  1. 파일의 첫 번째 패스를 통해 각 버킷의 카운터를 구축합니다.
  2. 버킷을 스캔하여 65536 히트 미만의 첫 번째 버킷을 찾으십시오.
  3. 파일의 두 번째 패스를 통해 2 단계에서 찾은 높은 16 비트 접두사를 가진 새 버킷을 빌드합니다.
  4. 3 단계에서 빌드 한 버킷을 스캔하고 히트가없는 첫 번째 버킷을 찾습니다.

코드는 위의 코드와 매우 유사합니다.

결론 : 파일 패스를 늘려 메모리를 줄입니다.

늦게 도착하는 사람들을위한 설명 : 질문에 따르면 파일에 포함되지 않은 정수가 정확히 하나라는 말은 없습니다. 적어도 대부분의 사람들이 그것을 해석하는 방식은 아닙니다. 주석 스레드의 많은 의견이 있다 하지만, 작업의 변화에 대해. 불행히도 댓글 스레드에 그것을 소개 한 댓글은 나중에 작성자에 의해 삭제되었으므로 이제 고아가 답글을 달아 모든 것을 오해 한 것처럼 보입니다. 매우 혼란 스럽습니다. 죄송합니다.

"정수"가 32 비트를 의미한다고 가정하면 : 10MB의 공간이 있으면 한 번의 패스에서 가능한 모든 16 비트 접두사에 대해 주어진 16 비트 접두사가있는 입력 파일에 몇 개의 숫자가 있는지 계산하기에 충분합니다. 입력 파일. 버킷 중 하나 이상이 2 ^ 16 회 미만으로 적중됩니다. 두 번째 패스를 수행하여 해당 버킷에서 이미 사용 된 가능한 숫자를 찾습니다.

32 비트 이상을 의미하지만 여전히 제한된 크기를 의미하는 경우 : 32 비트 범위 (부호 있음 또는 부호 없음, 선택)를 벗어나는 모든 입력 번호를 무시하고 위와 같이 수행합니다.

이 "정수"란 수학적 정수 : 읽기 한번 입력과의 킵 트랙을 통해 가장 많은 수의 당신이 이제까지 본 것 중 가장 긴 숫자의 길이. 완료되면 최대 값과 1 자리가 더있는 난수 1을 출력 합니다 . (파일에있는 숫자 중 하나는 정확히 표현하는 데 10MB 이상이 걸리는 큰 숫자 일 수 있지만 입력이 파일 인 경우 최소한 그 안에 맞는 길이 를 나타낼 수 있습니다 .)

통계적으로 정보에 입각 한 알고리즘은 결정적 접근 방식보다 더 적은 패스를 사용하여이 문제를 해결합니다.

매우 큰 정수가 허용되면 O (1) 시간에 고유 할 수있는 숫자를 생성 할 수 있습니다. GUID 와 같은 의사 난수 128 비트 정수는 640 억 개의 경우 중 1 개 미만으로 집합에있는 기존 40 억 개의 정수 중 하나와 만 충돌합니다.

정수가 32 비트로 제한되면 10MB 미만을 사용하여 단일 패스에서 고유 할 수있는 숫자를 생성 할 수 있습니다. 의사 랜덤 32 비트 정수가 40 억 개의 기존 정수 중 하나와 충돌 할 확률은 약 93 % (4e9 / 2 ^ 32)입니다. 1000 개의 의사 난수 정수가 모두 충돌 할 확률은 12,000 억억 분의 1 미만입니다 (1 충돌 확률 ^ 1000). 따라서 프로그램이 1000 개의 의사 난수 후보를 포함하는 데이터 구조를 유지하고 알려진 정수를 반복하여 후보에서 일치를 제거하는 경우 파일에없는 정수를 하나 이상 찾는 것이 확실합니다.

이 문제에 대한 자세한 논의는 Jon Bentley "Column 1. Cracking the Oyster" 프로그래밍 Pearls Addison-Wesley pp.3-10에서 논의되었습니다.

Bentley는 외부 정렬, 여러 외부 파일을 사용하는 Merge Sort 등 여러 접근 방식에 대해 설명합니다. 그러나 Bentley가 제안하는 가장 좋은 방법은 비트 필드를 사용하는 단일 패스 알고리즘 입니다. 그는이를 유머러스하게 "Wonder Sort"라고 부릅니다. :) Coming to the problem, 40 억 숫자는 다음과 같이 표현할 수 있습니다.

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

bitset을 구현하는 코드는 간단합니다. ( 솔루션 페이지 에서 가져옴 )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentley의 알고리즘은 파일에 대한 단일 패스를 만들어 set배열에서 적절한 비트를 지정한 다음 test위의 매크로를 사용하여이 배열을 검사 하여 누락 된 숫자를 찾습니다.

사용 가능한 메모리가 0.466GB 미만인 경우 Bentley는 사용 가능한 메모리에 따라 입력을 범위로 나누는 k-pass 알고리즘을 제안합니다. 매우 간단한 예를 들어, 1 바이트 (예 : 8 개의 숫자를 처리하는 메모리) 만 사용할 수 있고 범위가 0 ~ 31 인 경우이를 0 ~ 7, 8 ~ 15, 16 ~ 22 등의 범위로 나눕니다. 각 32/8 = 4패스 에서이 범위를 처리 합니다.

HTH.

문제는 파일에없는 가능한 가장 작은 숫자를 찾아야한다고 지정하지 않았기 때문에 입력 파일 자체보다 긴 숫자를 생성 할 수 있습니다. :)

1GB RAM 변형의 경우 비트 벡터를 사용할 수 있습니다. 40 억 비트 == 500MB 바이트 배열을 할당해야합니다. 입력에서 읽은 각 숫자에 대해 해당 비트를 '1'로 설정합니다. 완료되면 비트를 반복하고 여전히 '0'인 첫 번째 비트를 찾으십시오. 그 색인이 답입니다.

32 비트 정수인 경우 (2 32에 가까운 ~ 40 억 개의 숫자를 선택했을 가능성이 있음 ) 40 억 개의 숫자 목록은 가능한 정수의 최대 93 %를 차지합니다 (4 * 10 9 / (2 32 ) ). 따라서 각 비트가 0으로 초기화 된 2 32 비트의 비트 배열을 생성하는 경우 (2 29 바이트 ~ 500MB RAM 을 차지합니다 . 바이트 = 2 3 비트 = 8 비트를 기억 하십시오) 정수 목록을 읽고 각 int에 대해 해당하는 비트 배열 요소를 0에서 1까지 설정합니다. 그런 다음 비트 배열을 읽고 여전히 0 인 첫 번째 비트를 반환합니다.

RAM이 적은 경우 (~ 10MB)이 솔루션을 약간 수정해야합니다. 10MB ~ 83886080 비트는 0에서 83886079 사이의 모든 숫자에 대해 비트 배열을 수행하기에 충분합니다. 따라서 정수 목록을 읽을 수 있습니다. 비트 배열에 0에서 83886079 사이의 # 만 기록하십시오. 숫자가 무작위로 분포 된 경우 압도적 인 확률로 (약 10 -2592069 만큼 100 % 차이가 난다 ) 누락 된 int를 찾을 수 있습니다. 실제로 1에서 2048까지의 숫자 (256 바이트 RAM 만 포함) 만 선택하면 여전히 누락 된 숫자가 시간의 압도적 비율 (99.99999999999999999999999999999999999999999999999999999999999995 %)을 찾을 수 있습니다.

그러나 약 40 억 개의 숫자 대신에 가정 해 봅시다. 2 32-1 숫자와 10MB 미만의 RAM이 있습니다. 따라서 작은 범위의 정수는 숫자를 포함하지 않을 가능성이 적습니다.

당신이 목록의 각 INT 고유 것을 보장한다면, 당신은 숫자를 합계 한 # 전체 합계 (½)에 누락 된 합을 빼기 수 (2 32 ) (2 32 - 1)의 누락 INT를 찾을 수 = 9223372034707292160 . 그러나 int가 두 번 발생하면이 메서드는 실패합니다.

그러나, 당신은 항상 분할하고 정복 할 수 있습니다. 순진한 방법은 배열을 읽고 전반 (0 ~ 2 31 -1)과 후반 (2 31 , 2 32 )에 있는 숫자의 수를 세는 것 입니다. 그런 다음 더 적은 수의 범위를 선택하고 해당 범위를 반으로 나눕니다. ((2 31 , 2 32 )에 숫자가 두 개 더 적 으면 다음 검색은 (2 31 , 3 * 2 30 -1), (3 * 2 30 , 2 32 ) 범위의 숫자를 계산합니다 . 숫자가 0 인 범위를 찾고 답을 찾을 때까지 반복합니다 .O (lg N) ~ 32가 배열을 읽어야합니다.

그 방법은 비효율적이었습니다. 우리는 각 단계에서 두 개의 정수만 사용합니다 (또는 4 바이트 (32 비트) 정수가있는 약 8 바이트의 RAM). 더 나은 방법은 sqrt (2 32 ) = 2 16 = 65536 bin 으로 나누는 것입니다 . 각 bin에는 65536 개의 숫자가 있습니다. 각 bin은 개수를 저장하는 데 4 바이트가 필요하므로 2 18 바이트 = 256kB 가 필요합니다 . 빈 0이되어, (0 (2) = 65535 (16) -1), 빈 1 (2, 16 = 65536 (2) * 2 (16) , 빈 (2) -1 = 131,071) (2 * 2 16 = 131072 3 2 * 16 - 1 = 196607). 파이썬에서는 다음과 같은 것이 있습니다.

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

~ 40 억 정수 목록을 읽으십시오. 그리고 2 개의 16 개 bin 각각에 몇 개의 int가 있는지 계산 하고 65536 개의 숫자가 모두 포함되지 않은 incomplete_bin을 찾습니다. 그런 다음 40 억 개의 정수 목록을 다시 읽습니다. 그러나 이번에는 정수가 해당 범위에있을 때만 알아 차립니다. 당신이 그들을 찾을 때 조금 뒤집습니다.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

왜 그렇게 복잡하게 만들까요? 파일에없는 정수를 요구합니까?

지정된 규칙에 따라 저장해야하는 유일한 것은 파일에서 지금까지 발견 한 가장 큰 정수입니다. 전체 파일을 읽은 후에는 그보다 큰 숫자 1을 반환합니다.

규칙에 따라 정수의 크기 나 알고리즘이 반환하는 숫자에 대한 제한이 없기 때문에 maxint 또는 그 어떤 것도 적중 할 위험이 없습니다.

이것은 이진 검색의 변형을 사용하여 아주 작은 공간에서 해결할 수 있습니다.

  1. 허용되는 숫자 범위에서 시작 0합니다 4294967295.

  2. 중간 점을 계산하십시오.

  3. 파일을 반복하여 중간 값보다 작거나 높은 숫자의 수를 계산합니다.

  4. 숫자가 같지 않으면 완료된 것입니다. 중간 점 숫자가 답입니다.

  5. 그렇지 않으면 숫자가 가장 적은 범위를 선택하고이 새 범위로 2 단계부터 반복합니다.

파일을 통해 최대 32 개의 선형 스캔이 필요하지만 범위와 개수를 저장하는 데 몇 바이트의 메모리 만 사용합니다.

이것은 16k 대신 두 개의 bin을 사용한다는 점을 제외하면 Henning의 솔루션 과 본질적으로 동일 합니다.

편집 좋아, 이것은 파일의 정수가 일부 정적 분포를 따른다고 가정하기 때문에 충분히 고려되지 않았습니다. 분명히 그들은 그럴 필요가 없지만 그래도 시도해야합니다.

약 43 억 개의 32 비트 정수가 있습니다. 우리는 그것들이 파일에 어떻게 분포되어 있는지 모르지만 최악의 경우는 가장 높은 Shannon 엔트로피를 가진 것입니다. 이 경우 하나의 정수가 파일에 나타나지 않을 확률은 다음과 같습니다.

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Shannon 엔트로피가 낮을수록이 확률은 평균적으로 높지만이 최악의 경우에도 무작위 정수로 5 번 추측 한 후 발생하지 않는 숫자를 찾을 수있는 확률은 90 %입니다. 의사 난수 생성기로 이러한 숫자를 만들고 목록에 저장하십시오. 그런 다음 int 다음에 int를 읽고 모든 추측과 비교하십시오. 일치하는 항목이 있으면이 목록 항목을 제거하십시오. 파일을 모두 살펴본 후에는 추측이 두 개 이상 남을 가능성이 있습니다. 그들 중 하나를 사용하십시오. 추측이 남아 있지 않은 드물게 (최악의 경우에도 10 %) 이벤트에서 새로운 임의의 정수 세트를 얻습니다 (이번에는 더 많이 (10-> 99 %)).

메모리 소비 : 수십 바이트, 복잡성 : O (n), 오버 헤드 : 어쨌든 int를 비교하는 대신 피할 수없는 하드 디스크 액세스에 대부분의 시간이 소요되므로 필요합니다.

정적 분포를 가정 하지 않는 실제 최악의 경우 는 모든 정수가 최대로 발생한다는 것입니다. 한 번이면 모든 정수의 1-4000000000 / 2³² ≈ 6 % 만 파일에 나타나지 않기 때문입니다. 따라서 추측이 더 필요하지만 여전히 많은 양의 메모리를 소모하지는 않습니다.

[0, 2 ^ x -1] 범위에서 하나의 정수가 누락 된 경우 모두 함께 xor하십시오. 예를 들면 :

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(이 질문에 대한 정확한 답은 아니지만 매우 유사한 질문에 대한 좋은 답변입니다.)

원래 질문의 현재 문구를 기반으로 가장 간단한 해결책은 다음과 같습니다.

파일에서 최대 값을 찾은 다음 여기에 1을 더합니다.

값이 큰 집합의 일부가 아닌 경우 절대적으로 매우 효율적으로 결정할 수 있는 확률 적 블룸 필터에 대해 들어 봤는지 확인하려고 할 수 있습니다 (하지만 집합의 구성원 일 가능성이 높은 경우에만 결정할 수 있음).

를 사용합니다 BitSet. 바이트 당 8 개로 BitSet에 압축 된 40 억 정수 (최대 2 ^ 32 정수라고 가정)는 2 ^ 32 / 2 ^ 3 = 2 ^ 29 = 약 0.5Gb입니다.

좀 더 자세한 정보를 추가하려면 숫자를 읽을 때마다 BitSet에서 해당 비트를 설정하십시오. 그런 다음 BitSet을 통과하여 존재하지 않는 첫 번째 숫자를 찾습니다. 사실, 반복적으로 난수를 선택하고 존재하는지 테스트하여이를 효과적으로 수행 할 수 있습니다.

실제로 BitSet.nextClearBit (0)은 설정되지 않은 첫 번째 비트를 알려줍니다.

BitSet API를 살펴보면 0..MAX_INT 만 지원하는 것으로 보이므로 + 've에 대해 하나, 숫자'에 대해 하나씩 2 개의 BitSet이 필요할 수 있지만 메모리 요구 사항은 변경되지 않습니다.

크기 제한이없는 경우 가장 빠른 방법은 파일의 길이를 가져 와서 파일의 길이를 1 개의 임의의 숫자 (또는 "11111 ..."s)로 생성하는 것입니다. 장점 : 파일을 읽을 필요도없고 메모리 사용을 거의 0으로 최소화 할 수 있습니다. 단점 : 수십억 자릿수를 인쇄합니다.

그러나 유일한 요소가 메모리 사용량을 최소화하고 다른 중요한 사항이 없다면 이것이 최적의 솔루션이 될 것입니다. 심지어 "최악의 규칙 남용"상을받을 수도 있습니다.

숫자의 범위가 항상 2 ^ n (짝수 2의 거듭 제곱)이라고 가정하면 배타적 또는 작동합니다 (다른 포스터에 표시됨). 그 이유를 증명해 보겠습니다.

이론

2^n하나의 요소가 누락 된 요소가있는 정수의 0 기반 범위가 주어지면 , 단순히 알려진 값을 함께 xor-ing하여 누락 된 수를 산출함으로써 누락 된 요소를 찾을 수 있습니다.

증거

n = 2를 살펴 보겠습니다. n = 2의 경우 4 개의 고유 한 정수 (0, 1, 2, 3)를 나타낼 수 있습니다. 비트 패턴은 다음과 같습니다.

  • 0-00
  • 1-01
  • 2 ~ 10
  • 3-11

이제 살펴보면 모든 비트가 정확히 두 번 설정됩니다. 따라서 짝수로 설정되고 배타적-또는 숫자는 0이됩니다. 단일 숫자가 누락 된 경우 배타적-또는은 누락 된 숫자로 배타적 또는 배타적 일 때 결과가 나오는 숫자를 생성합니다. 0. 따라서 누락 된 숫자와 결과 배타적 ored 숫자는 정확히 동일합니다. 2를 제거하면 결과 xor는 10(또는 2)가됩니다.

이제 n + 1을 봅시다. 하자의 각 비트에 설정 한 횟수 전화 n, x각 비트가 설정 횟수를 n+1 y. 의 값은 y동일 할 것이다 y = x * 2있기 때문에 x와 요소 n+10 비트 세트 및 x와 소자 n+1(1)에 비트를 설정하고 이후 2x항상 짝수가 될 것이며, n+1항상 각 비트 횟수로 설정 한 것이다.

따라서 n=2작동하고 n+1작동하므로 xor 메서드는의 모든 값에 대해 작동합니다 n>=2.

0 기반 범위에 대한 알고리즘

이것은 아주 간단합니다. 2 * n 비트의 메모리를 사용하므로 32 비트 미만의 모든 범위에 대해 2 개의 32 비트 정수가 작동합니다 (파일 설명자가 사용하는 모든 메모리 무시). 그리고 그것은 파일의 단일 패스를 만듭니다.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

임의 기반 범위에 대한 알고리즘

이 알고리즘은 전체 범위가 2 ^ n 인 한 모든 시작 번호에서 끝 번호까지의 범위에 대해 작동합니다 ... 이것은 기본적으로 최소값이 0이되도록 범위를 다시 설정합니다.하지만 2 번의 패스가 필요합니다. 파일을 통해 (첫 번째는 최소값을 가져오고 두 번째는 누락 된 int를 계산합니다).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

임의 범위

모든 범위가 적어도 한 번은 2 ^ n의 거듭 제곱을 교차하므로이 수정 된 방법을 임의의 범위 집합에 적용 할 수 있습니다. 이것은 하나의 누락 된 비트가있는 경우에만 작동합니다. 정렬되지 않은 파일을 2 회 통과하지만 매번 누락 된 단일 번호를 찾습니다.

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

기본적으로 0을 기준으로 범위를 다시 설정합니다. 그런 다음 exclusive-or를 계산할 때 추가 할 정렬되지 않은 값의 수를 계산합니다. 그런 다음 누락 된 값을 처리하기 위해 정렬되지 않은 값의 개수에 1을 더합니다 (누락 된 값을 계산). 그런 다음 n 값을 계속 xoring하고 n이 2의 거듭 제곱이 될 때까지 매번 1 씩 증가합니다. 그런 다음 결과는 원래 기준으로 다시 기반합니다. 끝난.

다음은 PHP에서 테스트 한 알고리즘입니다 (파일 대신 배열을 사용하지만 동일한 개념).

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

값의 범위 (음수를 포함하여 테스트 함)가없는 배열을 해당 범위 내에없는 배열로 공급하면 매번 올바른 값을 찾았습니다.

또 다른 접근

외부 정렬을 사용할 수 있기 때문에 갭을 확인하는 것은 어떨까요? 이 알고리즘을 실행하기 전에 파일이 정렬되었다고 가정하면 :

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

부적절하게 인용되지 않는 한 속임수 질문. 최대 정수를 얻으려면 파일을 한 번 읽고 n반환하십시오 n+1.

물론 n+1정수 오버플로 가 발생할 경우를 대비하여 백업 계획이 필요합니다 .

입력 파일의 크기를 확인한 다음 그 크기의 파일로 표현하기에는 너무 큰 숫자 를 출력 하십시오 . 이것은 값싼 속임수처럼 보일지 모르지만 인터뷰 문제에 대한 창의적인 해결책이고 기억 문제를 깔끔하게 회피하며 기술적으로 O (n)입니다.

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Should print 10 bitcount - 1, which will always be greater than 2 bitcount. Technically, the number you have to beat is 2 bitcount - (4 * 109 - 1), since you know there are (4 billion - 1) other integers in the file, and even with perfect compression they'll take up at least one bit each.

  • The simplest approach is to find the minimum number in the file, and return 1 less than that. This uses O(1) storage, and O(n) time for a file of n numbers. However, it will fail if number range is limited, which could make min-1 not-a-number.

  • The simple and straightforward method of using a bitmap has already been mentioned. That method uses O(n) time and storage.

  • A 2-pass method with 2^16 counting-buckets has also been mentioned. It reads 2*n integers, so uses O(n) time and O(1) storage, but it cannot handle datasets with more than 2^16 numbers. However, it's easily extended to (eg) 2^60 64-bit integers by running 4 passes instead of 2, and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly, in which case run time is no longer O(n) but instead is O(n*log n).

  • The method of XOR'ing all the numbers together, mentioned so far by rfrankel and at length by ircmaxell answers the question asked in stackoverflow#35185, as ltn100 pointed out. It uses O(1) storage and O(n) run time. If for the moment we assume 32-bit integers, XOR has a 7% probability of producing a distinct number. Rationale: given ~ 4G distinct numbers XOR'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren't all distinct, the XOR method's probability of success rises.

For some reason, as soon as I read this problem I thought of diagonalization. I'm assuming arbitrarily large integers.

Read the first number. Left-pad it with zero bits until you have 4 billion bits. If the first (high-order) bit is 0, output 1; else output 0. (You don't really have to left-pad: you just output a 1 if there are not enough bits in the number.) Do the same with the second number, except use its second bit. Continue through the file in this way. You will output a 4-billion bit number one bit at a time, and that number will not be the same as any in the file. Proof: it were the same as the nth number, then they would agree on the nth bit, but they don't by construction.

You can use bit flags to mark whether an integer is present or not.

After traversing the entire file, scan each bit to determine if the number exists or not.

Assuming each integer is 32 bit, they will conveniently fit in 1 GB of RAM if bit flagging is done.

Strip the white space and non numeric characters from the file and append 1. Your file now contains a single number not listed in the original file.

From Reddit by Carbonetc.

Just for the sake of completeness, here is another very simple solution, which will most likely take a very long time to run, but uses very little memory.

Let all possible integers be the range from int_min to int_max, and bool isNotInFile(integer) a function which returns true if the file does not contain a certain integer and false else (by comparing that certain integer with each integer in the file)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

For the 10 MB memory constraint:

  1. Convert the number to its binary representation.
  2. Create a binary tree where left = 0 and right = 1.
  3. Insert each number in the tree using its binary representation.
  4. If a number has already been inserted, the leafs will already have been created.

When finished, just take a path that has not been created before to create the requested number.

4 billion number = 2^32, meaning 10 MB might not be sufficient.

EDIT

An optimization is possible, if two ends leafs have been created and have a common parent, then they can be removed and the parent flagged as not a solution. This cuts branches and reduces the need for memory.

EDIT II

There is no need to build the tree completely too. You only need to build deep branches if numbers are similar. If we cut branches too, then this solution might work in fact.

I will answer the 1 GB version:

There is not enough information in the question, so I will state some assumptions first:

The integer is 32 bits with range -2,147,483,648 to 2,147,483,647.

Pseudo-code:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

As long as we're doing creative answers, here is another one.

Use the external sort program to sort the input file numerically. This will work for any amount of memory you may have (it will use file storage if needed). Read through the sorted file and output the first number that is missing.

Bit Elimination

One way is to eliminate bits, however this might not actually yield a result (chances are it won't). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Bit Counts

Keep track of the bit counts; and use the bits with the least amounts to generate a value. Again this has no guarantee of generating a correct value.

Range Logic

Keep track of a list ordered ranges (ordered by start). A range is defined by the structure:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Go through each value in the file and try and remove it from the current range. This method has no memory guarantees, but it should do pretty well.

2128*1018 + 1 ( which is (28)16*1018 + 1 ) - cannot it be a universal answer for today? This represents a number that cannot be held in 16 EB file, which is the maximum file size in any current file system.

I think this is a solved problem (see above), but there's an interesting side case to keep in mind because it might get asked:

If there are exactly 4,294,967,295 (2^32 - 1) 32-bit integers with no repeats, and therefore only one is missing, there is a simple solution.

Start a running total at zero, and for each integer in the file, add that integer with 32-bit overflow (effectively, runningTotal = (runningTotal + nextInteger) % 4294967296). Once complete, add 4294967296/2 to the running total, again with 32-bit overflow. Subtract this from 4294967296, and the result is the missing integer.

The "only one missing integer" problem is solvable with only one run, and only 64 bits of RAM dedicated to the data (32 for the running total, 32 to read in the next integer).

Corollary: The more general specification is extremely simple to match if we aren't concerned with how many bits the integer result must have. We just generate a big enough integer that it cannot be contained in the file we're given. Again, this takes up absolutely minimal RAM. See the pseudocode.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

As Ryan said it basically, sort the file and then go over the integers and when a value is skipped there you have it :)

EDIT at downvoters: the OP mentioned that the file could be sorted so this is a valid method.

If you don't assume the 32-bit constraint, just return a randomly generated 64-bit number (or 128-bit if you're a pessimist). The chance of collision is 1 in 2^64/(4*10^9) = 4611686018.4 (roughly 1 in 4 billion). You'd be right most of the time!

(Joking... kind of.)

참고URL : https://stackoverflow.com/questions/7153659/find-an-integer-not-among-four-billion-given-ones

반응형

'developer tip' 카테고리의 다른 글

Python 애플리케이션에 가장 적합한 프로젝트 구조는 무엇입니까?  (0) 2020.09.30
모듈의 경로를 검색하는 방법은 무엇입니까?  (0) 2020.09.30
앱 스토어에서 앱에 연결하는 방법  (0) 2020.09.30
가장 유용한 속성  (0) 2020.09.29
C # 루프-중단 대 계속  (0) 2020.09.29

'developer tip'의 다른글

  • 현재글주어진 40 억 중 하나가 아닌 정수 찾기

관련글

댓글

티스토리툴바