코딩 인터뷰 문제 해결을 위한 궁극적인 가이드

코딩 인터뷰 질문에 대한 일반적인 전략

두 개의 포인터

두 포인터 기술은 배열 관련 문제를 효율적으로 해결하기 위해 자주 사용됩니다. 서로를 향하거나 같은 방향으로 움직이는 두 개의 포인터를 사용하는 것이 포함됩니다.

예: 정렬된 배열에서 합계가 목표 값에 해당하는 숫자 쌍 찾기

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



<h2>
  
  
  슬라이딩 윈도우
</h2>

<p>슬라이딩 윈도우 기술은 배열이나 문자열의 연속 시퀀스와 관련된 문제를 해결하는 데 유용합니다.</p>

<p>예: 크기 k인 하위 배열의 최대 합 찾기<br>
</p>

<pre class="brush:php;toolbar:false">/**
 * 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  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);

이 예에서는 다양한 지도 작업을 보여줍니다.

1. 새 지도 만들기
2. 을 사용하여 키-값 쌍 추가
3. 을 사용하여 값 검색
4. 으로 키 존재 확인
5. 값 업데이트
6. 을 사용하여 키-값 쌍 삭제
7. 을 사용하여 지도 반복
8. 지도 크기 가져오기
9. 전체 지도 지우기 이러한 작업은 map을 사용하여 문자 발생 횟수를 계산한 다음 개수가 1인 첫 번째 문자를 검색하는 firstNonRepeatingChar 함수에 사용된 것과 유사합니다.

동적 프로그래밍 튜토리얼

동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 데 사용되는 강력한 알고리즘 기술입니다. 피보나치 수 계산의 예를 통해 이 개념을 살펴보겠습니다.

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



<p>이 예에서는 동적 프로그래밍이 이전에 계산된 값을 저장하고 향후 계산에 사용하여 피보나치 수를 효율적으로 계산할 수 있는 방법을 보여줍니다.</p>

<h2>
  
  
  이진 검색 튜토리얼
</h2>

<p>이진 검색은 정렬된 배열에서 요소를 찾는 효율적인 알고리즘입니다. 자세한 로깅을 구현한 내용은 다음과 같습니다.<br>
</p>

<pre class="brush:php;toolbar:false">/**
 * 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  ${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)
• 힙(우선순위 대기열)
• Trie(접두사 트리)
• Union-Find(Disjoint Set)
• 토폴로지 정렬

깊이 우선 검색(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]  minHeap.insert(num));
console.log(minHeap.heap);
console.log(minHeap.extractMin());
console.log(minHeap.heap);

Trie(접두사 트리)

A Trie는 문자열 검색에 일반적으로 사용되는 효율적인 정보 검색 데이터 구조입니다.

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(Disjoint 집합)

Union-Find는 하나 이상의 분리된 세트로 분할된 요소를 추적하는 데이터 구조입니다.

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] 



<h2>
  
  
  토폴로지 정렬
</h2>

<p>토폴로지 정렬은 종속성이 있는 작업을 정렬하는 데 사용됩니다. 다음은 DFS를 사용한 구현입니다.<br>
</p>

<pre class="brush:php;toolbar:false">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 중국어 웹사이트의 기타 관련 기사를 참조하세요!