-
728x90
지난번 기술 면접을 본 곳에서 2차 면접을 보자는 연락이 왔다.
개인적으로 기술 면접에 아쉬움이 너무 많이 남아서 안되겠지..라고 생각했는데 너무나 감사하게도 다시 한 번 기회를 주셨다.
컬쳐핏 면접일 것이라고 생각하고 예상 질문을 뽑아서 연습했다.
그런데 생각과는 다른 질문들이 많이 나왔고, 이번에도 역시 제대로 답변하지 못한 질문이 많았다고 생각한다.
대답에 아쉬움이 남았던 질문
알고리즘에 대한 질문을 주셨는데 100층의 아파트에서 유리컵을 떨어뜨려 유리 컵이 깨지는 최소 높이를 구하는 문제였다.
내가 대답한 해결 방법은 첫 번째 유리컵이 깨질 때까지 2진탐색을 하며 위층으로 올라간 후, 첫 번째 유리컵이 깨지게 되면 바로 전에 던진 층수의 위층부터 한 칸씩 올라가며 던진다는 아이디어였다.
평균 시도 횟수를 구하라고 하셨는데 너무 긴장하기도 하고 멘탈이 나가서 제대로 계산을 못했다. 그리고 더 나은 방법이 있을까요? 라는 질문에 지금 생각나는 방법은 이게 최선이라고 답하고 말았다....
집에 가는 길에 다른 방법을 생각해봤다.
첫 유리컵이 깨질때까지 2진 탐색으로 올라가다보면 최악의 경우 50번을 떨어뜨려야 최소 높이를 구할 수 있다. 그래서 층수를 4등분부터 계속해서 쪼개보았다.
그 결과 층수를 쪼갤수록 최악의 경우가 줄어들고 평균 시도 횟수도 줄어드는 것을 확인할 수 있었다.
그러나 10등분 부터는 최악의 경우 시도 횟수가 19로 지속되는 것을 확인할 수 있었다.
이게 최선의 방법일까?
이떄 구글링의 도움을 받았다. 찾아본 결과 유리컵이 아닌 계란을 사용한 문제가 이미 오래전부터 공유되었던 것을 알 수 있었다.
최적의 해결 방법은 한 번에 뛰어넘는 층수를 고정하지 않고 가변적으로 가져가는 것이다
생각해보면 층수를 뛰어넘을 때마다 시도 횟수가 1씩 늘어나기때문에 최악의 시도 횟수도 늘어날수밖에 없다. 따라서 뛰어넘는 층수를 매번 1층씩 줄인다면 뛰어넘을 때마다 최대 시도 횟수가 동일해진다. 이걸 식으로 표현하면 다음과 같다.
$$x+(x-1)+(x-2)+\cdots +1\geq100$$
$$\frac{x(x+1)}{2}\geq100$$
x의 최소값을 찾으면 14가 나온다.
따라서 14층, 27층, 39층, ..., 95층, 99층, 100층으로 건너뛰면 된다.
그러면 만약 100층이 최소 높이라고 해도 시도 횟수는 12번이 되고, 최악의 경우도 14번이 된다.
재밌었던 질문
아이스크림 판매량이 증가할 때 상어가 출몰한다는 뉴스의 양이 증가한다고 했을 때 그 둘은 상관관계인가? 아니면 인과관계인가?
처음에 이 질문을 들었을 때에는 상황 예시를 일부러 말이 안되게 주신건가..? 라는 생각이 들어서 혼란이 왔었다. 그러다 대표님과 이야기를 나누면서 두 상황이 독립적인 상황이라는 것을 깨달았고, 두 상황이 상관관계라는 것을 이해했다.
꼬리 질문으로 둘의 관계를 추론해보라는 질문이 나왔다.
대답은 아이스크림 판매량이 높아졌다는 것은 기온이 올라갔다는 이야기이기 때문에 해수면의 온도가 상승해 상어의 출몰이 빈번해졌고 그로인해 뉴스 보도가 많아졌다고 답했다.
만약 상어의 출몰이 해수면의 온도와 상관이 없다면?
상어의 출몰이 온도와 상관이 없다면.. 똑같이 아이스크림의 판매량이 늘은 것은 여름이라는 것이고, 여름에는 바다에 가는 사람이 많기 때문에 사람들에게 상어를 조심하라는 의미로 뉴스 보다가 많아졌을 것이라고 추론했다.
이 질문은 면접 마지막즈음에 나온 질문이었는데 마지막이라 긴장이 풀려서 그런지 좀 대답을 잘한 느낌었다.
긍
- 처음으로 최종 면접까지 갔다.
- 이번에도 부딫혔어!!
- 그래도 답변할 수 있는 부분은 끝까지 답변했다.
부
- 이번에도 망해버렸다....
- 그리고 태도!!!! 진짜 고쳐야 함
- 얼마나 답답했으면 대표님이 자신감있게 대답하라고 하시겠냐고....
728x90