바위타는 두루미

문제 한 줄에 문자열 하나가 쓰여있는 20GB 짜리 파일이 있다고 하자. 이 파일을 정렬하려면 어떻게 해야할지 설명하라. 해결법 면접관이 20GB라는 제한을 준다는 것은 메모리에 모두 올릴 수 없다는 것을 의미한다. 바로 여기서 힌트를 얻는것이다. 가용 메모리의 크기가 x라고 가정했을때 파일을 x로 쪼개고 x 만큼씩 정렬하고 정렬이 끝나면 파일 시스템에 저장할 것이다. 모든 파일의 정렬이 끝나면 하나씩 병합한다. 모든 파일의 병합이 끝나 완벽히 정렬된 파일을 얻는다. 이런 알고리즘을 외부 정렬이라고 한다. 외부링크에 대한 참고링크 https://dudri63.github.io/2019/02/03/algo32/

문제 빈 문자열이 섞여 있는 정렬된 문자열 배열이 주어졌을때, 특정 문자열의 위치르 찾는 메서드를 작성하라. 입력 :"ball' , ["at", "" , "". "", "ball", "", "", "car", "" , "", "", "dad", "", ""] 해결법 빈 문자열이 없었다면 그냥 이진 탐색을 적용하면 될것이다. 이진 탐색을 적용하면서 빈 문자열에 대한 처리를 해주면 해결이 가능할 것이다. mid가 빈 문자열의 위치한 경우 가장 가까운 word의 위치를 mid로 변경해주고, 이진 탐색을 진행해 나가면 될 것같다. def Solution(list, target): if list is None or target=="" or target ==None : return -1 return findTarg..

문제 배열과 비슷하지만 size 메서드가 없는 Listy라는 자료구조가 있다. 여기에는 i 인덱스에 위치한 원소를 O(1) 시간에 알 수 있는 elementAt(i) 메서드가 존재한다. 만약 i가 배열의 범위를 넘어섰다면 -1를 반환한다. (이 때문에 이 자료구조는 양의 정수만 지원한다.) 양의 정수가 정렬된 Listy가 주어졌을때 원소 x의 인덱스를 찾는 알고리즘을 작성하라. 만약 x가 여러번 등장한다면 아무거나 반환하면 된다. 접근법 이것도 이진탐색법을 이용하면 문제가 해결될 것이다. 우선 배열의 size를 알려면 어떻게 하면 될까? 순차적으로 탐색을 할 수도 있지만 1,2,4,8,16 두배씩 늘려서 찾는다면 logN의 시간에 탐색이 가능할 것이다. 인덱스를 두배씩 늘리면서 탐색하다가 elementA..