- 相關(guān)推薦
微軟谷歌筆試題目
微軟和谷歌公司是我國的著名公司，微軟和谷歌公司的筆試題目有哪些呢?
微軟筆試題：地球上有多少個滿足這樣條件的點
站在地球上的某一點，向南走一公里，然后向東走一公里，最后向北走一公里，回到了原點。地球上有多少個滿足這樣條件的點?
北極點滿足這個條件。
距離南極點很近的一個圈上也滿足這個條件。在這個圓圈上，向南走一公里，然后向東走一公里恰好繞南極點一圈，向北走一公里回到原點。
所以地球上總共有無數(shù)點滿足這個條件。
或者
首先，在地球表面上，南北走向是沿著經(jīng)度方向，東西是沿著緯度方向。如果你一直往北走就會達到北極點，往南走就到了南極點。因此，向南走一公里，然后向東走一公里，最后向北走一公里，回到了原點，一種情況就是，出發(fā)點是在北極點，這樣向南走一公里，然后向東走任意幾公里，最后向北走一公里，最后都會回到北極點;
其次，可以這么認為如果從A點向南走一公里到達B點，那么若向東走一公里能回到B，那么最后向北走一公里，就能回到了原點A。這樣就可以先找出在南北極點附近找出繞一周只有1公里的圈，那么這個圈落在南極附近時，只要往北推1公里，此時該圈上的點都能滿足;若這個圈落在北極附近時，能不能往北推1公里我就不分析了。反正在南極附近能找到任意多個點就能回到這個問題了
微軟筆試題：利用天平砝碼，三次將140克的鹽 分成50、90克兩份?
有一個天平，2克和7克砝碼各一個。如何利用天平砝碼在三次內(nèi)將140克鹽分成50，90克兩份。
第一種方法：
第一次:先稱 7+2克鹽 (相當于有三個法碼2,7,9)
第二次:稱2+7+9=18克鹽 (相當于有2,7,9,18四個法碼)
第三次:稱7+18=x+2,得出x是23，23+9+18=50克鹽.
剩下就是90克了.
第二種方法：
1.先把140克鹽分為兩份，每份70克
2.在把70克分為兩份，每份35克
3.然后把兩個砝碼放在天平兩邊，把35克面粉分成兩份也放在兩邊(15+7=20+2)
現(xiàn)在有四堆面粉70，35，15，20，分別組合得到
70+20=90
35+15=50
微軟筆試題：正確標注水果籃
有三個水果籃。其中一個里面只有蘋果，一個里面只有橘子，另外一個既有蘋果又有橘子。每個水果籃上都有標簽，但標簽都是錯的。如何檢查某個水果籃中的一個水果，然后正確標注每個水果籃?
從標注成既有蘋果也有橘子的水果籃中選取一個進行檢查。
如果是橘子，則此籃中只有橘子;標有橘子的水果籃中只有蘋果;標有蘋果的水果籃中既有蘋果也有橘子。
如果是蘋果，則此籃中只有蘋果;標有蘋果的水果籃中只有橘子;標有橘子的水果籃中既有蘋果也有橘子。
微軟筆試題：不利用浮點運算，畫一個圓
不利用浮點運算，在屏幕上畫一個圓 (x**2 + y**2 = r**2，其中 r 為正整數(shù))。
考慮到圓的對稱性，我們只需考慮第一象限即可。
等價于找到一條連接點(0，r)到點(r，0)的一條曲線，曲線上的點距圓心(0，0)的距離最接近 r。
我們可以從點(0，r)開始，搜索右(1，r)，下(0，r-1)，右下(1，r-1)三個點到圓心的距離，選擇距圓心距離最接近 r 的點作為下一個點。反復進行這種運算，直至到達點(r，0)。
由于不能利用浮點運算，所以距離的比較只能在距離平方的基礎(chǔ)上進行。也就是比較 x**2 + y**2 和 r**2之間的差值。
微軟筆試題：將一個句子按單詞反序
將一個句子按單詞反序。比如 “hi baidu com mianshiti”，反序后變?yōu)?“mianshiti com baidu hi”。
可以分兩步走：
第一步按找字母反序，“hi baidu com mianshiti” 變?yōu)?“itihsnaim moc udiab ih”。
第二部將每個單詞中的字母反序，“itihsnaim moc udiab ih” 變成 “mianshiti com baidu hi”。
這個方法可以在原字符串上進行，只需要幾個整數(shù)變量來保持指針即可，空間復雜度低。
微軟筆試題：計算n bit的整數(shù)中有多少bit 為1
設(shè)此整數(shù)為x。
方法1：
讓此整數(shù)除以2，如果余數(shù)為1，說明最后一位是1，統(tǒng)計值加1。
將除得的結(jié)果進行上面運算，直到結(jié)果為0。
方法2：
考慮除法復雜度有些高，可以使用移位操作代替除法。
將 x 和 1 進行按位與操作(x&1)，如果結(jié)果為1，說明最后一位是1，統(tǒng)計值加1。
將x 向右一位(x >> 1)，重復上面過程，直到移位后結(jié)果為0。
方法3：
如果需要統(tǒng)計很多數(shù)字，并且內(nèi)存足夠大，可以考慮將每個數(shù)對應的bit為1的數(shù)量記錄下來，這樣每次計算只是一次查找操作。
微軟筆試題：判斷一個數(shù)是不是2的n次冪
設(shè)要判斷的數(shù)是無符號整數(shù)X。
首先判斷X是否為0，如果為0則不是2的n次冪，返回。
X和X-1進行按位與操作，如果結(jié)果是0，則說明這個數(shù)是2的n次冪;如果結(jié)果非0，則說明這個數(shù)不是2 的n次冪。
證明：
如果是2的n次冪，則此數(shù)用二進制表示時只有一位是1，其它都是0。減1后，此位變成0，后面的位變成1，所以按位與后結(jié)果是0。
如果不是2的n次冪，則此數(shù)用二進制表示時有多位是1。減1后，只有最后一個1變成0，前面的 1還是1，所以按位與后結(jié)果不是0。
微軟筆試題：三只螞蟻不相撞的概率是多少
在三角形的三個頂點上各有一只螞蟻，它們向另一個頂點運動，目標隨機(可能為另外兩個頂點的任意一個)。問三只螞蟻不相撞的概率是多少?
如果螞蟻順時針爬行記為0，逆時針爬行記為1。那么三只螞蟻的狀態(tài)可能為000，001，...，110，111中的任意一個，且為每種狀態(tài)的概率相等。在這8種狀態(tài)中，只有000和111可以避免相撞，所以螞蟻不相撞的概率是1/4。
微軟筆試題：判斷數(shù)組中是否包含重復數(shù)字
給定一個長度為N的數(shù)組，其中每個元素的取值范圍都是1到N。判斷數(shù)組中是否有重復的數(shù)字。(原數(shù)組不必保留)
給定一個長度為N的數(shù)組，其中每個元素的取值范圍都是1到N。判斷數(shù)組中是否有重復的數(shù)字。(原數(shù)組不必保留)
微軟筆試題：如何將蛋糕切成相等的兩份
一塊長方形的蛋糕，其中有一個小長方形的空洞(角度任意)。使用一把直刀，如何一刀將蛋糕切成相等的兩份?
通過長方形中心的的任意直線都能將長方形等分，所以連接兩個長方形的中心點的直線可以等分這個蛋糕。
一個沒有排序的鏈表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，請去掉重復項，并保留原順序，以上鏈表去掉重復項后為newlist={a,l,x,b,e,f,g,h,m}，請寫出一個高效算法(時間比空間更重要)。
建立一個hash_map，key為鏈表中已經(jīng)遍歷的節(jié)點內(nèi)容，開始時為空。
從頭開始遍歷鏈表中的節(jié)點：
- 如果節(jié)點內(nèi)容已經(jīng)在hash_map中存在，則刪除此節(jié)點，繼續(xù)向后遍歷;
- 如果節(jié)點內(nèi)容不在hash_map中，則保留此節(jié)點，將節(jié)點內(nèi)容添加到hash_map中，繼續(xù)向后遍歷。
微軟筆試題：小明一家5口如何過橋?
小明一家過一座橋，過橋時是黑夜，所以必須有燈�，F(xiàn)在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要8秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃后30秒就會熄滅。問：小明一家如何過橋?
小明與弟弟過去，小明回來，用4s;
媽媽與爺爺過去，弟弟回來，用15s;
小明與弟弟過去，小明回來，用4s;
小明與爸爸過去，用6s;
總共用29s。
題目的關(guān)鍵是讓速度差不多的一起走，免得過于拖累較快的一個人。
微軟筆試題：編一個程序求質(zhì)數(shù)的和
編一個程序求質(zhì)數(shù)的和，例如F(7) = 2+3+5+7+11+13+17=58。
方法1：
對于從2開始的遞增整數(shù)n進行如下操作：
用 [2，n-1] 中的數(shù)依次去除n，如果余數(shù)為0，則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說明n是質(zhì)數(shù)，對其進行加和。
空間復雜度為O(1)，時間復雜度為O(n^2)，其中n為需要找到的最大質(zhì)數(shù)值(例子對應的值為17)。
方法2：
可以維護一個質(zhì)數(shù)序列，這樣當需要判斷一個數(shù)是否是質(zhì)數(shù)時，只需判斷是否能被比自己小的質(zhì)數(shù)整除即可。
對于從2開始的遞增整數(shù)n進行如下操作：
用 [2，n-1] 中的質(zhì)數(shù)(2，3，5，7，開始時此序列為空)依次去除n，如果余數(shù)為0，則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說明n是質(zhì)數(shù)，將此質(zhì)數(shù)加入質(zhì)數(shù)序列，并對其進行加和。
空間復雜度為O(m)，時間復雜度為O(mn)，其中m為質(zhì)數(shù)的個數(shù)(例子對應的值為7)，n為需要找到的最大質(zhì)數(shù)值(例子對應的值為17)。
方法3：
也可以不用除法，而用加法。
申請一個足夠大的空間，每個bit對應一個整數(shù)，開始將所有的bit都初始化為0。
對于已知的質(zhì)數(shù)(開始時只有2)，將此質(zhì)數(shù)所有的倍數(shù)對應的bit都改為1，那么最小的值為0的bit對應的數(shù)就是一個質(zhì)數(shù)。對新獲得的質(zhì)數(shù)的倍數(shù)也進行標注。
對這樣獲得的質(zhì)數(shù)序列累加就可以獲得質(zhì)數(shù)和。
空間復雜度為O(n)，時間負責度為O(n)，其中n為需要找到的最大質(zhì)數(shù)值(例子對應的值為17)。
Google:
谷歌筆試題：判斷一個自然數(shù)是否是某個數(shù)的平方。當然不能使用開方運算。
假設(shè)待判斷的數(shù)字是 N。
方法1：
遍歷從1到N的數(shù)字，求取平方并和N進行比較。
如果平方小于N，則繼續(xù)遍歷;如果等于N，則成功退出;如果大于N，則失敗退出。
復雜度為O(n^0.5)。
方法2：
使用二分查找法，對1到N之間的數(shù)字進行判斷。
復雜度為O(log n)。
方法3：
由于
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到這些項構(gòu)成了等差數(shù)列(每項之間相差2)。
所以我們可以比較 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的關(guān)系。
如果大于0，則繼續(xù)減;如果等于0，則成功退出;如果小于 0，則失敗退出。
復雜度為O(n^0.5)。不過方法3中利用加減法替換掉了方法1中的乘法，所以速度會更快些。
谷歌筆試題：如何隨機選取1000個關(guān)鍵字
給定一個數(shù)據(jù)流，其中包含無窮盡的搜索關(guān)鍵字(比如，人們在谷歌搜索時不斷輸入的關(guān)鍵字)。如何才能從這個無窮盡的流中隨機的選取1000個關(guān)鍵字?
定義長度為1000的數(shù)組。
對于數(shù)據(jù)流中的前1000個關(guān)鍵字，顯然都要放到數(shù)組中。
對于數(shù)據(jù)流中的的第n(n>1000)個關(guān)鍵字，我們知道這個關(guān)鍵字被隨機選中的概率為 1000/n。所以我們以 1000/n 的概率用這個關(guān)鍵字去替換數(shù)組中的隨機一個。這樣就可以保證所有關(guān)鍵字都以 1000/n的概率被選中。
對于后面的關(guān)鍵字都進行這樣的處理，這樣我們就可以保證數(shù)組中總是保存著1000個隨機關(guān)鍵字。
谷歌筆試題：將下列表達式按照復雜度排序
將下列表達式按照復雜度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照復雜度從低到高為
n^Googol
2^n
n!
n^n
谷歌筆試題：在半徑為1的圓中隨機選取一點
假設(shè)圓心所在位置為坐標元點(0, 0)。
方法1.
在x軸[-1, 1]，y軸[-1, 1]的正方形內(nèi)隨機選取一點。然后判斷此點是否在圓內(nèi)(通過計算此點到圓心的距離)。如果在圓內(nèi)，則此點即為所求;如果不在，則重新選取直到找到為止。
正方形的面積為4，圓的面積為pi，所以正方形內(nèi)的隨機點在圓內(nèi)的概率是 pi / 4。
方法2.
從[0, 2*pi)中隨機選一個角度，對應于圓中的一條半徑，然后在此半徑上選一個點。但半徑上的點不能均勻選取，選取的概率應該和距圓心的長度成正比，這樣才能保證隨機點在圓內(nèi)是均勻分布的。
谷歌筆試題：給定一個未知長度的整數(shù)流，如何隨機選取一個數(shù)
方法1.
將整個整數(shù)流保存到一個數(shù)組中，然后再隨機選取。
如果整數(shù)流很長，無法保存下來，則此方法不能使用。
方法2.
如果整數(shù)流在第一個數(shù)后結(jié)束，則我們必定會選第一個數(shù)作為隨機數(shù)。
如果整數(shù)流在第二個數(shù)后結(jié)束，我們選第二個數(shù)的概率為1/2。我們以1/2的概率用第2個數(shù)替換前面選的隨機數(shù)，得到滿足條件的新隨機數(shù)。
....
如果整數(shù)流在第n個數(shù)后結(jié)束，我們選第n個數(shù)的概率為1/n。我們以1/n的概率用第n個數(shù)替換前面選的隨機數(shù)，得到滿足條件的新隨機數(shù)。
....
利用這種方法，我們只需保存一個隨機數(shù)，和迄今整數(shù)流的長度即可。所以可以處理任意長的整數(shù)流。
谷歌筆試題：設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，其中包含兩個函數(shù)，1.插入一個數(shù)字，2.獲得中數(shù)。并估計時間復雜度。
1. 使用數(shù)組存儲。
插入數(shù)字時，在O(1)時間內(nèi)將該數(shù)字插入到數(shù)組最后。
獲取中數(shù)時，在O(n)時間內(nèi)找到中數(shù)。(選數(shù)組的第一個數(shù)和其它數(shù)比較，并根據(jù)比較結(jié)果的大小分成兩組，那么我們可以確定中數(shù)在哪組中。然后對那一組按照同樣的方法進一步細分，直到找到中數(shù)。)
2. 使用排序數(shù)組存儲。
插入數(shù)字時，在O(logn)時間內(nèi)找到要插入的位置，在O(n)時間里移動元素并將新數(shù)字插入到合適的位置。
獲得中數(shù)時，在O(1)復雜度內(nèi)找到中數(shù)。
3. 使用大根堆和小根堆存儲。
使用大根堆存儲較小的一半數(shù)字，使用小根堆存儲較大的一半數(shù)字。
插入數(shù)字時，在O(logn)時間內(nèi)將該數(shù)字插入到對應的堆當中，并適當移動根節(jié)點以保持兩個堆數(shù)字相等(或相差1)。
獲取中數(shù)時，在O(1)時間內(nèi)找到中數(shù)。
給定一個固定長度的數(shù)組，將遞增整數(shù)序列寫入這個數(shù)組。當寫到數(shù)組尾部時，返回數(shù)組開始重新寫，并覆蓋先前寫過的數(shù)。
請在這個特殊數(shù)組中找出給定的整數(shù)。
假設(shè)數(shù)組為a[0, 1, ..., N-1]。
我們可以采用類似二分查找的策略。
首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。
然后判斷要找的整數(shù)是否在遞增子序列范圍內(nèi)。如果在，則使用普通的二分查找方法繼續(xù)查找;如果不在，則重復上面的查找過程，直到找到或者失敗為止。
給定兩個已排序序列，找出共同的元素。
不妨假設(shè)序列是從小到大排序的。定義兩個指針分別指向序列的開始。
如果指向的兩個元素相等，則找到一個相同的元素;如果不等，則將指向較小元素的指針向前移動。
重復執(zhí)行上面的步驟，直到有一個指針指向序列尾端。