Googleで働きたい！ 電話インタビュー（パート3、栄養）

前の記事のコメントから、多くの有用な情報、コードの欠点の議論に加えて、次のインタビューでC / C ++プログラミングを避けるためにフックまたは詐欺師によって戦略的な決定を下しました。 プログラム作成の練習不足に影響します。 4年以上も彼は触れられておらず、統計計算やデータの視覚化にはpythonで十分でした。 しかし、来週は間違いなく古典的な教科書に戻ります。 仲間のTheHorseと0leGGは2番目の記事で恥をかき 、 AxisPodは最後のクローブを、古い知識に行くことが判明するという私の希望のcoに打ち込んだ。 したがって、最愛のPythonに重点を移して、可能なタスクを見てみましょう。

そして、前線からのさらなるニュース： danmiruが提起した問題と、Habré（世界はまだ小さい）でこれらの出版物について学んだリクルーターからの電話について話し合った後、私は自分が持っていた特定のタスクを出版しないという強い意志の決定をしましたインタビュー。 準備のためのトピックのリストと公的な情報源から取られた標準タスクは、私の将来の雇用主にとって大きな問題を引き起こさないことを願っています。
何度も繰り返しますが、これらのトピックに関する活発な議論をしてくれた聴衆に非常に感謝しています。 「著者を壁に置いておく」というコメントを除外し、コードを議論する提案にまっすぐ進むと、自分にとって非常に有用なことをたくさん学びました。 どうもありがとう！

さて、Pythonで実装されているデータ構造とやや複雑なアルゴリズムを見てみましょう。 ここで考慮するタスクは、 Googleが尋ねるコーディングの質問の種類の本に非常に影響を受けています。 次の仕事を上陸させる秘Secret（プログラマーからプログラマーへ） '' John Mongan、Noah Suojanen、Eric Giguere。 しかし、私は著作権を侵害しないことを望みます。なぜなら、 これらは一般的なプログラミングの問題であり、他の場所で議論されたソースを提供します。 好きなものだけを選びます。 プラス本のタスクはCで解決されますが、私はそれらをPythonで書こうとしています。

リンクリスト

驚くべきことに、このデータ構造はCで実装されています。

typedef struct IntElement {
struct IntElement * next ;
intデータ;
} IntElement ;

前回、私はしません！ Pythonにはそれ自体のポインターはありませんが、任意のオブジェクトを変数に割り当てることができます。 したがって、チェーンから次のオブジェクトを前のリンクのプロパティに割り当てることにより、オブジェクトのチェーンを作成できます。 この設計には特に実用的な価値はありませんが、練習のために...（正当化すべきことがたくさんあります）。
つまり、このような構造を構築します。

クラス要素：
def __init__ （ self 、data = None ） ：
自己 。 next = なし
自己 。 データ =データ

シーケンス自体のクラスを作成する方が正確です。 チェーンの先頭に新しい要素を追加するには、必要なリンクを見つけます：

クラス LinkedList：
def __init__ （ self 、data = None ） ：
自己 。 head = なし
データの場合：
＃シートを初期化して、すぐにデータをプッシュしたい
newElement = Element （ data ）
自己 。 head = newElement

def insertFront （ self 、data ） ：
newElement = Element （ data ）
newElement。 next = self 頭
自己 。 head = newElement

def insertBack （ self 、data ） ：
pos = self 頭
while （ pos。nextではありません ） ：pos = pos。 次の
pos。 next =要素（データ）

def find （ self 、data ） ：
next = self 頭
while （ next and data ！ = next。data ） ：next = next。 次の
次に戻る

def delete （ self 、delElement ） ：
＃シーケンスの先頭の特別な場合
delElement == selfの 場合 。 頭 ：
自己 。 head = self 頭 。 次の
＃Pythonのgcは、誰も参照していない場合にオブジェクトを削除します
＃（参照カウント）
＃または：del delElement-専門家の意見
真を 返す
pos = self 頭
while （ pos。nextではありません ） ：
＃最後のアイテムできれいに。 pos-に変更されます
＃最後から2番目
delElement == posの場合 次 ：
pos。 next = delElement。 次の
＃最後の要素を削除した場合、delElement.next == None
＃繰り返しますが、del delElementはここで必要ですか？
真を 返す
pos = pos。 次の
偽を返す

def deleteAll （ self ） ：
一方 （ 自己で はなく、 頭 。 次 ） ：
delElement = self 頭
自己 。 head = self 頭 。 次の
del delElement ＃または十分なdelElement.next =なし
自己 。 head = なし

Pythonでは、ガベージコレクターは、このオブジェクトへのリンクの数によってオブジェクトの状態を追跡します。 すべてのリンクが削除または再割り当てされた場合、オブジェクトは削除されます。 ここでは、Pythonのバージョン2.0より前では、オブジェクトが自分自身を参照している場合、潜在的な問題がありました。削除されなかったため、ループの定期的なチェックを導入しました。

クラス Untouchable：
def __init__ （ self ） ：
自己 。 私 = 自己

しかし、これはとても叙情的な余談です。 一般的に、この種の設計は非常に人工的です。 Pythonでは、このタイプのデータは通常のシート（リスト、タプル）に簡単に置き換えられます。
しかし、タスクがこの種のデータ構成を記述することである場合、 ここで行われたように、一般にラムダ関数を使用して多くのことを実装できます 。

w = sys 標準 書きます
cons = lambda el、lst： （ el、lst ）
mklist = lambda * args： reduce （ lambda lst、el：cons （ el、lst ） 、reverse （ args ） 、 None ）
car = lambda lst：lst [ 0 ] if lst else lst
cdr = lambda lst：lst [ 1 ] if lst else lst
nth = lambda n、lst：nth （ n- 1 、cdr （ lst ） ） if n > 0 else car （ lst ）
length = lambda lst、count = 0 ：length （ cdr （ lst ） 、count + 1 ） if lst else count
begin = lambda * args：args [ -1 ]
display = lambda lst：begin （ w （ "％s" ％ car （ lst ） ） 、display （ cdr （ lst ） ） ） if lst else w （ "niln" ）

機能は少し混乱していますが、機能を調べることで理解できます。
次に、この構造に与えることができるタスクを見てみましょう

オブジェクトのリンクされたシーケンスを使用してスタックを書く

前に説明した2つのクラスに、2つのメソッドpush, popを追加する必要があります

クラス Stack （ LinkedList ） ：
def push （ self 、data ） ：insertFront （ data ）

def pop （ self ） ：
tmp = self 頭 。 データ
削除（ self。head ）
tmpを返す

残念なことに、前回のようになりました-最初にテキストの20％を書くのに多くの時間を費やし、それほど時間がないことに気付き、残りの80を真っ向から終えます。しかし、これはすでに伝統です。 さあ、行こう、私の高速80％が始まった。

シーケンスの最後からm番目の要素を返します（m = 0-最後の要素）

関連するシーケンスでトピック全体を使用します。 このタスクは、Cプログラミングスキルをよくテストします。 ポインターを操作し、特にコード実行エラー（メモリ不足、不正な入力データ）を監視する必要があります。 しかし、Pythonの場合、このようなタスクで十分です。

def mFromTheEnd （ self 、m ） ：
cur = self 。 頭
curでない 場合 ： Noneを 返す ＃空のシーケンスをチェックする
範囲内の i （ m ） ：
curの場合 。 次 ：cur = cur。 次の
else ： なしを 返し ます
mcur = self 頭
while （ cur。next ） ：
mcur = mcur。 次の
cur = cur。 次の
mcurを返す

考えは、シーケンス全体に関するデータを保存し、最初のm要素に沿って実行するのではなく、可能であれば（そうでない場合はNoneを返しますが、例外を発生させることもできます）。 そして、2番目のポインターと同時にシートの最後に到達します。これは、最初のポインターからm要素だけオフセットされています。 このメソッドはメモリを節約します-メモリに2つのポインタを保持するだけです。 そして、これは最悪の場合のO（n）アルゴリズムであり、これは一方向に接続されたシーケンスで達成できる最高のアルゴリズムです。

子を持つ二重リンクシーケンスを広げる

フィクションの瀬戸際にある不活発な舌。 この例は、再帰的な方法を使用して、たとえばここで説明しました。 すべてを反復処理で実装できます。 メソッドのアイデアは次のとおりです。

空の要素（シーケンスの最後）に出会うまで、最初にシーケンスを実行します
現在の要素に子があることがわかっている場合-シーケンスの最後にそれをスローし、テールを子と結び、逆も同様です
サイクルがある場合、2つのポインターで実行することで新しいテールを見つけます（テールはサイクルチェックの2倍の速度で実行されます）-ポインターは一致します。

このデータ構造のコンストラクターは非常に単純ですが、単純にそのようなデータ構造を作成するために行われました。 このクラスは、単純に二重リンクシーケンスを作成します。 また、スタンドアロン関数は、親likeのような2つの要素を接続します。 邪悪な言語を避けるために、私は事前に言った、これは意図的に行われた。 本番では、手を引きちぎる必要があります。

＃！/ usr / bin / env python
＃-*-コーディング：utf-8-*-

インポートシステム

クラス要素：
def __init__ （ self 、data = None ） ：
自己 。 next = なし
自己 。 prev = なし
自己 。 データ =データ
自己 。 子 = なし

クラス DoubleLinkedList：
def __init__ （ self 、data = None ） ：
自己 。 head = なし
自己 。 尾 = なし
データの場合：
データ内のデータの場合：
newEl =要素（ dat ）
自己の 場合 。 尾 ： 自己 。 尾の next = newEl
newEl。 prev = self しっぽ
自己で なければ 。 頭 ： 自己 。 head = newEl
自己 。 尾 = newEl

def addChild （親、子） ：
親 子 =子
＃ループのチェックなし

def flat （ lst ） ：
cur = lst。 頭
while （ cur ） ：
curの場合 。 子 ：
一番 尾の next = cur。 子
cur。 子 prev = lst。 しっぽ
cyclecheck = lst。 しっぽ
while （ lst。tail。next および lst。tail。next。next ） ：
cyclecheck = cyclecheck。 次の
一番 尾 = lst。 尾の 次へ 。 次の
＃本には、このアルゴリズムのエラーが含まれています。 最初のステップは取られません
＃および初期条件は同じです。 常に実行される場合
cyclecheck == lstの場合 。 尾 ：
印刷 （ 「データ構造のループ」 ）
sys 終了 （ ）
場合 尾の 次 ：lst。 尾 = lst。 尾の 次の
cur = cur。 次の

def main （ ） ：
st1 = DoubleLinkedList （ 範囲 （ 6 ） ）
st2 = DoubleLinkedList （ 範囲 （ 4 ） ）
st3 = DoubleLinkedList （ 範囲 （ 3 ） ）
addChild （ st1。head、st2。head ）
addChild （ st1。tail、st3。head ）
＃addChild（st2.tail、st3.head）-ループ。

フラット（ st1 ）

cur = st1。 頭
while （ cur ） ：
印刷 （ cur。 データ ）
cur = cur。 次の

__name__ == '__main__'の場合 ：
メイン（ ）

実際には、データ構造を復元できます（deFlatten）。 なぜなら 子に関する情報を削除しなかったので、順番に実行でき、子へのリンクが見つかったら、テールと子、およびテールを持つ子との接続を削除します。 子の関数を再帰的に呼び出します。
パーティション分割を繰り返し行うことができます。 ただし、最後から順番に実行する方が適切です。 子が見つかったら、前の要素から切り取り（これは新しいテールになります）、新しいテールから子へのリンクを削除します。 さらに順を追って。 構造内にサイクルがなかった場合、すべてが正常に機能します（スペシャリスト-アルゴリズム論者にコメントがありますか？） ただし、フラット構造を作成するときにこの条件を確認しました。

二分木の反復走査

トピックのリストにある質問の1つ（それらを公開することを許可されたのは良いことです）は、バイナリツリートラバースのタイプです。 覚えていない場合は、予約注文（KLP）、注文（LKP）、および注文後（KLP）についてお話します。 これは、ルート（K）、左（L）ブランチ、右（P）ブランチをどの順序で見るかを示しています。 この質問は非常に一般的であり、すでにこことstackoverflowで書かれています。

＃！/ usr / bin / env python
＃-*-コーディング：utf-8-*-

クラス N：
def __init__ （ self 、data、left = None 、right = None ） ：
自己 。 データ =データ
自己 。 左 =左
自己 。 右 =右

def __unicode__ （ self ） ：
'％s' ％ selfを 返します。 データ
＃ルート値を推測する素晴らしい方法

def inorder （ t ） ：
tの場合 ：
x for inorder （ t。left ） ：
収量 x
収量 t データ
x in inorder （ t。right ）の場合 ：
収量 x

def iterate_preorder （ root ） ：
スタック= [ ]
スタック。 追加 （ root ）
スタック中：
cur =スタック。 ポップ （ ）
利回り 。 データ
curの場合 。 右 ：スタック。 追加 （ cur。right ）
curの場合 。 左 ：スタック。 追加 （ cur。left ）

def iterate_inorder （ root ） ：
スタック= [ ]
cur =ルート
スタックまたは curの場合：
curの場合 ：
スタック。 追加 （ cur ）
cur = cur。 左
その他 ：
スタックの場合 ：
cur =スタック。 ポップ （ ）
利回り 。 データ
cur = cur。 そうだね


def main （ ） ：
bt = N （ 4 、N （ 2 、N （ 1 ） 、N （ 3 ） ） 、N （ 6 、N （ 5 ） 、N （ 7 、 None 、N （ 8 ） ） ） ）
印刷 （ リスト （ iterate_preorder （ bt ） ） ）
print （ リスト （ iterate_inorder （ bt ） ） ）
0を 返す

__name__ == '__main__'の場合 ：
メイン（ ）

ツリーを反復処理するには、訪問する必要があるブランチに関する情報を保存する必要があります。 スタックは事前注文クロールに適しています-これはディープクロールです。 反復的な順序のバイパスに長く座らなければなりませんでした。 しかし、前回と同じ考え。 ツリーの左端の要素を取得するために、空のシートに到達するまで下に行きます。 スタックから前の値を取り出します。これはシートそのものであり、その値を表示して右に見えます。 そこに何もない場合、スタックから既に適切な要素を持っている親を取得します。 などなど。 クロールは、左端、ルート、右端の要素の順序です。

文字列内の重複していない最初の文字を見つける

Pythonでは、辞書とセットはハッシュテーブルを使用して値/キーを保存および検索します。 以下に示すアルゴリズムは、新しい文字を辞書に追加するのにさらに時間がかかるため、少なくともO（n）（行全体に沿って渡す）になります。

＃！/ usr / bin / env python
＃-*-コーディング：utf-8-*-

def nonRepeated （ st ） ：
繰り返し= dict （ ）
stのlの場合：
l が繰り返される場合 ：繰り返し[ l ] = 0
その他 ：繰り返し[ l ] = 1
stのlの場合：
繰り返される場合 [ l ] ：lを返します

def main （ ） ：
print （ nonRepeated （ 'test' ） ）
0を 返す

__name__ == '__main__'の場合 ：
メイン（ ）

速度を上げる方法はまだありますか？ ここでは、すべてが通常のシーケンスで行われました。 辞書やセットのように、文字がシーケンス内にあるかどうかのチェックは一定時間O（1）で行われません。 ですから、辞書の使用はわずかに優れていると思います。

さて、今日の最後：

文の語順を反転する

reverseOrder = lambda str ： '' 。 join （ （ x [ ::- 1 ] for x in str [ ::- 1 ] 。split （ ） ） ）
rev_order = lambda s： '' 。 join （ s。split （ ） [ ::- 1 ] ） ＃信頼できるprintfの短いバージョン

2番目の方法は短いだけでなく、より高速です。

>>> timeit インポートタイマーから
>>> Timer （ "reverseOrder（ '1 2 3 45'）" 、 "from __main__ import reverseOrder" ） 。 timeit （ ）
3.4366888999938965
>>>タイマー（ "rev_order（ '1 2 3 45'）" 、 "from __main__ import rev_order" ） 。 timeit （ ）
0.9511728286743164

私のインタビューで問題はありません。 私はそれらを公開しないようにとても頼まれました。 ごめんなさい
すべて、蹴り始めましょう！

パート1
パート2