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

[Freak1033 (金が信念! XD)]

※ 引述《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: f 好像會有幾個不可微點?
推 peter26194: 我以為面試題只會用到高中程度數學，我太天真了...
推 FRAXIS: http://goo.gl/xWSkN6 解法應該是這個
推 choulu:  ....
→ FRAXIS: 抱歉 f 應該是沒有不可微點 但是微分 f 求極值 還要考慮
→ FRAXIS: 限制式 有簡單的方法可以作嗎？
推 DJWS: 窮舉圓周上每一點  然後算f(P)
→ DJWS: 因為f(P)是單峰函數  所以窮舉可以改為ternary search
推 FRAXIS: 那這樣就變成 iterative method 了
推 DJWS: 是的
推 FRAXIS: 我當時的回答是用 convex programming
→ FRAXIS: 但是我想應該可以用幾何學得到解析法 所以才上網找了論文
→ FRAXIS: 畢竟對這麼特定的問題 用 convex programming 或是
→ FRAXIS: iterative method 好像有點 overkill
→ FRAXIS: 不過我也不清楚面試官心理的答案是什麼就是了..
推 DJWS: P延著圓周跑的時候   f(P) 是 convex function 嗎？
推 FRAXIS: 應該可以把 P mapping 到一個線段 這樣就是 convex 了吧
推 FRAXIS: 哈，我想了想 單峰是很明顯的 convex 我就不知道了