Q1
https://www.zhihu.com/question/27547892?sort=created
有一個(gè)黑匣子尤蛮，黑匣子里有一個(gè)關(guān)于 x 的多項(xiàng)式 p(x) 尝艘。我們不知道它有多少項(xiàng)筒愚，但已知所有的系數(shù)都是正整數(shù)。每一次，你可以給黑匣子輸入一個(gè)整數(shù)整胃，黑匣子將返回把這個(gè)整數(shù)代入多項(xiàng)式后的值。那么喳钟，最少需要多少次屁使， 我們可以得到這個(gè)多項(xiàng)式每項(xiàng)的系數(shù)呢？
Q2
有n>2個(gè)交易員奔则，他們想知道他們平均的薪水蛮寂，但是又不想任何人知道自己的薪水。
Q3
Alice是色盲易茬，她有兩個(gè)球酬蹋，外觀完全一樣，Bob告訴她這兩個(gè)球顏色不同抽莱，問(wèn)Bob怎么向Alice證明這倆球顏色不同?
Q4
判斷兩個(gè)圖G和H是同構(gòu)的是NP的范抓，只要給出一組頂點(diǎn)的對(duì)應(yīng)關(guān)系就可以多項(xiàng)式時(shí)間檢驗(yàn)，Alice要給Bob證明這兩個(gè)圖是同構(gòu)的但又不給出這組對(duì)應(yīng)關(guān)系食铐。
Q5
有個(gè)list尉咕，已知存在majority element，就是出現(xiàn)次數(shù)多余一半的元素璃岳，怎么把它找出來(lái)年缎。比如 abaacbbacaa 中的a。 如果不知道list里面是不是有majority element铃慷，如果有就把它找出來(lái)单芜，沒(méi)有的話return none呢？
O(n)時(shí)間和constant memory犁柜。
算法很簡(jiǎn)單洲鸠，開始記錄0 遍歷第i個(gè)元素時(shí) ------如果當(dāng)前記錄的是0，那么記錄(第i個(gè)元素,1) ------如果當(dāng)前記錄是(x,y) ------------如果當(dāng)前元素是x，那么記錄(x,y+1) ------------否則記錄(x,y-1)（如果y-1=0扒腕，記為0)
在這個(gè)例子當(dāng)中绢淀， abaacbbacaa，根據(jù)看到的元素我們記錄 0->a->(a,1)->b->0 ->a->(a,1)->a->(a,2)->c->(a,1)->b->0 ->b->(b,1)->a->0 ->c->(c,1)->a->0 ->a->(a,1)
大概證明思路就是瘾腰，按每次記錄0劃分成sub list皆的，也就是ab,aacb,ba,ca,a，在除去最后一個(gè)的sub list的sub list當(dāng)中蹋盆，都沒(méi)有majority element费薄，（因?yàn)槠渲械谝粋€(gè)元素剛好出現(xiàn)一半次數(shù)），又因?yàn)橐阎麄€(gè)list存在majority element栖雾，那肯定就是最后一個(gè)sub list中的majority element楞抡，在這個(gè)例子就是a。
通過(guò)證明我們知道析藕，如果不知道是否有majority element的話沒(méi)啥區(qū)別召廷，就是遍歷兩遍，第一遍一樣账胧，找出來(lái)唯一可能的candidate竞慢，第二遍count一下出現(xiàn)次數(shù)，判斷是否真的是majority找爱。
Q6
有一種玻璃杯質(zhì)量確定但未知梗顺，需要檢測(cè)。 有一棟100層的大樓车摄，該種玻璃杯從某一層樓扔下寺谤，剛好會(huì)碎。 現(xiàn)給你兩個(gè)杯子吮播，問(wèn)怎樣檢測(cè)出這個(gè)杯子的質(zhì)量变屁，即找到在哪一層樓剛好會(huì)碎？
每次扔的區(qū)間減少一層意狠，這樣做可以保證每個(gè)區(qū)間查找的最差次數(shù)是一樣的粟关。 假定第一步在15樓扔，沒(méi)碎的話則下一步在29樓扔环戈，沒(méi)碎下一步在42樓扔....碎掉之后則在上一次沒(méi)碎的樓層開始向上扔闷板。那么最開始在哪一層開始扔呢？院塞？ 這里我們需要拿支筆算一下： x+(x-1)+(x-2)+...+2 >=100 求解出答案為14遮晚。
即最終給出的解決方案是： 最開始從14樓開始扔，沒(méi)碎的話在27樓扔拦止，再?zèng)]碎的話在39樓扔.....一旦碎掉县遣，則從上一次沒(méi)碎的樓層逐層往上扔糜颠，即可快速確認(rèn)杯子在哪一層剛好會(huì)碎掉。
這樣的方法可以保證在最差的情況下也能在14次內(nèi)找到樓層萧求，平均需要的次數(shù)不到10次其兴。
