淺談 D-ATC

A simple introduction to Digital Automatic Train Control system.

2008 高鐵營

2008 台灣高鐵營紀錄

速度碼? 速度?

速度碼? 速度?

2014聖誕美西遊

LA 迪士尼 環球影城 華納影城 SF 金門大橋 SEA 波音工廠 休閒

2011聖誕北京微軟面試之旅

一次有趣的面試經驗兼北京自由行

Wednesday, July 22, 2015

2014 聖誕美西遊 LAX SFO SEA




這個遊記離太遠就不細打了,這次去美西我的主題很簡單:牛排、星巴克創始店、迪士尼、六人行 !!

第 0 天  TPE(RCTP) → LAX(KLAX)


第 1 天  LA亂晃 Hollywood, Warner Bros, Santa Monica

Bill 推薦的牛 + 星光大道 + Santa Monica


WB 專區


第 2 天 迪士尼樂園


第 3 天 環球影城 LAX → SFO


第 4 天 SFO 睡到中午的自由行


第 5 天 SFO 金門大橋 SFO→SEA


第 6-8 天 SEA 聖誕節烤肉 波音工廠 Outlet 戰利品 SEA→TPE

Tuesday, July 21, 2015

2011 北京微軟面試之旅

說起來這也是篇故事回味


電話面試篇


2011.12.09 一個周五的早上11點,接到 HR 的電話希望約當天下午兩點線上語音面談,當時是應徵北京微軟搜尋技術中心的 Software Development Engineer  (就是Bing嗎~~)


時間來到兩點十分...

面: 可不可以說說您做過些什麼東西
(扯扯甲尚的case  扯扯計網的IM軟體  居然沒想到有Motion Planner)

扯到以前多媒體弄過搜尋引擎的時候,面試官就開始問有關搜尋的東西,像是爬下來的資料,如果還沒有任何使用者做過查詢,要怎麼決定優先順序之類的,講到某個程度瞎掰不下去就只好說研究領域不在這,順便提了一下在做什麼。


之後問了三個關於演算法的問題,由於個人腦細胞有限,最簡單的問題實在只記得大概了。這三個問題要順便說明複雜度。

1.  您知道數組吧~~  (是 array 嗎~~)  對  是 array ~~
給定一個二維數組  只會有 1 or 0  上下左右算是連通

ex:
        00101
        10100
        11111
        01000
        10101



這個裡面總共有 5 塊連通的 1s (右上、最底下的三個、和那一片),這問題您有沒有辦法解  (開始拿 motion planner 解釋寫過類似甚至更難的東西)

不過面試官的電腦沒有 Java ,早知道早點把 Qt 那個 UI 介面做完了......
所以後來面試官請我晚上八點前寄 C++ 程式碼 + 執行檔 + 一組你設計的測資 給他

2. 給一個一維數組,會有正數負數或零,請問怎麼找出一個連續子陣列其和最大。這題夠簡單吧...不過只記得大方向的亂喇賽了,反正就是要那個 O(n) 的演算法嗎~~

3. 您知道串列吧 (是linked list嗎??) 欸~~對!! 是 linked list 串列很基本是吧 (不妙...) 假設有個串列很長 他的尾端可能不小心又指回來自己某個節點造成 cycle ,那要怎麼偵測出一個串列有沒有迴圈

3-1. 因為list很長 記錄下每個節點的記憶體位置是不可行的
3-2. 不能改變串列節點的資料結構

龜兔賽跑來囉~~

剩下就是問對微軟有沒有什麼問題想了解的


北京海淀區篇

收到面試通知後(微軟出的機票跟住宿),2011/12/21 一個人隻身前往北京,第一次有一種,阿原來這就是自己獨立出來行走的感覺阿。晚上到了北京,姑丈載我到微軟安排的飯店,準備隔天的面試。

面試當天一連串四小時的真是可怕,從下午一點到晚上快七點,中間有一段時間等最後一關的 "部門頭頭",所以先讓我休息了一個多小時。

四個人裡面  推測前面三個應該都是工程師類型的人,目測年齡  應該是 4 > 3 > 1 > 2。
以下問題,如果直覺想到暴力法能解決的,都不是想要的答案 XD

附註:還要大概說一下自己的算法複雜度是多少

第一位:
自介閒聊等

1) 給一個 Unsorted int array 和 S 請找出所有的 pair (i, j) such that
    S = array[i] + array[j];   PS: (i, j) 和 (j, i) 視為相同
Hint: You can sorted if you like.

2) 一個平面上的正方形和圓形  要如何判斷是否重疊呢?  (寫過Planner沒道理不會阿)
那兩個正方形呢?!  (更簡單了)

第二位:
自介閒聊等

1) Thread 和 Process 有何不同 ?   盡量舉例  (這是OS吧)
   Thread / Process 有無自己的 Stack/Heap 呢 ?
   (其實沒把握的時候可以自己推  但是要有邏輯的推導)

2) C++和Java的差別  用C++遇過什麼瓶頸  virtual function知道怎麼實做的嗎?
    vTable 是class存在一份  還是每個實體都有一份

3) 給一個 3L 和 5L 的水桶 (無刻度  形狀不規則) 還有一個無限供水的水龍頭,
  如何裝出 4L 的水? (2L 2L倒入別的容器不算  要一次出現 4L)

擴展: 給 ML 和 NL 的水桶  如何到出 KL 的水? 具體的步驟
假設給定的 (M, N, K) 在有限的步數內保證有解


4) Java的GC機制如何,或者是說在 C++ 要如何實現 Garbage Collection的機制呢?
可以具體編程嗎?

5) 動態配置時  若是常常的 new / delete 會消耗蠻多的資源,因此我們會設計一個 ObjectPool 預先配置好空間,當有需要空間時  使用 getObj 跟這個 pool 申請,使用完畢用 returnObj 返回使用的空間。具體實現,這兩個函數的內容,且須支援 multi thread。

寫完後  getObj 裡面有沒有能加速的地方


第三位:
自介閒聊等

1) 一個環狀公路上  有N個加油站  這些加油站都有儲油 oil[N],這些加油站是隨機分布在這個環狀公路上,也就是非等距分布。假設有一台車走一單位的路需要耗一單位的油,且公路長為 D 且 Sigma(oil[i]) - D = 0 ( for i=0~N ) ,意即加油站的總油量足夠走完整圈路。
現在有一輛汽車油箱是空的,能找出從某個加油站出發,可以繞一圈回到原地,輸出該加油站的編號。


第四位: (部門頭頭)
自介閒聊等
原本以為他會問一些比較非程式的問題......結果.......


1)
我有一個 byte array 假設是 { 3, 2, 6, 6, 6, 6, 5 },裡面保證不會有 20 這個元素,可以試著壓縮這個 array 嗎? 壓縮的結果必須也是 byte array。你的算法 worst case 可以舉例嗎? 能更好嗎?

若是 20 亦會出現在此 array 中呢? 這樣算法結果勢必會差些  但有方法嗎?

PS: 此為串流所以不知道整個資料多大

頭頭: 恩  我只有一個問題要問你  今天就到這吧~~

Seminar時說的沒錯: 面試到後來已經不知道再說什麼鬼話了


整體說來面試過程不太像上對下的感覺,比較像是在實驗室討論,可以闡述想法和面試的人互動,他們會跟著你的思路去走。闡述久了,他們多少也會給些提示,有些東西要立馬想出來也是有難度,科科。

然後白板跟紙上 coding 一定要會 XD


後記


因為機票回去的時間是自己選的,微軟也好心地把旅館訂到面試的隔天,不會馬上趕你走。之後兩天就和姑丈在北京市內玩一玩,也順便去爬了長城,吃了烤鴨等。在聖誕夜那晚又回來了台北,結束這短短幾天的北京之旅。

Tuesday, July 7, 2015

Build Qt 5 in N Hours



前置準備

  • git
  • ActivePerl 5.16
  • Python 2.7
  • Ruby 1.9
  • OpenSSL
  • Bison
  • Flex
  • iconv
  • gperf

※確定以上執行檔的位置皆在 PATH 變數下
※只有粗體字的要自己安裝,後面四個公用程式在 Qt5 clone 下來的資料夾 gnuwin32\bin 內有,直接將這個資料夾新增到 PATH 即可

  • ICU    qtwebkit 處理 unicode 官方只提供 2010 的 prebuilt 其他版本要自己先下載原始碼用對應版本的 VS 編譯 (記得檢查專案設定是否 BUILD TARGET版本正確)
  • 環境變數新增:
    • INCLUDE:  Path/To/ICU/Include;Path/To/OpenSSL/Include
    • LIB: Path/To/ICU/Lib;Path/To/OpenSSL/Lib;Path/To/OpenSSL/Lib/VC
    • PATH: Path/To/ICU/Bin;上述公用程式的執行位置

      LIB請確定是正確的 VS 版本的 LIB 和正確的平台(32/64)

※底下指令部分皆為 CMD 的指令


下載原始碼

開啟 Visual Studio Native命令提示字元 (開2013 x64 就會 BUILD 出對應版本)

git clone  git://gitorious.org/qt/qt5.git
perl init-repository

會下載一陣子



編譯

  • Windows

configure -debug-and-release -c++11 -nomake tests -opensource -confirm-license -openssl -platform win32-msvc2010 -opengl desktop
nmake
nmake install

也可以用 jom 平行編譯
  • Mac

configure -c++11 -nomake tests -opensource -confirm-license -openssl -platform macx-clang-32
make
make install

之後 qtbase 資料夾內就是 build 好的 SDK

  • configure參數說明:
    • -platform 後面為 mkspec 資料夾內支援的平台 使用 VS2013 則將2010改為2013
    • -opengl desktop 使用 OPENGL 做 Qt GUI 的繪製,不加上則會使用libANGLE 在 WINDOWS上會用 DIRECTX 繪製
    • 可以加上 -nomake examples -nomake demos 節省一點時間

清除

git submodule foreach --recursive "git clean -dfx"

部署

  • 基本的
  • Qt5Widgets.dll       Qt 核心模組  
  • Qt5Core.dll            Qt 核心模組
  • Qt5Gui.dll              Qt Gui模組
  • platforms/qwindow.dll   (一定要放在platforms內  Qt5將平台拆開 )
  • icudtXX.dll
  • icuinXX.dll
  • icuucXX.dll            這三個是 ICU 的 DLL   XX為版本

  • 使用 LIBANGLE 需要的 DLL ( DIRECTX )
  • libEGL.dll                              LIBANGLE 的 DLL (必備)
  • libGLESv2.dll                        LIBANGLE 的 DLL (必備)
  • D3DCompiler_XX.dll             如果安裝 DX RUNTIME 應該系統會有

  • MSVC 相關的 DLL    XXX為版本
    (用 VISUAL STUDIO 編譯的 可以直接裝 C++ RUNTIME 就不需要特別包這個 )
  • msvcpXXX.dll
  • msvcrXXX.dll

以下部分要針對專案是否用到 Qt 官方外掛 $(QTSDK)/plugins 資料夾內相關內容須複製到 AP 同一層,不枚舉了。

  • 有使用 Jpg Gif ...等 imageformats 底下支援的格式
    imageformats/*.dll   ( Qt圖片的 Plugin )
  • SQL Drivers
    sqldrivers/*.dll