[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]