面試問題的最佳解決方案

Question

最近在面試中，我遇到了以下問題。

說我有如下表

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
a     |   15.00   | 1 
b     |   30.00   | 1 
c     |   20.00   | 1 
d     |   25.00   | 1 

其中WIDGET_NAME是持有小部件的名稱，widget_costs是一個小部件的價格，在股票的1

恆定現在對於我的商業保險我有一定的免賠額。我期待找到一個sql語句，它會告訴我每個小部件，並且它的價格超過了抵扣額。所以，如果我的dedudctible爲$ 50.00以上將只返回

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
a     |   15.00   | 1 
d     |   25.00   | 1 

由於部件B和C，其中用於滿足抵扣

我能得到最接近的是以下

SELECT 
    * 
FROM (
    SELECT 
      widget_name, 
      widget_price 
    FROM interview.tbl_widgets 
    minus 
    SELECT widget_name,widget_price 
    FROM (
      SELECT 
       widget_name, 
       widget_price, 
       50 - sum(widget_price) over (ORDER BY widget_price ROWS between unbounded preceding and current row) as running_total 
      FROM interview.tbl_widgets 
    ) 
    where running_total >= 0 
) 
; 

其中給出me

widget_Name  |  widget_Costs  | In_Stock 
--------------------------------------------------------- 
c     |   20.00   | 1 
d     |   25.00   | 1 

因爲它使用a和b來滿足大部分的deductibl Ë

我希望有人也許能夠告訴我正確的答案

編輯：我理解的面試問題要問這個。給定一個小部件和它們的價格表，並給予一美元的金額，減去儘可能多的小部件，你可以達到美元數額並返回這些小部件和它們的價格仍然

Answer 1

這看起來像一個Bin Packing problem這些都是真的很難解決特別是與SQL。

如果你在SO上搜索Bin Packing + SQL，你會發現how to find Sum(field) in condition ie 「select * from table where sum(field) < 150」除了你想添加一個NOT IN，它基本上是一樣的問題。

我無法得到通過brianegge接受的答案工作，但他一般寫的很有意思

你 形容這將關係最密切想要 用戶的選擇..the問題合適 成一個給定的大小，是一個bin包裝 的問題。這是一個NP-Hard問題， ，並且使用ANSI SQL 將不容易解決。然而，上述似乎 返回正確的結果，但實際上 它只是從最小的 項目開始，並繼續添加項目，直到 bin已滿。

一般而言，更有效的箱包裝 算法將從 最大項開始，並繼續添加小號適合的 。這 算法會選擇用戶5和4

所以用這個建議你可以寫一個遊標循環在桌子上做只是這一點（它只是不會是美麗的）。

Aaron Alton給出了series of articles的一個很好的鏈接，它嘗試用sql解決Bin包裝問題，但基本上可以得出結論，最好使用遊標來完成它。

Answer 2

我會提出一個答案，只是情況下，它更容易比它看起來，但如果這個想法是剛剛返回的成本比可抵扣任何更多的部件，那麼你會做這樣的事情：

Select 
    Widget_Name, Widget_Cost, In_Stock 
From 
    Widgets 
Where 
    Widget_Cost > 50 -- SubSelect for variable deductibles? 

爲了您的樣本數據我查詢不返回行。

Answer 3

我相信我理解你的問題，但我不是100％。以下是我假設你的意思：

你的免賠額是50美元。爲了達到免賠額，你有兩個「使用」項目。 （這是否總是兩個？它有多高？可以只有一個？如果它們總共不到50美元，則會有很多缺失信息）。然後您要返回不是用於抵扣的小部件。我有以下幾點。

CREATE TABLE #test 
(
    widget_name char(1), 
    widget_cost money 
    ) 

INSERT INTO #test (widget_name, widget_cost) 
SELECT 'a', 15.00 UNION ALL 
SELECT 'b', 30.00 UNION ALL 
SELECT 'c', 20.00 UNION ALL 
SELECT 'd', 25.00 


SELECT * FROM #test t1 
WHERE t1.widget_name NOT IN (
SELECT t1.widget_name FROM #test t1 
CROSS JOIN #test t2 
WHERE t1.widget_cost + t2.widget_cost = 50 AND t1.widget_name != t2.widget_name) 

它返回

widget_name widget_cost 
----------- --------------------- 
a   15.00 
d   25.00