Panduan muktamad untuk menyelesaikan masalah dalam temu bual pengekodan

Strategi Biasa untuk Soalan Temuduga Pengekodan

Dua Penunjuk

Teknik dua penunjuk sering digunakan untuk menyelesaikan masalah berkaitan tatasusunan dengan cekap. Ia melibatkan penggunaan dua penunjuk yang sama ada bergerak ke arah satu sama lain atau ke arah yang sama.

Contoh: Mencari sepasang nombor dalam tatasusunan diisih yang menjumlahkan kepada nilai sasaran.

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

Tingkap Gelongsor

Teknik tetingkap gelongsor berguna untuk menyelesaikan masalah yang melibatkan jujukan bersebelahan dalam tatasusunan atau rentetan.

Contoh: Mencari jumlah maksimum subarray saiz 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);

Jadual Hash

Jadual cincang sangat baik untuk menyelesaikan masalah yang memerlukan carian pantas atau mengira kejadian.

Contoh: Mencari aksara tidak berulang pertama dalam rentetan.

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

Strategi ini menunjukkan cara yang cekap untuk menyelesaikan masalah temu duga pengekodan biasa. Pengelogan verbose dalam setiap contoh membantu memahami proses langkah demi langkah algoritma, yang boleh menjadi penting semasa temu duga untuk menerangkan proses pemikiran anda.

Berikut ialah blok kod yang menunjukkan cara menggunakan peta untuk lebih memahami beberapa operasi ini:

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

Contoh ini menunjukkan pelbagai operasi Peta:

1. Mencipta Peta baharu
2. Menambah pasangan nilai kunci dengan
3. Mendapatkan semula nilai dengan
4. Menyemak kewujudan kunci dengan
5. Mengemas kini nilai
6. Memadamkan pasangan nilai kunci dengan
7. Lelaran pada Peta dengan
8. Mendapatkan saiz Peta
9. Mengosongkan seluruh Peta dengan Operasi ini serupa dengan yang digunakan dalam fungsi firstNonRepeatingChar, di mana kami menggunakan Peta untuk mengira kejadian aksara dan kemudian mencari aksara pertama dengan kiraan 1.

Tutorial Pengaturcaraan Dinamik

Pengaturcaraan dinamik ialah teknik algoritma yang berkuasa yang digunakan untuk menyelesaikan masalah yang kompleks dengan memecahkannya kepada submasalah yang lebih mudah. Mari kita terokai konsep ini dengan contoh pengiraan nombor 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));

Contoh ini menunjukkan cara pengaturcaraan dinamik boleh mengira nombor Fibonacci dengan cekap dengan menyimpan nilai yang dikira sebelum ini dan menggunakannya untuk pengiraan masa hadapan.

Tutorial Carian Binari

Carian binari ialah algoritma yang cekap untuk mencari elemen dalam tatasusunan yang diisih. Berikut ialah pelaksanaan dengan pengelogan terperinci:

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

Pelaksanaan ini menunjukkan cara carian binari mengecilkan julat carian dengan cekap sebanyak separuh dalam setiap lelaran, menjadikannya lebih pantas daripada carian linear untuk tatasusunan diisih yang besar.

• Depth-First Search (DFS)
• Breadth-First Search (BFS)
• Timbunan (Baris Gilir Keutamaan)
• Trie (Pokok Awalan)
• Union-Find (Set Berpisah)
• Isih Topologi

Carian Depth-First (DFS)

Depth-First Search ialah algoritma traversal graf yang meneroka sejauh mungkin di sepanjang setiap cawangan sebelum menjejak ke belakang. Berikut ialah contoh pelaksanaan untuk graf yang diwakili sebagai senarai bersebelahan:

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

Breadth-First Search (BFS)

BFS meneroka semua bucu pada kedalaman semasa sebelum bergerak ke bucu pada tahap kedalaman seterusnya. Berikut ialah pelaksanaan:

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

Timbunan (Baris Gilir Keutamaan)

Timbunan ialah struktur data berasaskan pokok khusus yang memenuhi sifat timbunan. Berikut ialah pelaksanaan mudah timbunan min:

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 (Pokok Awalan)

A Trie ialah struktur data perolehan semula maklumat yang cekap, biasanya digunakan untuk carian rentetan:

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 (Set Berpisah)

Union-Find ialah struktur data yang menjejaki elemen yang dipecahkan kepada satu atau lebih set berpisah:

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

Susun Topologi

Isihan topologi digunakan untuk memesan tugasan dengan kebergantungan. Berikut ialah pelaksanaan menggunakan 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());

Pelaksanaan ini menyediakan asas yang kukuh untuk memahami dan menggunakan algoritma dan struktur data penting ini dalam temu bual pengekodan dan aplikasi dunia sebenar.

Atas ialah kandungan terperinci Panduan muktamad untuk menyelesaikan masalah dalam temu bual pengekodan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!