今晚連著面了三輪依圖澳泵。性湿。毫無(wú)間隔玄柏。襟衰。累pee= =
第一輪
自我介紹+介紹項(xiàng)目
算法題1
一個(gè)長(zhǎng)度為n的數(shù)組，其中有一個(gè)數(shù)字出現(xiàn)次數(shù)大于n/2次粪摘，找出這個(gè)數(shù)字瀑晒。
這個(gè)題貌似是個(gè)競(jìng)賽經(jīng)典題。徘意。之前一個(gè)同事給我講過(guò)這個(gè)題苔悦，但是我給忘了！但是現(xiàn)場(chǎng)給出了兩種解法椎咧。玖详。第三種面試官怎么提示都想不出了。。
第一種：一個(gè)dictionary記每個(gè)元素出現(xiàn)次數(shù)蟋座，如果出現(xiàn)次數(shù)大于n/2劳澄，中斷當(dāng)前遍歷并返回，O(n)的復(fù)雜度
第二種：轉(zhuǎn)換為找第n/2大的數(shù)字的問(wèn)題蜈七，解決秒拔。平均O(n) //我當(dāng)時(shí)第一次說(shuō)的是排序之后然后中間那個(gè)數(shù)字就是要找的，結(jié)果面試官讓我寫排序算法飒硅，我寫著寫著快排反應(yīng)過(guò)來(lái)的砂缩。。
查了一下三娩，是http://blademastercoder.github.io/2015/02/04/leetcode-MajorityElement.html 的思路2的解法
算法題2
給出一個(gè)m行n列的矩陣庵芭，由元素0和1組成，元素0表示當(dāng)前位置可以走雀监，元素1表示當(dāng)前位置是圍墻不能走双吆。找出從(x0, y0)到(x1, y1)的任意一條路徑
深度優(yōu)先搜索
第二輪
自我介紹+職業(yè)規(guī)劃聊天=。=
算法題1
n皇后問(wèn)題会前，n*n矩陣?yán)锓舗個(gè)皇后好乐，給出一種解法
算法題2
已有一個(gè)Rand2()函數(shù)，可以等概率地生成0和1(都是1/2)瓦宜，問(wèn)利用這個(gè)函數(shù)如何等概率地生成0, 1, 2, 3, 4, 5, 6蔚万。
面試官給出提示，先考慮如何等概率地生成0-7
每個(gè)出現(xiàn)的概率是1/8临庇，這個(gè)可以用三位二進(jìn)制表示法反璃，每位是一個(gè)Rand2()
然后到等概率地生成0-6，只需在生成111的時(shí)候假夺，再生成一次就可以
第三輪
自我介紹+項(xiàng)目介紹
算法題1
進(jìn)階：
算法題2
然鵝我還是不知道解法現(xiàn)場(chǎng)想的淮蜈。。已卷。
進(jìn)階：
從最多只能進(jìn)行一次買賣改為最多可以進(jìn)行兩次買賣梧田，問(wèn)最大收益是多少
這個(gè)面到第三面腦子已經(jīng)完全不轉(zhuǎn)了。悼尾。柿扣。面試官給的解法肖方。闺魏。
從前往后掃一次，找前i天最大收益A[i]俯画；從后往前掃一次析桥，找后i天最大收益B[i]；這兩個(gè)可以一次遍歷做完。
然后再遍歷一遍泡仗，找A[i]+B[i]最大值
最后的吐槽埋虹。。無(wú)間斷連續(xù)三場(chǎng)(我開始還以為只面一場(chǎng)娩怎。搔课。也怪自己沒(méi)問(wèn)清楚。截亦。于是晚飯都沒(méi)吃就去了爬泥。。還好男票在面試前跑去給買了面包和水崩瓤，在前兩場(chǎng)中間塞了一個(gè)面包= =)還是挺懵以及挺難一直集中注意力的袍啡。。一個(gè)大屋子里却桶，就3v3的面試別人說(shuō)話也聽得很清楚境输，于是話到了腦子里腦子就會(huì)處理一下，于是思路也就會(huì)斷一下= =不過(guò)感覺面試官都很有趣~他們做的東西也都挺有趣的233(感覺自己被洗腦成功了颖系。嗅剖。
