讨论/技术交流/求助|字节跳动面试题:找出重复指令/
求助|字节跳动面试题:找出重复指令

问题描述

在服务器上有一个 10TB 大小的文本文件(假设是 in.txt),文件内存有一些指令,指令之间用逗号隔开(任何一个指令中都不含有逗号,且文件中所有字符均为 ASCII 码字符)。这些指令中,有一些指令出现了 2 次,试编写程序找出这些重复指令,并输出至一个文件(假设是 ans.txt)中,每行输出一个指令。注:该服务器仅有 256MB 内存。

样例输入(in.txt)
echo HelloWorld,ls,cd Desktop,mkdir work,cd work,touch test.py,rm *.py,ls,cd ..,cd ..,cd Desktop,echo GameIsOver,cd work
样例输出 (ans.txt)
ls
cd ..
cd Desktop
cd work

思考方向

我当时试图用布隆过滤器来解决这个问题。

  1. 由于所有字符都是 ASCII 码字符,因此,一条指令可以看作是一个 256 进制的数。
  2. 先设置 8 个不同的哈希函数
    hi(x)=x  mod  ci        i=0,1,2,3,...,7 h_i(x)=x \; mod \; c_i \;\;\;\; i=0,1,2,3,...,7
    其中 xx 为指令对应的 256 进制数。
  3. 那么,我们可以用 8 个 bitmap 来判断这些哈希值是否出现过(如果出现过则对应位置为1)。
  4. 当读入一个指令时,我们看这个指令对应的 8 个哈希值是否都出现过。
    • 如果都出现过,则我们认为这条指令之前出现过,是重复指令。我们把这条指令输出。
    • 如果有一个值没有出现过,则它不是重复指令。我们把 8 个 bitmap 对应的位置赋值为1。
  5. 考虑到指令可能非常长,内存里存不下,我用一个 temp.txt 文件来存储当前的指令。
代码实现
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>

using namespace std;

int size[8] = {209710001,209711003,209712023,209713019,209714009,209715007,209716009,209717017};
int cnt[8];
bitset<209717017> H[8];

bool check() {
    for (int i = 0; i < 8; ++ i) {
        if (!H[i].test(cnt[i])) {
            return false;
        }
    }
    return true;
}

void fillIt() {
    for (int i = 0; i < 8; ++ i) {
        H[i][cnt[i]] = 1;
    }
}

int main() {
    FILE* finp;
    finp = fopen("in.txt", "r");
    FILE* ftemp;
    ftemp = fopen("temp.txt", "w");
    FILE* fans;
    fans = fopen("ans.txt", "w");

    while (true) {
        int c = getc(finp);
        if (c==EOF || c==',') {
            fclose(ftemp);
            if (check()) {
                FILE* tp;
                tp = fopen("temp.txt", "r");
                int ch;
                while ((ch = getc(tp)) != EOF) {
                    fprintf(fans, "%c", (char)ch);
                }
                fprintf(fans, "\n");
                fclose(tp);
            } else {
                fillIt();
            }
            memset(cnt, 0, sizeof(cnt));
            ftemp = fopen("temp.txt", "w");
            if (c==EOF) {
                break;
            }
        } else {
            for (int i = 0; i < 8; ++ i) {
                cnt[i] = (int)(((long long)cnt[i] * 256ll + (long long)c) % (long long)size[i]);
            }
            fprintf(ftemp, "%c", (char)c);
        }
    }

    fclose(finp);
    fclose(ftemp);
    fclose(fans);
    return 0;
}

需要帮助的地方

当时我说完这个方案,面试官就说:我这个方法可能把不重复的指令也输出了,有没有什么办法可以解决这个缺陷?这个问题我到现在也不知道怎么回答。

2

一条指令 3GB 了解一下。

展开全部 6 讨论