Đề test thuật toán (any language)

nguyenhuuca · January 2, 2019, 4:58am

Hi mình có nhận được đề test này từ 1 người bạn, cũng gần 2 năm rồi. ở level SE/SA. chắc giờ công ty cũng đổi đề rồi nên đưa lên cho anh em rèn luyện và tham khảo(hình như vị trí này lúc đó rank lương từ 3-7k thì phải ở VN nha, giờ chắc giảm rồi :v).
Ah mình chưa giải được nha.

hungaya · January 2, 2019, 4:33am

Sao em thấy task 1 nó gần giống như mấy query trong Hadoop MapReduce nhỉ.

nguyenhuuca · January 2, 2019, 4:58am

Cái này ko rõ, có thể e đang nói đến Hbase đúng ko :D. Hbase nó hỗ trợ query trên csv file trong HSFS

hungaya · January 2, 2019, 5:03am

HBase khác a, Hadoop và HBase đều dựa trên HDFS cả. HBase dựa theo BigTable, nên nó phù hợp realtime read/write. Hadoop thì hiện thực MapReduce.

Còn Hadoop thì chỉ thiên về read, mà lại là batch processing (không realtime). Em thấy task 1 giống như tác vụ bên Hadoop vậy. Nhưng em không có viết code trực tiếp trên MapReduce đâu, viết SQL trên Hive cho khoẻ. Hive nó tối ưu cho mình hết rồi.

noname00 · January 2, 2019, 5:04am

Task 1 chỉ là với mỗi số điện thoại thì in ra ngày activate đầu tiên thôi ạ?

nguyenhuuca · January 2, 2019, 8:22am

ngày gần nhất chứ

noname00 · January 2, 2019, 9:33am

Thế cái số đuôi 001 tại sao không tính ngày 1/12 vậy ạ?

noz1995 · January 2, 2019, 9:40am

Không phải là ngày active cuối cùng mà là ngày active đầu tiên của chuỗi ngày liên tiếp active cuối cùng. Số 001 có 2 chuỗi ngày là từ 01-01 đến 05-01 và 06-01 đến “nay”

nguyenhuuca · January 2, 2019, 10:00am

Tại vì nó liên tiếp đó em, nhin vào 1 số điện thoại người ta muốn biết ngày active gần nhất, vì có 2 dạng là trả trước và trả sau, nên nếu đổi loại thì ngày active vẫn lấy cái trước đó.
tháng 6-9 : trả trước
tháng 9->12: trả sau
tháng 12 đến giờ trả trước
vậy tháng active gần nhất là tháng 6

noname00 · January 2, 2019, 10:03am

Em hiểu rồi ạ.

Cơ mà 1 số điện thoại cứ đổi chủ là đổi loại ạ?

nguyenhuuca · January 2, 2019, 10:06am

Không do người dùng tự đổi thôi, vi dụ A dùng số đó 1 thời gian sau đó không dùng nữa. thì người sau đăng ký dùng số đó muốn dùng trả trước trả sau thì điều ok mà. đề nó ví dụ thôi :D.

noname00 · January 2, 2019, 10:07am

À, vậy mà em cứ tưởng trả trước/sau ảnh hưởng đến bài

Rok_Hoang · January 3, 2019, 7:14am

Mình nghĩ task 1 chỉ cần sort giảm dần số phone và activation date các, sau đó lấy từng group phone duyệt để tìm ngày activate thôi

noname00 · January 3, 2019, 7:51am

Task 1:

Viết mã giả lâu quá, thôi thì code luôn.

Python:

import sys
import datetime

INF = 10**9


def is_longer_a_month(date1, date2):
	# date format is YYYY-MM-DD
	datetime1 = datetime.date(date1[0], date1[1], date1[2])
	datetime2 = datetime.date(date2[0], date2[1], date2[2])
	return (datetime2 - datetime1 >= datetime.timedelta(days=30))


with sys.stdin as fi, sys.stdout as fo:
	record = [line.strip() for line in fi.readlines()] # bỏ \n ở cuối xâu

	# chuyển data trong record về dạng tuple
	# (số_điện_thoại, activation_year, activation_month, activation_day, deactivation_year, deactivation_month, deactivation_day)
	for i in range(len(record)):
		data = record[i].split(',')
		new_tuple = [data[0]] + list(map(int, data[1].split('-')))
		if data[2] == '':
			new_tuple.extend([INF, INF, INF])
		else:
			new_tuple.extend(list(map(int, data[2].split('-'))))

		record[i] = tuple(new_tuple)
	
	record.sort()  # chỉ cần sort lại đơn giản

	last_deactivation_date = (1, 1, 0)
	list_last_activation_date = []

	for line in record:
		if len(list_last_activation_date) > 0 and line[0] == list_last_activation_date[-1][0]:
			# nếu số điện thoại này đã nằm trong list,
			# tức là đã có 1 thông tin về 1 ngày activation nào đó
			if is_longer_a_month(last_deactivation_date, (line[1], line[2], line[3])):
				# nếu đã ngày ngừng sử dụng trước cách ngày activation này hơn 1 tháng,
				# tức là số đã được chuyển cho người khác
				list_last_activation_date[-1][1] = (line[1], line[2], line[3])
			# nếu không thì không làm gì tiếp cả, số vẫn chưa bị tái sử dụng
		else: # nếu số này chưa xuất hiện
			list_last_activation_date.append([line[0], (line[1], line[2], line[3])])
		
		last_deactivation_date = (line[4], line[5], line[6])

	for u in list_last_activation_date:
		print("{0},{1:0>4}-{2:0>2}-{3:0>2}".format(u[0], u[1][0], u[1][1], u[1][2]))

Độ phức tạp thời gian: O(L + n log n + n) = O(L + n log n) (L là tổng độ dài các xâu ban đầu)
Độ phức tạp không gian: O(n)

VuVanChung · January 3, 2019, 8:07am

Theo mình hiểu thì nó khác với những gì bạn viết quá.
Hbase là một dạng cơ sở dữ liệu, nó giúp việc đọc ghi nhanh hơn hadoop do cách tổ chức dữ liệu có sắp xếp trước khi đưa xuống HDFS, còn Hadoop nó đẩy thẳng xuống luôn nên lúc đọc phải đọc tuần tự. Còn mapreduce là tên một phương pháp xử lý dữ liệu, không phải chỉ cho đọc ghi mà còn tính toán các thứ nữa. Đây là về phần xử lý dữ liệu phân tán chứ không còn lưu trữ phân tán nữa. Hive thì nó là like SQL nên cú pháp giống SQL rôi! :))

quancntt · January 3, 2019, 8:46am

Anh có resource file CSV ko ạ, cho e để e chạy test thử với dc ko, hihi

hungaya · January 3, 2019, 11:43am

Mình và bạn nói giống nhau mà

Nếu như chỉ tìm hiểu Hadoop không thì phần của bạn đúng. Giống cách diễn giải khi bạn nào làm bên Big Data vậy.

Tuy nhiên, phần này thuộc phần hiện thực cơ sở dữ liệu, DBMS implementation, thuộc database. Database ngoài phần RDBMS còn nhiều phần khác nữa mà ít khi giới thiệu, trong đó có hiện thực RDBMS từ File System. Phần mình nói là theo góc nhìn DBA.

Thay vì giấu hết tất cả kĩ thuật để implement như các RDBMS hay làm, thì Hadoop nó phô trương mấy kĩ thuật đó hết luôn. Điểm lợi là DBA có thể can thiệp sâu vào hệ thống, điểm nhược là nếu data có thể lưu dưới dạng relation thì nó tốn quá nhiều bước dư thừa. Vì vậy ai không học hết database (chỉ dừng lại cách sử dụng RDBMS) lại tưởng là cái mới.

Ps: xin lỗi anh huuca vì offtopic

VuVanChung · January 3, 2019, 12:59pm

Ra vậy đấy, hehe! Có vẻ bạn làm chuyên bên mảng DB này nhỉ? Mình mới làm Big Data được 4 tháng nên biết vậy