[回到版面]
回應模式
名 稱
內 文
附加圖檔[] []
  • 可附加圖檔類型:GIF, JPG, JPEG, PNG, WEBM,瀏覽器才能正常附加圖檔
  • 附加圖檔最大上傳資料量為 3072 KB。
  • 當檔案超過寬 125 像素、高 125 像素時會自動縮小尺寸顯示
  • 目前附加圖檔使用量大小: 152030 KB / 500000 KB
  • 回覆時程式碼縮排會被trim消掉,請善用[code][/code]標色或貼到ideone等網站
  • LaTeX記法可以用「$$」或「\( \)」包起來,例如「$\sum_{k=1}^{k=n} k^2 = \frac{n(n+1)(n+2)}{6}$」
  • 投稿時請點擊畫像認證後,再按下 [送出] 按鈕提交。
  • 鬧板、攻擊性發言、煽動性發言請無視(回應者也無視),並使用del或在貓管理部向管理員回報。
  • 新介面尚處於測試階段,如果有任何問題可以向管理員或於程設交流版反映。

檔名:1540981044824.png-(37 KB, 757x788)
37 KB
無題無名18/10/31(三)18:17:24 ID:92Fj97HINo.12918
各位好 最近在準備面試,有一些問題想請教各位

1.我打算面試asp.net mvc相關的職缺
目前要把asp.net mvc + html5 + CSS(bootstrap)
+ javascript (react.js)讀熟+實作作品

對演算法,和資料結構這方面有些疑惑
不知道要準備到什麼程度,才能通過面試
目前是打算準備

演算法
插入,快速,堆積,合併排序法

資料結構
Stack,Queue,Linked List
,Tree,Graph,Heap

會看這兩個網站複習
http://www.csie.ntnu.edu.tw/~u91029/
http://alrightchiu.github.io/SecondRound/

不知道還有哪些需要補足的地方,
需要去解leetcode的題目嗎?
想請各位給我一點建議

2.
複習快速排序法的時候遇到一個問題

C# Sharp Searching and Sorting Algorithm Exercises: Quick sort
http://0rz.tw/aED9I

這篇文章中的快速排序法,我實在弄不懂他如何實作的
執行結果是正確的,可是程式碼的部分有點無法理解

其他網站(演算法筆記,SecondRound)的快速排序法排序法
都還算能理解

第一篇文章的程式碼 Pivot跟Left重疊了,而且Pivot會跟Right交換
可是其他人實作的程式碼好像都沒有重疊

想請能理解程式碼的島民給我一點思路,我有在紙上實作過了,可是還是弄不太懂
薪水小偷18/11/01(四)17:07:04 ID:VDIh4JWcNo.12920
上班做得有點卡彈,來試著解釋看看作法。

其實圖片有一點誤導,讓我們一步一步來看。

開頭的 if 判斷只是確認 arr 的所有元素都會跑過一遍,所以跳過。

Partition 函式的作用是將比 pivot 小的元素留在左邊,比較大的留在右邊,全部元素跑過一遍後會回傳分割點的 index ,由於 if 判斷會讓 right 停留在最後一個比 pivot 小的元素上, arr[right+1] 一定會大於 pivot ,故 right 就是分割點 index 。

然而原始的函式裡有一段意義不明的判斷:
if (arr[left] == arr[right]) return right;


原以為是要處理同樣元素,但同元素出現的話這個演算法會出錯,所以⋯⋯坐等其他高手解釋。

這邊圖片有誤導的點在於,你會以為 51 只有在最後才會換,其實一開始就不斷切換了,直到兩邊都分好(如圖最終結果)。之後就是很單純的分治法,對 arr.L 與 arr.R 重跑一次上面的流程,最終你就會得到排好的 arr 。
無名18/11/02(五)18:40:46 ID:fWOoOhvQNo.12921
>>12920
非常感謝您的幫忙
看了您的敘述我終於理解了
不過我有一個疑問
這篇文章中的 pivot在 Partition函式中
因為跟 Left同一位置,所以跟 Right會一直做 Swap的動作

可是我看其他人寫的quicksort,pivot都是在這兩個地方做交換

1.Partition的最後一個步驟 (Partition過程好像都不會移動,像附圖那樣)

2.兩邊都分好->執行分治法
決定 左邊與 右邊的新pivot
對 arr.L 與 arr.R ,再次執行artition函式

QuickSort(arr, front, pivot - 1);
QuickSort(arr, pivot + 1, end);

所以是只要符合quicksort的演算法架構
pivot位置可以在Partition過程中任意移動
(不含最後一個步驟)

對這部分還有一些疑問,不好意思麻煩您了

另外第一個關於面試的問題,希望有島民能給我一些建議
我好怕面試的時候被考到不太擅長的程式解題,演算法,資料結構
想了解一些準備的方向
無名18/11/03(六)07:37:04 ID:V9xDHi4YNo.12922
跟你分享一下MSFT的經驗:

1. 面試通常個別為一小時. 通常分考演算法跟考系統設計.
考演算法基本上就是基本的leetcode原題(簡單/中)或變化題. 本身考題通常都設計在30-40分鐘能解出來的程度. 之後follow up 再繼續加要求.

有些基本的題目你也要會就是了. 總之你一直刷題這些都會知道.
比如說 k-th largest/smallest element in the array. 要用sorting還是 heap解?優缺點? 複雜度? 這問題我當初在MSFT, AMAZON...面試都被問過, 我自己有時也用這個問不少人. (通常是考你會不會heap就是了...)

考演算法通常題目會出的模擬兩可. 在寫白板前要問非常清楚面試官的要求, 他期望的是什麼. 在寫白板的時候注意你的命名方式 你寫c#就照微軟的命名方式. 開大寫就大寫 小寫就小寫, 基本上就是 clean code跟SOLID 原則. 這個就是靠經驗了.

最後寫完code, 加分項就是寫test case (edge case/corner case/base case/boundary case). 你test case 有目的的寫是加分 你test case亂寫就是扣分.
無名18/11/03(六)07:40:15 ID:V9xDHi4YNo.12923
>>12922
更正, 考系統設計的題目會出的模擬兩可.
無名18/11/03(六)07:51:18 ID:V9xDHi4YNo.12924
>>12923
忘了講最後一個建議, 也是我認為最重要的建議.
很多人面試被拒之後就放棄了. 其實我再進去之後才知道不少人也在同公司面試跪過不少次的.
面試被拒不要放棄, 哪邊不足就把哪邊補齊. 不斷學習不斷進步, 你會找到你的夢想職位的.
薪水小偷18/11/05(一)14:47:16 ID:KMzlqZDMNo.12925
>>12921

關於你的問題我的不是很明白,你的意思是說其他人的 swap 都是在 partition 與處理好後執行分治法時是嗎?

如果可以能提供一下最後才換的程式碼嗎?想不太出最後才換是怎麼樣。

這個作者的做法,好處在於從頭到尾都只用一個陣列,當然比較不便於理解,不斷切換就是為了確保 pivot (原始的 arr[left] ) 可以在 arr.L 與 arr.R 的正中間。

上面個問結果也回答了:
> 所以是只要符合quicksort的演算法架構
> pivot位置可以在Partition過程中任意移動
> (不含最後一個步驟)
這個部分,與其說任意移動,不如說就是要確保在正中間才不斷轉換。
無名18/11/05(一)21:11:25 ID:8YZA5WTwNo.12926
>>12922
感謝您提供的寶貴建議
最近開始練習leetcode的題目
希望能快點有些成果

>>12925
http://0rz.tw/zmjuB
Comparison Sort: Quick Sort(快速排序法)
我是看這篇文章裡的步驟圖解和程式碼
// C++ code

#include <iostream>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int Partition(int *arr, int front, int end){
int pivot = arr[end];
int i = front -1;
for (int j = front; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
i++;
swap(&arr[i], &arr[end]);//這裡交換pivot

//「所有比pivot小的數列」的最後一個位置,
//移動到「所有比 pivot大的數列」的第一個位置
return i;
}
void QuickSort(int *arr, int front, int end){
if (front < end) {
int pivot = Partition(arr, front, end);
QuickSort(arr, front, pivot - 1); //這裡決定新的pivot
QuickSort(arr, pivot + 1, end); //這裡決定新的pivot
}
}


我可能表達的不是很好,或是有理解錯誤的地方
感謝您耐心地替我解答

w3resource作者的做法,我現在雖然理解了
可是還是覺得好複雜,可能是我理解力不太好吧
薪水小偷(嗯?)18/11/06(二)01:53:42 ID:yPvtbAe6No.12927
>>12926
喔喔,原來是這樣來做最後交換,學到了。

我想你會困惑的點在於 w3resource 用兩個變數來記錄要交換的 index ( left & right ),但 alrightchiu 只使用 i 。

w3resource 不斷讓 pivot 移動,也就是開始在 left ,交換一次後變 right ,再一次又變回 left ,所以他用了兩個判斷去更改待交換 index 。
// 兩個判斷每次都只跑一個,因為 pivot 一定在 left | right
// 全元素跑完後,最終 left == right ,所以回傳 left 也行
while(arr[left] < pivot) {
left++
}
while(arr[right] > pivot) {
right--
}

w3resource 的 left 與 right 最後都指向換無可換的 pivot ,而 alrightchiu 則是最後直接把 pivot 換到 i ,因為基本是不同概念的做法啦,一時之間難以理解很正常。


【刪除文章】[]
刪除用密碼: