Googleで働きたい！ 電話インタビュー（部2）

今日は、PythonおよびC / C ++でのタスクの技術的な側面と実装について説明します。これらは、Googleのエンジニアによって投げられます。 最も単純な問題から始めて、その後複雑さが増します。 並行して、インタビュー中に言及する価値があるものと、trapに陥らない場所に注意を払います。

この記事に記載されているアルゴリズムまたはコードを改善する方法を見つけた場合は、コメントを購読解除してください。 私もこの出版物から何か新しいことを学びたいです。

電話による技術面接はそれ自体が非常に独創的です。 幸運にもこの会社を経験した会社では、通常、以前のプロジェクト、複雑さ、実装、コードの最適化について話しました。 次に、試験エンジニアが私の問題解決スキルをテストすることに決めた場合、彼は、擬似コードを言い、アルゴリズムとソリューションの分析を口頭で説明するだけで解決するタスクを与えます。 Googleでは、すべてが一桁複雑になります。 少なくともこれは、タスクを検討するプロセスと発声ソリューションに加えて、Google Docにコードを入力する必要があるという事実によるものです。GoogleDocでは、電話回線の反対側にいるエンジニアが同時に見ています。

Googleドキュメントに自動的に表示されないインデントを常に監視する必要があるため、状況は悪化します。また、構文の強調表示の欠如は、独自のコードの認識に実際には役立ちません。 私のアドバイスは、Google Docsでコードを書く練習をして、周りの人や困惑したペットにあなたがそこで何をしているのかおもしろいことを通知することです。

タスクが非常に単純で、今日これらを検討する場合、回答のアルゴリズムはおよそ次のようになります。

1. タスク条件、値の範囲、外部条件（おおよそのファイルサイズなど）を調整します。
2. アルゴリズムの複雑さの分析を伴う、いくつかのソリューションアルゴリズムの説明（それらを知っていて、もし何らかの方法で問題を解決できる場合）
3. コードの実装と保守で起こりうる問題をリストします。
4. この機能を実装するのにどの言語が適しているかについて話す
   • テキスト操作-Python
   • リンク構造（リンクリスト）、ツリー、固定長オブジェクト-C / C ++
5. エンジニアがタスクに関するその他の詳細を明確にすることを望んでいるかどうかを尋ねる

おそらくこのソースのパズルから始めましょう。

改行関数を書く

それはさらに簡単になりそうですか？ Pythonでは、いくつかの方法で文字列を反転できます。

オプション-額！

def reverse （ st ） ：
＃スライスを使用する
out1 = st [ ::- 1 ]

＃文字を行頭に置く
out2 = ''
stのchの場合：
out2 = ch + out2

＃老化の増加
out3 = '' 結合 （ [ x for x in reverse （ st ） ] ）

＃まあ、トップ-文字列で文字インデックスを使用
out4 = '' 。 join （ [ st [ len （ st ） -i- 1 ] for i in range （ len （ st ） ） ] ）

戻る1

タスクは非常に簡単です。 そして、一般的に実装を1行で記述するか、またはpythonラムダ機能を使用して記述できます。

def reverse （ st ） ：st [ ::- 1 ]を 返す

reverse = lambda st：st [ ::- 1 ]

ただし、審査官が別の実装オプションを作成するように要求したり、いくつかの追加条件を課すことがあります。 たとえば、追加の変数文字列を使用して関数を記述し、そこに特定の文字を最初に追加します（最初の例のout2のオプション）。 また、審査官は、追加の変数をまったく使用せずに関数を実装するように依頼する場合があります。
実装でfireを作るほど、機能が遅くなることは明らかです。

>>> rev1 = lambda st：st [ ::- 1 ]
>>> rev2 = lambda st： '' 。 結合 （ [ x for x in reverse （ st ） ] ）
>>> rev3 = lambda st： '' 。 join （ [ st [ len （ st ） -i- 1 ] for i in range （ len （ st ） ） ] ）
>>> timeit インポートタイマーから
>>>タイマー（ "rev1（ 'test'）" 、 "from __main__ import rev1" ） 。 timeit （ ）
0.36440300941467285
>>>タイマー（ "rev2（ 'test'）" 、 "from __main__ import rev2" ） 。 timeit （ ）
0.8630490303039551
>>>タイマー（ "rev3（ 'test'）" 、 "from __main__ import rev3" ） 。 timeit （ ）
1.6259169578552246

純粋なCでの外観を見てください。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>


#define MAX_STRING_LENGTH 128

int reverse （ char str [ ] ） { / *またはchar * str * /
char * buffer ;
size_t len 、 i ;

len = strlen （ str ） ; / *行末の\ \記号* /
buffer = （ char * ） malloc （ len + 1 ） ;
if （ ！バッファ）
0を 返し ます 。 / *バッファに十分なメモリがありませんでした* /

for （ i = 0 ; i < len ; i ++ ） {
バッファ[ i ] = str [ len -i - 1 ] ;
} ;
バッファー[ len ] = '\ 0' ;
strcpy （ str 、バッファ） ;
フリー（バッファー） ;
1を 返し ます。 / *正常に実行されました* /
} ;

void main （ ） {

char str [ MAX_STRING_LENGTH ] ;
int result ;

取得（ str ） ;
result = reverse （ str ） ;
if （ ！結果）
printf （ "実行エラー：メモリが足りません" ） ;
他に
printf （ "％s \ n" 、 str ） ;
} ;

この実装についていくつかの言葉を追加する必要があります。 まず、純粋なANSI Cにはブール型はありません（C ++ではboolがあります）。 したがって、この単純なintの場所に戻ります。 次に、なんでわざわざ返すのか？ 多くの場合、審査官がプログラムエラーの可能性を予測し、それらを防止するか、そのようなエラーが発生したことをプログラムに知らせる方法に注意を払っています。 Pythonでは、言語はtry: ... except ...コンストラクトでコードをラップすることで例外を処理できtry: ... except ... 。 Cでは、コード自体を使用してエラー処理を処理する必要があります。 したがって、それを実装するには2つの方法があります。 プロトタイプを書きましょう：

int reverse （ char * str ） ; / *成功した場合は1（True）を返します* /
char * reverse （ char str [ ] 、 int * success ） ; / *へのポインタに従って、新しい行を返します
成功書き込み成功操作* /

Cでは、引数が値によって関数に渡されることを忘れないでください（参照による呼び出しではなく、値による呼び出し）。関数に渡された引数の値はスタックにコピーされます。 したがって、関数内でこれらの引数の1つ以上を変更する場合は、この変数ではなく、この変数にポインターを渡す必要があります。
ただし、指定されたバージョンのコードは最も効果的ではありません。 これには2つの理由があります。

1. メモリー（バッファー）に一時行を作成し、そこに新しく形成された行の一時値を追加します
2. 行を反転するには、その長さの半分だけを行けば十分です

より高速でリソースを節約するコードを示してみましょう。

int qreverse （ char str [ ] ） {
char ch ;
size_t len ;
int i = 0 ;

len = strlen （ str ） ;
for （ i = 0 ; i < len >> 1 ; i ++ ） {
ch = str [ i ] ;
str [ i ] = str [ len - 1 - i ] ;
str [ len - 1 -i ] = ch ;
} ;
1を 返し ます。
} ;

forループのlen>>1は、ビット単位で右にシフトすることにより、2で簡単に除算できます。 このようなトリックを行うときは、最も単純な例（境界/初期条件と数学的帰納法のチェック）で実行の正確さを確認することをお勧めします。

• 文字列の長さが0の場合：0 >> 1 = 0-forループは実行されません。
• 文字列の長さは1：1 >> 1 = 0-ループは実行されません。
• 文字列の長さは2：2 >> 1 = 1-ループは1回実行され、最初と最後の文字が再配置されます
• 奇数の場合は1、偶数の場合は2

つまり この場合、偶数および奇数の長さで機能します。 さらに、文字列の長さがゼロの場合に、重要なケースをチェックしました。

おそらく、これがこのタスクの最速かつ最短のコードになるでしょう。 なぜなら Cの3分の1の助けを借りずに、場所で2つの変数を再配置することはできません。 文字列「\ 0」の最後の文字は開始されません。 i = 0の場合、最初から2番目の文字を変更します。行の長さはフリップ中に変更されません。

N番目のフィボナッチ数を計算する

沈黙しないように、そして実際に問題を明確にするために、シリーズの最初の数字（「0 1 1」、「1 1 2」、さらには「1 2 3」）を問い合わせる必要があります。 これは説明だけでなく、タスクを完全に理解せずにコードを書くために真っ向から飛び回るプログラマーではないことを示す方法でもあります。 問題を解決するためのいくつかのアルゴリズムまたは方法を引用することは良い習慣です（愚かなブルートフォースソリューションから始めましたが、改善できるため、このアルゴリズムは非常に効率が悪いとはっきりと警告しました）。 その後、彼はbig-O （big-O）のアルゴリズムの複雑さの分析を行い、審査官がどのような実装を望んでいるかを尋ねた後、コーディングを開始しました。 効率的なアルゴリズムには複雑な実装が必要になることがよくあります。 また、電話での会話（30〜45分、まれに最大1時間）で、試験官は少なくともいくつかのタスクでスキルを調べたいと考えています。 したがって、彼はそれを決定することができます 問題を解決するさまざまな方法を知っているなら、効率の悪いアルゴリズムを書くだけで十分ですが、より速く書くことができます。

def fib_N_rec （ n ） ：
n = int （ n ） ＃nが整数でない場合
n > 1の 場合 ：
return fib_N_rec （ n- 1 ） + fib_N_rec （ n- 2 ）
その他 ：
nを返す

memo = { 0 ： 0、1 ： 1 } ＃値の辞書
def fib_rec （ n ） ：
メモのn で ない 場合 ：
memo [ n ] = fib_rec （ n- 1 ） + fib_rec （ n- 2 ）
メモを返す [ n ]


def fib_iter （ n ） ：
fib1、fib2 = 0、1
n > 0の 場合 ：
for i が 範囲 （ n- 1 ）の場合 ：
fib1、fib2 = fib2、fib1 + fib2
fib2を返す
elif n == 0 ：fib1を返します
else ： なしを 返し ます

＃最初の70要素でのみ機能します-さらに丸め誤差
phi = （ 1 + 5 ** 0.5 ） / 2
def fib （ n ） ：
return int （ round （ （ phi ** n- （ 1 -phi ） ** n ） / 5 ** 0.5 ） ）

fib_N_recは、フィボナッチ数を見つける再帰的な方法です。 再帰の終了条件（基本ケース）を設定する必要があります。これらは、それぞれ0と1のゼロと最初の位置の数値になります。 再帰的なケース（n> 1）は、前の2つの数字で関数を呼び出します。 ただし、関数の各コピーが他の2つのコピーを呼び出すため、この実装方法はひどく無駄です。 スタック上の変数関数の値を保存するためにメモリを消費し、数えたばかりの数回の呼​​び出しをプロセッサにロードして、次数O（2 ^ n）のアルゴリズムの複雑さを与えます。 したがって、値をメモディクショナリに格納すると、プロセスは何度も高速化され（fib_rec）、O（n）が与えられます。さらに、以前の値が保持されるため、関数への後続の呼び出しはより高速に値を受け取ります。

どんなタスクでも、再帰を反復に置き換えることで、再帰を完全に回避できます。 ツリーまたはグラフを通過するタスクの場合、通常、スタックにローカル変数を保存する必要があります。 しかし、単純なタスクでは、最後の2つの変数フィボナッチ数の値のみを保持できます。 繰り返しますが、初期条件に注意し、いくつかの初期条件についてサイクルの実行を確認する必要があります。 このようにして、エラーの発生を防ぎます。

ビネ式を介してフィボナッチ数の値を表現する方法があります。 このようなインタビューでは通常、そのような詳細は求められませんが、シーケンスの数学的特性について知っている場合は、必ず言及してください。 このようにして、一般教育とさまざまな角度から問題を分析する能力を示します。

この場合、Binet式は、シーケンスの70番目の要素までしか機能しません。さらに、浮動小数点演算の累積誤差のため、計算値は誤っています。

Cの場合、単一行関数を作成できます。

unsigned long fib （ unsigned long n ） { return （ n < 2 ） ？ n ： fib （ n - 1 ） + fib （ n - 2 ） ; }

欠点は依然として同じであるため、この問題が質問に含まれている場合は、そのような解決策に言及し、欠点を説明し、値の保存を一時配列に追加し、Binet式（または一般的にLucosシーケンスの式）を呼び出して反復解を検討することができます。

学校の掛け算表12x12を印刷

def multTab （ ） ：
範囲 （ 1、13）のiの場合：
print （ '\ t'。join （ [ str （ x * i ） for x in range （ 1、13 ） ] ） ））

ここにはトリックはありません。 行内の個別のループの代わりに、リストを結合する方法（リスト連結）を使用しました。各要素は文字列に変換され、タブや他の要素に接続されました

  1 2 3 4 5 6 7 8 9 10 11 12
 2 4 6 8 10 12 14 16 18 20 22 24
 3 6 9 12 15 18 21 24 27 30 33 36
 4 8 12 16 20 24 28 32 36 40 44 48
 5 10 15 20 25 30 35 40 45 50 55 60
 6 12 18 24 30 36 42 48 54 60 66 72
 7 14 21 28 35 42 49 56 63 70 77 84
 8 16 24 32 40 48 56 64 72 80 88 96
 9 18 27 36 45 54 63 72 81 90 99108
 10 20 30 40 50 60 70 80 90100110120
 11 22 33 44 55 66 77 88 99 110 121 132
 12 24 36 48 60 72 84 96108120132144 

次のように単純に関数を作成することにした場合：

範囲 （ 1、13）のiの場合：
st = ""
範囲 （ 1、13）のjの場合：
st + = '\ t％d' ％ （ i * j ）
印刷 （ st ）

数字の形成に注意する必要があります。 st += '\t%d'% i*jを括弧なしで書くと、数値iが文字列に代入され、文字列がj回乗算されます-Pythonでは、このような操作は単に文字列のコピーを作成することを意味します したがって、この場合の括弧は必須です。

#include <stdlib.h>
#include <stdio.h>

void main （ ） {
int i 、 j ;
for （ i = 1 ; i < 13 ; i ++ ） {
for （ j = 1 ; j < 13 ; j ++ ） {
printf （ "\ t％d" 、 i * j ） ;
} ;
printf （ "\ n" ） ;
} ;
} ;

Cでは、同じ考え。 デフォルトでは、printfのみが改行を挿入しません。 したがって、内部ループを通過した後、一時変数（文字列）を保存して改行を追加できます。

数値（1行に1つの数値）を含むテキストファイルを読み取り、これらの数値の合計を返します

def sumIntFromFile （ filename ） ：
合計 = 0
FIN として open （ filename、 'r' ） を使用する場合 ：
FINの回線用 。 readlines （ ） ：
試してください ：
sum + = int （ line。strip （ ） ）
を除く ：
合格する
返金 額

sumOfFile = lambda filename： sum （ [ int （ line ） in line in open （ filename、 'r' ） 。 readlines （ ） ] ）

ここでは、一般的な形式の関数と、ラムダ関数による単一行バージョンを書き留めました。 ラムダの問題は、最初にシートを作成してから、そのすべての要素を合計することです。 ファイルが大きい場合、このシートの作成に時間を浪費します。 通常の実装では、合計金額という1つの数値のみを格納します。 また、一般的な実装では、文字列を数値に変換できない場合に備えて、 try ... except...コンストラクトを設定します。 例は空の文字列です。 可能性のある例外について審査官に伝え、最終目標が何であるかに応じて、関数のさまざまな動作を記録できることを説明するのは良いことです。

Cでは、いくつかの問題が同時に発生します。 コードを見てみましょう：

#include <stdio.h>
#include <stdlib.h>

long handle_line （ char * line ） {
return atoi （行） ; //長く戻ります
}

int main （ int argc 、 char * argv [ ] ） {
intサイズ= 1024 、 pos ;
int c ;
長い合計= 0 ;
char * buffer = （ char * ） malloc （サイズ） ;

ファイル* f = fopen （ argv [ 1 ] 、 "r" ） ;
if （ f ） {
do { //ファイルからデータの読み取りを開始
pos = 0 ;
do { // 1行のみを読み取る
c = fgetc （ f ） ;
if （ c ！= EOF ） buffer [ pos ++ ] = （ char ） c ;
if （ pos > = size - 1 ） { //バッファーのサイズを増やし、\ 0文字を1か所に増やす
サイズ* = 2 ;
buffer = （ char * ） realloc （バッファ、サイズ） ;
}
} while （ c ！= EOF && c ！= '\ n' ） ;
バッファ[ pos ] = 0 ;
//バッファ内の行-関数に渡します
summ + = handle_line （ buffer ） ;
} while （ c ！= EOF ） ;
fclose （ f ） ;
}
フリー（バッファー） ;
printf （ "Summ：％ld \ n" 、 summ ） ;
0を 返し ます 。
}

ファイルからデータを1文字ずつ読み取り、バッファに書き込む必要があります。 バッファが終了しても、行の終わりがまだない場合は、2倍のボリュームのメモリを再割り当てする必要があります。 このタスクでは、固定長バッファを指定できます。 しかし、私は非常に長い行に対処する方法を示したかっただけです。 金額を保存するには、long型を使用します。 同じタイプが文字列処理関数によって返されます。
C ++では、操作の一部を標準関数にすることができます。

#include <string>
#include <iostream>
#include <fstream>
#include <cstdlib>

名前空間stdを使用します。

int main （ ） {
長い合計= 0 ;
ifstream input （ "test.dat" ） ;
文字列行;

while （ getline （ input 、 line ） ） {
// cout << line << 'n';
summ + = atoi （ line.c_str （ ） ） ;
}
cout << summ << '\ n' ;
0を 返し ます 。
}

おわりに

上記のタスクは非常に単純であり、アルゴリズムやデータ構造の詳細な知識は必要ありません。 むしろ、言語の機能とその標準構造を習得する能力に関する知識を示すように設計されています。 また、10分以内に同様の関数を作成できる必要があります。 次のパートでは、もう少し複雑な問題について説明します。

パート1
パート3