データ構造とアルゴリズム 面接の質問

データ構造とアルゴリズム 面接で問われる内容

データ構造とアルゴリズム 面接の質問例

• 配列内の2つの数値で合計が目標値になるものを見つけてください（計算量の分析も）。
  良い回答が押さえる点

  • ハッシュマップによるO(n)解法
  • ブルートフォースのO(n^2)との比較
  • エッジケース（空配列、解なし）の考慮
  • フォローアップ: ソート済み配列でのtwo-pointer

  サンプル回答を見る

  この問題はハッシュマップ（JavaScriptではMapオブジェクト）を使うことでO(n)時間、O(n)空間で解けます。配列を走査しながら、各要素について「目標値から現在の要素を引いた値（相棒）」がすでにハッシュマップに存在するかをチェックします。存在すればその2つのインデックスを返し、存在しなければ現在の要素をインデックスとともにハッシュマップに保存します。ブルートフォースは二重ループでO(n^2)ですが、ハッシュマップを使うと各要素の探索が定数時間になるため効率的です。注意点として、同じ要素を2回使えないため、保存前にチェックする順序が重要です。解が常に1つ存在するという前提ですが、解がない場合の処理も考慮すべきです。フォローアップとして、配列がソート済みならtwo-pointer法でO(n)時間、O(1)空間でも解けます。

  def two_sum(nums, target):
      # 値->インデックスのハッシュマップ
      seen = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              # 相棒が既出ならそのインデックスと現在のインデックスを返す
              return [seen[complement], i]
          # 現在の要素をマップに追加
          seen[num] = i
      # 解がない場合は空リスト（問題の前提に依存）
      return []
  
  # 時間計算量: O(n)
  # 空間計算量: O(n)

• 連結リストの循環を検出してください。
  良い回答が押さえる点

  • Floydの循環検出アルゴリズム（うさぎとかめ）
  • O(n)時間、O(1)空間
  • 循環の開始位置検出への拡張
  • ハッシュセットを使った解法との比較

  サンプル回答を見る

  連結リストの循環検出にはFloydの循環検出アルゴリズム（通称「うさぎとかめ」）が標準的です。2つのポインタ（遅いポインタは1ステップ、速いポインタは2ステップ）を先頭から進め、循環があれば必ずどこかで一致します。このアルゴリズムはO(n)時間、O(1)空間で動作し、破壊的操作が不要です。ハッシュセットを使う方法（O(n)空間）も簡単ですが、面接ではフロイド法を求められることが多いです。注意点として、空リストや要素数1の場合は循環がないので適切に処理します。フォローアップとして循環の開始位置を求める問題もあります。その場合は、一致点を見つけた後、一方のポインタを先頭に戻し、両方を1ステップずつ進めると開始位置で再び一致します。

  class ListNode:
      def __init__(self, x):
          self.val = x
          self.next = None
  
  def has_cycle(head):
      # フロイドの循環検出
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow == fast:
              return True
      return False
  
  # 時間計算量: O(n)
  # 空間計算量: O(1)

• 繰り返し文字のない最長部分文字列を見つけてください。
  良い回答が押さえる点

  • スライディングウィンドウ＋ハッシュセット/マップ
  • O(n)時間、O(min(m,n))空間（mは文字セットサイズ）
  • ウィンドウ拡張・縮小の条件
  • エッジケース（空文字列）

  サンプル回答を見る

  この問題はスライディングウィンドウ手法で解きます。左端と右端のポインタ（通常left, rightまたはi, j）を使い、右端を1つずつ進めながら、現在のウィンドウ内に重複文字がないかをハッシュセットで管理します。重複が見つかった場合は左端を進めてウィンドウを縮小し、重複がなくなるまで繰り返します。各ステップで最大長を更新します。時間計算量はO(n)（各文字が高々2回処理される）、空間計算量はO(min(m, n))で、mは文字の種類数（英小文字なら26、ASCIIなら128、Unicodeなら多め）。注意点として、単に最長の長さだけでなく部分文字列自体を求める場合にも対応可能です。フォローアップとして、英小文字限定ならサイズ26の配列を使うとより効率的です。

  def length_of_longest_substring(s: str) -> int:
      # 文字の出現位置を管理する辞書（またはサイズ128の配列）
      char_map = {}
      left = 0
      max_len = 0
      for right, ch in enumerate(s):
          # chが既にマップにあり、かつウィンドウ内にあればleftを更新
          if ch in char_map and char_map[ch] >= left:
              left = char_map[ch] + 1
          # chの最新位置を更新
          char_map[ch] = right
          # 現在のウィンドウ長で最大値を更新
          max_len = max(max_len, right - left + 1)
      return max_len
  
  # 時間計算量: O(n)
  # 空間計算量: O(min(m, n))  (mは文字セットのサイズ)

• 二分木のレベル順（BFS）トラバーサルを行ってください。
  良い回答が押さえる点

  • キューを使ったBFS、O(n)時間
  • レベルごとのリスト生成方法
  • 再帰DFSによる方法との比較
  • ヌルノードの扱い

  サンプル回答を見る

  二分木のレベル順トラバーサル（BFS）はキューを用いて実装します。まずルートノードをキューに入れ、キューが空になるまで以下の処理を繰り返します：現在のレベルのノード数だけキューから取り出し、その値をリストに追加し、子ノードをキューに追加します。各レベルのリストを結果リストに追加します。時間計算量はO(n)（各ノードを1回処理）、空間計算量は最悪ケース（完全二分木の最下層）でO(n)です。注意点として、Pythonでdequeを使うとO(1)のpopleftが可能です。フォローアップとして、各レベルの平均値や右側面ビューなども同様の手法で解けます。再帰的DFSでもレベルを管理しながら同様の結果を得られますが、BFSが直感的です。

  from collections import deque
  
  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  def level_order(root):
      if not root:
          return []
      result = []
      queue = deque([root])
      while queue:
          level_size = len(queue)
          level_vals = []
          for _ in range(level_size):
              node = queue.popleft()
              level_vals.append(node.val)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          result.append(level_vals)
      return result
  
  # 時間計算量: O(n)
  # 空間計算量: O(n)

• グリッド内の島の数（BFS/DFS）。
  良い回答が押さえる点

  • グリッド探索（BFS/DFS）、O(m×n)時間・空間
  • 訪問済みマークの方法（別配列 or グリッド書き換え）
  • 4方向 or 8方向の考慮
  • エッジケース（空グリッド、全部1）

  サンプル回答を見る

  この問題は、連結した'1'（陸）の塊を島として数えます。典型的な解法はDFSまたはBFSで、各セルを走査し、'1'の未訪問セルを見つけたら島カウントを増やし、そのセルから連結する全ての'1'を探索して訪問済みにします。訪問済みの管理は、別の二次元配列を使うか、グリッド自体を'0'に書き換える破壊的方法があります（ただし入力変更が許される場合）。時間計算量はO(m×n)（全セルを1回ずつ処理）、空間計算量は再帰DFSの場合は最悪O(m×n)（スタック）、BFSの場合はキューが最大O(min(m,n))程度。注意点として、グリッドが空の場合の処理を忘れずに。フォローアップとして、島の最大面積や島の周長を求める問題もあります。また、Union-Find（DSU）を使った解法も可能ですが、面接ではDFS/BFSがシンプルです。

  def num_islands(grid):
      if not grid or not grid[0]:
          return 0
      rows, cols = len(grid), len(grid[0])
      count = 0
      
      def dfs(r, c):
          # 範囲外または水なら終了
          if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
              return
          # 訪問済みにする（'0'に書き換え）
          grid[r][c] = '0'
          # 4方向を再帰的に探索
          dfs(r+1, c)
          dfs(r-1, c)
          dfs(r, c+1)
          dfs(r, c-1)
      
      for i in range(rows):
          for j in range(cols):
              if grid[i][j] == '1':
                  count += 1
                  dfs(i, j)
      return count
  
  # 時間計算量: O(m×n)
  # 空間計算量: O(m×n) (再帰の深さが最悪で全セル)

• 階段ののぼり方/コインの組み合わせ（基本的な動的計画法）。
  良い回答が押さえる点

  • DPボトムアップ: 階段のぼりはFibonacci、O(n)時間・O(1)空間
  • コインの組み合わせ: 重複を許す場合・許さない場合の区別
  • DPテーブルの初期化と遷移式
  • メモ化再帰との比較

  サンプル回答を見る

  代表的な2つの問題を説明します。 1. 階段のぼり（n段を1段または2段で上がる方法の数）は、フィボナッチ数列そのものです。DPボトムアップではdp[0]=1, dp[1]=1として、i>=2に対してdp[i]=dp[i-1]+dp[i-2]。O(n)時間、O(1)空間に最適化できます（直前2つの値のみ保持）。 2. コインの組み合わせ（特定の金額をコインで作る方法の数、順序を考慮しない組合せ）は、典型的なDP問題です。コインの種類ごとに外側ループを回し、金額を内側ループで回すことで重複を防ぎます（組合せ順序が異なるものは同一とみなす）。dp[0]=1とし、各コインについて金額coinからamountまでdp[i] += dp[i-coin]。時間計算量O(amount*coins)、空間O(amount)。注意点として、順序を考慮する（パーミュテーション）場合はループの順序を逆にします。また、メモ化再帰でも解けますが、ボトムアップの方がスタックオーバーフローの心配がありません。

  # 階段のぼり（n段、1段か2段）
  def climb_stairs(n: int) -> int:
      if n <= 1:
          return 1
      prev1, prev2 = 1, 1  # dp[0], dp[1]
      for i in range(2, n+1):
          current = prev1 + prev2
          prev2, prev1 = prev1, current
      return prev1
  
  # コインの組み合わせ（順序不問）
  def coin_change_combinations(coins, amount):
      dp = [0] * (amount + 1)
      dp[0] = 1
      for coin in coins:
          for i in range(coin, amount + 1):
              dp[i] += dp[i - coin]
      return dp[amount]
  
  # 時間計算量: climb_stairs O(n), coin_combinations O(amount*len(coins))
  # 空間計算量: climb_stairs O(1), coin_combinations O(amount)

準備方法

• 問題ではなくパターンを学びましょう — ほとんどの質問は少数のテンプレートにマッピングされます。
• 常に時間計算量と空間計算量を述べ、ブルートフォースの場合はより良いアプローチを探しましょう。
• コーディング前に計画を口に出して説明し、最後に小さな例でテストしましょう。
• ホワイトボードやオートコンプリートのないプレーンなエディタでバグのないコードを書く練習をしましょう。

よくある質問