今天我有一個非常有趣的面試問題。我有一個芯片芯片（比如說黃色）和一系列的芯片提供給兩個芯片（一個黃色 - >一個綠色，一個藍色）。爲了達到結果集，我必須做的最少交易次數是多少。獲取節點子集的路徑
所以我們可以說，我開始用一種顏色A，我需要得到的顏色D, E, F, G，
A
A -> B, C
B -> D, E
C -> F, G
我可以交易A到B，C和貿易這兩個得到d，E，F ，G.
我需要什麼算法來解決這個問題？從結果集中反向工作是一些東西，但交易可以循環（一個A芯片用於兩個A芯片）是非常棘手的。這看起來像一個圖形問題。 MST看起來很相似，但它是無向的，在我的情況下，我可以重複交易（非獨特的路徑）。
簡單的邏輯就足夠了，不需要程序/算法。
由於每個行業的變化，你有相同的量（這是一個）的芯片數量，你可以劃分在一組，並在組大小的變化設定的目標之間的芯片的區別：
chipsIn = 1
chipsOut = 2
changePerTrade = chipsOut - chipsIn
numTrades = (goalSet.size - startSet.size)/changePerTrade
幾個注意事項：
需要注意的是這隻能是因爲限制的，所有的行業都有相同的輸入和輸出尺寸，並假定每一個芯片必須朝着目標集數下工作（例如如果你試圖獲得AB，那麼擁有ABC是失敗的）。
這隻會告訴你最少的交易次數（這也只是交易的最大次數），而不是是否有可能實現目標集。
這僅僅是一個樹的搜索，在樹中探索時在樹中生成節點。你的樹看起來是這樣的（你的例子）：
A
|
B,C
/ \
D,E,C B,F,G
| |
D,E,F,G D,E,F,G
其中芯片的樹繼續，每一個節點是一組（或列表中，如果允許重複）。一些想法可以幫助解釋樹的概念：
goalSet.size級別。您從節點A開始，循環遍歷所有芯片，並一次執行一次可能的交易，每次執行一個更深的交易。
Here是一篇維基百科文章，解釋如何做樹遍歷，您可以在探索它們時調整它以創建節點。深度優先搜索將是最簡單的，因爲您一次只需跟蹤一個節點，但廣度優先搜索可能會更快，但更多的實施困難。