Re: [經驗] Google、FB、LinkedIn 面試經驗

看板Oversea_Job作者Freak1033 (金が信念! XD)時間8年前 (2016/04/28 08:02)推噓11(11推 0噓 7→)

留言18則, 4人參與討論串3/5 (看更多)

※ 引述《peter26194 (啦啦哼哈)》之銘言： : ※ 引述《FRAXIS (喔喔)》之銘言： : : 我被問過一個問題：在三維空間中有兩個相同大小的圓盤位於不同位置 : : （朝向也可能不同），求這兩圓盤間的最短距離。除了暴力法我還真想 : : 不出來怎麼作.. : 最近也在面試，看到那道題目，試著想了一下解法： : 給定兩圓c1, c2 : 找出兩圓各自所在的平面p1, p2 : 把兩圓圓心連線得到L線段 : 將L投影到p1上，得到L1線段 : L1的一端點是c1圓心， : 1)另一端點如果在圓c1之內，那麼此端點就設為a1; : 2)另一端點如果在圓c1之外，那麼則把a1定為L1和c1的交點 : 用同樣方法，將L投影到p2上，得到L2線段，再找出a2 : 則a1, a2連線就是最短距離 : 靈感是從「平面上的兩圓，要找最短距離，要找圓心連線和兩圓的交點」而來的， : 我也不太確定這是對的，大家覺得呢？ : (雖然在這裡討論怪怪的，不過應該是可以的吧？) 先釐清一下問題的定義, 確定大家討論的是同一個問題. 圓盤的定義是在某平面上距離圓心小於某半徑的點集合對吧? 如果是兩個圓周找最近點的話問題就簡單得多. 首先先簡化問題. 由於對空間進行旋轉跟平移不影響問題的答案(證明留給讀者), 所以先假設兩圓盤的半徑為 1, 其中一個圓盤位於 XY 平面上, (i.e. 即圓心為原點 {0, 0, 0} , 法向量平行 Z 軸 {0, 0, 1}), 另一個圓盤圓心向量 C, 法向量 N. 於是這個問題可以寫成求 argmin[A,B](|A - B|), A · {0, 0, 1} = 0 (1. A 點位於 XY 平面) |A × {0, 0, 1}| <= 1 (2. A 點限制在半徑 1 的 Z 軸圓柱) B · N = C · N (3. B 點與 C 共平面, 法向量 N) |(B - C) × N| <= 1 (4. B 點限制在半徑 1 的 CN 圓柱) 由於條件 1 跟 3 可以簡化一維的自由度, 即已知 Az = 0 Bz = (C · N - BxNx - ByNy) / Nz 問題可簡化為四元二次的 optimization with boundary condition. 當然這樣還是太複雜, 我們必須進一步簡化問題. 一個觀察是, 當兩個圓盤的法向量平行的時候這個問題有 degenerate solution, 可以直接將兩個圓盤投影到任意一個平行平面上, 若有重疊則重疊範圍內的任一對點皆是最短距離. 若無重疊則可選圓心投影連線與兩個圓周的交點. 現在考慮兩個圓盤法向量不平行的情形, 可以證明兩點至少有一個點位於圓周上. 利用歸謬法, 假設兩點皆非位於圓周, 則兩點連線必然與其中一個圓盤的法向量不平行, 因此可以移動該圓盤上的點往連線方向移動而使得連線縮短. 在此我們將問題再次簡化成空間中一圓盤與一圓周求最近兩點. (三元二次最佳化問題.) 現在我們再考慮簡化問題, 求空間中一點與圓盤間最短距離. 這個問題可以寫成簡單函數. 我們再次經由空間變換把圓盤換到以原點為圓心, 法向量平行 Z 軸, 半徑 1, 輸入點為 P. 若 P 點在 XY 平面的投影落在圓內, 則答案為 Pz. 不然則取投影點與圓心連線在圓周上的交點, 即 hypot(hypot(Px, Py)-1, Pz). Lemma 1: 空間中一點 P 與單位圓盤的最短距離為 f(P) = if hypot(Px, Py) < 1, Pz else, hypot(hypot(Px, Py)-1, Pz) 回到原問題, 求空間中一圓周與單位圓盤之最短距離, 可以改寫為 argmin[P](f(P)) P · N = C · N |(P - C) × N| = 1 由於 P 點的自由度只有一維, 其實可以視為一元最佳化問題, 可以經由微分 f 來求極值. -- その乾いた哀愁の瞳に去來するものは何か？失ったもの得たものそして廣大なネットの狹間で彼が見たものとは？虛像と實存と記號の中に彼は今、何を想うのか？＜バトルプログラマーシラセ＞ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 54.68.90.183 ※ 文章網址: https://www.ptt.cc/bbs/Oversea_Job/M.1461801749.A.F86.html

推

FRAXIS

04/28 09:55, , 1^F

04/28 09:55, 1^F

推

peter26194

04/28 10:31, , 2^F

04/28 10:31, 2^F

推

FRAXIS

04/28 10:38, , 3^F

04/28 10:38, 3^F