인터뷰 퀴즈!
글쓴이: ssangdog / 작성시간: 금, 2007/11/09 - 7:38오후
계정을 잊을 정도로 오랜만에 찾아 왔네요 계정을 다시 만들어야 했어요 ~_~
퀴즈는 아직도 머리가 아픈데요.
우선 답을 모릅니다 그래서 답을 못 알아내서 죽을 맛입니다,
그래서 더 불쾌했던 구직 인터뷰중의 퀴즈 입니다 ... _ _;
길이를 알수없을 정도로 긴 링크드 리스트의 반복을 찾아내는 방법은?
단 조건은 node compare 만 할수 있는 리소스만 있다!
예를 들면
리스트 노드의 내용이
0->1->2->3->4->5->2->3->6... (2->3)circular!
아무리 생각해도 주어진 조건에선 방법이 없는 듯 한데요.
문제를 잘못 낸것일까요?
학부 졸업한지 어언 5년...
퀵소트의 시간복잡도를 알고 계시는분?
여러모로 짬뽕나는 인터뷰 였어요! ㅠ.ㅜ
Forums:
..
방금 구글에서 sorting에 관한 괜찮은 사이트가 있네요.
각 sorting별로 sorting 되는 과정을 보여주네요.
http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/Database/algorithm/bubble_Sort?action=diff
-----
Do It Now!
-----
Do It Now!
혹시 list의 싸이클이 있냐 없냐를 묻는 문제인가요?
그거라면 빠른노드가 느린노드보다 한발 앞서가지구 둘이 같이 돌기 시작해서 빠른놈이 한바퀴 돌고나서 느린노드를 따라잡으면 싸이클이 있는걸로 판명하는거같은데.. 그 문제를 말씀하시는건진 모르겠네요
퀵소트는 평균적으론 NlogN이고, 최악의 경우에는 n^2 아니었나요
..
혹시 이렇게 하는건 아닐까요?
위에 정렬에 관한 말도 있었으니까.
노드를 처음 부터 끝까지 읽으며 정렬을 한뒤
앞에 노드보다 작은 것이 존재하면 사이클이 존재한다고 말이죠. ^^
-----
Do It Now!
-----
Do It Now!
아, 여기서 빠른놈은..
제 글에 뭔가 내용이 빠졌는데 편집이 안되서 제댓글에 제가 다시 댓글을 다네요;;
빠른노드는 한번에 두 노드씩, 느린노드는 한번에 한노드씩 움직여서 이름을 빠른놈, 느린놈이라 붙인거에요,,
..
아... 그렇군요.
그렇게 쉬운방법이 있었네요 ^^;
역시 공부를 많이 해야 겠어요.
-----
Do It Now!
-----
Do It Now!
,.,,
구글 인터뷰라도 보셨을까요? 그거 Floyd 문제로 알고 있는데, 위의 분 말씀대로 포인터 두개 써서 하나는 2개씩 뛰고
하나는 하나씩 뜁니다. 그러다 두개가 같은 곳을 가리킨다면 cycle 이 있는거죠.
가장 빨리 linked list의 중간을 찾는 문제랑 결론적으로 같습니다.
;;
음 우선 조건중의 하나가 길이를 알수 없는 긴 리스트라 했어요...
그말은 loop 한번에 찾아야 하는 의미 같은데요.
정렬과 관계가 있는 것 같기도 해요! 음!
신생 웹 2.0 회사 인데 저의 주 캐려는 arm 환경에서 멀티미디어 s/w 였어요.
뭐 이래저래 니가 한일은 알고리즘을 연구하는 것보다 가져다 포팅한거 밖에 없네 라고 결론지으니
ioi 두손 들게 되었습니다.
`o'
...
제가 말한 솔루션이 이미 길이가 무한대인 것을 가정하고 있는 겁니다.
O(N)의 time complexity와 O(1)의 space complexity 솔루션으로 가능하다는 말입니다.
포인터 계산하는걸 굳이 따로 따로 할 필요는 없겠죠?
글을 읽다가 조금
글을 읽다가 조금 혼란스러워서 글을 남깁니다.
이라고 하셨는데요..
문제가 "링크드 리스트의 반복" 이라고 하셨느데 이게 circular를 의미하시는 건가요?
답변들은 floyd cycle-finding 알고리즘을 설명하고 계신데..
예로 보여주신것은 linear linked list 안에서 반복..( 중복되는 sub-list 가 존재하는지..)
에 대해서 물으신 것처럼 보여 답변글을 읽다가 잠시 정신이 멍해졌습니다 :oops:
덧. 윗분들이 요약해서 잘 설명해 주셨는데요. 아래 링크로 가시면 linked list에서 cycle(!!) 을 찾는 방법에 대해 정리가 되어 있습니다. (참고 하시기 바랍니다 :wink: )
http://ostermiller.org/find_loop_singly_linked_list.html
-----
Know yourself - Temple of Apollo, Delphi
-----
Know yourself - Temple of Apollo, Delphi
맞습니다. 맞고요...
floyd cycle-finding 문제가 아닌 List 내에서 sublist 의 반복됨을 찾는 것의 의미로 여쭈었던 것 입니다.
아니면 제가 문제를 잘못 이해 한것 이겠죠 ;;
일반적으로 잘 알려진 문제를 물었을 경우가 많으므로 floyd cycle-finding 문제가 맞는 듯 합니다.(제가 문제 이해를 잘못 한 케이스)
그런데 floyd cycle-finding 문제도 저는 생소한데요...
제가 학부때 좀 날라리긴 했지만, 그래도 알고리즘 이름들은 기억들은 하는데 이것은 참으로 생소하네요.
아무튼 여러모로 자극적인 경험이었습니다.
답변에도 감사드립니다.
`o'
감사합니다.
이걸 보고 소팅 알고리즘을 다시 보게되었어요. :)