Interview Trace

이진 탐색 트리 검증

이진 트리의 루트가 주어졌을 때, 이것이 유효한 이진 탐색 트리(BST)인지 판단하세요. 유효한 BST는 다음과 같이 정의됩니다: - 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드들만 포함합니다. - 노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드들만 포함합니다. - 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리여야 합니다.

이진 트리의 좋은 노드 개수 세기

이진 트리 root가 주어진다. 트리의 노드 X는 root에서 X까지의 경로에서 X보다 큰 값을 가진 노드가 없으면 "좋은" 노드라고 한다. 이진 트리의 좋은 노드의 개수를 반환하시오.

이진 트리 우측 뷰

이진 트리의 루트가 주어졌을 때, 트리의 우측에 서 있는 자신을 상상하고, 위에서 아래로 순서대로 볼 수 있는 노드의 값들을 반환하세요.

이진 트리 레벨 순서 순회

이진 트리의 루트가 주어질 때, 노드 값들의 레벨 순서 순회를 반환하세요. (즉, 왼쪽에서 오른쪽으로, 레벨별로)

이진 탐색 트리의 최저 공통 조상

이진 탐색 트리(BST)가 주어지면, 두 개의 주어진 노드 p와 q의 최저 공통 조상(LCA) 노드를 찾으세요. 위키피디아의 LCA 정의에 따르면: "최저 공통 조상은 두 노드 p와 q 사이에서 p와 q를 모두 후손으로 가지는 T의 가장 낮은 노드로 정의됩니다(노드가 자기 자신의 후손이 될 수 있습니다)."

다른 트리의 부분트리

두 개의 이진 트리의 루트 root와 subRoot가 주어질 때, root의 부분트리 중에 subRoot와 같은 구조와 노드 값을 가진 트리가 있으면 true를, 그렇지 않으면 false를 반환합니다. 이진 트리 tree의 부분트리는 tree의 한 노드와 그 노드의 모든 자손으로 이루어진 트리입니다. tree 자신도 tree의 부분트리로 간주될 수 있습니다.

같은 트리

두 이진 트리의 루트 p와 q가 주어질 때, 두 트리가 동일한지 확인하는 함수를 작성하세요. 두 이진 트리가 같다고 간주되려면 구조적으로 동일하고 노드의 값이 모두 같아야 합니다.

균형 이진 트리

이진 트리가 주어졌을 때, 해당 트리가 높이 균형(height-balanced)을 만족하는지 판단하세요. 높이 균형 트리는 모든 노드에서 왼쪽 부분 트리의 높이와 오른쪽 부분 트리의 높이 차이의 절댓값이 1 이하인 이진 트리입니다.

이진 트리의 지름

이진 트리의 루트가 주어졌을 때, 트리의 지름의 길이를 반환하세요. 이진 트리의 지름은 트리의 임의의 두 노드 사이의 가장 긴 경로의 길이입니다. 이 경로는 루트를 지날 수도 있고 지나지 않을 수도 있습니다. 두 노드 사이 경로의 길이는 그 사이의 간선(edge)의 개수로 표현됩니다.

이진 트리의 최대 깊이

이진 트리의 루트가 주어졌을 때, 그것의 최대 깊이를 반환하세요. 이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가는 가장 긴 경로 위의 노드 개수입니다.

이진 트리 뒤집기

이진 트리의 루트가 주어졌을 때, 트리를 뒤집고 루트를 반환하세요. 트리를 뒤집는 것은 각 노드에서 왼쪽 자식과 오른쪽 자식을 서로 교환하는 것을 의미합니다.

k개 노드씩 연결 리스트 뒤집기

연결 리스트의 head가 주어질 때, 리스트의 노드를 k개씩 묶어 역순으로 뒤집고 수정된 리스트를 반환하세요. k는 양의 정수이며 연결 리스트의 길이 이하입니다. 노드의 개수가 k의 배수가 아니면 끝에 남는 노드들은 그대로 유지해야 합니다. 리스트의 노드 값은 변경할 수 없으며, 노드들의 연결 관계만 변경할 수 있습니다.

k개 정렬 리스트 병합

k개의 링크드 리스트로 이루어진 배열 lists가 주어집니다. 각 링크드 리스트는 오름차순으로 정렬되어 있습니다. 모든 링크드 리스트를 하나의 정렬된 링크드 리스트로 병합하고 반환하세요.

LRU 캐시

Least Recently Used (LRU) 캐시의 제약을 따르는 데이터 구조를 설계하세요. LRUCache 클래스를 구현하세요: - LRUCache(int capacity): 양수 크기의 capacity로 LRU 캐시를 초기화합니다. - int get(int key): key가 존재하면 해당 값을 반환하고, 그렇지 않으면 -1을 반환합니다. - void put(int key, int value): key가 존재하면 해당 값을 업데이트합니다. 그렇지 않으면 key-value 쌍을 캐시에 추가합니다. 이 작업 후 키의 개수가 capacity를 초과하면 가장 최근에 사용되지 않은 키를 제거합니다. get과 put 함수는 각각 O(1) 평균 시간 복잡도로 실행되어야 합니다.

중복된 숫자 찾기

n + 1개의 정수를 포함하는 정수 배열 nums가 주어지며, 각 정수는 [1, n] 범위 내에 있습니다. nums에는 정확히 하나의 중복된 숫자가 있습니다. 이 중복된 숫자를 반환해야 합니다. 배열 nums를 수정하지 않고 O(1) 상수 추가 공간만을 사용하여 문제를 풀어야 합니다.

연결 리스트 순환 감지

연결 리스트의 헤드 노드가 주어졌을 때, 연결 리스트에 순환(사이클)이 있는지 판별하시오. 연결 리스트에서 순환이란 리스트의 어떤 노드에서 시작하여 next 포인터를 따라 계속 이동할 때 다시 도달할 수 있는 노드가 존재하는 경우를 말합니다. 내부적으로 pos는 tail의 next 포인터가 연결된 노드의 인덱스를 나타냅니다. pos는 입력 매개변수로 주어지지 않음을 주의하시오. 연결 리스트에 순환이 있으면 true를 반환하고, 그렇지 않으면 false를 반환하시오.

두 숫자 더하기

두 개의 비어있지 않은 연결 리스트가 주어졌습니다. 각각은 음이 아닌 정수를 나타냅니다. 숫자의 자릿수는 역순으로 저장되며, 각 노드는 한 자리 숫자를 포함합니다. 두 수를 더하고 합을 연결 리스트로 반환하세요. 두 수는 숫자 0을 제외하고 앞에 0이 없다고 가정할 수 있습니다.

랜덤 포인터가 있는 리스트 복사

각 노드에 random 포인터가 추가된 길이 n인 링크드 리스트가 주어집니다. random 포인터는 리스트의 어떤 노드를 가리킬 수도 있고, null을 가리킬 수도 있습니다. 리스트의 깊은 복사본(deep copy)을 구성하세요. 깊은 복사본은 정확히 n개의 완전히 새로운 노드로 구성되어야 하며, 각 새 노드의 값은 대응하는 원본 노드의 값으로 설정되어야 합니다. 새 노드의 next와 random 포인터는 모두 복사된 리스트의 새 노드를 가리켜야 하므로, 원본 리스트의 포인터와 복사된 리스트의 포인터가 동일한 리스트 상태를 나타냅니다. 새 리스트의 어떤 포인터도 원본 리스트의 노드를 가리키면 안 됩니다. 예를 들어, 원본 리스트에 X와 Y 두 개의 노드가 있고 X.random --> Y인 경우, 복사된 리스트의 대응하는 두 노드 x와 y에 대해 x.random --> y이어야 합니다.

리스트 끝에서 N번째 노드 제거

링크드 리스트의 헤드가 주어졌을 때, 끝에서 n번째 노드를 제거하고 헤드를 반환하세요.

연결 리스트 재배치

싱글 연결 리스트의 헤드가 주어집니다. 리스트는 다음과 같이 표현됩니다: L₀ → L₁ → … → Lₙ₋₁ → Lₙ 리스트를 다음 형태로 재배치합니다: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → … 리스트의 노드 값은 수정할 수 없습니다. 노드 자체만 변경할 수 있습니다.

정렬된 두 연결 리스트 병합

두 개의 정렬된 연결 리스트 list1과 list2의 헤드가 주어진다. 두 리스트를 하나의 정렬된 리스트로 병합하라. 리스트는 두 리스트의 노드들을 함께 연결하여 만들어야 한다. 병합된 연결 리스트의 헤드를 반환하라.

연결 리스트 뒤집기

단일 연결 리스트의 헤드(시작 노드)가 주어질 때, 리스트를 역순으로 뒤집고 역순으로 뒤집어진 리스트를 반환하세요.

두 정렬 배열의 중앙값

크기가 각각 m과 n인 두 개의 정렬된 배열 nums1과 nums2가 주어질 때, 두 배열의 중앙값을 반환하세요. 전체 실행 시간 복잡도는 O(log (m+n))이어야 합니다.

시간 기반 키-값 저장소

같은 키에 대해 서로 다른 시간에 여러 값을 저장하고, 특정 시간에 해당하는 키의 값을 검색할 수 있는 시간 기반 키-값 데이터 구조를 설계하세요. TimeMap 클래스를 구현하세요: - TimeMap() 데이터 구조의 객체를 초기화합니다. - void set(String key, String value, int timestamp) 주어진 시간 timestamp에서 key 키와 value 값을 저장합니다. - String get(String key, int timestamp) 이전에 set이 호출되었으며, timestamp_prev <= timestamp를 만족하는 값을 반환합니다. 이러한 값이 여러 개 있다면, 가장 큰 timestamp_prev와 관련된 값을 반환합니다. 값이 없으면 빈 문자열 ""을 반환합니다.

회전된 정렬 배열에서 검색

정수 배열 nums가 오름차순으로 정렬되어 있습니다 (모든 값이 서로 다릅니다). 함수에 전달되기 전에, nums는 미지의 인덱스 k (1 <= k < nums.length)에서 왼쪽으로 회전된 상태일 수 있습니다. 회전된 배열은 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 형태입니다 (0-인덱싱). 예를 들어, [0,1,2,4,5,6,7]을 3만큼 왼쪽으로 회전하면 [4,5,6,7,0,1,2]가 됩니다. 회전된 후의 배열 nums와 정수 target이 주어질 때, target이 nums에 있으면 그 인덱스를, 없으면 -1을 반환하세요. O(log n) 시간 복잡도로 작동하는 알고리즘을 작성해야 합니다.

회전된 정렬 배열에서 최솟값 찾기

길이 n인 오름차순 정렬 배열이 1번에서 n번 사이로 회전되었다고 하자. 예를 들어, 배열 [0,1,2,4,5,6,7]은 4번 회전되면 [4,5,6,7,0,1,2]가 된다. 배열 [a[0], a[1], a[2], ..., a[n-1]]을 1번 회전하면 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]가 된다. 고유한 원소들로 이루어진 정렬되고 회전된 배열 nums가 주어졌을 때, 이 배열의 최솟값을 구하시오. O(log n) 시간 복잡도의 알고리즘을 작성해야 한다.

코코의 바나나 먹기

코코는 바나나를 먹는 것을 좋아합니다. n개의 바나나 더미가 있으며, i번째 더미에는 piles[i]개의 바나나가 있습니다. 경비원들이 가서 h시간 후에 돌아올 예정입니다. 코코는 시간당 바나나 먹는 속도 k를 정할 수 있습니다. 매 시간마다, 그녀는 어떤 바나나 더미를 선택하고 그 더미에서 k개의 바나나를 먹습니다. 만약 더미에 k개보다 적은 바나나가 있다면, 모두 먹고 그 시간 동안 더 이상의 바나나를 먹지 않습니다. 코코는 천천히 먹고 싶지만, 경비원이 돌아오기 전에 모든 바나나를 먹어야 합니다. 코코가 h시간 내에 모든 바나나를 먹을 수 있는 최소 정수 k를 반환하세요.

2D 행렬 검색

m × n 크기의 정수 행렬이 주어지며, 다음 두 가지 성질을 만족합니다: 각 행은 오름차순으로 정렬되어 있습니다. 각 행의 첫 번째 원소는 이전 행의 마지막 원소보다 큽니다. 정수 target이 주어질 때, target이 행렬에 존재하면 true를, 없으면 false를 반환하세요. O(log(m * n)) 시간 복잡도의 해결책을 작성해야 합니다.

이진 탐색

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 target을 찾는 함수를 작성하세요. target이 존재하면 그 인덱스를 반환합니다. 존재하지 않으면 -1을 반환합니다. O(log n) 시간 복잡도의 알고리즘을 작성해야 합니다.

히스토그램에서 가장 큰 직사각형

정수 배열 heights가 주어지며, 각 원소는 너비가 1인 히스토그램의 막대 높이를 나타냅니다. 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 반환하세요.

자동차 떼

n대의 자동차가 주어진 거리에서 시작하여 목표 거리에 도달하려고 합니다. 두 개의 정수 배열 position과 speed가 주어집니다. 둘 다 길이가 n이며, position[i]는 i번째 자동차의 시작 거리, speed[i]는 i번째 자동차의 시간당 거리 속도입니다. 자동차는 다른 자동차를 추월할 수 없지만, 따라잡은 후 더 느린 자동차의 속도로 나란히 이동할 수 있습니다. 자동차 떼는 단일 자동차 또는 나란히 움직이는 자동차 그룹입니다. 자동차 떼의 속도는 그 안에 있는 모든 자동차 중 최소 속도입니다. 자동차가 목표 거리에서 자동차 떼를 따라잡으면, 그 자동차도 자동차 떼의 일부로 간주됩니다. 목표 지점에 도달하는 자동차 떼의 개수를 반환하세요.

일일 기온

정수 배열 temperatures가 주어지며, 각 요소는 매일의 기온입니다. i번째 날 이후로 더 따뜻한 기온을 얻을 때까지 기다려야 하는 날의 개수를 answer[i]에 넣은 배열 answer를 반환합니다. 그러한 날이 없으면 answer[i]는 0으로 유지합니다.

괄호 생성하기

n개의 괄호 쌍이 주어졌을 때, 올바르게 형성된 괄호의 모든 조합을 생성하는 함수를 작성하시오.

최소값 스택

스택이 푸시, 팝, 탑, 그리고 최소 원소를 상수 시간에 검색하는 기능을 지원하도록 설계하세요. MinStack 클래스를 구현하세요: - MinStack()은 스택 객체를 초기화합니다. - void push(int val)은 요소 val을 스택에 추가합니다. - void pop()은 스택의 맨 위 요소를 제거합니다. - int top()은 스택의 맨 위 요소를 반환합니다. - int getMin()은 스택의 최소 원소를 검색합니다. 모든 함수의 시간 복잡도가 O(1)이어야 합니다.

역폴란드 표기법 계산

산술 표현식을 역폴란드 표기법(RPN)으로 나타낸 문자열 배열 tokens가 주어집니다. 표현식을 계산하여 결과를 나타내는 정수를 반환하세요. 주의: - 유효한 연산자는 '+', '-', '*', '/'입니다. - 각 피연산자는 정수입니다. - 두 정수의 나눗셈은 항상 0을 향해 절단됩니다. - 0으로 나누는 경우는 없습니다. - 입력은 유효한 역폴란드 표기법 산술식입니다. - 답과 모든 중간 계산 결과는 32비트 정수로 표현 가능합니다.

유효한 괄호

괄호 문자 '(', ')', '{', '}', '[', ']'만 포함하는 문자열 s가 주어질 때, 입력 문자열이 유효한지 판단하세요. 입력 문자열이 유효하려면: 1. 열린 괄호는 같은 유형의 괄호로 닫혀야 합니다. 2. 열린 괄호는 올바른 순서로 닫혀야 합니다. 3. 모든 닫힌 괄호는 같은 유형의 해당하는 열린 괄호를 가져야 합니다.

슬라이딩 윈도우 최댓값

정수 배열 nums와 윈도우 크기 k가 주어집니다. 크기 k인 슬라이딩 윈도우가 배열의 맨 왼쪽에서 맨 오른쪽으로 이동합니다. 각 이동마다 윈도우 내의 최댓값을 구해야 합니다. 매번 윈도우가 한 칸씩 오른쪽으로 이동할 때, 각 윈도우의 최댓값들을 반환하세요.

최소 윈도우 부분문자열

길이가 각각 m과 n인 두 문자열 s와 t가 주어졌을 때, t의 모든 문자(중복 포함)를 포함하는 s의 최소 윈도우 부분문자열을 반환하세요. 그러한 부분문자열이 없으면 빈 문자열 ""을 반환하세요. 테스트 케이스는 답이 유일하도록 생성됩니다.

문자열의 순열

두 문자열 s1과 s2가 주어질 때, s2가 s1의 순열을 부분문자열로 포함하면 true를, 그렇지 않으면 false를 반환하세요. 다시 말해, s1의 순열 중 하나가 s2의 부분문자열이면 true를 반환하세요.

가장 긴 반복 문자 치환

문자열 s와 정수 k가 주어집니다. 문자열의 임의의 문자를 다른 대문자로 변경할 수 있으며, 이 작업을 최대 k번 수행할 수 있습니다. 주어진 작업을 수행하여 얻을 수 있는 같은 문자로만 이루어진 가장 긴 부분 문자열의 길이를 반환하세요.

중복 없는 최장 부분 문자열

문자열 s가 주어질 때, 중복된 문자가 없는 최장 부분 문자열의 길이를 구하세요.

주식을 사고팔기 가장 좋은 시점

정수 배열 prices가 주어지며, prices[i]는 i번째 날의 주식 가격입니다. 한 주의 주식을 사는 하나의 날과 그 이후의 다른 날에 파는 날을 선택하여 이득을 최대화하려고 합니다. 이 거래에서 얻을 수 있는 최대 이득을 반환하세요. 이득을 얻을 수 없다면 0을 반환하세요.

빗물 정거량

n개의 음이 아닌 정수로 이루어진 배열이 주어지며, 이는 높이 맵을 나타냅니다. 여기서 각 막대의 너비는 1입니다. 비가 내린 후 얼마나 많은 물을 담을 수 있는지 계산하세요.

물이 가장 많은 용기

길이가 n인 정수 배열 height가 주어집니다. n개의 수직선이 있고, i번째 선의 끝점은 (i, 0)과 (i, height[i])입니다. 두 선이 x축과 함께 만드는 용기가 가장 많은 물을 담을 수 있도록 두 선을 찾으세요. 용기가 담을 수 있는 물의 최대량을 반환하세요. 용기를 기울일 수 없다는 점에 유의하세요.

3Sum

정수 배열 nums가 주어질 때, i != j, i != k, j != k이고 nums[i] + nums[j] + nums[k] == 0을 만족하는 모든 삼중쌍(triplet) [nums[i], nums[j], nums[k]]을 반환하세요. 주의: 결과 집합은 중복된 삼중쌍을 포함하면 안 됩니다.

두 수의 합 II - 입력 배열이 정렬됨

1부터 인덱싱되는 정수 배열 numbers가 비내림차순으로 정렬되어 있을 때, 특정 target 값으로 더해지는 두 수를 찾으세요. 이 두 수를 numbers[index1]과 numbers[index2]라 하면 1 <= index1 < index2 <= numbers.length를 만족합니다. 두 수의 인덱스 index1과 index2를 각각 1씩 증가시킨 정수 배열 [index1, index2]로 반환하세요. 테스트는 정확히 하나의 해가 존재하도록 생성됩니다. 같은 원소를 두 번 사용할 수 없습니다. 당신의 솔루션은 상수 크기의 추가 공간만 사용해야 합니다.

올바른 팰린드롬

문구가 팰린드롬인지 판별하는 방법: 모든 대문자를 소문자로 변환하고 모든 영숫자가 아닌 문자를 제거한 후, 앞에서 읽으나 뒤에서 읽으나 같은지 확인합니다. 영숫자 문자는 문자와 숫자를 포함합니다. 주어진 문자열 s에 대해, 이것이 팰린드롬이면 true를 반환하고, 그렇지 않으면 false를 반환하세요.

최장 연속 수열

정렬되지 않은 정수 배열 nums가 주어질 때, 연속된 정수들로 이루어진 최장 수열의 길이를 반환하세요. O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

문자열 인코딩과 디코딩

문자열 목록을 하나의 인코딩된 문자열로 변환하는 encode 함수와, 인코딩된 문자열을 원래의 문자열 목록으로 복원하는 decode 함수를 설계하세요. 인코딩 포맷은 쉼표나 특수 문자를 포함할 수 있는 임의의 문자열을 정확히 처리할 수 있어야 합니다. 빈 문자열도 포함될 수 있습니다.

유효한 스도쿠

9 x 9 스도쿠 보드가 유효한지 판단하시오. 채워진 셀만 다음 규칙에 따라 유효성을 검사하면 됩니다: 각 행은 1-9의 숫자를 중복 없이 포함해야 합니다. 각 열은 1-9의 숫자를 중복 없이 포함해야 합니다. 9개의 3 x 3 부분 박스 각각은 1-9의 숫자를 중복 없이 포함해야 합니다. 참고: 스도쿠 보드는 부분적으로 채워질 수 있으며 유효하지만 해결 불가능할 수 있습니다. 채워진 셀만 위의 규칙에 따라 검사하면 됩니다.

자신을 제외한 배열의 곱

정수 배열 nums가 주어졌을 때, answer[i]가 nums[i]를 제외한 nums의 모든 원소의 곱이 되도록 하는 배열 answer를 반환하세요. nums의 어떤 prefix 또는 suffix의 곱도 32비트 정수에 맞다고 보장됩니다. O(n) 시간에 작동하는 알고리즘을 작성해야 하며, 나눗셈 연산을 사용할 수 없습니다.

유효한 애너그램

두 문자열 s와 t가 주어졌을 때, t가 s의 애너그램인지 판단하세요. 애너그램은 같은 문자들을 같은 개수로 포함하되 순서만 다른 단어입니다.

두 수의 합

배열에서 합이 목표값이 되는 두 원소의 인덱스를 찾기

애너그램 그룹화

문자열 배열 strs가 주어졌을 때, 애너그램끼리 그룹화하여 반환하세요. 답은 어떤 순서로든 반환할 수 있습니다.

상위 K개 빈도 요소

정수 배열 nums와 정수 k가 주어졌을 때, 가장 자주 나타나는 k개의 요소를 반환하세요. 답은 어떤 순서로든 반환할 수 있습니다. 팔로우업: 알고리즘의 시간 복잡도는 O(n log n)보다 나아야 합니다. 여기서 n은 배열의 크기입니다.

Two Sum

정렬되지 않은 정수 배열 nums 와 정수 target 이 주어질 때, nums[i] + nums[j] == target 인 두 인덱스 [i, j] 를 반환하라. 정답이 정확히 1쌍 존재한다고 가정. 같은 원소를 두 번 사용할 수 없음.