면접 문제
10.5 드문드문 탐색
- 빈 문자열이 섞여 있는 정렬된 문자열 배열이 주어졌을 때, 특정 문자열의 위치를 찾는 메서드를 작성하라.
10.6 큰 파일 정렬
- 한 줄에 문자열 하나가 쓰여 있는 20GB짜리 파일이 있다고 하자. 이 파일을 정렬하려면 어떻게 해야 할지 설명하라.
10.7 빠트린 정수
- 음이 아닌 정수 40억개로 이루어진 입력 파일이 있다. 이 파일에 없는 정수를 생성하는 알고리즘을 작성하라. 단, 메모리는 1GB만 사용할 수 있다.
10.8 중복 찾기
- 1부터 N(≤32,000)까지의 숫자로 이루어진 배열이 있다. 배열엔 중복된 숫자가 나타날 수 있고, N이 무엇인지는 알 수 없다. 사용 가능한 메모리가 4KB일 때, 중복된 원소를 모두 출력하려면 어떻게 할 수 있을까?
10.9 정렬된 행렬 탐색
- 각 행과 열이 오름차순으로 정렬된 MXN 행렬이 주어졌을 떄, 특정한 원소를 찾는 메서드를 구현하라.
10.10 스트림에서의 순위
- 정수 스트림을 읽는다고 하자. 주기적으로 어떤 수 x의 랭킹(x보다 같거나 작은 수의 개수)을 확인하고 싶다. 해당 연산을 지원하는 자료구조와 알고리즘을 구현하라. 수 하나를 읽을 떄마다 호출되는 메서드 track(int x)와, x보다 같거나 작은 수의 개수(x 자신은 제외)를 반환하는 메서드 getRankOfNumber(int x)를 구현하면 된다.
10.11 Peak과 Valley
- 정수 배열에서 ‘peak’이란 현재 원소가 인접한 정수보다 크거나 같을 때를 말하고, ‘valley’란 현재 원소가 인접한 정수보다 작거나 같을 때를 말한다. 예를 들어 [5,8,6,2,3,4,6]이 있으면 [8,6]은 ‘peak’이 되고, [5,2]는 ‘valley’가 된다. 정수 배열이 주어졌을 때, ‘peak’과 ‘valley’가 번갈아 등장하도록 정렬하는 알고리즘을 작성하라.
댓글