Python コーディング面接の前に解くべき 10 個のアルゴリズム

アルゴリズムの練習がなぜ重要なのか?

私が最初に問題を解き始めたときのように世間知らずにならないでください。時々アルゴリズムをいくつか解くのは楽しいと思っていましたが、練習にあまり時間をかけず、ただ問題を解くことだけに専念していました。時々、問題を不注意に解いてしまうこともありますが、なぜそうしたのか理解できません。私自身としては、結局のところ、一日中アルゴリズムを解くというのはちょっとオタクっぽくて、実際の日常の仕事環境では実用的ではなく、長期的に見てもあまり利益をもたらさないだろうと考えていました。

「アルゴリズムを解く方法を知っていると、就職活動で競争上の優位性が得られます」

しかし、プログラマーの場合、日々の業務で複雑な問題が発生するのが現実であり、大企業は求職者の問題解決能力や細部への注意力を収集するための標準化されたプロセスを見つけなければなりません。つまり、あまり知られていない企業でも同様の評価方法を使用する傾向があるため、アルゴリズムを解く方法を知っていると、就職活動中に競争上の優位性が得られることになります。

アルゴリズムをより一貫して解き始めてすぐに、練習したり、これらの問題を解決するための最も効果的な戦略を学んだり、面接に向けて精神的に準備したりするためのリソースがたくさんあることに気付きました。 （Niuke.com、Likou、Lingkouなど）

これらのサイトでは、面接の質問を練習するだけでなく、アルゴリズムを企業別にグループ化したり、人々が面接体験の詳細な概要を共有するアクティブなブログを埋め込んだり、プレミアムプランの一部として模擬面接の質問を提供したりすることさえあります。

最初は問題に本当に苦労してもがっかりしないでください。これは完全に正常なことです。非常に経験豊富な Python プログラマーであっても、十分なトレーニングを受けなければ、多くのアルゴリズムを短期間で解決するのは難しいことに気付くでしょう。

また、面接が期待通りに進まず、アルゴリズムを解き始めたばかりの場合でも、がっかりしないでください。面接に臨む前に、いくつかの質問を準備し、毎日定期的に練習するなど、何ヶ月もかけて準備する人もいます。

トレーニング プロセスを支援するために、電話コーディング面接で何度も出てくる 10 個のアルゴリズム (主に文字列操作と配列を中心としたもの) を以下に選びました。これらの質問のレベルは比較的簡単ですが、簡単に手に入るものが多いので、良い出発点としてご利用ください。

文字列操作

数字を逆にする

# 整数を与えられたら、その逆数を返す
# 数値は負数または整数になります
 
定義ソリューション(x):
    文字列 = str(x) 
     
    文字列[0] == '-'の場合:
戻る 整数( '-' + 文字列[:0:-1])
それ以外：
戻る 整数(文字列[::-1]) 
     
 print(解(-289))
印刷(ソリューション(123)) 
 
出力:
 -132
 543

平均単語長

# 指定された文の平均単語長を返します。
 # 最初に句読点を削除することを忘れないでください。 
 
 sentence1 = 「皆さんこんにちは。私の名前はトムです。オーストラリア出身です。」  
 sentence2 = 「Python のアルゴリズムについてもっと学ぶには、一生懸命努力する必要があります!」   
 
定義ソリューション(文):
ピン用  「!?',;." :
        文 =文.replace (p, '' )
    単語 = 文.split()
 round(合計(単語数 len(単語) /単語数len(単語),2)を返す) 
     
 print(ソリューション(文1))
 print(ソリューション(文2)) 
 
出力:
 4.2
 4.08

文字列に対して簡単な計算を適用するアルゴリズムは非常に一般的なので、.replace() や .split() などのメソッドに精通しておくことが重要です。この場合、これらのメソッドは不要な文字を削除し、長さを簡単に測定して合計できる単語のリストを作成するのに役立ちました。

文字列の追加

# 文字列として表される 2 つの非負整数 num1 と num2 が与えられた場合、num1 と num2 の合計を返します。
 # 組み込みの BigInteger ライブラリを使用したり、入力を直接整数に変換したりしないでください。 
 
 
 
数値1 = '364'  
数値2 = '1836'   
 
 # アプローチ1:
定義ソリューション(num1,num2):
    評価(数値1) + 評価(数値2)
 str(eval(num1) + eval(num2))を返す
             
 print(ソリューション(num1,num2)) 
 
 #アプローチ2
 # 長さ1の文字列が与えられた場合、パラメータがUnicodeオブジェクトであれば、ord()関数は文字の表現を返します。
 # 文字列の Unicode コード ポイントを表す整数、または引数が 8 ビット文字列の場合はバイト値。 
 
定義ソリューション(num1, num2):
    n1, n2 = 0, 0
    m1、m2 = 10**(len(num1)-1)、10**(len(num2)-1) 
 
 iが num1の場合:
        n1 += (ord(i) - ord( "0" )) * m1
        m1 = m1//10 
 
 i がnum2にある場合:
        n2 += (ord(i) - ord( "0" )) * m2
        m2 = m2//10 
 
 str(n1 + n2)を返す
プリント(ソリューション(num1, num2)) 
 
出力:
 2200
 2200

どちらのアプローチも同じように優れていると思います。1 つ目は簡潔で、直感的な eval() メソッドを使用して文字列ベースの入力を動的に評価します。2 つ目は ord() 関数を巧みに使用して、文字の Unicode コード ポイントを介して両方の文字列を実際の数値として再構築します。本当に 2 つのうちどちらかを選択しなければならない場合、おそらく 2 番目のアプローチを選択します。これは、最初は複雑に思えるかもしれませんが、より高度な文字列操作アルゴリズムを必要とする問題を解決するときに便利なことが多いためです。

最初のユニークな文字を見つける

#文字列が指定されると、その中の最初の繰り返しのない文字を見つけて、そのインデックスを返します。
 #存在しない場合は-1を返します。 # 注意: 入力文字列はすべて小文字です。
 #アプローチ1
定義ソリューション:
    頻度 = {}
 iが sの場合:
        もし私が 頻度:
            頻度[i] = 1
それ以外：
            頻度[i] += 1
 iが範囲(len(s))内にある場合:
        頻度[s[i]] == 1の場合:
戻る​
-1を返す
 
 print(solution( 'アルファベット' ))
 print(solution( 'バルバドス' ))
 print(solution( 'crunchy' )) 
 
印刷( '---' ) 
 
 #アプローチ2
コレクションをインポートする
 
定義ソリューション:
    # ハッシュマップを構築:文字 そしてそれがどのくらいの頻度で現れるか
count = collections.Counter(s) # < -- 単語の出現回数を格納した辞書を返します 
                                         #カウンター({ 'l' :1、 'e' :3、 't' :1、 'c' :1、 'o' :1、 'd' :1})
    #インデックスを見つける 
 idx、chの列挙の場合:
        count [ch] == 1の場合:
 idxを返す
-1を返す
 
 print(solution( 'アルファベット' ))
 print(solution( 'バルバドス' ))
 print(solution( 'crunchy' )) 
 
出力:
 1
 2
 1
 ---  
 1
 2
 1

この場合も、2 つの解決策が提供されています。アルゴリズムにまだ慣れていない場合は、空の辞書から始まる単純なカウンターであるため、最初のアプローチの方が馴染みがあると思われます。

ただし、2 番目のアプローチを理解しておくと、長期的にはより役立ちます。これは、このアルゴリズムでは、文字カウンタを自分で構築するのではなく、単に collection.Counter を使用し、range(len(s)) を enumerate に置き換えたためです。これにより、インデックスの威力をよりエレガントに識別できるようになります。

有効な回文

# 空でない文字列 s を指定すると、最大 1 文字を削除できます。回文にできるかどうかを判定します。
 # 文字列には小文字の a ～ z のみが含まれます。
 s = 'サドカス'  
定義ソリューション:
 iが範囲(len(s))内にある場合:
        t = s[:i] + s[i+1:]
        t == t[::-1]の場合:戻り値 真実  
 
 s == s[::-1]を返す
   
解決策
 
出力:
真実 

「有効な回文」の問題はまさに古典的であり、さまざまな状況で何度も遭遇する可能性があります。この場合のタスクは、その反対の文字に一致する文字を最大 1 つ削除して天気をチェックすることです。 s = 'sadkas' の場合、関数は 'k' を除外して True を返し、回文である単語 'sadas' を取得します。

配列

モノトーン配列

# 整数の配列が与えられた場合、その配列が単調かどうかを判断します。
 A = [6, 5, 4, 4]
 B = [1,1,1,3,3,4,3,2,4,2]
 1,1,2,3,7 の
 
定義ソリューション(数値):
戻り値(すべて(nums[i] <= nums[i + 1]、 iがrange(len(nums) - 1)内にある)または  
すべて(nums[i] >= nums[i + 1]、 iが範囲 (len(nums) - 1))内) 
   
印刷(ソリューション(A))
 print(ソリューション(B))
 print(ソリューション(C)) 
 
出力:
真実 
間違い 
真実 

これはもう一つの非常に一般的な問題ですが、上記の解決策は 1 行で記述できるため、非常にエレガントです。配列が単調となるのは、単調増加または単調減少のいずれかであり、評価配列である場合のみです。上記のアルゴリズムは、反復可能オブジェクト内のすべての項目が True の場合は True を返し、それ以外の場合は False を返す all() 関数の機能を活用します。 all() 関数は、反復可能オブジェクトが空の場合にも True を返します。

ゼロを移動

# 配列numが与えられたら、ゼロをすべて配列の末尾に移動する関数を記述してください。
 # ゼロ以外の要素の相対的な順序。
配列1 = [0,1,0,3,12]
配列2 = [1,7,0,0,8,0,10,12,0,4] 
 
定義ソリューション(数値):
数値のiの場合:
        数値が0 の場合:
            数値を削除(0)
            数値を追加(0)
数値を返す
 
解(配列1)
解(配列2) 
 
出力:
 [1, 3, 12, 0, 0]
 [1、7、8、10、12、4、0、0、0、0]

.remove() メソッドと .append() メソッドは、配列を操作するときに役立ちます。この問題では、まず元の配列に属していたすべてのゼロを削除し、次にそれを同じ配列の末尾に追加するためにこれらを使用します。

空欄を埋めてください

# None値を含む配列が与えられた場合、配列内の最新のNone以外の値でNone値を埋めます
配列1 = [1,なし,2,3,なし,なし,5,なし] 
 
 defソリューション(配列):
    有効 = 0
    解像度 = []
数値のiの場合:
        もし私が なしではない:
            res.append(i)
            有効 = i
それ以外：
            res.append(有効)
戻り値
 
解(配列1)  
 
出力:
 [1、1、2、3、3、3、5、5]

どちらの場合も、ソリューションにはエッジ ケースを含める必要があります (ここでは簡潔にするために省略しています)。表面的には、これは簡単に構築できるアルゴリズムですが、for ループと if ステートメントで何を達成しようとしているのかを念頭に置き、None 値の操作に慣れる必要があります。

一致する単語と一致しない単語

# 2つの文が与えられた場合、1つの文に現れる単語の配列を返す。
 # 別の単語。共通の単語を持つ単語の配列を返します。
 sentence1 = '私たちの街であなたに会えて本当に嬉しいです'  
 sentence2 = 「この街はひどい嵐に見舞われた」   
 
定義ソリューション(文1、文2):
    set1 = set (sentence1.split())
    set2 = set (sentence2.split()) 
     
 sorted(list(set1^set2))、sorted(list(set1&set2))を返します。 
 
 print(解決策(文1、文2)) 
 
出力:
 （ [ 「私たち」 、 「ある」 、 「によって」 、 「重い」、「ヒット」、「で」 、 「会う」 、 「私たちの」 、
 「喜んだ」 、 「嵐」 、 「に」 、 「だった」 、 「あなた」 ]、
 [ '都市' 、 '本当に' ])

この問題は非常に直感的ですが、アルゴリズムでは、set()、intersection() または &、symmetric_difference() または ^ などの非常に一般的な集合演算が利用されており、ソリューションをよりエレガントにするのに非常に役立ちます。

素数配列

# n 未満の k 個の数が与えられた場合、それらの中の素数の集合を返します
# 注: タスクは、間隔内のすべての素数を出力するプログラムを作成することです。
 # 定義: 素数とは、1 とそれ自身以外に約数を持たない、1 より大きい自然数です。 
 
 35人
定義ソリューション(n):
    素数 = []
範囲(n)内のnumの場合:
        if num > 1: #すべての素数は 1 より大きい
iが範囲(2, num)内にある場合:
                if (num % i) == 0: # 剰余が 0 の場合、その数値は前の数値で割ることができることを意味します
                    壊す
それ以外：
                prime_nums.append(数値)
 prime_numsを返す
解決策
 
出力:
 [2、3、5、7、11、13、17、19、23、29、31]

もう一つの古典的な質問でこの記事を締めくくりたいと思います。素数の定義と剰余演算の両方に精通している場合は、谷(n)の範囲を調べることで簡単に解を見つけることができます(剰余演算)。

結論は

この記事では、面接でよく聞かれる 10 個の Python アルゴリズムの解決策を紹介します。有名なテクノロジー企業との面接の準備をしている場合、この記事は一般的なアルゴリズムのパターンに慣れ、より複雑な問題に進むための素晴らしい出発点となります。また、この記事で紹介されている演習 (およびその解答) は、フォース ボタンとカラー ボタンで見つかった問題の部分的な再解釈であることにも注意してください。私はこの分野の専門家からは程遠いので、私が提案する解決策はあくまでも参考的なものにすぎません。