Algoritma apa yang diterapkan pengembang Yandex setiap hari

Perdebatan tentang apakah pengembang perlu menulis kode algoritmik untuk wawancara tidak ada habisnya. Untuk mendukung jawaban positif, saya sudah menerbitkan cerita tentang bagian algoritmik dengan menulis kode dalam Yandex dan contoh-contoh tugas yang dapat ditemukan di sana. Sekarang saya ingin mengembangkan topik ini dan menunjukkan contoh kode produksi nyata.

Semua contoh pernah ditulis oleh pengembang tertentu dalam proses penyelesaian tugas yang cukup rutin. Saya tidak memperbaiki kode sebelum dipublikasikan, saya hanya mengadaptasinya di beberapa tempat sehingga dapat dipahami tanpa mengenal basis kode kami. Oleh karena itu, beberapa contoh kode mungkin tidak tampak cukup keren bagi Anda, tetapi dalam kondisi tekanan tenggat waktu yang konstan, mustahil untuk menggiling secara total seluruh kode.

. C++, TypeScript Python. — , .

1. .

2016- .. , , . :

.

, , « », . . - - — , , : « », «», «». , - - «» «», .

. , , : - , ; . , -, . :

bool ContainsStopHash(const TString& text,
                      TEasyParser& easyParser,
                      const THashSet<size_t>& stopHashes)
{
    std::vector<TString> words;
    easyParser.ParseUTF8Text(text, &words);

    size_t unigramHash = 0;
    size_t bigramHash = 0;

    for (const TString& word : words) {
        const size_t lastUnigramHash = unigramHash;
        const size_t wordHash = word.hash();
        unigramHash = wordHash;
        bigramHash ^= wordHash;
        if (stopHashes.contains(unigramHash) || stopHashes.contains(bigramHash)) {
            return true;
        }
        bigramHash ^= lastUnigramHash;
    }
    return false;
}

TEasyParser — , , , THashSet — std::unordered_set, TString — .

— , : , . , , .

2. Reservoir sampling MapReduce

, - , . , , .

. , — , - - .

, , , , - . , std::shuffle.

, . , . , ; i, 0 i .

. , , K — , . K , , K . std::shuffle : K — , , .

: i- 0 i . , K — , - . reducer' :

void Do(TMRReader* input, TMRWriter* output) override {
    TVector<TNode> sample;

    TMersenne<ui64> mersenne;
    size_t passedItems = 0;

    for (; input->IsValid(); input->Next()) {
        ++passedItems;
        size_t position = mersenne.GenRand64() % passedItems;

        if (position >= ItemsToTake) {
            continue;
        }

        if (sample.size() < ItemsToTake) {
            sample.push_back(input->GetRow());
        } else {
            sample[position] = input->GetRow();
        }
    }

    Shuffle(sample.begin(), sample.end(), mersenne);
    for (const TNode& node : sample) {
        output->Add(node);
    }
}

TMersenne — mersenne twister, , TNode — , MapReduce-.

, .

3. TypeScript

-. — .

url' . , url /action?param=¶m=1;2;3¶m=8, url :

{
    "param" : ["", "1;2;3", "8"]
}

, . , , :

{
    "param" : ["1", "2", "3", "8"]
}

:

export type TParamValue = string | string[];
export type TParams = Record<string, TParamValue>;

export function normalizeParams(params: TParams): TParams {
    const result = {};

    for (const [paramName, paramValue] of Object.entries(params)) {
        //        query-
        if (Array.isArray(paramValue)) {
            result[paramName] = paramValue.reduce((acc, part) => {
                if (part) {
                    acc = acc.concat(part.split(';').filter(Boolean));
                }

                return acc;
            }, []);
        } else if (paramValue) {
            result[paramName] = paramValue.split(';').filter(Boolean);
        }
    }

    return result;
}

. — . — : , , .

4. Python

-; , , , . , . , !

— . — , . , , , , - - .

count = 0
firstPos = -1
clicks = 0

for block in blocks:
    result = bl.GetMainResult()
    if result.IsA('TWebResult'):
        url = result.Url
        pos = result.Pos
        propValue = result.PropValue

        if propValue in interestingValues:
            count += 1

            if firstPos == -1:
                firstPos = pos

            for cl in bl.GetClicks():
                clicks += 1

yield Record(count=count,firstPos=firstPos,clicks=clicks)

set, .

, — , , .

5.

, , , — . , YouTube (, ) .

. , . , .

def foo(nums):
    current = 0
    best = 0
    for n in nums:
        if n > 0:
            current += 1
            best = max(best, current)
        else:
            current = 0
    return best

. . , : . .

def dictFromString(s):
    d = defaultdict(int)
    for c in s:
        d[c] += 1
    return d

def areAnagrams(a, b):
    return dictFromString(a) == dictFromString(b)

. : n. 2n .

def generate(cur, open, closed, n):
    if len(cur) == 2 * n:
        print cur
        return
    if open < n:
        generate(cur + '(', open + 1, closed, n)
    if closed < open:
        generate(cur + ')', open, closed + 1, n)
def parens(n):
    generate('', 0, 0, n)

, , :

• ;
• , ;
• (, );
• ; , .

, , — , machine learning, , , , . , -: , , .

aka nkmakarov, , , !