나는 60분의 코딩 과제를 기반으로 개발자의 기술을 측정하는 것을 크게 믿지 않습니다. 대부분의 경우 이러한 문제는 알고리즘을 알고 있으면 해결하는 데 15분이 걸리는 방식으로 설계됩니다. 실생활의 어려운 문제를 그렇게 짧은 시간에 해결한 적이 언제인지 기억이 나지 않습니다. 모든 복잡한 문제는 해결하는 데 시간이 걸립니다.

그러나 이번 주 월요일인 1월 6일에 두 번의 코딩 인터뷰가 있습니다. 그래서 인터뷰 과정에 대해 불평하는 대신 내일 아침 2020년 1월 4일 오전 8시부터 1월 5일 오후 8시까지 24시간을 할애하겠습니다. 그 시간 동안 저는 데이터 구조와 알고리즘을 공부할 것입니다.

진행 상황을 주기적으로 업데이트하고 메모와 코드를 게시합니다. 제가 염두에 두고 있는 주제는 다음과 같습니다.

배열 및 문자열

연결된 목록

스택 및 대기열

나무

그래프

비트 조작

재귀

동적 프로그래밍

검색 및 정렬

저는 Gayle Laakmann McDowell의 Cracking the Coding 인터뷰와 JavaScript를 사용한 데이터 구조 및 알고리즘: Michael McMillan의 웹에 대한 고전적인 컴퓨팅 접근 방식을 읽을 계획입니다.

나는 다른 블로그 게시물을 읽고 가능한 한 많은 코딩 문제를 해결하고 DEV 커뮤니티와 공유할 것입니다.

당신이 알고 있는 좋은 인터뷰 준비 자료를 저와 공유해 주세요. 이 글과 대화가 코딩 인터뷰를 준비할 시간이 없을 때 누구나 참고할 수 있는 좋은 자리가 되었으면 합니다.

1일차(2020년 1월 4일)

오전 10시에 24시간 코딩 면접 준비 챌린지를 시작했습니다. 나는 완벽한 커피 한 잔을 가지고 있으며 코딩 인터뷰 준비를 할 준비가 되었습니다. 오늘 제가 다룰 주제는 다음과 같습니다.

어레이

문자열

연결된 목록

스택

대기열

나무

그래프

검색

주제를 연구하고, 모든 유용한 리소스를 문서화하고, 각 주제에서 5/10 문제를 해결하고, 2시간마다 커뮤니티를 업데이트합니다. 저는 커뮤니티가 훌륭한 책임 파트너가 될 수 있다고 믿습니다.

데이터 구조를 빠르게 마스터하는 방법에 대한 최고의 아이디어를 공유하십시오. 모든 제안에 감사드립니다.

다음 업데이트는 오후 12시에 진행될 예정입니다.

오후 12시 업데이트

나는 Cracking the Coding Interview 책의 첫 장을 읽었다.

내가 작업한 프로그래밍 문제는 다음과 같습니다.

배열과 문자열

1. 고유함: 문자열에 고유한 문자가 모두 있는지 확인하는 알고리즘을 구현합니다. 추가 데이터 구조를 사용할 수 없으면 어떻게 합니까?

function uniqueCharacters(str) {
  const ASCII_CHARS = 256;

  if(str.length > ASCII_CHARS) {
    return false;
  }

  const chars = Array(ASCII_CHARS).fill(false);

  for(let char of str){
    const index = char.charCodeAt(0);
    if (chars[index] === true) {
      return false;
    }
    chars[index] = true;
  }

  return true;
}

console.log(uniqueCharacters('abcd10jk')); // true
console.log(uniqueCharacters('hutg9mnd!nk9')); // false

2. 순열 확인: 두 개의 문자열이 주어지면 하나가 다른 하나의 순열인지 결정하는 방법을 작성하십시오.

function isPermutation(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }

  const map = new Map();

  for(const char of str1) {
    if(map.has(char)) {
      map.set(char, map.get(char) + 1);
    } else {
      map.set(char, 1);
    }
  }

  for(const char of str2) {
      if(map.has(char)) {
        const value = map.get(char);
        if(value === 0) {
          return false;
        } else {
          map.set(char, map.get(char) - 1);
        }
      }
  }

  for(const value of map.values()) {
    if(value !== 0) {
      return false;
    }
  }
  return true;

}

console.log(isPermutation("god", "dog")); // true

3. URLify: 문자열의 모든 공백을 '%20'으로 바꾸는 메서드를 작성합니다.

function replaceSpaces(str, trueLength) {
  let output = "";
  let chars = 0;

  for(let char of str) {
    if(char !== " ") {
      chars++;
    }
  }

  let spaces = trueLength - chars;

  for(let char of str) {
    if(char === " " && spaces > 0) {
      output += "%20";
      spaces--;
    } else if(char !== " ") {
      output += char;
    }
  }

  while(spaces > 0) {
    output += "%20";
    spaces--;
  }

  return output;
}

console.log(replaceSpaces("Mr 3ohn Smith", 13)); // "Mr%203ohn%20Smith"

3. Palindrome Permutation: 문자열이 주어졌을 때 그것이 palindrome의 순열인지 확인하는 함수를 작성하십시오.

function isPermutationOfPalindrome(str) {
  let charCount = 0;
  let map = new Map();

  for(let char of str) {
    if (char === " ") {
      continue;
    }

    if(map.has(char)) {
      map.delete(char);
    } else {
      map.set(char, true);
    }

    charCount++;
  }

  if(charCount % 2 === 0) {
    return map.size === 0;
  } else {
    return map.size === 1;
  }
}

console.log(
  isPermutationOfPalindrome("tacoa cat") === true,
  isPermutationOfPalindrome("atco cat") === true,
  isPermutationOfPalindrome(" rac ecar rara ") === true
);

4. 문자열 압축: 반복된 문자 수를 사용하여 기본 문자열 압축을 수행하는 방법을 구현합니다.

function compress (str) {
  const map = new Map();
  let result = '';

  for(const char of str) {
    if(map.has(char)) {
      map.set(char, map.get(char) + 1);
    } else {
      map.set(char, 1);
    }
  }

  for(let [key, value] of map) {
    result += key + value;
  }

  return str.lenght >= result.lenght ? str : result;
}

console.log(compress('aabcccccaaa')); // "a5b1c5"

5. 회전 행렬: 이미지의 각 픽셀이 4바이트인 NxN 행렬로 표현되는 이미지가 주어지면 이미지를 90도 회전하는 방법을 작성하십시오.

function rotateMatrix(arr) {
    let n = arr.length - 1;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - i; j++) {
            let temp = arr[i][j];

            arr[i][j] = arr[n - j][n - i]; // top row
            arr[n - j][n - i] = temp; // right column
        }
    }

    return arr;
}


console.log(rotateMatrix([
  [1,2,3],
  [4,5,6],
  [7,8,9]
])); 

/* 
[
    [9, 6, 3], 
    [8, 5, 2], 
    [7, 4, 1]
] 
*/

6. 문자열 회전; 한 단어가 다른 단어의 하위 문자열인지 확인하는 isSubstring g 메서드가 있다고 가정합니다. s1과 s2라는 두 개의 문자열이 주어지면 isSubstring[예: "waterbottle"은 oP'erbottlewat"의 회전입니다.)

const isSubstring = (str1, str2) => str1.includes(str2);

function isRotation(str1, str2) {
  if(!str1 || !str2) {
    return false;
  }

  if(str1.length !== str2.length) {
    return false;
  }

  return isSubstring(str1 + str2, str2);
}

console.log(isRotation("waterbottle", "erbottlewat")); // true
console.log(isRotation("aacdf", "acda")); // false

7. 주어진 문자열 또는 배열에서 첫 번째 고유 문자 찾기

function findFirstUniqueCharacter(str) {
  if(!str) return;

  const map = new Map();

  for(let char of str) {
      if(map.has(char)) {
        map.set(char, map.get(char) + 1);
      } else {
        map.set(char, 1);
      }
  }

  for(let [key, value] of map) {
    if(value === 1) {
      return key;
    }
  }
  return "None";
}

console.log(findFirstUniqueCharacter('foobar')); // f
console.log(findFirstUniqueCharacter('aabbccdef')); // d
console.log(findFirstUniqueCharacter('aabbcc')); // 'No Unique Character Found'

오후 3시 30분 업데이트

연결된 목록

연결된 목록 노드 클래스

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

연결 리스트 인쇄 기능

function print(node) {
  while(node !== null) {
      console.log('->' + node.value);
      node = node.next;
  }
}

1. 중복 제거: 정렬되지 않은 연결 목록에서 중복을 제거하는 코드를 작성합니다.

function removeDups(node) {
  if(node === null) return null;

  let nodes = new Map();
  let current = node.next;
  let prev = node;
  nodes.set(node.value, 1);

  while(current !== null) {
    if(nodes.get(current.value) === 1) {
      prev.next = current.next;
    } else {
      nodes.set(current.value, 1);
      prev = current;
    }
    current = current.next;
  }
  return node;
}

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(2);
let node5 = new Node(1);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

print(removeDups(node1));

/* 
"->1"
"->2"
"->3"
*/

2. K번째를 마지막으로 반환: 단일 연결 목록의 마지막 요소에서 k번째를 찾는 알고리즘을 구현합니다.

function KthToLast(root, n) {
  if(!root) return null;
  let current = root;
  let follower = root;

  for(let i = 0; i < n; i++) {
    current = current.next;
  }

  while(current.next !== null) {
    current = current.next;
    follower = follower.next;
  }

  return follower;
}


let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

console.log(KthToLast(node1, 2).value);  // 3

3. 연결 리스트 중간 삭제

function removeDups(head) {
  if(head === null) return null;

  let fast = head;
  let slow = head;
  let prev = null;

  while(fast !== null && fast.next !== null) {
    fast = fast.next.next;
    prev = slow;
    slow = slow.next;
  }

  prev.next = slow.next;

  return head;
}

let nodeA = new Node('a');
let nodeB = new Node('b');
let nodeC = new Node('c');
let nodeD = new Node('d');
let nodeE = new Node('e');
let nodeF = new Node('f');

nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
nodeF.next = null;

print(removeDups(nodeA)); 
/*
"->a"
"->b"
"->c"
"->e"
"->f"
*/

4. 주어진 값을 중심으로 연결된 목록을 분할하고 목록의 요소를 안정적으로 만드는 데 관심이 없는 경우

function partition(head, x) {
  let tail = head;
  let current = head;

  while(current !== null) {
    let next = current.next;
    if(current.value < x) {
      current.next = head;
      head = current;
    } else {
      tail.next = current;
      tail = current;
    }
    current = next;
  }
  tail.next = null;

  return head;
}

let nodeA = new Node(3);
let nodeB = new Node(5);
let nodeC = new Node(8);
let nodeD = new Node(2);
let nodeE = new Node(10);
let nodeF = new Node(2);
let nodeH = new Node(1);

nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
nodeF.next = nodeH;
nodeH.next = null;

print(partition(nodeA, 5));
/*
"->1"
"->2"
"->2"
"->3"
"->5"
"->8"
"->10"
*/

5. 각 노드에 다음 노드에 대한 포인터와 목록의 임의 노드에 대한 포인터가 있는 연결 목록이 있으면 연결 목록을 복제합니다.

function clone(node) {
  if(node === null) return node;

  let map = new Map();
  let copy = new Node(node.value);
  let current = node;
  let newHead = copy;

  map.set(current, copy);

  current = current.next;
  while(current !== null) {
    let temp = new Node(current.value);
    map.set(current, temp);
    copy.next = temp;
    copy = temp;
    current = current.next;
  }

  current = node;
  copy = newHead;

  while(current !== null) {
    if(current.randome !== null) {
      copy.random = map.get(current.random);
    } else {
      copy.random = null;
    }

    current = current.next;
    copy = copy.next;
  }

  return newHead;
}

6. 연결된 목록이 주어지면 순환이 포함되어 있는지 확인합니다.

function hasCycle(node) {
  if(node === null) return false;
  let slow = node;
  let fast = node.next;

  while(fast !== null && fast.next !== null) {
    if(fast === slow) return true;
    slow = slow.next;
    fast = fast.next.next;
  }

  return false;
}

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node3;

console.log(hasCycle(node1)); // true

7. 한 번에 연결된 목록의 중간 요소를 찾는 방법은 무엇입니까?

function findMiddle(node) {
    if(node === null) return null;
    let fast = node.next;
    let slow = node;

    while(fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    console.log(slow.value);
}

let node1 = new Node(5);
let node2 = new Node(6);
let node3 = new Node(7);
let node4 = new Node(1);
let node5 = new Node(2);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

findMiddle(node1); // 7

8. 두 개의 숫자 더하기

// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
// Output: 7 -> 0 -> 8
// Explanation: 342 + 465 = 807.

const addTwoNumbers = function(l1, l2) {
  let head = new Node(0);
  let carry = 0;
  let current = head;

  while(l1 !== null || l2 !== null ) {
    const x = l1 !== null ? l1.value : 0;
    const y = l2 !== null ? l2.value : 0;

    const sum = carry + x + y;
    carry = Math.floor(sum / 10);

    current.next = new Node(sum % 10);
    current = current.next;

    if(l1 != null) l1 = l1.next;
    if(l2 != null) l2 = l2.next;
  }

  if (carry > 0) {
    current.next = new ListNode(carry);
  }
  return head.next;
};

const node13 = new Node(3);
const node12 = new Node(4);
const node11 = new Node(2);
node11.next = node12;
node12.next = node13;
const l1 = node11; 

const node23 = new Node(4);
const node22 = new Node(6);
const node21 = new Node(5);
node22.next = node23;
node21.next = node22;
const l2 = node21;

print(addTwoNumbers(l1, l2));
/*
"->7"
"->0"
"->8"
*/

오후 7시 45분 업데이트

스택

1. 스택이 주어지면 추가 스택만 사용하여 스택의 요소를 정렬합니다.

Array.prototype.peek = function() {
  return this[this.length -1];
}

Array.prototype.isEmpty = function() {
  return this.length <= 0;
}

function sortStack(stack) {
  if(!stack || stack.length ===0) return stack;

  let newStack = [];
  newStack.push(stack.pop());

  while(!stack.isEmpty()) {
    const temp = stack.pop();
    while(!newStack.isEmpty() && temp > newStack.peek()) {
      stack.push(newStack.pop());
    }
    newStack.push(temp);
  }
  return newStack;
}

console.log(sortStack([5, 1, 3, 2, 4])); // [5, 4, 3, 2, 1]

2. Javascript에서 역 폴란드어 표기법 평가

function reversePolishNotation(seq) {
  if(seq.length <= 2) {
    return;
  }

  const operands = ['+', '-', '*', '/'];
  const stack = [];
  let i = 0;

  stack.push(seq[i]);
  i++;

  while(i <= seq.length) {
    let item = seq[i];
    let index = operands.indexOf(item);

    if(index < 0) {
      stack.push(item);
    } else {
      const a = parseInt(stack.pop(), 10);
      const b = parseInt(stack.pop(), 10);

      if(index === 0) {
        stack.push(a + b);
      } 
      if(index === 1) {
        stack.push(a - b);
      }
      if(index === 2) {
        stack.push(a * b);
      }
      if(index === 3) {
        stack.push(b/a);
      }
    }
    i++;
  }

  return parseInt(stack[0], 0);
}

console.log(reversePolishNotation(["2", "1", "+", "3", "*"])) // 9
console.log(reversePolishNotation(["4", "13", "5", "/", "+"])) // 6
console.log(reversePolishNotation(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) // 22
console.log(reversePolishNotation(["2", "1"])) // undefined

3. javascript를 사용하여 스택 구현

function Stack() {
  this.top = null;
}

Stack.prototype.push = function (val) {
  let node = {
    data : val,
    next : null
  };

  node.next = this.top;
  this.top = node;
};

Stack.prototype.pop = function () {
  if(this.top === null) {
    return null;
  } else {
    const top = this.top;
    this.top = this.top.next;
    return top.data;
  }
};

Stack.prototype.peek = function() {
  if(this.top === null) {
    return null;
  } else {
    return this.top.data;
  }
}

var S1 = new Stack();
S1.push(5);
S1.push(6);
S1.push(7);
S1.push(8);

console.log(S1.pop()); // 8
console.log(S1.pop()); // 7

4. 두 개의 스택 javascript를 사용하여 대기열

function Queue() {
  this.pushStack = new Stack();
  this.popStack = new Stack();
}

Queue.prototype.enqueue = function(value) {
  this.pushStack.push(value);
}

Queue.prototype.dequeue = function() {
  let popStack = this.popStack;
  let pushStack = this.pushStack;

  if(popStack.peek()) {
    const deq = popStack.pop();
    return deq;
  }

  while(pushStack.peek()) {
    popStack.push(pushStack.pop());
  }
}

const q1 = new Queue();
q1.enqueue(3);
q1.enqueue(4);
q1.enqueue(5);
q1.enqueue(6);
q1.enqueue(7);
q1.dequeue();
q1.dequeue();
q1.dequeue();

console.log(q1);

5.

function stepsToSolveTowerOfHanoi(height, from, to, via) {
  if (height >= 1) {
    // Move a tower of height - 1 to buffer peg using destination peg
    stepsToSolveTowerOfHanoi(height - 1, from, via, to);
    // Move the remaining disk to the destination peg.
    console.log(`Move disk ${height} from Tower ${from} to Tower ${to}`);
    // Move the tower of `height-1` from the `buffer peg` to the `destination peg` using the `source peg`.        
    stepsToSolveTowerOfHanoi(height - 1, via, to, from);
  }

  return;
}

stepsToSolveTowerOfHanoi(3, "A", "C", "B");
/*
"Move disk 1 from Tower A to Tower C"
"Move disk 2 from Tower A to Tower B"
"Move disk 1 from Tower C to Tower B"
"Move disk 3 from Tower A to Tower C"
"Move disk 1 from Tower B to Tower A"
"Move disk 2 from Tower B to Tower C"
"Move disk 1 from Tower A to Tower C"
*/

6. 문자열이 유효한 괄호로 구성되어 있는지 확인

function isMatchingBrackets(str) {
  if(str.length <= 1) {
    return false;
  }

  let stack = [];
  const map = {
    '{': '}',
    '[': ']',
    '(': ')'
  };

  for(let char of str) {
    if(char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else {
      const last = stack.pop();
      if (char !== map[last]) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

console.log(isMatchingBrackets("(){}")); // true
console.log(isMatchingBrackets("[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]")); // true
console.log(isMatchingBrackets("({(()))}}"));  // false