262가지 문제로 정복하는 코딩 인터뷰 in Java

아드난 아지즈

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

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

2부 자료구조와 알고리즘
4장 기본 자료형
문제 4.1 패리티 계산하기
문제 4.2 비트 스왑
문제 4.3 비트 뒤집기
문제 4.4 같은 무게를 가진 가장 가까운 정수 찾기
문제 4.5 곱셈과 덧셈 없이 x*y 계산하기
문제 4.6 x/y 계산하기
문제 4.7 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 개미수열 문제
문제 6.9 로마 숫자를 10진수로 바꾸기
문제 6.10 유효한 IP 주소 구하기
문제 6.11 사인 곡선 형태로 문자열 작성하기
문제 6.12 반복 길이 부호화로 문자열을 압축ㆍ해제하기
문제 6.13 부분 문자열이 첫 번째로 등장한 위치 찾기

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 재귀를 사용하지 않고 전위 순회 구현하기
문제 9.9 중위 순회에서 k번째 노드 구하기
문제 9.10 후임 노드 구하기
문제 9.11 O(1) 공간을 사용해서 중위 순회 구현하기
문제 9.12 순회한 데이터를 사용해 이진 트리 복원하기
문제 9.13 마커가 포함된 전위 순회를 사용해 이진 트리 복원하기
문제 9.14 이진 트리의 단말 노드에서 연결리스트 구성하기
문제 9.15 이진 트리의 테두리 구하기
문제 9.16 오른쪽 형제 트리 구하기

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 성을 제외한 중복되는 이름 제거하기
문제 13.4 동전으로 만들 수 없는 가장 작은 숫자 구하기
문제 13.5 달력 만들기
문제 13.6 구간 합치기
문제 13.7 구간의 합 구하기
문제 13.8 반복되는 원소가 많은 배열, 정렬하고 나누기
문제 13.9 팀 사진 찍는 날 - 1
문제 13.10 리스트를 빠르게 정렬하는 알고리즘 구현하기
문제 13.11 급여의 한계 구하기

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 n개의 퀸이 서로 공격하지 못하는 상황을 모두 나열하기
문제 15.3 순열 구하기
문제 15.4 멱집합 구하기
문제 15.5 크기가 k인 모든 부분 집합 생성하기
문제 15.6 괄호의 짝이 맞는 문자열 생성하기
문제 15.7 회문 분해하기
문제 15.8 이진 트리 생성하기
문제 15.9 스도쿠 해법 구현하기
문제 15.10 그레이 코드 구하기

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 수직선 쌍에 담을 수 있는 물의 최대 양 구하기