今日下午去面試這個(gè)公司，依稀記得幾個(gè)很有意思題目，也算是考察個(gè)人思考邏輯能力。下面分享幾個(gè)還算有意思的題目。

1、有17根等長木棍，每根長度為11.1，現(xiàn)在切成等量的兩種木棍，以下簡稱A木棍和B木棍。

A木棍長1，B木棍長0.7 求問：最多能切出多少組木棍（1個(gè)A和1個(gè)B稱為1組）。

A 99 B 105 C 111 D 125

解答：顯然17*11.1/(1+0.7) = 111 也就是說利用率為100%的時(shí)候，能達(dá)到111組。于是我們考慮如何能100%利用這些棍子。首先考慮一根棍子的拆解

如下：11.1 = 3*0.7 + 9*1 1

11.1 = 13*0.7 + 2*1 2

顯然要100%利用率只能是如上兩種切法。假設(shè)切法1切了（k）個(gè)木棍，切法2切了（17-k）個(gè)木棍

則：k*3 + 13*（17-k） = 9*k + 2*（17-k） 若此方程有正整數(shù)解，則可以達(dá)到100%利用率。

解得k=11 。 答案為111

2、有兩個(gè)杯子，容量分別為30，70，求如何最快得到20和80

這種小學(xué)數(shù)學(xué)競賽見過的題目。下面直接給出解法了。80的留給讀者思考，先得到10即可。

30 | 70 杯子

————————

30 | 0 30裝滿水

0 | 30 30的水全部倒入70

30 | 30 30再裝滿水

0 | 60 30的水再全部倒入70

30 | 60 30再裝滿水

20 | 70 30的水再倒入70直到滿

至此，得到20

3、有4個(gè)人過獨(dú)木橋，僅有一個(gè)手電筒，過橋必須依賴手電筒。橋一次最多允許兩個(gè)人，求這4個(gè)人最快過橋時(shí)間。其中：兩人一起過橋的時(shí)間是計(jì)以慢的那個(gè)人時(shí)間。

四個(gè)人過橋時(shí)間：1,2,5,8

解答：初看這道題目，可能很容易就進(jìn)入這樣的思考：每次讓最快的人來護(hù)送。

于是：

1、1,8電筒過橋 +8

2、1帶電筒回 +1

3、1,5電筒過橋 +5

4、1帶電筒回 +1

5、1,2電筒過橋 +2

總耗時(shí)為：17

但是這個(gè)卻不是最優(yōu)。

當(dāng)人數(shù)等于1，2，3的時(shí)候：答案很容易得出；
當(dāng)人數(shù)大于等于4時(shí)：

若設(shè)過橋速度最快的那個(gè)人過橋時(shí)間為a,第二快為b;過橋第二慢的那個(gè)人過橋時(shí)間為y,最慢為z;
此時(shí)有兩種過橋方案：
一.最快和次快的人先過，然后最快的回來，然后最慢與次慢的人再過，次快的回來；
二.最快的和最慢的過，快的回來，在和次慢的過，快的再回來；

最優(yōu)方案：

1、1,2電筒過橋 +2

2、1帶電筒回 +1

3、5,8電筒過橋 +8

4、2帶電筒回 +2

5、1,2電筒過橋 +2

總耗時(shí)為：15

4、有一個(gè)水庫，假設(shè)年降水量恒定；水庫可供12W人使用20年。由于某些原因人口增加到15W，水庫的水只夠使用15年。市長呼吁節(jié)約用水，希望水可以用到30年。求每個(gè)人的用水量為原來的幾分之幾。（假設(shè)人數(shù)不會(huì)再增加，年降水恒定）

解答：初看此題，還有點(diǎn)迷糊，一直糾結(jié)在：12*20 > 15*15 ，后來一想，水庫應(yīng)該還有存儲(chǔ)。

假設(shè)水庫本來有水W，年降雨為k，每人用水為y，則有

W + 20*k = 12*20*y

W + 15*k = 15*15*y

假設(shè)節(jié)約用水后的人用水量為x，則

W + 30*k = 15*30*x

以上三式，求解得 x = 3/5 * y

5、有序數(shù)組{1,2,3,4}，進(jìn)行移動(dòng)，比如移動(dòng)1為{4,1,2,3}，移動(dòng)2位{3,4,1,2}。現(xiàn)在有一個(gè)這樣的有序數(shù)組，經(jīng)過若干位移，但不知道移動(dòng)了多少。求在該數(shù)組查找某個(gè)數(shù)的效率。

解答：假設(shè)數(shù)據(jù)為{a1,a2,...,an},假設(shè)移位了k，則{a1,a2,...,ak},{ak+1,...an}分別有序。

二分查找，找出am，則am必然屬于{a1,a2,...,ak}或{ak+1,...an}，則必然有

{a1,a2,...,am}或者{am,am+1,...,an}其中一個(gè)是有序的。

a。若待查找的數(shù)是在有序的一組數(shù)中，則直接二分查找即可。

b。若待查找的數(shù)不在有序的一組，則在另一組中查找。

c。另一組無序的數(shù)組，仍然滿足{a1,...,an}的性質(zhì)。此時(shí)問題規(guī)模縮減，遞歸子問題即可。

時(shí)間復(fù)雜度logn

比如：{17,20,33,1,3,5,6,8,13,15},查找20

1、二分?jǐn)?shù)組{17,20,33,1,3}，{5,6,8,13,15}

2、第二組有序，20不在5~15，所以查找第一組數(shù){17,20,33,1,3}

3、{17,20,33,1,3}滿足有序數(shù)組移位的性質(zhì)，遞歸即可。

4、{17,20} {33,1,3}，發(fā)現(xiàn)20在有序的那組中17~20，則直接對有序數(shù)組二分查找即可。

轉(zhuǎn)載于:https://blog.51cto.com/lonelyc/1320548

總結(jié)

以上是生活随笔為你收集整理的2013-11-5 深圳尚游网络公司 - 服务器开发工程师的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。