# Solution for BE-Group Data Science Test

## Problem 1
Đối với bài toán này thì bản thân em có 3 điều muốn nói sau khi đọc kỹ đề bài:

* Bài toán không có giới hạn các thuộc tính của một **User** (người dùng) hay một **Item** (tạm gọi là sản phẩm). Vậy thì những em xin phép có một số giả sử về những thuộc tính tồn tại đối với một **User** hay một **Item**
* Em sẽ đặt lại tên biến như sau: $R$ là tập hợp các **giao dịch**, một **giao dịch** $r_{i} = (x_i, y_i, t_i)$ với $x_i \in \mathbb{Z}^+$ ám chỉ **User** $u_{x_{i}}$, $y_i \in \mathbb{Z}^+$ ám chỉ **Item** $n_{y_{i}}$

### Với tình huống đầu tiên **[S01]**:

* Ở đây đề bài chưa nói rõ là chúng ta sẽ phải gợi ý cho khách hàng nào. Nên em sẽ giả sử chúng ta cần gợi ý cho khách hàng $u_{x_{1}}$ với tập các giao dịch của khách hàng này là ${G} \subset {R}$. Đồng thời đề bài cũng không đề cập tới việc chúng ta **chỉ sử dụng** thông tin về tập $G$ thôi hay không nên em sẽ giả sử là chỉ sử dụng thông tin từ tập $R$

#### Trường hợp chỉ sử dụng thông tin từ tập $R$

Những thuộc tính quan trọng của một sản phẩm sẽ được cân nhắc trong tình huống này:
* Tên của sản phẩm $\rightarrow$ rất phù hợp cho việc so sánh giữa thứ người dùng tìm bằng **Search bar** và tên sản phẩm
* Đối tượng khách hàng của sản phẩm (Trẻ em, học sinh, sinh viên, người đi làm, người lớn tuổi,...)
* Loại sản phẩm (đồ công nghệ, đồ gia dụng, đồ nấu ăn, dụng cụ học tập,...)
* Hãng sản xuất (Apple, Samsung, BKAV,...)
* Nơi sản xuất, cung cấp $\rightarrow$ có những mặt hàng rất ít được chọn đó là những sản phẩm công nghệ đến từ một quốc gia nào đó (em lấy ví dụ là Trung Quốc). Hoặc nơi bán cũng là một trong những điều mà khách hàng quan tâm khi mua một sản phẩm nào đó.
* **Giá thành của sản phẩm**
* Khối lượng sản phẩm bán ra trong quãng thời gian nào đó trước $t$
* Em tạm gọi một sản phẩm có một thuộc tính gọi là "Return duration" và "Return rate"
* Với **Return duration** chúng ta có thể sẽ quan tâm đến khả năng mua lại mặt hàng đó (hoặc những mặt hàng cùng loại) của một khách hàng sau khoảng thời gian là bao lâu. Thuộc tính này có thể được tìm hiểu dựa trên tập $G$, nhưng đúng hơn nó vẫn sẽ khó ở việc biết được hai mặt hàng có mục đích sử dụng giống nhau hay không. Ví dụ một bịch đồ ăn cho cá sẽ được khách hàng $x_1$ sử dụng trong thời gian 2 tháng (vì nhà ít cá) nhưng khách $x_2$ lại sử dụng chỉ trong 1 tháng (nhà nhiều cá gấp đôi $x_1$), từ đó chúng ta có thể biết được có nên gợi ý cho $x_1$ đồ ăn cho cá vào khoảng thời gian $t$ nào đó hay không.
* Với **Return rate**, nghe nó hơi mang khuynh hướng kinh tế nhưng mà một mặt hàng thì nên có chỉ số này. Chỉ số này thể hiện việc quay lại và mua sản phẩm như vậy, nếu một sản phẩm có chỉ số quay lại mua cao thì nên gợi ý, vì có khả năng cao nó sẽ được mua tiếp (tất nhiên là nên gợi ý tầm khoảng thời gian sau cái **Return duration** em nói ở trên)
* Các thẻ (tags) của sản phẩm $\rightarrow$ Đây là một trong những tính năng quan trọng, có thể tóm tắt được rất nhiều thông tin của một sản phẩm nếu sản phẩm này được đính thẻ một cách có tâm. Nhưng hầu hết khi bán hàng online thì các tiểu thương sẽ có 2 trường hợp:
* Không quan tâm đến việc đỉnh thẻ lên sản phẩm
* Đính thẻ tràn lan và không chính xác thông tin của sản phẩm $\rightarrow$ Dữ liệu hoặc bị thiếu rất nhiều hoặc có thể bị nhiễu rất cao $\rightarrow$ dẫn đến đây chỉ là một trong những tính năng phụ để xem xét tới.

Những thuộc tính quan trọng của một người dùng sẽ được cân nhắc trong tình huống này:
* Độ tuổi
* Nghề nghiệp
* Giới tính
* Những thông tin về giỏ hàng của khách hàng
* Điều này nên có vì những thứ bỏ trong giỏ thì sẽ có khả năng là do chưa có dịp mua (đang chờ sale, chờ lương, chờ xin tiền bố mẹ,...) hoặc đang cân nhắc giữa các sản phẩm khác nhau, nên chúng ta có thể dựa trên thuộc tính của những thứ nằm trong giỏ hàng của khách để gợi ý.
* Danh sách yêu thích của khách hàng
* Những gian hàng mà khách hàng theo dõi
* (Những) Địa chỉ của khách hàng

### Với tình huống tiếp theo **[S02]**:

Với tình huống này thì hầu hết chúng ta sẽ gặp khi một **User** lần đầu tiên sử dụng nền tảng thương mại điện tử, hoặc những **User** chưa đăng nhập vào nền tảng.
Em sẽ tiếp cận bài toán và gợi ý dựa trên chiến thuật là gợi ý không cá nhân hóa (non-personalized recommendation) ví dụ một số chiến thuật có thể kể đến như:
* Gợi ý sản phẩm bán chạy nhất
* Gợi ý sản phẩm đang được khuyến mãi / sắp được khuyến mãi
* Gợi ý sản phẩm mới nhất
* Gợi ý sản phẩm bán chậm nhất

Tất nhiên, những sản phẩm này sẽ liên quan đến **action** của khách hàng trên nền tảng thương mại điện tử của chúng ta.

Những thuộc tính của sản phẩm mà em mong muốn có được khi giải quyết bài toán này vẫn dựa trên **[S01]**

* Miêu tả ngắn về sản phẩm của người bán
* Tên của sản phẩm $\rightarrow$ rất phù hợp cho việc so sánh giữa thứ người dùng tìm bằng **Search bar** và tên sản phẩm
* Loại sản phẩm (đồ công nghệ, đồ gia dụng, đồ nấu ăn, dụng cụ học tập,...)
* Hãng sản xuất (Apple, Samsung, BKAV,...)
* Nơi sản xuất, cung cấp
* Khối lượng sản phẩm bán ra trong quãng thời gian nào đó trước $t$
* Tần suất mua bán sản phẩm

## Problem 2
### Sub-problem A
Khác biệt cơ bản giữa trung bình (mean) và trung vị (median) là:
* Trung bình **(mean)** là giá trị trung bình (**average**) của cả tập dữ liệu đã cho
* Trung vị **(median)** là giá trị nằm giữa của tập dữ liệu đã cho khi sắp xếp dữ liệu tăng dần (hoặc giảm dần) theo một độ đo nào đó nhất định.

Với câu hỏi rằng liệu giá nhà ở **Quận 4** sẽ có Trung bình hay Trung vị lớn hơn thì em có những nhận xét sau:

* Quận 4 nếu so với Thành phố Hồ Chí Minh thì được tính là một vùng tiếp giáp với trung tâm thành phố, được bao quanh bởi các nhánh sông, diện tích thuộc dạng nhỏ và chưa được đầu tư quá nhiều về mặt kinh tế cũng như điều kiện sinh hoạt như các quận cận trung tâm khác như Tân Bình, Tân Phú, Quận 10, Quận 11,...
* Quận 4 có 4 tuyến đường chính nhưng chỉ 3 tuyến đường chính là giáp sông, đó là nơi tập trung những tòa chung cư mới và có tầm nhìn sông nên giá sẽ hơi cao hơn một tí, bên cạnh đó Quận 4 gồm những chung cư khá là già cỗi và nhiều những ngôi nhà, khu nhà cho thuê.
* Dân cư Quận 4 trước năm 2020 chủ yếu là dân lao động từ các tỉnh thành lân cận, sinh viên học sinh các trường đại học / cao đẳng / trung cấp ở khu vực Quận 5, Quận 3, Quận 1, Quận 10 và đôi khi là khu vực Quận 7 $\rightarrow$ dẫn đến việc là với tệp khách hàng có xu hướng không thể chi quá nhiều vào việc nhà đất, giá thuê nhà (và cả giá căn hộ) ở đây có xu hướng thấp (vì không có người đến mua, mà đến thuê để ở là nhiều).
* Tuy nhiên ở Quận 4 có một khu mà tất cả mọi người đều biết, đó là đường Khánh Hội, cung đường này cắt ngang Quận 4, có thể coi Khánh Hội như là trung tâm của quận này, giá nhà đất ở đây sẽ khá cao, sẽ vượt mặt bằng chung khá là lớn.
* Tuy Quận 4 là nơi có mặt bằng sống thấp nhưng nhờ vậy, một số tệp khách hàng là những người giàu có sẽ chọn Quận này để sinh sống vì nhìn chung ở đây không có quá ồn ào và náo nhiệt, thích hợp cho những biệt thự sang ơi là sang vì giá đất nó rẻ quá.

Kết luận của em là cái phân phối nhà ở quận 4 nó sẽ có dạng lệch mạnh về bên trái so với phân phối chuẩn, một ví dụ dễ hiểu
$[0.8,0.9,0.97,0.98,1,1,1.1,1.25,1.25,1.34,1.52,1.75,1.78,1.9,1.92,10.3,10.4,10.5,50.1]$

Thì theo tập em đề ra ở trên và những ý mà em đã ghi chú, cá nhân em cho rằng giá nhà ở **Quận 4** sẽ có Trung bình lớn hơn trung vị

### Sub-problem B

Khi đọc đề em có những nhận xét sau:

* Bài toán không giới hạn số dòng trong tập dữ liệu, em tạm gọi số dòng sẽ là $N$ và vì $N$ không thể dùng thuật toán sắp xếp được thì em sẽ giả sử $N \sim 10^{12}$
* Em giả sử những tất cả thông số nhiệt độ của em đã có sẵn trong một danh sách liên kết đơn $A$ nào đó.
* Đề bài không cho em biết là nhiệt độ sẽ giới hạn ở bao nhiêu chữ số thập phân nên em sẽ giả sử một nhiệt độ có tối đa $4$ chữ số thập phân.

Cách tiếp cận bài toán của em là dùng phương pháp đánh tần số, em hay tự gọi nó là *frequencing*. Cách này như sau

Em sẽ có một mảng `freq`, gồm $2*10^{7} + 1$ phần tử, phần tử thứ $x$ là `freq[x]` sẽ là số lần xuất hiện của mức nhiệt độ $\frac{x}{10^{4}} - 1000$ (do có 4 chữ số thập phân).

Ví dụ: `freq[3000000]` sẽ là số lần xuất hiện của nhiệt độ `300 - 1000 = -700` độ.

Em sẽ duyệt mảng $A$, và đếm số lần xuất hiện của từng phần tử trong $A$, sau khi thực hiện xong việc này, em sẽ duyệt mảng `freq` để biết `median` của dữ liệu nằm ở đâu bằng cách sẽ cộng dồn số phần tử tới khi nào mà con số này vượt quá hoặc bằng $N/2$.

Em ví dụ em có dữ liệu $A =[3,2,1,1,1,2,4,2,4,2,1,3,3,2,3,1,2,3,3,1,2,2,3,1]$

thì $N$ và `freq` của em lúc này lần lượt sẽ là $24$ và $[7,8,7,2]$

Vậy em thấy rằng $7 + 8 = 15 > 12$, nên trung vị của em sẽ là $2$

Mã giả

Input:
A: List[float]
Freq: List[int]
N: int

for i in A:
    Freq[i] += 1

count = 0
ind = 0
for i in range(len(Freq)):
    count += Freq[i]
    if count >= N / 2:
        ind = i
        break
return ind
    

Với bài toán này em thấy rằng em thật may mắn khi được cho cái range của cái nhiệt độ, nhưng em cũng thử suy nghĩ đến trường hợp nếu bài toán không cho cái range đó thì mình sẽ làm như nào. Em cũng thử propose một cách làm khác trong trường hợp mọi thông tin đều thiếu.

Với bài toán như vậy thì em nhận thấy rằng nhiệt độ (hoặc một đại lượng nào đó) không có quá nhiều khả năng thay đổi lớn trong một khoảng thời gian. Nên em sẽ giả sử luôn là cái đại lượng này nó không thay đổi trong vòng $1$ phút, vậy với từng phút em sẽ lấy một giá trị bất kỳ được log ra trong vòng $1$ phút đó, vậy thì một ngày em sẽ có là $14400$ giá trị nhiệt độ, và em có thể lấy được trung vị của tập này bằng việc sắp xếp thông thường và in giá trị ở giữa.

## Problem 3

Bài toán này thật ra khi em đọc đề thì hiểu, nhưng có quá nhiều trường hợp mà bài toán này dẫn đến:

* Liệu rằng `frequency` ở đây được tính như thế nào? Bài toán có nói là *frequency of time* nhưng *time* này là gì? Là trong vòng 24 giờ một ngày hay là tổng *time* mà người dùng sử dụng tất cả các app.
* Nói đơn giản là ví dụ người $A$ sử dụng app $B$ trong 3 giờ và app $C$ trong 7 giờ vậy thì `frequency` của app $B$ là $30\%$ hay sẽ là $12.5\%$
* Điều này sẽ dẫn đến độ phức tạp của thuật toán
* Yêu cầu của `output` cũng sẽ ảnh hưởng đến thuật, nhưng theo em hiểu nó sẽ là trường hợp chỉ đơn thuần là làm gọn cái `dataframe` lại, để cô đọng thông tin hơn mà thôi.
* Liệu rằng ở một hàng nào đó cặp (user, app) có xuất hiện lại không, hay cặp này cũng là giá trị unique trên cả bảng.

Với bài toán này các bước làm của em sẽ là:
* Tìm danh sách các ứng dụng
* Tìm danh sách khách hàng
* Với mỗi khách hàng thì cho anh ấy một `dictionary` có sẵn $n$ khóa (key) trước, mỗi key $i$ $(i \leq n)$ này có giá trị là mã của app thứ $i$ sẽ tham chiếu đến một số thực được khởi tạo là $0$
* Sau đó em sẽ duyệt cả `df01` để cộng dồn `frequency` (nếu cặp (user, app) có khả năng xuất hiện nhiều lần)

Bài toán này cũng hỏi cả hai Scenario là **[S01]**, **[S02]**

Nhưng em không thực sự hiểu rõ mục đích của việc $n < 1000$ và $n > 10000$, theo em nghĩ thì dù trường hợp $n$ nào đi nữa, để có thể ra được `df02` một cách chuẩn xác thì chúng ta chỉ có thể duyệt hết tất cả các observations trong `df01`, nên em chưa thể nghĩ ra với trường hợp **[S02]**

Vậy ở bài này em nghĩ em sẽ trả lời là ở cả hai trường hợp em đều sẽ làm như trên

## Problem 4

Bài toán được đính kèm trong file `ipynb` kèm theo