數據結構設計：網上書店

Question

我越過了我的採訪這個問題，我想這是測試數據結構和算法：

「請設計一個網上書店，那裏有3個功能：

1. 買了一本書

2. 獲得上出售（如第三最暢銷的書）的排名

3. 獲得頂級暢銷書

例如：

如果我買了一個名爲 「介紹到Python」 的書。

函數＃1將更新本書的內部數據結構（將由您設計）（更新：售出的）。然後，如果調用func＃2，我將獲得「該書是第五大暢銷書」（通過傳遞任何書名），如果我打電話給func＃3，我將獲得「最暢銷的3本書：book1-name ，book2-name，book3-name「。

我認爲這個問題的關鍵是什麼數據結構來存儲書籍（本書的名稱，本書出售的）。這樣我們可以快速更新＃銷售，獲得排名並獲得暢銷書。

目標是這樣做的數據結構很快。 希望我明確。 謝謝！

Answer 1

一個order statistic tree可能適合在這裏，與map:string->node的組合。

訂單統計樹是一個常規二叉搜索樹，它還保存每個子樹根中的節點數。這樣可以很容易找到第k個元素（對數時間），也可以獲得任意節點在對數時間的排名。

樹會按照每本書出售的書籍數量排序，並且您的地圖會將每本書鏈接到樹中的節點。

這使得O（LOGN）爲「買了一本書」和「得到上銷售排名」，此外，發現前k元素O(k+logn)

Answer 2

你應該問更多的問題。 獲取更多規格。

用極簡主義和簡單的方法。

• 沒有數據庫開頭。無需連接。
• 極品書籍...創建一個書類。
• 這本書有什麼重要之處？名稱，銷售和當前可用。
• 吸氣/安裝人員（保持簡單）。
• 需要書店...創建一個書店類。
• 什麼樣的結構可以給我一個等級和書？鑰匙，價值響鐘？ HashMap（key = rank，value = Book Object）。
• 添加您的功能。
• Shenanigans。編碼時間！
• 出售（書本）方法：從您的特定書籍管理遞增/遞減。
• getRankOnBook（Book book）method：從hashMap中獲取並返回鍵/等級。
• getTopBestSeller（）方法：檢索並返回列表。

添加東西

• 數據庫和連接
• 線程安全的（可能併發性問題提供/賣出）
• 性能問題（頂級書籍批處理作業）
• 對象面向原理：使你的代碼更加抽象（單一責任原則和依賴倒置原則）
• Bla bla bla。