C++プログラミングの質問 面接の質問

元の投稿アドレス 100億の質問辞書からC++のプログラミング問題の面接質問を紹介 著者 100億の質問辞書

1. リンクリストの最後尾のノードを探す

2. リンクリストを反転させる

3. 親へのポインタを持つノードを持つ二分木の最近接共通祖先を求める。

4. 配列が与えられたとき、その配列を構成する集合のすべての部分集合を表示するにはどうすればよいですか。

5. 文字列は2つあり、1つはテキスト、もう1つはコマンドで、コマンドは4種類あります。

 '+': テキストの位置を1つ進める

 '-': 本文中の1つ後ろの場所

 a': 現在の位置に文字を挿入します。文字はコマンドの最後の桁によって決定されます。
'd': 現在の文字を削除する

 関数 Process(string& text, string& command, string& result)を実装しています。
コーディングの質問、一般的なポイント。

1. コマンドを走査して文字があるものを確認し、サイズ要件を満たす一時配列を作成し、テキストをコピーする
2. 挿入と削除の両方の複雑さがO(N)であることに注意して、一時的な配列に対して演算を行う

6. LRUキャッシュの実装

 データ構造

 新しいキャッシュを挿入するためのアルゴリズム。

1. 見つかった場合は、splice 関数を使用して、直前にアクセスされた CacheEntry をキューの先頭に移動します。

マルチスレッドについてですが、一般にリーダライタロックは、リーダもLRUキャッシュを変更するため、うまくいきません。一つの解決策は、各スレッドが独自のキャッシュを持つようにすることです。

7. 2つのソートされた配列の交点を求めよ

8. 8. バイナリツリーに2つのポインタを追加し（ツリーは完全でなくてもよい）、ツリー全体をトラバースし、同じレベルのノードをこの2つのポインタで接続する。

9. 与えられた値で配列を分割し、その値は必ずしも配列に現れないことに注意する。

10. キューを配列で実装するために、以下のいくつかを考えてみましょう。

a)   固定サイズの導入

b)  可変サイズの実装   サイズが足りなくなるたびに、より大きな配列を作成し、元のデータをコピーする

c)  リンクリストの実装と比較した場合のメリットとデメリットを教えてください。 定数O(1)の演算が保証されるが、メモリが無駄になり、連続性がない

d)   スレッドセーフの扱い方

1. キューが変更された場合に備えてロッカーを使用する
2. ロックフリーのコード

11. シャッフルアルゴリズム

 i = 0 から n-1 まで。

iとn-1の間の乱数jを生成し、v[i]とv[j]を入れ替える。

12. [Microsoft】スタック上の要素をソートするには、pop()、top()、push()、isEmpty()、isFull()の各メソッドを使用することができます。）

13. [Microsoft]はM*N行の行列を持ち、(i, j)番目の要素が0の場合、i行とj列の両方を0に設定し、できるだけ余分なスペースを使わないように注意すること

以下のステップに分解してください。

1. M行目、N列目をスキャンして、(M,N)をゼロに設定する必要があるかどうかを確認します。
2. 各行と列をスキャンし、対応する列と行の結果をM行とN列に記録する
3. M行とN列をスキャンし、対応する列と行をゼロとして記録する。
4. 処理(M,N)

14. [マイクロソフト】2次元空間の第1象限にはたくさんの点がありますが、一番外側の点はどのように見つけるのでしょうか？

グラハムスキャンアルゴリズム。

1. yが最も小さい始点p0を選ぶ。
2. 他のすべての点をp0を基準とした極角でp1,p2,...pN-1としてソートする。
3. p0, p1, p2 をスタックに積む。
4. 残りのすべてのポイントについて

a)   Pxはスタックの一番上の次の点、Pyはスタックの一番上の点、現在の点はPiです

b)   Py->Piの場合、Px->Pyを右側に相対化すると

i.   ポップスタック

ii.   Piをスタックにプッシュ

アルゴリズムの複雑さはO(NlogN) (2段階目のソート)

15. [Google] は、"abc", "abcdef", "abcd" のような文字列集合の最長の共通接頭語を返し、次に "abc" を返します。

16. [Microsft]は、平面の第1象限における風景の輪郭、すなわち(x,y)座標のいくつかの列、x=0,1,...,Nを与える。
と、Y軸上の光源座標(0,H)を指定します。このN+1時方向のどれが照らされ、どれが影になるかを問う。（フォークの掛け算）

光源が(x,y)に当てる角度を1つずつ計算し、左の角度と比較することで陰になるかどうかがわかる、複雑さO(N)

17. [Microsoft] リンクリストでは、各ノードは通常の次のポインタに加えて余分なポインタを持っており、このポインタはチェーン内の任意のノードを指すことができ、異なる余分なポインタは同じノードを指すことができ、余分なポインタはまた、可能性があります
この構造体をコピーする方法を教えてください。

18. [Microsoft】クロスパズルを解くときに、条件を満たすすべての単語を素早く取得できるように辞書を整理する方法（例：「◎」「◎」「◎」「◎」「◎」）。
oが2文字目、Hが5文字目のすべての単語)。でも、これは頭脳戦なので、コードを書く必要はありません。

 単語の長さで複数のコンテナを構成する

同じ長さの単語の集合に対して、(2,o), (5, H) から単語 (id) に対応する複数のインデックスを構築し、それぞれのコレクションを順序付けしてマージを高速化する。

19. [Google] バイナリツリーとハッシュテーブルのイテレータを設計する方法

バイナリーツリーイテレータ。

中順位の探索を想定し、探索状態（親ノードスタック）がイテレータに格納される。

ハッシュテーブルイテレータ。

ハッシュテーブルのデータ構造にもよるが、通常は配列順またはバケット順で反復処理するのが素直である。

20. [Google] スタックに似ているが、O(1)時間でmin()を返すことができるクラスを設計してください。

現在の最小値のみを保持するスタックをstackに追加し、pushするときに、現在の値がminStackスタックの先頭よりも小さければ、minStackにもpushし、popするときに、minStackスタックの先頭が現在のpop要素と同じサイズであれば、minStackにもpopします。

21. [Google】2つの二分木を比較して同一かどうかを確認する

再帰的比較 if (tree1->value == tree2->value) && is_equal(tree1->left, tree2->left) && is_equal(tree1->right, tree2- >right)であること。

22. [Google] 整数配列の最大値と最小値の両方を求め、比較の回数をできる限り最適化する方法

 2つの数a,bを考え、まずaとbを比較し、大きい方を現在の最大値と比較し、小さい方を現在の最小値と比較します。この2つの数値は合計3回比較する必要がある。

23. [Google] 円形の順序付き配列の中の数字を見つける

 24. [Google] 配列と目標値が与えられたとき、配列内の2つの数値の合計が目標値であるかどうかをチェックしなさい。

 2つのアプローチ :

1. 最初に配列をソートし、その後両端からスキャンします。
2. ハッシュテーブルを構築し、配列をスキャンしてそれを見つける。ちょうど1つの数字が対象の半分である場合を処理するように注意する。

25. [Google] テキストを与え、次にいくつかのキーワードとそれらが現れる場所を与える、例として
この 1, 16, 55....
です。5, 33, 77...
与えられたキーワードを含む最短の段落が必要です。

 大まかなアルゴリズム：すべての単語が現れるまで、位置ごとに後方を調べ、その後、再び左の位置を絞り込んでみる。これをより短い間隔を見つけるまで行う。

Find_min_window のプログラムでは、逆インデックスを扱う必要があるので、後で参照してください。

26. [Google】木が与えられたとき、木には特徴がない、つまり、複数の子を持つことができ、親と左右の子も
大きさの関係はありません。しかし、各ノードの値は等しくない。(12, 24)のようないくつかの値があるとき、ルートノードから値12と24を持つノードまでの部分木を求めよ。

27. [Google】配列とsh値が与えられたとき、配列の全要素を右にシフトする（数値のシフト）関数を設計しなさい。
配列が円に見える)。

プログラミングパール参照、まず[a,c]を反転し、次に[a,b], [b,c]を反転する。

28. [Microsoft】配列から重複する要素を取り除く

を省略した。

29. [Microsoft] 数値の文字列を次のルールで変換します。
(>=1 回出現する整数)
(2回出現する整数)
...
(出現回数が >=n 回の整数）
で、文字を元の順番のままにしておく
例：12223314->12342312

を省略した。

30. [Microsoft] 式中の括弧が合法かどうかを確認します。括弧は {, [, (, ), ], } を含みます。

スタックの簡単な応用例

31. [マイクロソフト】スタックでキューを効率的にエミュレートする方法。

2つのスタック、s1 と s2 を使用します。

プッシュするときは、s1 にプッシュする

Popの場合、s2が空でなければs2からpopし、s2が空であればs1の全要素をs2にpopし、その後s2からpopします。

振り分けの複雑さはO(1)

32. [Microsoft] 2つの整数の範囲にあるすべての素数を表示する 例: (12, 15) ->13

1. ある数字が素数かどうか個別に検証する

2.ふるい分け法

33. [Google] ヒストグラムの内側の最大矩形を求めよ

 TODO

34. [Google] NxN行順序行列で数を求める

2つの方法、1、隅から探す、2、Divide and Conquer

行と列に順序がある2次元配列の中で、0より大きい/小さい要素はいくつあるかという問題です。

35. [Google] MxN の行列をランクに転置し、必要な空間複雑度は O(1) です。環状群、群論における群を参照。
ジェネレータ

学ぶために

36.インプレース・パーフェクト・シャッフル

学ぶために

37. ある行列Aがある。この行列のA(i,j)のうち、行と列がすべて0であるものをすべて求めよ。

順番にスキャンする？わずかです。

38. 各文字が可変長のバイトを占有する可変長文字システムがある。各文字は
文字 文字列は、これらの可変長の文字から構成されます。文字列
この文字列を反転させることを要求する。余分なスペースは少ないほどよい。

まず文字列全体を反転させ、次に文字ごとに反転させます。

39. n枚のトランプがあり、その中からランダムに数枚が選ばれる。選ばれたトランプの点数が1点以上となるように、選ばれたトランプをすべて求めよ。
再帰は不要で、コードの行数は少ないほどよい。

TODO 再帰を使わないにはどうしたらいいですか？

40. [Google]は1Gのメモリと40億の整数を持ち、その整数の中にない数を出力する、メモリが10MBしかない場合はどうするか？

1. 1Gのメモリには1024*1024*1024*8ビットがあり、ビットをスキャンして記憶します。

2. メモリが足りない場合、10*1024*1024*8の数字を順番に処理するには、4*1024/10/8を50回ほどスキャンする必要があります

41. [Google] N個のソートされた配列をマージする

42. [Google] サイズNの配列が与えられたとき、サイズKの部分集合をすべて出力しなさい (K<=N)

 TODO

43. [マイクロソフト】bstと2つの数値がわかっている状態で、この範囲にあるノードの数を求めよ。再帰的と非再帰的

コレクションを引数とした中位トラバーサルで十分である

44. [Microsoft] bstとある数を知っていて、次に大きい数を求める、O(logn)時間

 コード

45. N*N個の正方形の中に黒と白があり、4辺がすべて黒である最大の部分正方形を求めよ。

 学ぶために

46. 平面上に点の集合があり、最も多くの点を通る直線を求めよ

2つの点が作る直線の方程式x+By+C=0を計算し、最も多く出現する方程式を求めよ。

47. itoaの実装

48. 2次元の行列があるとき、螺旋状に印刷しなさい。

49. [Google] ある文字列の x をすべてコピーし、z をすべて削除、それ以外は変更しない。

が省略されました。

50. [Google] memcpy(void *src, int size, void *dest) の実装です。
引数の正当性、src,destが等しいかどうか、オーバーラップしたときにエラーが発生するかどうかを判断する

 memcpyとmemmoveの違いに注意

51. [Google] サイズKのランダムな部分集合が与えられたときの、サイズNの配列

シャッフルを行い、最初のKを選ぶ（だからシャッフルはK番目に行くだけである）

52. [マイクロソフト】4つの点が長方形を形成しているかどうかを判定する

 TODO

53. 実装 char* strtok(char* str, const char* delimeter)

が省略されました。静的変数を使用する必要があるはずです

54. アメリカのコインは1、5、10、25と設計されており、任意のおつりが出た場合、必要最小限のコインの枚数を貪欲アルゴリズムを用いて計算することができる。コインのセットが貪欲アルゴリズムで使用可能かどうかを判断するにはどうすればよいでしょうか。

学ぶために

コインを探すためのDPプログラム。

55. 5枚のカードがあるとき、2つのペアがあるかどうかを判断する関数を書きなさい。

わずかに

56. BSTのノードを削除する

57. [マイクロソフト]は、アドレス/a/b/...を与えます。/c/. /d.txtを与え、それを正規化するように指示します。

 58. [マイクロソフト】BSTと値が与えられたとき、その合計がこの値に等しいすべてのPathを求めよ。

 59. [Microsoft】ツリーをレイヤーごとに印刷する

 わずかに

60. [Google] 5つの非常に大きな配列の交点（時間、空間、I/Oを考慮した場合）

 わずかに

61. [Google] 並べ替えられた2つの配列から、和が最小となるM組を求めよ。例：A={1, 2, 4, 5, 6}, B={3, 5, 7, 9｝
m=3 ならば結果は (1, 3), (2, 3), (1, 5) です。

 この構造は行順行列を形成しており、問題は行順行列のk番目の要素を見つけることと類似している。

 結論

n×m（n ≦ m）行列に対して、各行、各列が増加する場合、k番目の最大数はO（nlog2m/n）で求めることができる。論文のタイトルは「"」。 一般化 選択と順位付け。行列の並べ替え "

中央値を確認する場合。

 まず各行（列）の中央値を求め、次にその中央値を求めることで、半分近くの数字を削除し、残りの数字で中央値を求めるだけで、計算量は O(N(logN)^2) となります。

62. [マイクロソフト】大文字と小文字、数字を1つずつ並べた配列で、大文字は一緒に、小文字は一緒に、数字は一緒に並べます。

 138を参照。オランダ国旗問題(DNFP)

63. [Google] 1. 木と任意の2つのノードがある場合、その2つのノードを含む最小の部分木を求めます。  第26問
2. サブツリーのノードを表示するBFSアルゴリズムを書く 階層的アクセスツリーに相当する。
3. 木をグラフにした場合（ループがある場合もある）、先ほどのBFSはどう変わるのでしょうか？訪問したポイントに印をつける必要がある

64. next_permutationの実装

 アルゴリズム

1. 1.   a[x1]が成り立つように、奥から順に最初のx1,を求めよ。
2. 2.   後ろから見てa[x2]>a[x1]となるような最初のx2を求めよ。
3. 3.   a[x1],a[x2]を入れ替え、a[x1+1 ... end]を反転させる。

65. 最長の昇順部分配列

 66. 真と偽のノードを持つ単一のリンクリストがあるとき、そのリンクリストに
真のノードと偽のノードをソートし、真ん中に新しいノードを生成して2つのクラスを分離するプログラムを書いてください。

 trueとfalseのノードは2つの異なるリストに接続され、最後にマージされます。

67. 過去5分間で最も頻度の高い1000クエリを選択する10億クエリ、1パス

 正確な解決策：5分以内のすべてのクエリを選択し、各クエリの数をカウントし、最大ヒープを維持し、最後にクエリを取得します。

 拡張機能 クエリの数が非常に多い場合、1つのタイムウィンドウでいくつかのサンプルを行い、最終的に5分後にサンプルの結果をマージすることができます。

68. 2つのソートされた配列は共通の中央値を見つける。

 69. strstr(str1、str2)を実装する。

70. 順序付きリンクリストが与えられたとき、その中から重複する要素をすべて削除しなさい。例えば、1->2->3->3->が与えられたとする。
4->4->5, 1->2->5 を返します。1->1->1->2->3 が与えられたとき、2->3 を返します。

71. 与えられた文字列のうち、アルファベット順と一致しない最初のインデックスを返します。例えば、abcdafなら2番目のaのインデックスを、aZeならeのインデックスを返す必要があります。

 順番にスキャンするだけ

72.数独の入力が有効であることを確認し、解答が不完全であることを許容する。

 わずかに

73. ワイルドキャスト文字列マッチングを実装する。

 74. 辞書を渡され、任意の7文字を与えられて、その7文字を含む最も長い単語を見つける。条件は 前処理が可能なので、毎回違う文字が与えられても非常に効率的です

長さの長い単語から短い単語への番号付け

各文字について、番号順に並べたコレクションを作成する。

与えられた7つの文字について、そのコレクションの中で、すべてに共通する最初の文字を見つけなさい。

75. 表現力評価

 76.2つの文字列、その2つの部分文字列を与え、その距離をdistance=sum_i|s1[i]-s2[i]|と定義すると、距離が最も大きい2つの部分文字列はどのようにして見つけるか。

 網羅的なリストです。もっと良い方法はないのでしょうか？

77個のN*N 0/1行列のうち、最大の全0行列を求めよ

最大ヒストグラムの応用、時間計算量O(N^3)

78. リンクリストを異なる要素の値でグループ化する

 複数のヘッドを使用して、異なる要素のグループを配置し、最後にマージします。