Meituan 面接質問

Meituan 面接の重点項目

Meituan のよくある面接質問

• 配送ポイント（緯度/経度）のリストと開始位置が与えられたとき、すべてのポイントを訪れて戻る最短ルートを見つけてください。
  良い回答が押さえる点

  • この問題は巡回セールスマン問題（TSP）の変種で、すべての点を訪れて出発点に戻る最短経路を求める。
  • 点の数が少ない場合（≤20）は動的計画法（Held-Karp）で厳密解が得られるが、大規模にはヒューリスティック（最近傍法、2-opt最適化など）が必要。
  • 緯度経度から球面距離（Haversine式）を計算し、対称性を利用する。
  • 実用的には、近似的な解法（例えば遺伝的アルゴリズム）を選ぶ場合もある。
  • コードではDPを用いた厳密解を示す。

  サンプル回答を見る

  この問題はNP困難な巡回セールスマン問題（TSP）に相当します。点の数が少ない場合（≤20）は、動的計画法（Held-Karp法）で厳密解を得られます。この手法はO(n^2 * 2^n)の時間計算量で動作し、部分集合と終点の状態を保持します。距離は緯度経度からHaversine式で計算します。しかし、点の数が多い場合は指数時間となるため、最近傍法や2-opt、シミュレーテッドアニーリングなどの近似解法を用います。実務では、数千点を扱う場合、距離行列を前計算し、クラスタリングで問題を分割することもあります。以下に、動的計画法を用いた厳密解のコードを示します。

  import math
  from itertools import combinations
  
  def haversine(lat1, lon1, lat2, lon2):
      R = 6371  # 地球半径 (km)
      dlat = math.radians(lat2 - lat1)
      dlon = math.radians(lon2 - lon1)
      a = math.sin(dlat/2)**2 + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon/2)**2
      c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
      return R * c
  
  def tsp_dp(points):
      """
      points: [(lat, lon), ...] のリスト。最初の点が出発点で、戻る必要あり。
      全点を訪れる最短ルートの距離を返す（厳密解）。
      """
      n = len(points)
      if n == 0:
          return 0
      # 距離行列
      dist = [[0]*n for _ in range(n)]
      for i in range(n):
          for j in range(n):
              dist[i][j] = haversine(points[i][0], points[i][1], points[j][0], points[j][1])
      
      # DPテーブル: dp[mask][i] = maskの集合を訪れてiにいる最小距離 (maskはビットセット, 0は出発点を含まない)
      # 出発点0は常に含まれるため、maskは0以外の点の部分集合を表す (iビットはiが含まれる)
      # ここではmaskをn-1ビットで管理 (点1からn-1)
      size = 1 << (n-1)
      dp = [[float('inf')]*n for _ in range(size)]
      # 初期状態: 点0から点iへ (i>=1)
      for i in range(1, n):
          mask = 1 << (i-1)  # iに対応するビット
          dp[mask][i] = dist[0][i]
      
      # DP計算
      for mask in range(1, size):
          for i in range(1, n):
              if not (mask & (1 << (i-1))):
                  continue
              if dp[mask][i] == float('inf'):
                  continue
              # 未訪問の点jを追加
              for j in range(1, n):
                  if mask & (1 << (j-1)):
                      continue
                  new_mask = mask | (1 << (j-1))
                  new_dist = dp[mask][i] + dist[i][j]
                  if new_dist < dp[new_mask][j]:
                      dp[new_mask][j] = new_dist
      # 全点訪問後、点0に戻る
      full_mask = size - 1
      ans = float('inf')
      for i in range(1, n):
          if dp[full_mask][i] == float('inf'):
              continue
          ans = min(ans, dp[full_mask][i] + dist[i][0])
      return ans
  
  # 使用例
  points = [(35.6895, 139.6917), (34.0522, -118.2437), (40.7128, -74.0060)]
  print(f"最短距離: {tsp_dp(points):.2f} km")
  # 時間計算量: O(n^2 * 2^n), 空間計算量: O(n * 2^n)

• 数百万のユーザー向けのリアルタイム注文追跡システムを設計し、レイテンシ、一貫性、フォールトトレランスを考慮してください。
  良い回答が押さえる点

  • 低レイテンシのためにWebSocketを使用し、位置情報はKafkaで非同期処理。
  • 一貫性はイベントソーシングと楽観的ロックで確保し、フォールトトレランスはレプリケーションとチェックポイントで対応。
  • 数百万ユーザーに対応するため、注文IDで水平分割（シャーディング）し、地理的に分散配置。
  • リアルタイム性を高めるため、Redisを使ったキャッシュ層を導入。
  • 障害時はグレースフルデグラデーションを採用し、遅延データはバッチで補完。

  サンプル回答を見る

  まず要件を整理します。数百万ユーザーが自身の注文の配送状況をリアルタイムで確認できるようにし、遅延は数秒以内、一貫性は結果的整合性で許容しますが、配送状態の更新は厳密に順序を保つ必要があります。アーキテクチャとしては、配達員のモバイルアプリから位置情報がHTTPまたはWebSocketで送られ、Kafkaなどのメッセージキューにパブリッシュされます。ストリーム処理エンジン（Apache Flinkなど）で集約・検証後、注文ごとに状態を更新し、データベース（CassandraやTiDBなどの分散DB）に書き込みます。ユーザー向けには、APIサーバーがWebSocketでクエリを受け付け、Redisキャッシュに最新状態があれば即座に返します。フォールトトレランスには、Kafkaのパーティションとレプリケーション、データベースのマルチAZ展開、そして配達員の位置情報は再送可能な設計にします。一貫性は、楽観的ロックとバージョン管理により衝突を回避します。また、注文が非常に多いため、注文IDでシャーディングし、各シャードは独立したKafkaコンシューマーグループで処理します。監視にはPrometheusとGrafanaを使い、レイテンシやスループットを可視化します。

• getおよびput操作を平均O(1)でサポートするLRU削除ポリシーのキャッシュを実装してください。
  良い回答が押さえる点

  • getとputをO(1)で実現するために、ハッシュマップと双方向リンクリストを組み合わせる。
  • 双方向リンクリストはアクセス順を管理し、ハッシュマップでノードへのポインタを保持。
  • 容量制限を超えたら、リンクリストの末尾（最も古いアクセス）を削除。
  • get時には該当ノードを先頭に移動し、put時には既存キーなら更新して先頭に移動、新規なら追加し容量超えなら末尾削除。
  • スレッドセーフが必要な場合はミューテックスなどを追加。

  サンプル回答を見る

  LRUキャッシュは、最近使われたアイテムを優先的に保持するキャッシュ戦略です。平均O(1)のget/putを実現するには、ハッシュマップ（キーからノードへのマップ）と双方向リンクリスト（アクセス順を管理）を組み合わせます。リンクリストの先頭が最も最近アクセスされたアイテム、末尾が最も古いアイテムです。get時にはキーをハッシュマップで検索し、存在すればノードを先頭に移動させて値を返します。put時には、キーが存在すれば値を更新しノードを先頭に移動、存在しなければ新しいノードを作成して先頭に追加し、容量を超えた場合は末尾ノードを削除します。削除時にはハッシュマップからもエントリを削除します。以下にPythonによる実装例を示します。

  class ListNode:
      def __init__(self, key=0, val=0):
          self.key = key
          self.val = val
          self.prev = None
          self.next = None
  
  class LRUCache:
      def __init__(self, capacity: int):
          self.capacity = capacity
          self.cache = {}  # key -> ListNode
          # ダミーヘッドとテール
          self.head = ListNode()
          self.tail = ListNode()
          self.head.next = self.tail
          self.tail.prev = self.head
  
      def _remove_node(self, node):
          node.prev.next = node.next
          node.next.prev = node.prev
  
      def _add_to_front(self, node):
          node.next = self.head.next
          node.prev = self.head
          self.head.next.prev = node
          self.head.next = node
  
      def _move_to_front(self, node):
          self._remove_node(node)
          self._add_to_front(node)
  
      def get(self, key: int) -> int:
          if key in self.cache:
              node = self.cache[key]
              self._move_to_front(node)
              return node.val
          return -1
  
      def put(self, key: int, value: int) -> None:
          if key in self.cache:
              node = self.cache[key]
              node.val = value
              self._move_to_front(node)
          else:
              if len(self.cache) >= self.capacity:
                  # 末尾ノードを削除（LRUアイテム）
                  lru = self.tail.prev
                  self._remove_node(lru)
                  del self.cache[lru.key]
              new_node = ListNode(key, value)
              self.cache[key] = new_node
              self._add_to_front(new_node)
  
  # 時間計算量: get/put ともに O(1)
  # 空間計算量: O(capacity)

• Meituanのフードデリバリー向けレコメンデーションシステムの改善を任されました。多様性を確保しながら、どのようにパーソナライズしますか？
  良い回答が押さえる点

  • パーソナライズには協調フィルタリングとコンテンツベースフィルタリングを組み合わせ、ユーザーの注文履歴や検索行動を利用。
  • 多様性を確保するために、MAB（多腕バンディット）やMMR（最大限の関連性を持つ多様性）を導入し、類似店舗の連続表示を避ける。
  • 時間帯や場所に応じたコンテキスト情報を特徴量として追加。
  • 新規ユーザーには人気度と多様性を重視した初期レコメンドを提供。
  • ABテストで効果を測定し、オフライン評価ではNDCGや多様性指標を監視。

  サンプル回答を見る

  フードデリバリーのレコメンデーションでは、ユーザーの好みに合わせつつ、毎回同じ店舗ばかり勧めないよう多様性を持たせることが重要です。まず、協調フィルタリング（ユーザーベース・アイテムベース）とコンテンツベース（料理カテゴリ、価格帯など）を組み合わせたハイブリッド手法を採用します。さらに、多様性を高めるために、候補リストからMMR（Maximum Marginal Relevance）アルゴリズムを使って、既に表示したアイテムとの類似度が低く、かつ関連性の高いものを選びます。また、新規ユーザーには探索と活用のバランスを取るために、ε-greedyやUCBなどの多腕バンディットアルゴリズムを使用します。コンテキストとして、時間帯（朝食・昼食・夕食）、位置情報（近くの店舗を優先）、天気などを考慮します。レコメンデーションのパイプラインは、オフラインで特徴量を計算し、オンラインでリアルタイムにランキングを行います。評価はオフラインでNDCGや多様性指標（カバレッジ、セレンディピティ）を測定し、オンラインではABテストでクリック率や注文率を比較します。

• スピードと品質のトレードオフを迫られた経験について教えてください。どのように決定し、結果はどうでしたか？
  良い回答が押さえる点

  • 緊急のバグ修正リリースで、手動テストを省略して素早くデプロイするか、品質を優先してスケジュールを遅らせるかの判断を迫られた。
  • 影響範囲を評価し、バグがクリティカルでユーザー体験に大きく影響するため、スピードを優先した。
  • ただし、自動テストとカナリアリリースを徹底し、モニタリングを強化してリスクを最小化。
  • 結果として、迅速に問題を解決し、ユーザーからの苦情が激減した。後日、回帰テストを追加して品質を確保した。

  サンプル回答を見る

  以前、フロントエンドの重要な注文処理にバグが見つかり、ユーザーが注文を完了できない問題が発生しました。通常は手動テストを含むフルテストを実施してからデプロイしますが、影響範囲が広く、早急な対応が必要でした。私はスピードを優先し、自動テスト（ユニットテストと統合テスト）がパスした時点でカナリアリリースすることに決めました。ただし、モニタリングを強化し、エラーレートや注文成功率をリアルタイムで監視しました。結果として、問題は迅速に修正され、ユーザーからの苦情は大幅に減少しました。後日、回帰テストケースを追加し、同様の問題が再発しないようにしました。この経験から、リスクを適切に評価し、スピードと品質のバランスを取ることの重要性を学びました。

• クラッシュすることなくフラッシュセールを処理できるスケーラブルなクーポン/割引システムをどのように設計しますか？
  良い回答が押さえる点

  • フラッシュセールでは瞬間的な高負荷に対応するため、非同期処理とキューイングが必須。
  • クーポン残数をRedisのAtomic操作（INCR/DECR）で管理し、DBへの書き込みは非同期で行う。
  • 楽観的ロックや分散ロック（RedisのRedlock）で二重使用を防止。
  • リクエストのレート制限（トークンバケット）を実装し、過負荷を回避。
  • スケーラビリティのため、クーポンサービスをステートレスにし、水平スケール可能に。

  サンプル回答を見る

  フラッシュセール向けのクーポンシステムでは、大量のリクエストをさばきつつ、一貫性を保つ必要があります。設計のポイントは以下の通りです。まず、クーポンの在庫数はRedisのアトミック操作（DECR）で管理し、データベースへの書き込みは非同期キュー（Kafka）で行います。これにより、DBへの負荷を軽減しつつ、在庫の正確性を保ちます。二重使用を防ぐため、ユーザーごとにクーポン取得の冪等性を担保し、楽観的ロックやRedisの分散ロックを使用します。APIサーバーはステートレスに設計し、ロードバランサーの背後で水平スケールします。また、レート制限（トークンバケット）を適用し、特定ユーザーやIPからの過剰なリクエストを制御します。クーポンの発行履歴は最終的にDBに書き込み、結果的整合性を許容します。障害対策として、Redisがダウンした場合のフォールバックとして、DBの悲観的ロックを使用するフェイルセーフ機構を用意します。

• 技術的な方向性についてマネージャーと意見が合わなかった状況を説明してください。どのように対処しましたか？
  良い回答が押さえる点

  • 新規機能のアーキテクチャ選択で、マイクロサービス化を主張するマネージャーに対し、モノリスでのスタートを提案した。
  • チームの規模や開発速度、運用コストを考慮し、モノリスで十分と判断。
  • データとプロトタイプを示し、将来の分割可能性も考慮した設計を提示。
  • 合意に至り、モノリスでスタートし、後日マイクロサービスにリファクタリングした。

  サンプル回答を見る

  私のマネージャーは、新機能をマイクロサービスとして実装することを強く推していました。しかし、私は当時のチーム規模やリリースサイクルを考慮し、モノリスアーキテクチャで始める方が生産性が高いと主張しました。私は過去のプロジェクトデータを基に、マイクロサービスのオーバーヘッド（ネットワークレイテンシ、分散トランザクション）がメリットを上回る可能性を示しました。また、モノリスでも明確なモジュール境界を設ければ、後でマイクロサービスに分割できることを提案しました。マネージャーは私のデータに納得し、モノリスでスタートすることになりました。結果として、開発速度は速く、半年後に必要に応じてマイクロサービス化しました。この経験から、技術的な議論ではデータと具体的なトレードオフを示すことが重要だと学びました。

• ユーザーレビューの大規模データセットが与えられたとき、リアルタイムで偽のレビューを検出およびフィルタリングするシステムを設計してください。
  良い回答が押さえる点

  • リアルタイム検出にはストリーム処理（Apache Flink）と機械学習モデル（異常検知）を組み合わせる。
  • 特徴量として、レビューのテキスト（NLP）、ユーザー行動パターン（レビュー頻度、IP）、時間的パターンを抽出。
  • ルールベースのフィルタ（短時間の大量レビュー、既知のスパムパターン）とMLモデルを並列実行し、スコアリング。
  • スケーラビリティのため、特徴量生成とモデル推論をパイプライン化し、Kafkaでデータを流す。
  • 誤検出を減らすため、人間によるサンプリングチェックとフィードバックループでモデルを継続的に改善。

  サンプル回答を見る

  大規模なユーザーレビューデータからリアルタイムで偽レビューを検出するシステムは、ストリーム処理と機械学習を組み合わせたアーキテクチャが適しています。まず、Kafkaにレビューイベントを流し、Apache Flinkなどのストリーム処理エンジンでウィンドウ単位に集約します。特徴量エンジンでは、テキストのNLP特徴（感情スコア、類似度）、ユーザーの行動パターン（レビュー頻度、IPアドレス、デバイス情報）、レビュー間の時間間隔などを計算します。これらの特徴量を基に、事前学習された異常検知モデル（例えばIsolation ForestやLSTMオートエンコーダ）で異常スコアを算出します。同時に、ルールベース（例：5分間に10件以上のレビュー、不自然なIP）で即座にフィルタリングします。スコアが閾値を超えたレビューはフラグされ、後で人間が確認します。モデルは人間のフィードバックを基に継続的に再学習します。スケーリングには、モデル推論をマイクロサービス化し、水平スケール可能にします。レイテンシ要件は数秒以内を目標とします。

準備のヒント

• グラフ走査（ダイクストラ、A*など）と動的計画法に焦点を当てたLeetCodeの難問を練習しましょう。Meituanは配送/物流のシナリオをよく使用します。
• システムデザインでは、ライドシェアリングやフードデリバリーアプリのような大規模アーキテクチャを研究しましょう。一貫性、可用性、レイテンシのトレードオフを議論する準備をしてください。
• 行動回答をMeituanの核となる価値観（顧客第一、長期的影響への焦点、反復的改善の受け入れ）に合わせましょう。経験から具体的な例を使用してください。
• ビジネス指標について議論する準備をしましょう。エンジニアリングの決定がコンバージョン率、配送時間、ユーザー維持率にどのように影響するかを理解し、回答に数字やKPIを使用してください。
• タイマーを使って模擬面接を行いましょう。Meituanの面接はペースが速いです。時間的プレッシャーの下で声に出して考える練習を、特にコーディングとデザインで行ってください。

よくある質問