[Powered by Google Translate] [講座：技術訪談] [肯尼於哈佛大學] 這是CS50。[CS50.TV] 大家好，我是肯尼。我目前正在一個初中學習計算機科學。 我是一個CS TF前，我希望我有這個當我是低年級， 這就是為什麼我給本次研討會。 所以，我希望你喜歡它。 本次研討會是技術面試， 和我所有的資源，可以發現在這個環節， 此鏈接在這裡，一對夫婦的資源。 所以，我提出的問題清單，實際上，不少問題。 另外，一般的資源頁面，在這裡我們可以找到提示 如何準備接受記者採訪時， 提示在實際的採訪中你應該做的， 以及如何處理問題和資源，以備將來參考。 這一切都在網上。 而就在前言本次研討會，免責聲明， 這樣不應該 - 你的面試準備 不應該被限制到該列表。 這只是意味著是一個指南， 你一定要我說的一切與一粒鹽， 而且還用我來幫助你在你的面試準備的一切。 

我要加速通過下面的幾張幻燈片 因此，我們可以得到的實際案例研究。 結構的軟件工程現在的位置接受記者採訪時， 它通常是30到45分鐘， 多輪，根據公司。 你經常會在白板上進行編碼。 因此，這樣的白板，但往往在一個較小的規模。 如果你有一個接受電話採訪時，你可能會被使用 collabedit或一個谷歌文檔，這樣他們就可以看到你住的編碼 當你通過電話採訪。 接受記者採訪時本身通常是2個或3個問題 測試您的計算機科學知識。 它幾乎肯定會涉及編碼。 的問題的類型，你會看到通常是數據結構和算法。 而在做這些各種各樣的問題， ，他們會問你喜歡什麼，是時間和空間複雜度，大O？ 通常情況下，他們也要求更高層次的問題， 這樣，設計系統時， 你怎麼會躺在你的代碼嗎？ 什麼樣的接口，哪個班的，你有什麼模塊在您的系統， 怎麼互動起來呢？ 因此，數據結構和算法，以及設計系統。 

一些通用的技巧之前，我們深入到我們的案例研究。 我認為最重要的規則總是在想大聲。 採訪應該是你的機會來炫耀你的思維過程。 在接受記者採訪時的點是面試官評估 你怎麼想的，你如何去通過一個問題。 在整個採訪中，最糟糕的事情你能做的就是保持沉默。 這只是沒有好。 當你一個問題，你要確保你明白的問題。 因此，重複的問題，早在你自己的話 並嘗試工作的深入一些簡單的測試用例 以確保您了解的問題。 通過一些測試案例，也會給你一個如何解決這個問題的直覺。 你甚至可能發現一些模式，以幫助您解決問題。 他們的大秘訣是不要沮喪。 不要沮喪。 面試是具有挑戰性的，但你可以做的最糟糕的事情， 除了沉默，是明顯受挫。 你不想給你那種印象的面試官。 有一件事你 - 所以，很多人，當他們進入接受記者採訪時， 他們試圖嘗試找到最好的解決方案， 當真的，通常一個有目共睹的解決方案。 它可能是緩慢的，它可能是低效的，但你應該只說明它， 只要你有一個起點，更好地工作。 同時，指出了解決的辦法是緩慢的，在 大O時間複雜度和空間複雜度， 將展示給面試官，你明白 這些問題在編寫代碼時。 所以，不要怕先拿出最簡單的算法 ，然後從那裡。 有任何疑問，這麼遠嗎？好吧。 

因此，讓我們深入到我們的第一個問題。 “給定一個數組，n為整數，寫一個函數，打亂數組 等地方的所有排列的n個整數同樣有可能。“ 假設你有一個隨機整數發生器 生成的範圍內的整數，從0到i，一半範圍。 每個人都理解這個問題呢？ 我給你n個整數的數組，我希望你能洗牌。 在我的目錄，我寫了幾個方案，以證明我的意思。 我要洗牌的20個元素的數組， 從-10到+9， 我要你這樣輸出的列表。 所以這是我已排序的數組中，我希望你能洗牌。 我們將繼續這樣做。 每個人都明白的問題嗎？好吧。 所以這是給你的。 有哪些想法？你能做到這為n ^ 2，N日誌N，N？ 開放的建議。 好吧。因此，一個想法，建議由艾美獎， 是第一計算一個隨機數，隨機整數，從0到20的範圍內。 因此，假設我們的數組的長度為20。 在我們的20個元素的圖， 這是我們的輸入數組。 而現在，她的建議是，創建一個新的陣列， 所以這將是輸出數組中。 並在此基礎上，我回到蘭特 -  所以，如果我是，比方說，17日， 複製17到第一位置的元件。 現在，我們需要刪除 - 我們需要將所有元素 過來，使我們有一定的差距結束時，中間沒有孔。 現在，我們重複這個過程。 現在，我們選擇一個新的0和19之間的隨機整數。 我們有一個新的我在這裡，和我們這個元素複製到這個位置。 然後我們轉移項目結束，我們重複這個過程，直到我們有充分的新的陣列。 該算法的運行時間是什麼？ 那麼，讓我們來看看這方面的影響。 我們的每一個元素轉移。 當我們除去這個，我，我們將所有的元素後，到左邊。 這是一個O（n）的成本 因為如果我們刪除第一個元素？ 因此，對於每個刪除，我們會刪除 -  每次刪除會導致O（n）操作， ，因為我們有n清除，這將導致一個O（N ^ 2）洗牌。 好吧。因此，良好的開端。良好的開端。 

另一項建議是使用一種被稱為高德納洗牌， 或費雪耶茨洗牌的。 它實際上是一個線性時間的洗牌。 的想法是非常相似的。 同樣，我們有我們的輸入數組， 但我們的輸入/輸出，而不是使用兩個數組， 我們使用的第一部分的陣列來跟踪我們的混洗部， 我們跟踪，然後我們離開的其餘我們的陣列的unshuffled部分的。 因此，這裡是我的意思。我們開始 - 我們選擇的我， 從0到20的一個數組。 我們當前的指針指向第一個索引。 我們選擇了一些我在這裡 現在我們交換。 因此，如果這是5，這是4， 生成的數組將有5個在這裡和這裡。 現在，我們注意到這裡的標誌。 一切的左側洗牌， 是unshuffled的一切權利。 現在，我們可以重複這個過程。 我們選擇一個1到20之間的隨機指數現在。 因此，假設我們的新的，我是在這裡。 現在，我們交換這方面，我在這裡與我們目前的新位置。 所以，我們做了這樣的交換來回。 讓我的代碼，使之更加具體。 我們從我們的選擇我 -  我們開始與我等於0，我們選擇一個隨機的位置j 在unshuffled一部分陣列，i到n-1。 所以，如果我在這裡，在這裡，其餘的陣列之間選擇一個隨機指數， 和我們交換。 這是所有的代碼需要重新洗牌您的陣列。 有什麼問題嗎？ 

那麼，一個需要的問題是，為什麼這是正確的嗎？ 為什麼每個排列同樣有可能嗎？ 我不會去通過證明了這一點， 但在計算機科學的許多問題可以證明，通過誘導。 你們有多少人是熟悉的感應嗎？ 好吧。酷。 所以，你可以通過簡單的歸納證明該算法的正確性， 歸納假設，假設 我的iPod Shuffle將返回每個置換同樣可能 到第i個元素。 現在，我+ 1。 我們選擇我們的指標j交換的方式， 這導致了 - 然後你工作的細節， 至少充分證明了該算法返回的原因 每個排列以同樣可能的概率。 

好吧，下一個問題。 因此，“給定一個整數數組，陽性，零，負， 寫一個函數，計算的最高金額 的的任何continueous子數組的輸入數組。“ 這裡的一個例子是，在所有的數字是正的情況下， 那麼目前最好的選擇是採取全陣列。 1，2，3，4，等於10。 當你有一些底片，在那裡， 在這種情況下，我們只是想第一 因為選擇-1和/或-3帶給我們的一筆。 有時候，我們可能要開始的數組中。 有時候，我們要選擇什麼都沒有，最好不要採取任何。 有時，它採取的秋天， 因為事情後，超級大。因此，任何想法嗎？ （學生，不知所云）>>呀。 如果我不採取-1。 任我選擇1000和20000， 我只是選擇了3億美元。 那麼，最好的選擇是把所有的數字。 這個-1，儘管是消極的， 整個的總和比我不採取-1。 所以我前面提到的秘訣之一是要清楚地陳述明顯 和暴力的解決方法。 蠻力解決方案，在這個問題上是什麼？是嗎？ [簡]嗯，我覺得蠻力解決方案 將添加所有可能的組合（不知所云）。 記者：好。因此，簡的想法是採取一切可能的 -  我釋義 - 是採取一切可能的連續子數組， 計算其總和，然後採取所有可能的連續子數組的最大。 什麼唯一地標識一個在我的輸入數組子數組？ 一樣，我需要做兩件事情嗎？是嗎？ （學生，不知所云）>>右。 指數和上界指標的下限 唯一確定一個連續的子數組。 [女學生]我們估計它是一個數組的唯一的數字？ [於]第所以，她的問題是，我們假設我們的陣列 -  是我們的一系列獨特的數字，答案是否定的。 

如果我們用我們的蠻力解決方案，然後開始/結束指數 我們唯一確定的連續子數組。 因此，如果我們遍歷所有可能的啟動條目， 所有項目>或=開始，和<N， 你計算的金額，然後我們的最高金額，到目前為止，我們已經看到的。 這是清楚了嗎？ 該解決方案的大O是什麼？ 在時間上。 不太N ^ 2。 請注意，我們遍歷從0到n， 所以這是一個用於環路。 我們再次重複幾乎從開始到結束，另一個循環。 而現在，在那個，我們要總結每一個項目， 所以這是一個循環。因此，我們有三個嵌套的for循環，n ^ 3個。 好吧。這正好為出發點。 我們的解決方案是毫不遜色於N ^ 3。 每個人都明白的蠻力解決方案嗎？ 

好吧。一個更好的解決方案是使用的動態規劃的想法。 如果你把CS124，這是算法和數據結構， 用這種方法，你就會變得很熟悉。 的想法是，嘗試建立小問題的解決方案，以第一。 我的意思是，我們目前擔心兩件事情：開始和結束。 很煩人。如果我們能夠擺脫這些參數之一，怎麼辦？ 一個想法是 - 我們給我們原來的問題， 找到任何子陣列的範圍內的最大總和[O，n-1個]。 現在，我們有一個新的子問題，在這裡我們知道，在我們目前的索引i， 我們知道我們必須得出結論。我們的子數組必須結束當前索引。 因此，剩下的問題是，我們應該在哪裡開始我們的子數組？ 這有意義嗎？好吧。 所以，我編碼這件事，讓我們來看看這是什麼意思。 在的codirectory，有一個程序叫子陣， 和需要的項目數， 在我拖著列表，它返回的最大子數組的總和。 因此，在這種情況下，我們的最大子陣列是3。 而這只是用2和1的採取。 讓我們再次運行它。這也是3。 但是這一次，注意我們是如何走到3。 我們採取了 - 我們只取3本身 因為它的四周底片兩側， 這將帶來一個總和<3。 讓我們運行10個項目。 這一次，它是7，我們以領先的3和4。 這一次它是8，和我們得到通過服用1，4及3。 所以如何給你的直覺就可以解決這個轉變的問題， 讓我們來看看在這個子數組。 我們在此輸入數組，我們知道，答案是8。 我們以1，4，和3。 但是讓我們看看我們如何實際上得到答案。 讓我們來看看在最大的子數組的結束，這些指標。 什麼是最大的子數組，結束在第一個位置？ [學生]：零。 >>零。只要不採取-5。 這裡將是0。是嗎？ （學生，不知所云） 記者：哦，對不起，這是一個-3。 因此，這是一個2，這是一個-3。 好吧。因此，-4，什麼是最大的子數組結束位置 -4是在哪裡呢？零。 一？ 1，5，8。 現在，我必須結束在位置-2是。 因此，6，5，7，和最後一個是4。 要知道，這些都是我的作品 轉換的問題，在這裡我必須結束這些指標， 然後我最後的答案是，一個橫掃， 的最大數量。 因此，在這種情況下，它的8。 這意味著最大的子陣列端部在這個索引， 和以前在什麼地方開始。 每個人都明白這個轉換的子數組？ 

好吧。那麼，讓我們來看看復發。 讓我們只考慮前幾個項目。 因此，這裡是0，0，0，1，5，8。 然後是-2這裡，並把它下降到6。 所以，如果我調用的入口位置，我子問題（一） 我怎麼能使用到以前的子問題的答案 以回答此子？ 如果我看，讓我們說，此項目。 看我怎樣才能計算出答案6 陣列和前面的子問題的答案，此數組中的組合？是嗎？ [女學生]你把陣列的款項 的位置，所以， 然後添加在當前子。 記者：所以她的建議是看這兩個數字， 這個數目和此號碼。 所以這個8指的是子問題的答案（I  -  1）。 讓我們叫我輸入數組A. 為了找到一個最大的子數組，我結束位置， 我有兩個選擇：我可以繼續的子數組 結束在上一個索引，或者開始一個新的數組。 如果我繼續開始在以前的指數的子數組， 然後我可以達到的最高金額是前面的子問題的答案 加上當前的數組項。 但是，我也可以選擇開始一個新的子陣， 在這種情況下的總和為0。 因此，答案是，子問題我最大的0  -  1，再加上目前的數組項。 這是否復發有意義嗎？ 我們的復發，我們剛剛發現的部分問題是，我 是等於前面的子加我最大的數組項， 這意味著繼續前面的子陣， 或0，在我目前的指數開始一個新的子陣。 一旦我們建立這個表的解決方案，那麼我們最終的答案， 只是做了一個線性掃描整個子問題陣列 的最大數量。 我剛才說的，這是一個確切的實施。 因此，我們創建了一個新的子問題陣列，子。 第一項是0或第一個條目，這兩個最大。 而對於其餘的子 我們使用我們剛剛發現的確切復發。 現在我們計算我們的子陣列的最大的，這就是我們最終的答案。 

所以多大的空間，我們在該算法中使用嗎？ 如果你只有採取CS50，那麼你可能沒有討論的空間很大。 嗯，有一點要注意的是，我這裡稱為malloc的大小為n。 給你什麼建議嗎？ 該算法採用線性空間。 我們可以做的更好嗎？ 有您發現來計算最終的答案是不必要的？ 我想一個更好的問題是，什麼樣的信息 我們需要隨身攜帶，一路過關斬將，到最後呢？ 現在，如果我們看這兩條線， 我們只關心前面的子， 我們只關心我們見過的最大的，到目前為止。 為了計算我們最終的答案，我們不需要整個陣列。 我們只需要在最後一個號碼，最後兩個數字。 最後的是，一階數組，最後一個數字的最大數量。 因此，事實上，我們可以融合這些循環 從線性空間不變的空間。 目前的總和到目前為止，在這裡，替換子問題，子問題陣列的作用。 因此，目前的總和，到目前為止，前面的子問題的答案。 而這一筆，到目前為止，以我們最大的地方。 我們計算最大的，因為我們走。 因此，我們從線性空間不變的空間， 我們也有一個線性的解決方案，我們的子數組的問題。 

這些類型的問題，你會得到在接受記者採訪時。 是什麼時間複雜度，空間複雜度是什麼？ 你可以做的更好嗎？是否有不必要的事情是保持周圍嗎？ 我這樣做是為了突出自己的分析，你應該考慮 你的工作，通過這些問題。 應始終問自己，“我可以做的更好？” 事實上，我們可以做的比這更好的嗎？ 排序的一個棘手的問題。你不能，因為你需要 至少讀取輸入的問題。 因此，事實上，你需要至少讀取輸入的問題 意味著你不能做的更好不是線性的時間， 你不能這樣做比恆定的空間。 因此，這是，事實上，此問題的最佳解決方案。 有問題嗎？好吧。 

股市的問題： “n個整數，正的，零或負的給定一個數組， 代表n天的股票價格， 寫一個函數來計算最大的利潤，你可以使 因為你買入和賣出股票在n天正好是1。“ 從本質上講，我們希望低買高賣。 我們要找出我們可以做最好的利潤。 讓我們回到我的頭，什麼是立即清除，最簡單的答案，但它的速度慢？ 是嗎？ （學生，不知所云）“是的。 “等你去你看股票價格 在每個時間點上，（不知所云）。 記者：好了，所以她的解決方案 - 她的建議的計算 最低和計算最高不工作 因為之前可能會出現的最高最低。 那麼，什麼是蠻力解決這個問題呢？ 什麼是兩件事情，我需要唯一確定的利潤，我做嗎？右。 蠻力解決方案是 - 哦，所以，我們只需要兩天，喬治的建議是 唯一地確定這兩天的利潤。 因此，我們計算每對，喜歡買/賣， 計算的利潤，這可能是負數或正數或零。 計算後遍歷所有天對我們最大的利潤。 這將是我們最後的答案。 該解決方案將是O（N ^ 2），這是因為n選擇2對 -  ，你可以選擇結束日期之間的天數。 好了，所以我不打算在這裡走了過來蠻力解決方案。 我要告訴你，有一個n日誌n解決方案。 什麼樣的算法你知道這是n日誌n？ 這是一個棘手的問題。 

合併排序。合併排序是n日誌n， 而事實上，解決這個問題的一種方式是使用 合併排序樣的想法，要求，在一般情況下，分而治之。 其思想是，如下所示。 你想計算出最佳的買/賣對的左半邊。 你可以做，只是用了為期兩天的第n尋找最佳的利潤。 然後，你要oompute最好的買/賣對的右半部分， 所以最後n超過兩天。 現在的問題是，我們如何合併這些解決方案一起回來嗎？ 是嗎？ （學生，不知所云） “好了。因此，讓我畫一幅畫。 是嗎？ （喬治，不知所云） “沒錯。喬治的解決方案是完全正確的。 因此，他的建議是，首先計算出最佳的買入/賣出一雙， 中出現的左半邊，讓我們的呼籲，左，從左到右。 百思買/賣對發生在右半。 但是，如果我們只比較這兩個數字，我們缺少的情況下 在我們這裡買和賣的地方的右半邊。 我們買的左半邊，銷售於右半邊。 而最好的方法計算出最佳的買入/賣出對跨越兩半 是計算出最小在這裡和在這裡計算的最大 它們的區別。 因此，在兩種情況下，買/賣對只發生在這裡， 只有在這裡，這三個數字被定義為兩半。 因此，我們的算法，我們的解決方案合併到一起， 我們要計算出最佳的買入/賣出對 在我們的左半邊買和賣的右半部分。 而最好的方式做到這一點是上半年最低的價格來計算， 在右半邊，最高價和它們的區別。 由此產生的利潤，這三個數字，你最大的三個， 這是最好的利潤，你可以對這些開始和結束的日子裡​​。 在這裡，重要的線是紅色的。 這是一個遞歸調用計算的左半邊中的回答。 這是一個遞歸調用計算的右半部分中的回答。 這些兩個for循環計算上的左和右半邊的最小和最大，分別。 現在，我計算的利潤，跨越了兩半， 和最後的答案是這三個最大。 好吧。 

所以，肯定的是，我們有一個算法，但更大的問題是， 的時間複雜度是什麼？ 為什麼我提到合併排序的原因是，這種形式的分裂的答案 一分為二，然後合併我們的解決方案 正是歸併排序的形式。 所以，讓我去的時間。 如果我們定義了一個函數的t（n）的步驟數 n天， 我們的兩個遞歸調用 每個要花費T（N / 2）， 和這些調用。 現在我需要計算出最小的左半部分， 我可以做n / 2的時間，再加上最大的右半邊。 所以，這僅僅是N。 然後再加上一些經常性工作。 而這個遞推公式 正是歸併排序的遞推方程。 我們都知道，歸併排序是n日誌n時間。 因此，我們的算法也n日誌n。 本次迭代中是否有意義嗎？ 只是一個簡單回顧一下： T（N）的步數計算最大的利潤 超過n天的過程中。 這樣，我們分手了遞歸調用 是第n / 2天致電我們的解決方案， 所以這是一個電話， 然後我們再次呼籲對下半年。 所以，這兩個通話。 然後，我們找到一個最低的左半邊，這是我們可以做的線性時間， 發現的最大的右半邊，這是我們可以做的線性時間。 因此n / 2 + n / 2個是僅僅局限於N。 然後，我們有一些固定的工作，這是像做算術。 這個遞推公式是完全合併排序的遞推方程。 因此，我們的洗牌算法是n日誌n。 因此，我們使用了多少空間？ 讓我們回去的代碼。 

一個更好的問題是，多少個堆棧幀，我們曾經有在任何給定的時刻嗎？ 因為我們使用了遞歸， 堆棧幀的數量決定了我們的空間使用情況。 讓我們考慮n = 8。 我們稱之為洗牌月8日， 這將調用洗牌的前四個條目， 這將調用一個洗牌的前兩個項目。 因此，我們的協議棧是 - 這是我們的協議棧。 然後，我們呼籲再次洗牌月1日， 這就是我們的基本情況是，所以我們立即返回。 我們有更多的比這多的棧幀嗎？ 因為每次我們做了一個調用， 的遞歸調用重新洗牌， 我們把我們的規模的一半。 因此，堆棧幀的最大數量，我們有過在任何給定的時刻 是的日誌n的棧幀順序。 每個堆棧幀具有恆定的空間， 因此，總的空間量， 我們曾經使用過的最大空間量是O（log n）的空間 其中n是的天數。 

現在，要問自己，“我們可以做的更好？” 特別是，我們可以減少這種一個問題，我們已經解決了嗎？ 一個提示：我們只討論兩個問題，在此之前，它不會被洗牌。 我們可以把這個股市的問題，最大的子數組的問題。 如何才能做到這一點呢？ 你們中的一個嗎？艾美獎嗎？ （艾美獎，不知所云） 記者：沒錯。 因此，最大的子數組的問題， 我們正在尋找一筆，在一個連續的子數組。 和艾美獎的股票問題的建議，， 考慮更改，或三角洲。 和圖片，這是 - 這是一個股票的價格， 但如果我們採取了連續兩天之間的差異 -  所以我們看到的最高價格，最大的利潤，我們可以使 如果我們在這裡買和賣在這裡。 但是讓我們看看在連續 - 讓我們來看看子數組的問題。 所以在這裡，我們可以 - 從這裡到這裡， 我們有一個積極的變化，然後再從這裡到這裡，我們有一個負面的變化。 但是，然後，從這裡到這裡，我們有一個巨大的積極變化。 這些變化，我們要總結，讓我們的最終利潤。 然後，我們在這裡有更多的負面變化。 我們最大的子數組的問題的關鍵在於減少我們的庫存問題 考慮天之間的增量。 因此，我們創建了一個新的數組三角洲， 初始化為0的第一個條目， ，然後為每個三角洲（I），那一定是在差異 我的輸入數組（I），和數組（I  -  1）。 然後，我們呼籲我們的常規程序的最大子數組 通過三角洲的陣列中。 而且，由於最大的子數組是線性時間， 這種減少，在這個過程中，創建此增量陣列， 也是線性的時間， 那麼股票的最終解決方案是O（n）的工作，加上O（n）的工作，仍然是O（n）的工作。 因此，我們有一個線性時間解決我們的問題。 是否每個人都明白這個轉變？ 

在一般情況下，一個好主意，你應該始終有 盡量減少一個新的問題，你看到。 如果它看起來很像一個老問題， 請嘗試降低到一個老問題。 如果你能使用所有的工具，你已經使用的老問題 要解決的新問題。 因此，包裝，技術面試是具有挑戰性的。 這些問題可能是一些比較困難的問題 你可能會看到在接受記者採訪時， 所以，如果你不明白，我只是涵蓋的所有問題，也沒關係。 這些是一些更有挑戰性的問題。 實踐，實踐，再實踐。 我給了很多的講義中存在的問題，所以一定要檢查出這些。 祝你好運，你的採訪。我所有的資源都貼在這個環節， 我的高中朋友提供了做模擬技術訪談 所以，如果你有興趣，電子郵件將姚明的電子郵件地址。 如果你有問題，你可以問我。 你們是否有具體問題，相關技術訪談 到目前為止，我們已經看到的任何問題？ 好吧。那麼你的採訪，祝你好運。 [CS50.TV]