Interview_Code
1.0.0
มีปัญหาอัลกอริทึมคลาสสิกทั้งหมดเจ็ดข้อที่นี่ (ฉันใส่ไว้ใน 7 โฟลเดอร์);
Q1 และ Q2 เป็นสองหัวข้อที่เกี่ยวข้องกับการประมวลผลข้อมูลขนาดใหญ่
อีกห้าหัวข้อคือ:
1.DBScan clustering algorithm,
2.simple dynamic programming,
3.classic sorting algorithm,
4.full arrangement of strings,
5.calculation of tf-idf
มีปัญหาอัลกอริทึมคลาสสิกเจ็ดเรื่องที่นี่ (ฉันใส่ไว้ใน 7 โฟลเดอร์ตามลำดับ);
Q1 และ Q2 เป็นคำถามสองข้อที่เกี่ยวข้องกับการประมวลผลข้อมูลขนาดใหญ่
อีกห้าคำถามคือ:
1.DBScan聚类算法、
2.简单的动态规划、
3.经典的排序算法、
4.字符串的全排列、
5.tf-idf的计算
ต่อไปนี้เป็นคำอธิบายของเอกสารที่เกี่ยวข้องสำหรับ Q1 และ Q2
ต่อไปนี้เป็นเอกสารที่เกี่ยวข้องสำหรับ Q1 และ Q2
1. คำอธิบายคำถาม
2. ความคิด.
3. สภาพแวดล้อม
4. การดำเนินการรหัส
ในช่วงไม่กี่วันที่ผ่านมาฉันได้สัมภาษณ์วิศวกรอัลกอริทึมและพบคำถามทดสอบเป็นลายลักษณ์อักษรสองข้อโดยเฉพาะ นี่คือแนวคิดและรหัสที่ฉันส่ง พวกเขาอาจไม่ใช่ทางออกที่ดีที่สุด แต่พวกเขาก็เป็นผลมาจากการศึกษาของฉันและคิดในช่วงสองวันที่ผ่านมา
ตารางเป็นที่รู้จักกันในการบันทึกจำนวนไลค์สำหรับแต่ละไดอารี่และใช้ภาษาการเขียนโปรแกรมที่คุณคุ้นเคยในการคำนวณจำนวนไลค์สำหรับไดอารี่ P90 คำจำกัดความของ p90: สมมติว่า p90 = n จากนั้นจำนวนไลค์ใน 90% ของไดอารี่น้อยกว่าหรือเท่ากับ n หมายเหตุ: ข้อมูลต้นฉบับไม่ได้ถูกเรียงลำดับจำนวนไดอารี่ถึง 1 พันล้าน
โครงสร้างตารางมีดังนี้:
note_id, like_count
1, 4
2, 6
..., ...
ตัวอย่าง:
1. จำนวนไลค์สำหรับ 10 ไดอารี่คือ: 1, 2, 2, 3, 3, 4, 5, 5, 6, 50, จากนั้น P90 = 6
2. จำนวนคลิกสำหรับ 9 ไดอารี่คือ: 1, 2, 2, 3, 3, 4, 5, 5, 6, จากนั้น P90 = 5.5
ไฟล์ที่มี 10 พันล้านข้อความหนึ่งต่อบรรทัดและระดับของแต่ละข้อความไม่เกิน 1024 และอาจมีข้อความซ้ำ ใช้ภาษาการเขียนโปรแกรมที่คุณคุ้นเคยกับการค้นหาข้อความมากที่สุด 10,000 เงื่อนไขมีดังนี้:
1. ไม่มีการทำซ้ำระหว่างข้อความ
2. หากข้อความถูกเก็บไว้ในผลลัพธ์ดังนั้นข้อความทั้งหมดที่มีระดับเดียวกับข้อความควรเก็บไว้ในผลลัพธ์
คำอธิบาย: การเรียงลำดับภายนอกใช้การคำนวณค่า p90 ของไดอารี่เช่นตาราง
1.读取大文件表，维护一个数据总量nTotal
2.分为n个小文件（第一次内部排序<采用优化后的快排>；注意：内存量 大于等于 小文件的数据量大小）
3.采用外部排序排序每个小文件
4.合并所有小文件并输出到一个新的文件（依次读取每个文件从第一行到末尾，比较获取极（大/小）值，存入新文件）
5.最终获得一个排序好的大文件
6.通过排序后的大文件获取p90的位置 通过文件指针偏移读取具体的p90数据
注：小文件倒序排列，点击数多的排在前面
คำอธิบาย: แพนด้าสามารถประมวลผลไฟล์ด้วย <= 5tb และใช้แพนด้าโดยตรงเพื่อประมวลผลไฟล์ขนาดใหญ่สุด ๆ
1.读入文件为DataFrame：reader
2.去重
3.新增文本长度列和索引列
4.按文本长度列分组（1024个分组）并返回每个分组的元素个数，产生新的DataFrame：group
5.通过group表返回top_n文本的最小长度
6.在reader大表中按条件查找行，产生DataFrame:result
7.通过result表返回符合条件的top_n文本
คำอธิบาย: แผนที่แฮช
1.读取大文件表，生成hash key&value 存入1024个小文件（采用桶排序/计数排序，注意value不是字符串内容而是记录所在大文件中的行数）
1.1 key为hash值（采用md5<散列化>）
1.2 value为所在大文件中的行数
2.根据顺序依次从大到小读出topN
3.获取topN在文件中的行数并读取大文件表获取内容
4.循环输出topN
md5码：128位，16个字节
Python3.6
pip install tqdm
pip install pandas
ฟังก์ชั่นรายการ: Q1/get_p90.py ดำเนินการ:
cd Q1
python get_p90.py
ฟังก์ชั่นรายการ: Q2/get_top_1w_pandas.py ดำเนินการ:
cd Q2
python get_top_1w_pandas.py
ฟังก์ชั่นรายการ: Q2/get_top_1w_hash.py ดำเนินการ:
cd Q2
python get_top_1w_hash.py
