Google Python挑戰賽：不服，就來！

轉載來自：量化投資與機器學習

這是一個來自谷歌的秘密招聘挑戰（Google FooBar Invitation)?），如果你收到了谷歌的FooBar邀請，你應該感到高興。谷歌的許多開發人員都是通過FooBar而被聘用的。

獲得Google Foobar邀請也是一件神秘的事情，不是每個人都能接受這個挑戰。沒有人確切知道 Google Foobar 邀請資格的標準。

當你收到邀請時，它上面寫著：

“You’re speaking our language. Up for a challenge?”

接受邀請后，你會看到一個看起來很酷的IDE，你可以在請求后打開右側的代碼編輯器并導航到解決方案文件solution.py。

交互界面模仿了 UNIX Shell：你可以通過命令來請求（ request ）一個新的 Challenge、 提交（ submit ）代碼、驗證（ verify ）代碼正確與否。

一旦你有了一個潛在的解決方案你可以驗證它，你可通過測試來看看你的最終解決方案能否被接受。

整個挑戰有3個level，level 1有1道題目，level 2有2道，level 3有3道。

level 1和level 2的題目十分簡單，每個題目會給24–48個小時的做答時間，考的主要是一些基礎的編程概念；

level 3會考一些簡單的算法，每個題目會給96個小時的做答時間；

level 4的題目就比較難了，會考一些不常見的算法。

讓我們看看今天的這道題目吧（重點標記出來了）：

Commander Lambda has had an incredibly successful week: she completed the first test run of her LAMBCHOP doomsday device, she captured six key members of the Bunny Rebellion, and she beat her personal high score in Tetris. To celebrate, she's ordered cake for everyone - even the lowliest of minions! But competition among minions is fierce, and if you don't cut?exactly equal slices of cake for everyone, you'll get in big trouble.

The cake is round, and decorated with M&Ms in a circle around the edge. But while the rest of the cake is uniform, the M&Ms are not: there are multiple colors, and every minion must get exactly the same sequence of M&Ms. Commander Lambda hates waste and will not tolerate any leftovers, so you also want to make sure you can serve the entire cake.

To help you best cut the cake, you have turned the sequence of colors of the M&Ms on the cake into a string: each possible letter (between a and z) corresponds to a unique color, and the sequence of M&Ms is given clockwise (the decorations form a circle around the outer edge of the cake).

Write a function called solution(s) that, given a non-empty string less than 200 characters in length describing the sequence of M&Ms, returns the maximum number of equal parts that can be cut from the cake without leaving any leftovers.

我們來把問題進行可視化：

再看看每個字母的劃分：

最后是重復模式的劃分：

我們將在后面討論邊界情況，但至少現在我們或多或少對這個問題有了一個想法，讓我們開始進行編程，我們需要構造一個函數，設置一個參數，找到一個模式，展示重復出現的模式次數，這是我們最初的解決方案：

def?solution(s):

sub?=?s[0:len(set(s))]

return(s.count(sub))

print(solution('abcabcabcabc'))

>>?4

print(solution('abccbaabccba'))

>>?2

不幸的是，這個方法沒有通過所有的測試，所以我們需要更創建一些額外的邊界情況，以找到剩余的解決方案。

現在，我們首先需要找出模式中字符的數量是奇數還是偶數：

對于偶數個切片沒有落單的，但是對于不均勻數量的切片，我們可以有一些額外的切片。但請記住，這個問題要求的是等分的最大數量（the maximum number of equal parts），讓我們使用取模運算（Modulus Operation）就可以很容易的識別奇數/偶數：

def?solution(s):

if?(len(s)?%?2?!=?0):

print('Odd')

else:

print('Even')

solution('abcabcN')

>>?ODD

solution('abcabc')

>>?EVEN

在這里給大家科普一下取模運算（mod）和取余運算（rem）兩個概念，他們的主要區別在于對負整數進行除法運算時操作不同。

取模和取余的區別

取余運算 在計算商值時 商值向0方向舍入；靠近0原則

取模運算 在計算商值時 商值向負無窮方向舍入；盡可能讓商值小的原則(不超多商值的最大值)

計算步驟

假設有整數a和b，那么取模/取余運算可以分為兩步運算：

1、求整數商：c = a/b;

2、計算模/余數：r = a - (c*b);

3、總計算模/余數：a mod b = a - b[a/b] ? ([a/b]表示整數商)

回到主題。列表上的下一個項目是找到完整的模式，這可以通過查找模式重復的索引來完成。

def?solution(s):

print('INPUT:'?+?s)

i?=?(s+s).find(s,1,?-1)

sub?=?s[:i]

print('Substring:',?sub)

solution('abccbaabccba')

>>?INPUT:abccbaabccba

>>?Substring:?abccba

solution('xyztxyztxyzt')

>>?INPUT:xyztxyztxyzt

>>?Substring:?xyzt

這里唯一奇怪的是find()方法上的-1索引，它將用于捕捉模式不是偶數的情況，考慮以下兩種情況：

def?solution(s):

print('INPUT:'?+?s)

i?=?(s+s).find(s,1,?-1)

sub?=?s[:i]

print("i:",?i)

print('Substring_1:',?sub)

s2?=?s

s2?=?s2[:-1]

sub2?=?s2[0:len(set(s2))]

print('Substring_2:'?+??sub2)

solution('wewewe')

>>?INPUT:wewewe

>>?i:?2

>>?Substring_1:?we

>>?Substring_2:we

solution('weweweT')

>>?INPUT:weweweT

>>?i:?-1

>>?Substring_1:?wewewe

>>?Substring_2:we

給大家科普一下find()方法：

find()方法從字符串中找出某個子字符串第一個匹配項的索引位置，該方法與index()方法一樣，只不過如果子字符串不在字符串中不會報異常，而是返回-1。

S.find(sub[,start=0[,end=len(S)]])

sub -- 指定檢索的子字符串

S -- 父字符串

start -- 可選參數，開始索引，默認為0。（可單獨指定）

end -- 可選參數，結束索引，默認為字符串的長度。（不能單獨指定）

返回子字符串第一個匹配項出現在字符串中的索引位置，如果沒有匹配項則返回-1。例如：

quote?=?'Let?it?be,?let?it?be,?let?it?be'

result?=?quote.find('let?it')

print("Substring?'let?it':",?result)

Substring?'let?it':?11

回到主題。另一個需要考慮的邊界情況是單字符重復模式，像這樣：

加一行代碼就行：

if?len(set(s))?==?1:

看看最終的一個解決方案：

def?solution(s):

print('-------')

print('INPUT:'?+?s)

i?=?(s+s).find(s,?1,?-1)

print?(i)

if?(len(s)?%?2?!=?0):

print('ODD')

if(len(set(s))?==?1):

print("CASE:?ODD?SINGLE?CHARACTER")

print('pattern:'?+??(s[0]))

print('Divisions:'?+?str(len(s)))

return

else:

s?=?s[:-1]

if?len(set(s))?==?1:

print('pattern:'?+??(s[0]))

print("CASE:?ODD?SINGLE?CHARACTER?EXTRA?CHARACTER")

print('Divisions:'?+?str(len(s)))

return

elif?i?==?-1:

sub?=?s[0:len(set(s))]

print('pattern:'?+??sub)

print('Divisions:'?+?str(s.count(sub)))

print("CASE:?MULTI?CHARACTER?EXTRA?CHARACTER")

return

else:

sub?=?s[:i]

print('pattern:'?+??sub)

print('Divisions:'?+?str(s.count(sub)))

print("CASE:?ODD?MULTI?CHARACTER")

return

else:

print('EVEN')

if?len(set(s))?==?1:

print('pattern:'?+??(s[0]))

print('Divisions:'?+?str(len(s)))

print("CASE:?EVEN?SINGLE?CHARACTER")

return

else:

sub?=?s[:i]

print('pattern:'?+??sub)

print('Divisions:'?+?str(s.count(sub)))

print("CASE:?EVEN?MULTI?CHARACTER")

return

有6個測試案例：

solution('a')

solution('aa')

solution('abcabc')

solution('abcabcabc')

solution('aaT')

solution('ababT')

對應的輸出：

------

INPUT:a

-1

ODD

CASE:?ODD?SINGLE?CHARACTER

pattern:a

Divisions:1

-------

INPUT:aa

1

EVEN

pattern:a

Divisions:2

CASE:?EVEN?SINGLE?CHARACTER

-------

INPUT:abcabc

3

EVEN

pattern:abc

Divisions:2

CASE:?EVEN?MULTI?CHARACTER

-------

INPUT:abcabcabc

3

ODD

pattern:abc

Divisions:2

CASE:?ODD?MULTI?CHARACTER

-------

INPUT:aaT

-1

ODD

pattern:a

CASE:?ODD?SINGLE?CHARACTER?EXTRA?CHARACTER

Divisions:2

-------

INPUT:ababT

-1

ODD

pattern:ab

Divisions:2

CASE:?MULTI?CHARACTER?EXTRA?CHARACTER

一旦我們完成一個更小、更簡潔的腳本，并且通過了所有的測試，你的頁面會出現一只兔子，然后你就可以進行下一挑戰了！

有些人可能已經注意到，第4個casebabcabc有問題，這個留給讀者們發揮你的聰明才智！

你們可以看看Stack Overflow上的回答：

https://stackoverflow.com/questions/29481088/how-can-i-tell-if-a-string-repeats-itself-in-python

在你完成所有的題目后，你會填寫一張信息表，一兩天后，你會收到谷歌的電話或郵件，并得到面試邀請：

接下來 Google recruiter 會問你個人傾向于什么崗位，可選 SRE 或者 SWE。然后會收到了 Google recruiter 的電話，大概內容是：

了解個人情況

一些關于計算機基礎知識的題目

即便是Google FooBar通過了，還要有兩輪電話面試……

電話聊完之后，recruiter 還會發送了一個 self-rating form ，讓你自助式地評估下自己的技術水準，形式如下：

與此同時，recruiter 還發送了一份長達 6 頁的非常詳盡的求職面試指南文檔《Guide to Getting an SRE job with Google》，內容包含了崗位需求、面試要求、考查題目范圍、樣例面試題目等等。

兩輪電話面試后，如果通過，你就可以去 Sydney office onsite 了。

說下具體的 onsite 面試流程吧。Google 的 onsite 面試共有 5 輪，每輪 45 分鐘，一般會從上午 10 點開始，上午 2–3 輪，然后 recruiter 會帶你去 Google 那天下聞名的食堂吃個午飯，讓你休整下放松下心情，飯后回到會議室再面 2–3 輪。

SRE 崗 5 輪面試大致考查如下方向：

Coding & Algorithm

System Design

Troubleshooting

Networking

Linux/UNIX system

其中，Coding & Algorithm 方面，編程語言不限，選擇自己擅長的就好（推薦用 Python，寫起來比 C++/Java 要快很多）；Linux/UNIX system 方面，文件系統、內存、系統調用、進程調度方面都有可能考，而且幾乎沒有辦法準備，也沒有辦法刷題，靠的是平時的積累；SRE 崗還會考一些 Shell Script 方面的細節問題；Networking 方面考的不多，需要你對 Web Application 的常見網絡架構有一個基礎的理解，經典的題目有“從瀏覽器輸入一個 URL 到頁面渲染完成，其中發生了什么？”、“DNS 的基本原理”等等；Troubleshooting考查的是現實工作場景中如何 debug 的能力；System design 會考查在 45 分鐘之內從無到有寫一個具有良好 API 接口、滿足基礎性能要求的一個 library/class 層面上的小程序。

總結一下

1、1 輪 foo.bar，2.5 輪電話面試，5 輪 onsite 面試，持續 4 個月，總體耗時 3–4 周。

2、整個應聘的流程，至少接觸了 4 位 recruiter，8 個面試官，2 個第三方服務者，算上人力的時間成本，加上 onsite 的機票酒店餐飲簽證成本，最后再考慮下 onsite 的通過率，估計 Google 要招聘到一個合格的員工，成本至少是在十萬人民幣級別的。可見頂尖的人才是相當昂貴的，這還僅僅只是招聘成本。

3、就現在的 IT 技術招聘體制而言，大多數公司采用的無非就是在一定的時間和資源限制下，解決一些面試官心中有明確標準答案的 puzzles——但是這種選拔真得能很好的反應一個面試者在實際工作中的能力么？值得探討···

4、你要知道，改善隨著時間的推移，你的領域知識（語言和問題本身）和你的回答會變得更好。如果你不能在一開始就不能很好地理解題目，也不能快速地想出一個很好的解決方案，不要氣餒，總有量變到質變的那一刻，你會感受到的！

以上，便是今天的內容，希望大家喜歡，歡迎「轉發」或者點擊「在看」支持！

“掃一掃，關注我吧”

點的“在看”，否則就看不到我了555

Python 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。