Guide ultime pour la résolution de problèmes lors des entretiens de codage

Stratégies courantes pour coder les questions d’entretien

Deux pointeurs

La technique des deux pointeurs est souvent utilisée pour résoudre efficacement les problèmes liés aux tableaux. Il s'agit d'utiliser deux pointeurs qui se déplacent l'un vers l'autre ou dans la même direction.

Exemple : Trouver une paire de nombres dans un tableau trié qui totalisent une valeur cible.

/**
 * 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);

Fenêtre coulissante

La technique de la fenêtre coulissante est utile pour résoudre des problèmes impliquant des séquences contiguës dans des tableaux ou des chaînes.

Exemple : Trouver la somme maximale d'un sous-tableau de taille 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);

Table de hachage

Les tables de hachage sont excellentes pour résoudre des problèmes qui nécessitent des recherches rapides ou un comptage des occurrences.

Exemple : Recherche du premier caractère non répétitif dans une chaîne.

/**
 * 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);

Ces stratégies démontrent des moyens efficaces de résoudre les problèmes courants d'entretien de codage. La journalisation détaillée dans chaque exemple aide à comprendre le processus étape par étape des algorithmes, ce qui peut être crucial lors des entretiens pour expliquer votre processus de réflexion.

Voici un bloc de code montrant comment utiliser les cartes pour mieux comprendre certaines de ces opérations :

// 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);

Cet exemple illustre diverses opérations sur la carte :

1. Créer une nouvelle carte
2. Ajout de paires clé-valeur avec
3. Récupération des valeurs avec
4. Vérification de l'existence de la clé avec
5. Mise à jour des valeurs
6. Suppression des paires clé-valeur avec
7. Itérer sur la carte avec
8. Obtenir la taille de la carte
9. Effacer toute la carte avec Ces opérations sont similaires à celles utilisées dans la fonction firstNonRepeatingChar, où nous utilisons une Map pour compter les occurrences de caractères, puis recherchons le premier caractère avec un compte de 1.

Tutoriel de programmation dynamique

La programmation dynamique est une technique algorithmique puissante utilisée pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples. Explorons ce concept avec un exemple de calcul des nombres de Fibonacci.

/**
 * 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));

Cet exemple montre comment la programmation dynamique peut calculer efficacement les nombres de Fibonacci en stockant les valeurs précédemment calculées et en les utilisant pour des calculs futurs.

Tutoriel de recherche binaire

La recherche binaire est un algorithme efficace pour trouver un élément dans un tableau trié. Voici une implémentation avec une journalisation détaillée :

/**
 * 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);

Cette implémentation montre comment la recherche binaire réduit efficacement la plage de recherche de moitié à chaque itération, ce qui la rend beaucoup plus rapide que la recherche linéaire pour les grands tableaux triés.

• Recherche en profondeur (DFS)
• Recherche en largeur d'abord (BFS)
• Tas (file d'attente prioritaire)
• Trie (Arbre de préfixes)
• Union-Find (ensemble disjoint)
• Tri topologique

Recherche en profondeur d'abord (DFS)

Depth-First Search est un algorithme de traversée de graphiques qui explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Voici un exemple d'implémentation pour un graphique représenté sous forme de liste de contiguïté :

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'));

Recherche en largeur d'abord (BFS)

BFS explore tous les sommets à la profondeur actuelle avant de passer aux sommets au niveau de profondeur suivant. Voici une implémentation :

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'));

Tas (file d'attente prioritaire)

Un tas est une structure de données arborescente spécialisée qui satisfait à la propriété du tas. Voici une implémentation simple d'un min-heap :

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);

Trie (arbre de préfixes)

Un Trie est une structure de données de recherche d'informations efficace, couramment utilisée pour la recherche de chaînes :

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 (ensemble disjoint)

Union-Find est une structure de données qui garde la trace des éléments divisés en un ou plusieurs ensembles disjoints :

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

Tri topologique

Le tri topologique est utilisé pour classer les tâches avec dépendances. Voici une implémentation utilisant 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());

Ces implémentations fournissent une base solide pour comprendre et utiliser ces algorithmes et structures de données importants dans le codage d'entretiens et d'applications du monde réel.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!