266가지 문제로 정복하는 코딩 인터뷰 in C++

---

1부 면접

1장 면접 준비하기
2장 훌륭한 면접을 위한 전략
3장 면접관 입장에서 바라보기

2부 자료구조와 알고리즘

4장 기본 자료형
문제 4.1 패리티 계산하기
문제 4.2 비트 스왑
문제 4.3 비트 뒤집기
문제 4.4 같은 무게를 가진 가장 가까운 정수 찾기
문제 4.5 곱셈과 덧셈 없이 x*y 계산하기
문제 4.6 산술 연산자 없이 나눗셈 계산하기
문제 4.7 pow(x, y) 계산하기
문제 4.8 숫자 뒤집기
문제 4.9 회문 확인하기
문제 4.10 임의의 숫자를 균등한 확률로 생성하기
문제 4.11 사각형이 겹치는지 확인하기

5장 배열
문제 5.1 네덜란드 국기 문제
문제 5.2 임의의 정수값 증가시키기
문제 5.3 임의의 두 정수값 곱하기
문제 5.4 배열에서 이동하기
문제 5.5 정렬된 배열에서 중복 제거하기
문제 5.6 주식 한 번 사고팔기
문제 5.7 주식 두 번 사고팔기
문제 5.8 대체 연산
문제 5.9 n보다 작은 모든 소수 나열하기
문제 5.10 배열 안의 원소로 순열 구하기
문제 5.11 다음 순열 구하기
문제 5.12 오프라인 데이터 샘플 구하기
문제 5.13 온라인 데이터 샘플 구하기
문제 5.14 임의의 순열 계산하기
문제 5.15 임의의 부분 집합 만들기
문제 5.16 균등하지 않은 임의의 숫자 생성하기
문제 5.17 스도쿠 체크
문제 5.18 2차원 배열에 나선형으로 원소 배치하기
문제 5.19 2차원 배열 회전하기
문제 5.20 파스칼의 삼각형에서 행 계산하기

6장 문자열
문제 6.1 문자열과 정수 상호 전환하기
문제 6.2 밑수 바꾸기
문제 6.3 스프레드시트 열 인코딩 계산하기
문제 6.4 문자열 바꾸고 삭제하기
문제 6.5 회문 확인하기
문제 6.6 문장의 모든 단어 뒤집기
문제 6.7 개미수열 문제
문제 6.8 로마 숫자를 10진수로 바꾸기
문제 6.9 유효한 IP 주소 구하기
문제 6.10 사인 곡선 형태로 문자열 작성하기
문제 6.11 반복 길이 부호화로 문자열을 압축ㆍ해제하기
문제 6.12 부분 문자열이 첫 번째로 등장한 위치 찾기

7장 연결리스트
문제 7.1 두 개의 정렬된 리스트 합치기
문제 7.2 부분 리스트 하나 뒤집기
문제 7.3 사이클이 존재하는지 확인하기
문제 7.4 사이클이 없는 두 리스트가 겹치는지 확인하기
문제 7.5 사이클이 존재하는 두 리스트가 겹치는지 확인하기
문제 7.6 단순 연결리스트에서 노드 삭제하기
문제 7.7 리스트에서 뒤에서 k번째 원소 삭제하기
문제 7.8 정렬된 리스트에서 중복된 원소 삭제하기
문제 7.9 단순 연결리스트에서 오른쪽 원형 시프트 구현하기
문제 7.10 짝수-홀수 병합 구현하기
문제 7.11 단순 연결리스트가 회문인지 확인하기
문제 7.12 리스트의 피벗 구현하기
문제 7.13 리스트로 표현된 정수의 덧셈

8장 스택과 큐
문제 8.1 최댓값 찾는 API로 스택 구현하기
문제 8.2 RPN 수식 계산하기
문제 8.3 문자열이 올바른 형태인지 확인하기
문제 8.4 경로 이름 표준화하기
문제 8.5 노을이 보이는 건물 찾기
문제 8.6 깊이 순서대로 이진 트리의 노드 구하기
문제 8.7 환형 큐 구현하기
문제 8.8 스택을 사용해서 큐 구현하기
문제 8.9 최댓값 API로 큐 구현하기

9장 이진 트리
문제 9.1 이진 트리의 높이가 균형 잡혀 있는지 확인하기
문제 9.2 이진 트리가 대칭인지 확인하기
문제 9.3 이진 트리의 최소 공통 조상 구하기
문제 9.4 노드에 부모를 가리키는 정보가 있을 때 최소 공통 조상 구하기
문제 9.5 이진 트리에서 루트-단말 노드 경로의 합 구하기
문제 9.6 주어진 합에 해당하는 루트-단말 노드 경로 구하기
문제 9.7 재귀를 사용하지 않고 중위 순회 구현하기
문제 9.8 중위 순회에서 k번째 노드 구하기
문제 9.9 후임 노드 구하기
문제 9.10 O(1) 공간을 사용해서 중위 순회 구현하기
문제 9.11 순회한 데이터를 사용해 이진 트리 복원하기
문제 9.12 마커가 포함된 전위 순회를 사용해 이진 트리 복원하기
문제 9.13 이진 트리의 단말 노드에서 연결리스트 구성하기
문제 9.14 이진 트리의 테두리 구하기
문제 9.15 오른쪽 형제 트리 구하기

10장 힙
문제 10.1 정렬된 파일 합치기
문제 10.2 증가했다가 감소하는 배열 정렬하기
문제 10.3 거의 정렬된 배열 정렬하기
문제 10.4 k개의 가까운 별 찾기
문제 10.5 실시간으로 주어진 데이터의 중앙값 찾기
문제 10.6 최대힙에서 가장 큰 원소 k개 구하기

11장 탐색
문제 11.1 정렬된 배열에서 k가 첫 번째로 등장한 위치 찾기
문제 11.2 정렬된 배열에서 인덱스와 값이 같은 엔트리 찾기
문제 11.3 환형으로 정렬된 배열에서 탐색하기
문제 11.4 정수의 제곱근 구하기
문제 11.5 실수의 제곱근 구하기
문제 11.6 정렬된 2차원 배열에서 탐색하기
문제 11.7 최솟값과 최댓값을 동시에 찾기
문제 11.8 k번째로 큰 원소 찾기
문제 11.9 빠진 IP 주소 찾기
문제 11.10 중복된 원소와 빠진 원소 찾기

12장 해시 테이블
문제 12.1 회문 순열 확인하기
문제 12.2 익명의 편지 작성하기
문제 12.3 ISBN 캐시 구현하기
문제 12.4 최적화된 최소 공통 조상 찾기
문제 12.5 배열에서 반복되는 가장 가까운 원소 찾기
문제 12.6 모든 값을 포함하는 가장 작은 부분 배열 구하기
문제 12.7 모든 값을 순차적으로 포함하는 가장 작은 부분배열 구하기
문제 12.8 서로 다른 엔트리를 포함하는 가장 긴 부분배열 구하기
문제 12.9 가장 긴 구간의 길이 찾기
문제 12.10 모든 문자열 분해하기
문제 12.11 콜라츠 추측 테스트
문제 12.12 체스에서 해시 함수 구현하기

13장 정렬
문제 13.1 정렬된 두 배열의 교집합 구하기
문제 13.2 정렬된 두 배열 합치기
문제 13.3 H-인덱스 계산하기
문제 13.4 성을 제외한 중복되는 이름 제거하기
문제 13.5 동전으로 만들 수 없는 가장 작은 숫자 구하기
문제 13.6 달력 만들기
문제 13.7 구간 합치기
문제 13.8 구간의 합 구하기
문제 13.9 반복되는 원소가 많은 배열, 정렬하고 나누기
문제 13.10 팀 사진 찍는 날 - 1
문제 13.11 리스트를 빠르게 정렬하는 알고리즘 구현하기
문제 13.12 급여의 한계 구하기

14장 이진 탐색 트리
문제 14.1 이진 트리가 이진 탐색 트리의 속성을 만족하는지 확인하기
문제 14.2 이진 탐색 트리에서 주어진 값보다 큰 첫 번째 키 찾기
문제 14.3 이진 탐색 트리에서 가장 큰 k개의 원소 찾기
문제 14.4 이진 탐색 트리에서 최소 공통 조상 구하기
문제 14.5 순회한 데이터를 통해 이진 탐색 트리 재구성하기
문제 14.6 세 개의 정렬된 배열에서 가장 가까운 원소 찾기
문제 14.7 a+b√2 꼴의 숫자 나열하기
문제 14.8 정렬된 배열에서 높이가 최소인 이진 탐색 트리 만들기
문제 14.9 이진 탐색 트리의 노드 세 개가 완전히 정렬되어 있는지 확인하기
문제 14.10 범위 확인 문제
문제 14.11 신용 정보 관리 서버 설계하기

15장 재귀
문제 15.1 하노이 타워 문제
문제 15.2 전화번호에 대한 모든 연상기호 계산하기
문제 15.3 n개의 퀸이 서로 공격하지 못하는 상황을 모두 나열하기
문제 15.4 순열 구하기
문제 15.5 멱집합 구하기
문제 15.6 크기가 k인 모든 부분 집합 생성하기
문제 15.7 괄호의 짝이 맞는 문자열 생성하기
문제 15.8 회문 분해하기
문제 15.9 이진 트리 생성하기
문제 15.10 스도쿠 해법 구현하기
문제 15.11 그레이 코드 구하기

16장 동적 프로그래밍
문제 16.1 가능한 점수가 몇 개인지 구하기
문제 16.2 레벤슈타인 거리 구하기
문제 16.3 2차원 배열을 순회할 수 있는 방법의 개수 구하기
문제 16.4 이항계수 구하기
문제 16.5 2차원 배열에서 수열 찾기
문제 16.6 배낭 문제
문제 16.7 BEDBATHANDBEYOND.COM 문제
문제 16.8 삼각형에서 무게가 가장 작은 경로 찾기
문제 16.9 합이 최대가 되도록 동전 선택하기
문제 16.10 계단을 올라가는 방법의 개수 구하기
문제 16.11 텍스트를 예쁘게 배치하기
문제 16.12 감소하지 않는 가장 긴 부분 수열 찾기

17장 그리디 알고리즘과 불변식
문제 17.1 최적의 업무 할당 구하기
문제 17.2 기다리는 시간을 최소화하기
문제 17.3 모든 구간을 커버하기
문제 17.4 세 개의 원소를 합해 원하는 숫자를 얻을 수 있는지 확인하기
문제 17.5 다수 원소 찾기
문제 17.6 주유소 문제
문제 17.7 수직선 쌍에 담을 수 있는 물의 최대 양 구하기
문제 17.8 스카이라인에서 가장 큰 직사각형 구하기

18장 그래프
문제 18.1 미로 찾기
문제 18.2 불 행렬 색칠하기
문제 18.3 닫힌 지역 찾기
문제 18.4 데드락 찾기
문제 18.5 그래프 복제하기
문제 18.6 와이어로 회로 연결하기
문제 18.7 문자열을 다른 문자열로 바꾸기
문제 18.8 팀 사진 찍는 날 - 2

19장 병렬 컴퓨팅
문제 19.1 다중 스레드 사전을 위한 캐시 구현하기
문제 19.2 두 개의 스레드가 동기화되지 않은 채 번갈아 수행되는 경우 분석하기
문제 19.3 두 개의 스레드가 번갈아 수행될 때 동기화 구현하기
문제 19.4 스레드 풀 구현하기
문제 19.5 데드락 피하기
문제 19.6 읽는자-쓰는자 문제
문제 19.7 쓰는 작업에 선호도가 존재할 때 읽는자-쓰는자 문제
문제 19.8 타이머 클래스 구현하기
문제 19.9 콜라츠의 추측 병렬로 확인하기

3부 특정 도메인 문제

20장 설계 문제
문제 20.1 맞춤법 검사 설계
문제 20.2 스테밍 문제의 해법 설계하기
문제 20.3 표절 찾기
문제 20.4 속성에 따른 사용자의 쌍
문제 20.5 저작권 침해를 발견하는 시스템 설계하기
문제 20.6 TEX 설계하기
문제 20.7 검색 엔진 설계하기
문제 20.8 페이지 순위 매기기
문제 20.9 테라 정렬 및 페타 정렬 설계하기
문제 20.10 분산 서비스 조절하기
문제 20.11 확장 가능한 우선순위 시스템 설계하기
문제 20.12 모자이크 사진 만들기
문제 20.13 마일리지 이동 구현하기
문제 20.14 사진 공유 서비스 구현하기
문제 20.15 온라인 광고 시스템 설계하기
문제 20.16 추천 시스템 설계하기
문제 20.17 많은 파일을 분산시킬 수 있는 최적화된 방법 설계하기
문제 20.18 월드 와이드 웹 설계하기
문제 20.19 사진 공유 앱의 하드웨어 비용 추측하기

21장 언어 관련 질문
문제 21.1 참조와 포인터
문제 21.2 값에 의한 전달과 참조에 의한 전달
문제 21.3 스마트 포인터
문제 21.4 반복자
문제 21.5 생성자
문제 21.6 기본 함수
문제 21.7 malloc(), free(), new, delete
문제 21.8 문자열
문제 21.9 push_back()과 emplace_back()
문제 21.10 맵 갱신하기
문제 21.11 빠른 함수 호출
문제 21.12 템플릿 함수
문제 21.13 런타임 타입 식별
문제 21.14 동적 링크

22장 객체 지향 설계
문제 22.1 템플릿 메서드 패턴 vs. 전략 패턴
문제 22.2 옵서버 패턴
문제 22.3 푸시 옵서버 패턴 vs. 풀 옵서버 패턴
문제 22.4 싱글턴 vs. 플라이웨이트
문제 22.5 클래스 어댑터 vs. 객체 어댑터
문제 22.6 생성 패턴
문제 22.7 라이브러리와 설계 패턴

23장 프로그래밍 관련 도구
문제 23.1 버전 관리 시스템의 병합
문제 23.2 버전 관리 시스템의 훅
문제 23.3 스크립트가 더 효율적인가?
문제 23.4 스크립트 언어의 다형성
문제 23.5 의존성 분석
문제 23.6 Ant vs. Maven
문제 23.7 SQL과 NoSQL
문제 23.8 데이터베이스 정규화
문제 23.9 SQL 설계
문제 23.10 IP vs. TCP vs. HTTP
문제 23.11 HTTPS
문제 23.12 DNS

4부 고난도 문제

24장 고난도 문제
문제 24.1 최대공약수 구하기
문제 24.2 배열에 존재하지 않는 가장 작은 양의 정수 찾기
문제 24.3 주식 최대 k번 사고팔기
문제 24.4 하나를 뺀 나머지를 모두 곱했을 때의 최댓값 구하기
문제 24.5 가장 길게 증가하는 부분배열을 구하기
문제 24.6 배열 회전시키기
문제 24.7 룩에게 공격당하는 위치 판별하기
문제 24.8 텍스트 줄 맞추기
문제 24.9 리스트 지핑 구현하기
문제 24.10 게시글 목록 복사하기
문제 24.11 유효한 괄호 중에 가장 긴 부분 문자열 구하기
문제 24.12 최대 슬라이딩 윈도 계산하기
문제 24.13 합당한 보너스 구하기
문제 24.14 길이를 알 수 없는 정렬된 배열에서 탐색하기
문제 24.15 두 개의 정렬된 배열에서 탐색하기
문제 24.16 n이 크고 k가 작은 경우, k번째로 큰 원소 찾기
문제 24.17 한 번만 등장한 원소 찾기
문제 24.18 가장 많은 점을 지나는 선 구하기
문제 24.19 정렬된 이중 연결리스트를 이진 탐색 트리로 변환하기
문제 24.20 이진 탐색 트리를 정렬된 이중 연결리스트로 변환하기
문제 24.21 두 개의 이진 탐색 트리 합치기
문제 24.22 정규표현식 매칭 구현하기
문제 24.23 연산자 조합으로 원하는 결괏값을 만들 수 있는지 확인하기
문제 24.24 역의 개수
문제 24.25 스카이라인 그리기
문제 24.26 눈금이 지워진 비커로 우유의 양 측정하기
문제 24.27 환형 배열에서 최대 부분배열의 합 구하기
문제 24.28 임계 높이 구하기
문제 24.29 최대 2차원 부분배열 찾기
문제 24.30 허프만 코드 구하기
문제 24.31 가둬둔 물의 양 구하기
문제 24.32 일정 횟수 이상 등장한 단어 찾기
문제 24.33 합이 k를 넘지 않는 가장 긴 부분배열 찾기
문제 24.34 고속도로에 구간 추가하기
문제 24.35 차익 거래가 가능한지 테스트하기

---