Unduh Interview_Code - Unduh Kode Sumber Interview

Interview_Code

Kode sumber lainnya

1.0.0

Unduh

Ada total tujuh masalah algoritma klasik di sini (saya memasukkannya ke dalam 7 folder);

Q1 dan Q2 adalah dua topik yang terkait dengan pemrosesan data besar;

Lima topik lainnya adalah:

  1.DBScan clustering algorithm, 
  2.simple dynamic programming, 
  3.classic sorting algorithm, 
  4.full arrangement of strings, 
  5.calculation of tf-idf

Ada tujuh masalah algoritma klasik di sini (saya masing -masing memasukkannya ke dalam 7 folder);

Q1 dan Q2 adalah dua pertanyaan yang terkait dengan pemrosesan data besar;

Lima pertanyaan lainnya adalah:

   1.DBScan聚类算法、
   2.简单的动态规划、
   3.经典的排序算法、
   4.字符串的全排列、
   5.tf-idf的计算

Berikut ini adalah deskripsi dokumen terkait untuk Q1 dan Q2

Berikut ini adalah dokumentasi yang relevan untuk Q1 dan Q2

Daftar isi

1. Deskripsi Pertanyaan.

2. Ide.

3. Lingkungan.

4. Eksekusi kode.

Dalam beberapa hari terakhir, saya telah mewawancarai insinyur algoritma dan menemukan dua pertanyaan tes tertulis yang sangat baik. Berikut adalah ide dan kode yang saya kirimkan. Mereka mungkin bukan solusi terbaik, tetapi mereka juga merupakan hasil dari studi dan pemikiran saya selama dua hari terakhir.

1. Deskripsi Pertanyaan

Pertanyaan 1. Hitung P90

Tabel diketahui mencatat jumlah suka untuk setiap buku harian, dan menggunakan bahasa pemrograman yang Anda kenal untuk menghitung jumlah suka untuk buku harian P90. Definisi P90: Asumsikan p90 = n, maka jumlah suka dalam 90% buku harian kurang dari atau sama dengan n. Catatan: Data asli tidak diurutkan, jumlah buku harian mencapai 1 miliar

Struktur tabel adalah sebagai berikut:

 note_id, like_count
1, 4
2, 6
..., ...

Contoh:

1. Jumlah suka untuk 10 buku harian adalah: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, lalu p90 = 6

2. Jumlah klik untuk 9 buku harian adalah: 1, 2, 2, 3, 3, 4, 5, 5, 6, lalu p90 = 5.5

Pertanyaan 2. Teks terpenting

File yang berisi 10 miliar teks, satu per baris, dan tingkat setiap teks tidak melebihi 1024, dan mungkin ada teks duplikat. Gunakan bahasa pemrograman yang Anda kenal untuk menemukan 10.000 teks terbanyak, kondisinya adalah sebagai berikut:

1. Tidak ada duplikasi antar teks.

2. Jika suatu teks disimpan dalam hasilnya, maka semua teks dengan derajat yang sama dengan teks harus disimpan dalam hasilnya.

2. Ide

Pertanyaan 1. Hitung P90

Deskripsi: Penyortiran Eksternal mengimplementasikan perhitungan nilai p90 dari tabel seperti buku harian

 1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面

Pertanyaan 2. Teks terpenting

Solusi 1

Deskripsi: PANDAS dapat memproses file dengan <= 5tb, dan menggunakan panda secara langsung untuk memproses file super besar

 1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本

Solusi 2

Deskripsi: Peta hash

 1.读取大文件表，生成hash key&value 存入1024个小文件（采用桶排序/计数排序，注意value不是字符串内容而是记录所在大文件中的行数）
    1.1 key为hash值（采用md5<散列化>）
    1.2 value为所在大文件中的行数
2.根据顺序依次从大到小读出topN
3.获取topN在文件中的行数并读取大文件表获取内容
4.循环输出topN
md5码：128位，16个字节