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

아드난 아지즈

Adnan Aziz
페이스북에서 연구과학자로 일하고 있다. 텍사스 주립대학교 오스틴 캠퍼스에서 전기, 컴퓨터 공학과의 교수로 재직하며 연구 및 응용 알고리즘 수업을 가르친 적이 있다. 인도 공과 대학 칸푸르에서 학사 학위를 받았고, 캘리포니아 주립대학교 버클리 캠퍼스에서 박사 학위를 받았다. 또한 구글, 퀄컴, IBM, 몇몇 소프트웨어 관련 스타트업 회사에서 일한 경험이 있다. 알고리즘 설계를 하지 않을 때는 주로 세 아이와 시간을 보낸다.

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 속성에따른사용자의쌍<