LeetCode Top Interview150メモ
LeetCode Top Interview150とは
技術面接に頻出する150問の問題を厳選してまとめた特定の問題リストのことです。このリストは、求職者がプログラミングインタビューの準備を効果的に行えるように設計されています。企業の面接でよく問われるデータ構造やアルゴリズムに関連した問題が含まれており、幅広いスキルをテストするように構成されています。
問題分野と内容
出題される問題は以下のようなものがあった。各内容についての詳細をchatGPTに聞いたら以下のように返ってきた。
Array/String
配列や文字列に関する問題: 配列（Array）や文字列（String）を使って行う操作やアルゴリズムに関連する問題です。たとえば、配列の要素の並べ替え、特定の要素の検索、部分文字列の探索などがあります。
Two Point
ツーポインタ法: 配列や文字列に対して、二つのポインタを用いて同時に処理を進めるアルゴリズムです。ポインタを左右から中央に向けて移動させたり、一方を固定してもう一方を動かしたりして解く問題が含まれます。たとえば、配列の部分集合の探索や、特定の条件を満たす部分配列を見つける問題があります。
Sliding Window
スライディングウィンドウ: 配列や文字列において、固定サイズまたは可変サイズのウィンドウ（部分配列や部分文字列）を用いて処理を行う手法です。効率的に部分配列や部分文字列を探索・処理する問題が含まれます。
Matrix
行列に関する問題: 2次元配列（行列）を扱う問題です。行列内の要素を操作したり、特定のパターンを見つけたりするアルゴリズムが含まれます。例えば、行列の回転、パス探索などがあります。
HashMap
ハッシュマップ（辞書）に関する問題: キーと値のペアを効率的に管理するデータ構造を使用する問題です。たとえば、データの頻度を数えたり、特定の条件を満たすペアを見つけたりする問題があります。
Intervals
区間（インターバル）に関する問題: 区間の重なりを調べたり、複数の区間を効率的に管理する問題です。たとえば、会議のスケジュール管理や範囲の結合などがあります。
Stack
スタックに関する問題: 後入れ先出し（LIFO）のデータ構造を使って解く問題です。括弧のバランスチェックや逆ポーランド記法の計算などが含まれます。
LinkedList
リンクリストに関する問題: ノードがポインタで次のノードを指し示す線形データ構造を使う問題です。リストの要素の操作（挿入、削除、反転など）に関連する問題があります。
Binary Tree General
一般的な二分木に関する問題: 二分木の構造を使ったアルゴリズムに関連する問題です。木の遍歴、ノードの追加・削除、木の高さや平衡性のチェックなどがあります。
Binary Tree BFS
二分木における幅優先探索（BFS）に関する問題: 二分木の探索で、各レベルごとにノードを探索していく手法を使う問題です。レベルオーダー探索などがあります。
Binary Search Tree
二分探索木に関する問題: 特に整列された二分木の構造を使って効率的にデータを検索、挿入、削除する問題です。これには、二分探索木の特性を利用した探索や範囲クエリが含まれます。
Graph General
グラフに関する問題（一般）: グラフのデータ構造を使って解く一般的な問題です。ノードのつながりを表現し、探索や最短経路などの問題が含まれます。
Graph BFS
グラフにおける幅優先探索（BFS）に関する問題: グラフの探索手法で、特定のノードから開始し、隣接するノードをすべて探索していく手法を用いた問題です。レベルオーダー探索や最短経路探索などが含まれます。
Trie
トライ木（前置木）に関する問題: 文字列の集合を効率的に管理するための木構造を使う問題です。単語の検索や自動補完機能の実装などに関連する問題があります。
BackTracking
バックトラッキング: 解候補を逐次探索しながら不適な解を排除し、解空間を効率的に探索する手法を使った問題です。ナップサック問題や全てのパーミュテーションを生成する問題などがあります。
Divide & Conquer
分割統治法: 問題をいくつかの部分問題に分割し、それぞれを解決してから統合する手法を使う問題です。マージソートやクイックソートなどが代表的です。
Kadane's Algorithm
カデーンのアルゴリズム: 配列の部分配列の最大和を効率的に計算するためのアルゴリズムです。最大部分配列問題（Maximum Subarray Problem）に使われます。
Binary Search
二分探索: 整列されたデータに対して、効率的に探索を行う手法を使った問題です。典型的には、特定の値を見つける問題や、挿入位置を特定する問題があります。
Heap
ヒープに関する問題: ヒープデータ構造を用いて、優先度付きキューの操作や最大・最小要素の管理を行う問題です。ヒープソートや最小・最大ヒープを使った問題が含まれます。
Bit Manipulation
ビット操作: ビット単位の操作を使って効率的に問題を解決する分野です。ビットマスク、ビットシフトを用いて、数値の性質や集合演算を行う問題があります。
Math
数学に関連する問題: 数学的な定理や計算に基づく問題です。素数判定や最大公約数、最小公倍数の計算などが含まれます。
1D DP
一次元の動的計画法: 一次元配列を使った動的計画法の手法を用いる問題です。フィボナッチ数列や最大部分配列問題などが含まれます。
Multidimensional DP
多次元の動的計画法: 二次元以上の配列を使った動的計画法の問題です。例えば、ナップサック問題や、文字列の編集距離（Levenshtein距離）を計算する問題が含まれます。
Discussion