コーディング面接の問題解決のための究極のガイド-jsチュートリアル-php.cn

Ultimate guide for problem solving in coding interviews

面接の質問をコーディングするための一般的な戦略

2 つのポインター

2 ポインター手法は、配列関連の問題を効率的に解決するためによく使用されます。これには、互いに向かって移動するか、同じ方向に移動する 2 つのポインターを使用することが含まれます。

例: ソートされた配列内で合計が目標値になる数値のペアを見つけます。

/**
 * Finds a pair of numbers in a sorted array that sum up to a target value.
 * Uses the two-pointer technique for efficient searching.
 * 
 * @param {number[]} arr - The sorted array of numbers to search through.
 * @param {number} target - The target sum to find.
 * @returns {number[]|null} - Returns an array containing the pair if found, or null if not found.
 */
function findPairWithSum(arr, target) {
  // Initialize two pointers: one at the start and one at the end of the array
  let left = 0;
  let right = arr.length - 1;

  // Continue searching while the left pointer is less than the right pointer
  while (left < right) {
    console.log(`Checking pair: ${arr[left]} and ${arr[right]}`);

    // Calculate the sum of the current pair
    const sum = arr[left] + arr[right];

    if (sum === target) {
      // If the sum equals the target, we've found our pair
      console.log(`Found pair: ${arr[left]} + ${arr[right]} = ${target}`);
      return [arr[left], arr[right]];
    } else if (sum < target) {
      // If the sum is less than the target, we need a larger sum
      // So, we move the left pointer to the right to increase the sum
      console.log(`Sum ${sum} is less than target ${target}, moving left pointer`);
      left++;
    } else {
      // If the sum is greater than the target, we need a smaller sum
      // So, we move the right pointer to the left to decrease the sum
      console.log(`Sum ${sum} is greater than target ${target}, moving right pointer`);
      right--;
    }
  }

  // If we've exhausted all possibilities without finding a pair, return null
  console.log("No pair found");
  return null;
}

// Example usage
const sortedArray = [1, 3, 5, 7, 9, 11];
const targetSum = 14;
findPairWithSum(sortedArray, targetSum);

ログイン後にコピー

引き違い窓

スライディングウィンドウ手法は、配列または文字列内の連続したシーケンスが関係する問題を解決するのに役立ちます。

例: サイズ k の部分配列の最大合計を求めます。

/**
 * Finds the maximum sum of a subarray of size k in the given array.
 * @param {number[]} arr - The input array of numbers.
 * @param {number} k - The size of the subarray.
 * @returns {number|null} The maximum sum of a subarray of size k, or null if the array length is less than k.
 */
function maxSubarraySum(arr, k) {
  // Check if the array length is less than k
  if (arr.length < k) {
    console.log("Array length is less than k");
    return null;
  }

  let maxSum = 0;
  let windowSum = 0;

  // Calculate sum of first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }
  maxSum = windowSum;

  console.log(`Initial window sum: ${windowSum}, Window: [${arr.slice(0, k)}]`);

  // Slide the window and update the maximum sum
  for (let i = k; i < arr.length; i++) {
    // Remove the first element of the previous window and add the last element of the new window
    windowSum = windowSum - arr[i - k] + arr[i];
    console.log(`New window sum: ${windowSum}, Window: [${arr.slice(i - k + 1, i + 1)}]`);

    // Update maxSum if the current window sum is greater
    if (windowSum > maxSum) {
      maxSum = windowSum;
      console.log(`New max sum found: ${maxSum}, Window: [${arr.slice(i - k + 1, i + 1)}]`);
    }
  }

  console.log(`Final max sum: ${maxSum}`);
  return maxSum;
}

// Example usage
const array = [1, 4, 2, 10, 23, 3, 1, 0, 20];
const k = 4;
maxSubarraySum(array, k);

ログイン後にコピー

ハッシュテーブル

ハッシュテーブルは、素早い検索や出現回数のカウントが必要な問題の解決に最適です。

例: 文字列内の最初の非繰り返し文字を検索します。

/**
 * Finds the first non-repeating character in a given string.
 * @param {string} str - The input string to search.
 * @returns {string|null} The first non-repeating character, or null if not found.
 */
function firstNonRepeatingChar(str) {
  const charCount = new Map();

  // Count occurrences of each character
  for (let char of str) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
    console.log(`Character ${char} count: ${charCount.get(char)}`);
  }

  // Find the first character with count 1
  for (let char of str) {
    if (charCount.get(char) === 1) {
      console.log(`First non-repeating character found: ${char}`);
      return char;
    }
  }

  console.log("No non-repeating character found");
  return null;
}

// Example usage
const inputString = "aabccdeff";
firstNonRepeatingChar(inputString);

ログイン後にコピー

これらの戦略は、コーディング面接の一般的な問題を解決する効率的な方法を示しています。各例の詳細なログは、アルゴリズムの段階的なプロセスを理解するのに役立ちます。これは、面接で思考プロセスを説明する際に非常に重要になる可能性があります。

これらの操作の一部をより深く理解するためにマップを使用する方法を示すコードブロックを次に示します。

// Create a new Map
const fruitInventory = new Map();

// Set key-value pairs
fruitInventory.set('apple', 5);
fruitInventory.set('banana', 3);
fruitInventory.set('orange', 2);

console.log('Initial inventory:', fruitInventory);

// Get a value using a key
console.log('Number of apples:', fruitInventory.get('apple'));

// Check if a key exists
console.log('Do we have pears?', fruitInventory.has('pear'));

// Update a value
fruitInventory.set('banana', fruitInventory.get('banana') + 2);
console.log('Updated banana count:', fruitInventory.get('banana'));

// Delete a key-value pair
fruitInventory.delete('orange');
console.log('Inventory after removing oranges:', fruitInventory);

// Iterate over the map
console.log('Current inventory:');
fruitInventory.forEach((count, fruit) => {
  console.log(`${fruit}: ${count}`);
});

// Get the size of the map
console.log('Number of fruit types:', fruitInventory.size);

// Clear the entire map
fruitInventory.clear();
console.log('Inventory after clearing:', fruitInventory);

ログイン後にコピー

この例では、さまざまな Map 操作を示します。

新しいマップの作成
によるキーと値のペアの追加
による値の取得
でキーの存在を確認しています
値を更新しています
によるキーと値のペアの削除
によるマップの反復処理
マップのサイズを取得する
マップ全体をクリアするこれらの操作は、firstNonRepeatingChar 関数で使用されるものと似ています。Map を使用して文字の出現をカウントし、カウント 1 の最初の文字を検索します。

動的プログラミングのチュートリアル

動的プログラミングは、複雑な問題をより単純な部分問題に分割して解決するために使用される強力なアルゴリズム手法です。フィボナッチ数の計算例を使ってこの概念を詳しく見てみましょう。

/**
 * Calculates the nth Fibonacci number using dynamic programming.
 * @param {number} n - The position of the Fibonacci number to calculate.
 * @returns {number} The nth Fibonacci number.
 */
function fibonacci(n) {
  // Initialize an array to store Fibonacci numbers
  const fib = new Array(n + 1);

  // Base cases
  fib[0] = 0;
  fib[1] = 1;

  console.log(`F(0) = ${fib[0]}`);
  console.log(`F(1) = ${fib[1]}`);

  // Calculate Fibonacci numbers iteratively
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
    console.log(`F(${i}) = ${fib[i]}`);
  }

  return fib[n];
}

// Example usage
const n = 10;
console.log(`The ${n}th Fibonacci number is:`, fibonacci(n));

ログイン後にコピー

この例は、以前に計算された値を保存し、それを将来の計算に使用することによって、動的プログラミングがフィボナッチ数を効率的に計算する方法を示しています。

二分探索のチュートリアル

二分探索は、ソートされた配列内の要素を見つけるための効率的なアルゴリズムです。詳細なログを記録する実装は次のとおりです。

/**
 * Performs a binary search on a sorted array.
 * @param {number[]} arr - The sorted array to search.
 * @param {number} target - The value to find.
 * @returns {number} The index of the target if found, or -1 if not found.
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    console.log(`Searching in range [${left}, ${right}], mid = ${mid}`);

    if (arr[mid] === target) {
      console.log(`Target ${target} found at index ${mid}`);
      return mid;
    } else if (arr[mid] < target) {
      console.log(`${arr[mid]} < ${target}, searching right half`);
      left = mid + 1;
    } else {
      console.log(`${arr[mid]} > ${target}, searching left half`);
      right = mid - 1;
    }
  }

  console.log(`Target ${target} not found in the array`);
  return -1;
}

// Example usage
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 7;
binarySearch(sortedArray, target);

ログイン後にコピー

この実装は、バイナリ検索が反復ごとに検索範囲を効率的に半分に絞り込み、大規模な並べ替えられた配列の線形検索よりもはるかに高速になる方法を示しています。

深さ優先検索 (DFS)
幅優先検索 (BFS)
ヒープ (優先キュー)
トライ (接頭辞ツリー)
Union-Find (素集合)
トポロジカルソート

深さ優先検索 (DFS)

深さ優先検索は、後戻りする前に各分岐に沿って可能な限り探索するグラフ走査アルゴリズムです。隣接リストとして表されるグラフの実装例を次に示します。

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  dfs(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfsHelper(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      console.log(`Visiting vertex: ${vertex}`);

      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          console.log(`Exploring neighbor: ${neighbor} of vertex: ${vertex}`);
          return dfsHelper(neighbor);
        } else {
          console.log(`Neighbor: ${neighbor} already visited`);
        }
      });
    })(start);

    return result;
  }
}

// Example usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex => graph.addVertex(vertex));
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log(graph.dfs('A'));

ログイン後にコピー

幅優先検索 (BFS)

BFS は、次の深さレベルの頂点に移動する前に、現在の深さのすべての頂点を探索します。実装は次のとおりです:

class Graph {
  // ... (same constructor, addVertex, and addEdge methods as above)

  bfs(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    visited[start] = true;

    while (queue.length) {
      let vertex = queue.shift();
      result.push(vertex);
      console.log(`Visiting vertex: ${vertex}`);

      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
          console.log(`Adding neighbor: ${neighbor} to queue`);
        } else {
          console.log(`Neighbor: ${neighbor} already visited`);
        }
      });
    }

    return result;
  }
}

// Example usage (using the same graph as in DFS example)
console.log(graph.bfs('A'));

ログイン後にコピー

ヒープ (優先キュー)

ヒープは、ヒープ特性を満たす特殊なツリーベースのデータ構造です。これは最小ヒープの簡単な実装です:

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }

  insert(key) {
    this.heap.push(key);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(i) {
    let currentIndex = i;
    while (this.heap[currentIndex] < this.heap[this.getParentIndex(currentIndex)]) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return min;
  }

  heapifyDown(i) {
    let smallest = i;
    const left = this.getLeftChildIndex(i);
    const right = this.getRightChildIndex(i);

    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }

    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }

    if (smallest !== i) {
      this.swap(i, smallest);
      this.heapifyDown(smallest);
    }
  }
}

// Example usage
const minHeap = new MinHeap();
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].forEach(num => minHeap.insert(num));
console.log(minHeap.heap);
console.log(minHeap.extractMin());
console.log(minHeap.heap);

ログイン後にコピー

トライ (プレフィックスツリー)

トライは効率的な情報検索データ構造であり、一般的に文字列検索に使用されます。

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children[char]) {
        current.children[char] = new TrieNode();
      }
      current = current.children[char];
    }
    current.isEndOfWord = true;
    console.log(`Inserted word: ${word}`);
  }

  search(word) {
    let current = this.root;
    for (let char of word) {
      if (!current.children[char]) {
        console.log(`Word ${word} not found`);
        return false;
      }
      current = current.children[char];
    }
    console.log(`Word ${word} ${current.isEndOfWord ? 'found' : 'not found'}`);
    return current.isEndOfWord;
  }

  startsWith(prefix) {
    let current = this.root;
    for (let char of prefix) {
      if (!current.children[char]) {
        console.log(`No words start with ${prefix}`);
        return false;
      }
      current = current.children[char];
    }
    console.log(`Found words starting with ${prefix}`);
    return true;
  }
}

// Example usage
const trie = new Trie();
['apple', 'app', 'apricot', 'banana'].forEach(word => trie.insert(word));
trie.search('app');
trie.search('application');
trie.startsWith('app');
trie.startsWith('ban');

ログイン後にコピー

Union-Find (素集合)

Union-Find は、1 つ以上の素のセットに分割された要素を追跡するデータ構造です。

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill().map((_, i) => i);
    this.rank = Array(size).fill(0);
    this.count = size;
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);

    if (rootX === rootY) return;

    if (this.rank[rootX] < this.rank[rootY]) {
      [rootX, rootY] = [rootY, rootX];
    }
    this.parent[rootY] = rootX;
    if (this.rank[rootX] === this.rank[rootY]) {
      this.rank[rootX]++;
    }
    this.count--;

    console.log(`United ${x} and ${y}`);
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

// Example usage
const uf = new UnionFind(10);
uf.union(0, 1);
uf.union(2, 3);
uf.union(4, 5);
uf.union(6, 7);
uf.union(8, 9);
uf.union(0, 2);
uf.union(4, 6);
uf.union(0, 4);

console.log(uf.connected(1, 5)); // Should print: true
console.log(uf.connected(7, 9)); // Should print: false

ログイン後にコピー

トポロジカルソート

トポロジカルソートは、依存関係のあるタスクの順序付けに使用されます。 DFS を使用した実装は次のとおりです:

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
  }

  topologicalSort() {
    const visited = {};
    const stack = [];

    const dfsHelper = (vertex) => {
      visited[vertex] = true;
      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          dfsHelper(neighbor);
        }
      });
      stack.push(vertex);
      console.log(`Added ${vertex} to stack`);
    };

    for (let vertex in this.adjacencyList) {
      if (!visited[vertex]) {
        dfsHelper(vertex);
      }
    }

    return stack.reverse();
  }
}

// Example usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex => graph.addVertex(vertex));
graph.addEdge('A', 'C');
graph.addEdge('B', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');

console.log(graph.topologicalSort());

ログイン後にコピー

これらの実装は、インタビューや現実世界のアプリケーションのコーディングにおいて、これらの重要なアルゴリズムとデータ構造を理解し、使用するための強固な基盤を提供します。

以上がコーディング面接の問題解決のための究極のガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。