https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
보통 Tree 는 root 밑에 left와 right 가 있다. 포인터는 이 두개만 있는 것이 보통의 트리인데, 이 문제에서는 left와 right 를 root 를 통하지 않고 바로 next 로 연결하기를 원한다. root의 root 를 통해야 하는 right 에서 left로의 연결도 해야한다. Balanced Binary Tree 라면 쉽게 풀 수 있다. 또 그런 문제도 있었다. 이번문제는 unBalanced Binary Tree 이다.
Balanced 의 경우에는 root의 left의 left의 left 는 null이 나올 때 까지 계속 존재하고, 맨 왼쪽에 있는 TreeNode 에서 left 에서 right 로 직접이동할 수 있는 next 포인터를 추가해줬고, right의 오른쪽에 있는 left TreeNode 에 연결하기 위해서는 root 의 next 를 타고 넘어가 연결을 해줬다.
하지만, 이 문제는 맨 왼쪽의 TreeNode 가 없을 수도 있다. 보통의 방식으로 했다간, NullPointerException이 나올 수 있다. 어제 풀었던 Level-Order Traversal을 응용하기로 했다.
위에서 아래로 level 에 따라서 queue 에 들어가게 되고, 각 level 은 왼쪽에서 오른쪽으로 들어가게 된다. queue 에서 뽑아가면서 next pointer 를 만들어 주면 아무리 TreeNode 가 멀리 떨어져 있어도 포인터를 구축 할 수 있다. iteration으로 가장 가까운 형제노드를 찾는 것은 너무 어렵다.
2015년 8월 21일 금요일
LeetCode Happy Number
https://leetcode.com/problems/happy-number/
숫자의 각 자리 수를 제곱해서 합을 내고, 그것을 또 반복해서 마지막에 1이 나오는 수는 Happy Number 라고 정의를 했다.
이것은 숫자 n을 입력받았을 때, 그 수가 happy 한지 아닌지 판단해 내는 프로그램이다.
기본적인 idea는 간단하다. 각자리 숫자를 n%10 으로 해서 가져오고, 10으로 나눠 맨 뒷자리를 삭제하는 것이다. 두번째 while(n > 0) 은 놓치기 쉬운 edge 부분인데, 100 이라면 10으로 두번 나누면 1이 남고 마지막 것도 해줘야 하기 때문에 n이 0보다 클 동안은 계속 하는 것으로 했다.
이 연산을 할 때 1로 가지 못하고 영원히 연산이 끝나지 않는 경우는 언젠가 한번은 이전에 나왔던 중복된 수가 나오게 된다. 그렇기 때문에 HashSet 을 이용해서 삽입하면서 자동으로 판단할 수 있게 했다.
2015년 8월 18일 화요일
LeetCode Binary Tree Level Order Traversal
https://leetcode.com/problems/binary-tree-level-order-traversal/
tree traversal 에는 여러가지 방법이 있다. 제일 유명한 세가지.
preOrder, inOrder, postOrder 들이 제일 유명하다. 이번에는 tree 의 levelOrder 로 트리를 탐방하는 것이다. 위에서부터 차례대로 읽어가는 것이다.
이 문제는 queue 를 이용해서 풀 수 있더라.
queue 는 뒤로 들어와 앞으로 나가는 FIFO 방식이기 때문에, 맨 앞의 item 의 left와 right를 queue에 넣도록 한다. 그리고 맨 앞의 item 를 빼주면서 List에 추가해줌. queue 에서 item 을 뺄 때 몇개를 뺄 지는 loop 에 들어가기 전에 queue의 사이즈를 알아내도록 한다.
tree traversal 에는 여러가지 방법이 있다. 제일 유명한 세가지.
preOrder, inOrder, postOrder 들이 제일 유명하다. 이번에는 tree 의 levelOrder 로 트리를 탐방하는 것이다. 위에서부터 차례대로 읽어가는 것이다.
이 문제는 queue 를 이용해서 풀 수 있더라.
2015년 8월 16일 일요일
LeetCode Meeting Rooms
https://leetcode.com/problems/meeting-rooms/
이 문제는 좀 재밌었다.
미팅의 시작 시간과 종료시간이 적혀있는 interval 클래스 배열들을 입력 받아서 모든 미팅에 정시간에 제대로 참석할 수 있는지를 판단하는 것이다.
그러기 위해서는 다음 미팅의 start 가 전 미팅의 end 후여야 한다. 즉, 시간이 겹쳐서는 안된다는 것이다.
어떻게 풀어야 할 지 고민했었는데, 내가 생각했던 것은 모든 미팅 시간입력은 분(정수)로 입력이 되기 때문에, HashSet<Integer>를 이용하려고 했었다. start~end 매분을 HashSet 에 싹 다 입력을 하는 것이다. 그럼 다음 interval 의 입력이 있을 때, 혹시 시간이 겹치게 되면 HashSet 에서 false를 return 하는 것을 잡으려고 했는데, 이것은 O(n^2) 시간이 걸리게 된다. interval 배열과 end - start 입력.
푸는 방법으로는 sort를 이용하는 것이 있었다. Comparator 라는게 있어서 좀 재밌는 거 같다. PriorityQueue도 Comparator 를 이용해서 재배치가 가능하고, Arrays.sort 에도 Comparator를 붙일 수 있어서 자기의 기준에 맞춰서 배열을 정렬할 수 있게 되었다.
앞-- Object1, Object 2 ...... --뒤 return이 양수이면 순서를 바꾸고, 음수이면 그대로 둔다.
랜덤하게 입력받는 시간들을 start 시간으로 정렬해서 차례대로 입력을 받도록 한다. end 시간과 다음 미팅의 start 시간을 비교해서 판단을 하게 했다.
LeetCode Reverse Words in a String
https://leetcode.com/problems/reverse-words-in-a-string/
이 문제는 String 을 입력 받아서 스페이스로 구분되어 있는 단어들을 역순으로 재배치 하는 것이다. 물론 단어내의 문자 순서는 그대로 유지하고
이것은 간단했다.
String 을 스페이스로 split 해서 역순으로 다시 붙이면 되는 것이다.
단, 살짝 까다로웠던 부분이 문장 마지막에 스페이스가 붙어 있으면 split 했을 때 배열에 들어가진 않지만, 문장 시작 부분에 스페이스가 붙어 있으면 첫배열에 들어간다는 것이다. 그것도 " " 가 아니라 ""로 들어가게 되어서 디버그 하기 전까지는 계속 오답처리가 되었었다. 그것 빼도는 쉽게 해결
LeetCode Reverse Words in a String 2
https://leetcode.com/problems/reverse-words-in-a-string-ii/
문장을 char 배열로 받아서 단어만 역순으로 재배치 하는 것이다.
해법은 금방 생각 났는데, 뭔가 좀 스마트한 방법은 없을까 고민을 좀 했었는데.. 솔루션을 봐도 특별한 건 없었다.
1. 전체를 뒤집는다. 0번과 n번, 1번과 n-1번 ......
2. 단어만 다시 뒤집는다. 0번과 i번, 1번과 i-1번 ...
완성. index 를 start와 end 두개를 써서 while로 start < end 일 동안 진행되게 했다.
for를 쓸경우, 0번부터 n번까지 돌리면 두번이 swap 되므로, 제자리로 돌아오게 되니. (n-1)/2 로 해서 중간까지만 한번씩 swap 되도록 한다.
LeetCode Binary Tree Upside Down
https://leetcode.com/problems/binary-tree-upside-down/
이 문제는 이해하기 좀 어려웠다. 어떤 규칙으로 되는지 찾는데 시간이 걸렸다.
문제 이름은 upside down 인데 그게 아니라 모든 노드를 시계방향으로 돌리는 것이다.
left 를 root 로 root 를 right 로, right 를 left로.
물론 left, right 에 있는 sub-tree 까지도 따라서 이동해야 한다.
이건 방법이 잘 안떠올라서 solution을 참고했다.
문제를 보고 바로 저런 해결책이 떠오른다면 대단할 것이다.
그리고 내가 본 solution 은 next, prev, cur 이런 변수를 이용해서 이해하기가 더 힘들었다.
그래서 new_left, new_right 를 이용해서 새로 짰고, 결과적으로는 같은게 나왔다.
마지막에 return new_right 를 하는 이유는 마지막으로 cur 이 들어가기 때문이고, node 가 하나밖에 없었다고 가정하면 그것은 right 로 이동을 한다.
2015년 8월 15일 토요일
LeetCode PaintHouse
https://leetcode.com/problems/paint-house/
집이 일렬로 정렬되어 있는데 3가지 색으로 칠해나가는 것이다. 단, 양쪽으로 인접한 두 집의 색상과는 같아서는 안된다. 조건이 좀 특이한데, 각 색마다 가격이 정해져 있는 것이 아니라, 몇번째 집을 어떤 색으로 칠할 건지에 따라 가격이 다른 것 같다. costs[n][3] 배열로 가격이 들어온다.
마지막 집 까지 색칠해서 최저가격을 찾아내는 것이다.
처음에는 트리를 생각 했었다.
첫번째 집을 0,1,2 색상중에 선택할 수 있다고 하면
두번째 집은 1,2/0,2/1,2
세번째 집은 0,2/0,1/1,2/0,1/0,2/0,1 이런식으로 계속 퍼져나가게 된다. 경우의 수가 너무 많게 된다.
잘 생각해 보면 n번째의 집을 색칠하기 위해서는 n-1번째의 집 색상이 아닌 것이 된다. 즉 두가지의 조건밖에 없고, 최저가격을 찾는 것이기 때문에, n 번째의 색상을 고를 때에는 칠할 수 있는 두가지 색상중에서 최저가격을 고르면 되는 것이다.
집이 일렬로 정렬되어 있는데 3가지 색으로 칠해나가는 것이다. 단, 양쪽으로 인접한 두 집의 색상과는 같아서는 안된다. 조건이 좀 특이한데, 각 색마다 가격이 정해져 있는 것이 아니라, 몇번째 집을 어떤 색으로 칠할 건지에 따라 가격이 다른 것 같다. costs[n][3] 배열로 가격이 들어온다.
마지막 집 까지 색칠해서 최저가격을 찾아내는 것이다.
첫번째 집을 0,1,2 색상중에 선택할 수 있다고 하면
두번째 집은 1,2/0,2/1,2
세번째 집은 0,2/0,1/1,2/0,1/0,2/0,1 이런식으로 계속 퍼져나가게 된다. 경우의 수가 너무 많게 된다.
잘 생각해 보면 n번째의 집을 색칠하기 위해서는 n-1번째의 집 색상이 아닌 것이 된다. 즉 두가지의 조건밖에 없고, 최저가격을 찾는 것이기 때문에, n 번째의 색상을 고를 때에는 칠할 수 있는 두가지 색상중에서 최저가격을 고르면 되는 것이다.
LeetCode Permutations
https://leetcode.com/problems/permutations/
Permutations 은 개인적으로 좀 생각하기 어려웠다.
메인 아이디어는 nums 배열로 여러가지 숫자가 들어오는데, 그 안에서 첫번째 아이템을 일단 결과 리스트에 넣는 것이다. 아직 아이템이 하나밖에 없기 때문에, 조합이 1개밖에 나오지 않는다.
nums 의 모든 아이템을 넣어야 한다.
리스트에 들어있던 조합을 꺼내서 그곳에 아이템을 추가한다.
그 아이템을 넣을 곳을 for를 돌려가면서 새로운 결과를 만들어서 리스트에 추가한다.
처음에 1 밖에 없었을 때에는 1이었지만.
두번째 아이템 2를 넣을 때에는 12, 21 두가지의 결과가 나온다.
세번째 아이템 3을 넣을 때에는 12, 21 두가지의 결과를 꺼내와서 새로운 아이템 3을 추가하면서 312, 132, 123 / 321, 231, 213 만들어서 넣는다. 이런식으로 진행을 한다.
Permutations 은 개인적으로 좀 생각하기 어려웠다.
메인 아이디어는 nums 배열로 여러가지 숫자가 들어오는데, 그 안에서 첫번째 아이템을 일단 결과 리스트에 넣는 것이다. 아직 아이템이 하나밖에 없기 때문에, 조합이 1개밖에 나오지 않는다.
nums 의 모든 아이템을 넣어야 한다.
리스트에 들어있던 조합을 꺼내서 그곳에 아이템을 추가한다.
그 아이템을 넣을 곳을 for를 돌려가면서 새로운 결과를 만들어서 리스트에 추가한다.
처음에 1 밖에 없었을 때에는 1이었지만.
두번째 아이템 2를 넣을 때에는 12, 21 두가지의 결과가 나온다.
세번째 아이템 3을 넣을 때에는 12, 21 두가지의 결과를 꺼내와서 새로운 아이템 3을 추가하면서 312, 132, 123 / 321, 231, 213 만들어서 넣는다. 이런식으로 진행을 한다.
2015년 8월 7일 금요일
교토대학 오픈캠퍼스
공부에 쓰려고 노트를 사러 학교 매점에 갔다 왔다.
교토대학 상품을 하나도 가지고 있지 않기 때문에(하나 있다. 학교로고가 그려진 이력서, 근데 손으로 써야 해서 나같은 외국인에게는 ㅈㅈ), 교토대학이 적힌 노트라도 사서 공부해볼까.. 해서 갔는데 너무 비쌌다. 일반 노트가 좋은건 120엔 그냥 대충 쓰는건 90엔 정도 하는데, 교토대학 이름 적혀 있는건 250엔 정도했다. 비싸서 안샀다. 90엔짜리 사서 나옴. 학교가 방학 시작했는데, 교토대학 적혀져 있는 쇼핑백 같은거 들고 있는 애들도 많고 고딩들이 너무 많아서 좀 의아했다.
평소에도 관광으로 오는 사람들이 많긴 한데.. 특별히 더 많았다.
오픈캠퍼스 였다.
대충 이런 느낌이었다. 나도 하나 받을까 했는데, 받아봤자 짐만 늘고 그냥 관뒀다.
그리고 교토역으로 신칸센 티켓을 사러 갔다왓다.
4:00 AM
2015년 8월 4일 화요일
indeed tokyo 1차 skype 면접은 통과
어제 2015/08/03(월) 스카이프로 indeed tokyo 면접을 봤다. 30분 정도.
교수가 논문쓰라고 압박 줘가지고 공부할 여유가 없어서 면접 날짜를 미뤄달라고 했었는데 안된다고 그래서. 원래 일정대로 8/3에 면접을 진행햇다. 문제는 쉬웠다. 어렵진 않았음. 근데 일단 그 회사가 미국에서 시작한 회사이고, 일본자본(Recruit holdings)이 사들인 회사인데, 미국의 IT 문화를 남기고 싶어했고 이 회사를 시발점으로 일본의 다른 IT 기업들이 바뀌길 바라고 있었다. 일본의 IT 회사들은 한국 보다는 낫지만, 역시 미국이나 유럽보다는 좀 뒤쳐져 있다. 기술도 그렇고, 급여도 그렇고, 회사안에서의 자유도 라던가.. 그래서 미국의 시스템을 그대로 남겨두려고 하는 거 같다.
어쨌든, 전형 얘기를 해보자면, 첨에 엔트리 시트를 쓰는데 Recruit holdings 의 global engineer 전형으로 집어넣는다. global engineer 말고도 뭐 web engineer, data analysist 등등 많은데 저것들은 Recruit holdings 본사 소속이 되는 거고, global engineer 는 Recruit holdings 의 자회사 indeed tokyo 소속이 되는 거다. 근데, indeed tokyo 가 연봉이 더 높다. 그래서 일본인들한테 인기가 많은데, 회사 공용어가 영어라서(Rakuten 처럼 공용어를 영어로 했지만, 영어를 쓰지 않는 회사와는 달리 구성원의 반 이상이 일본어를 못하는 외국인이어서 영어를 안쓰면 안된다.) 면접을 영어로 진행한다. 영어 못하는 일본인들은 그냥 탈락.
엔트리 시트에 지원동기, 포부 이런거는 안물어보고, 그냥 할 줄 아는 언어가 무엇인지만 묻는다.
그리고 그 후에 온라인 프로그래밍 테스트를 하게 된다. 2시간 동안 4문제.
첫 2문제는 어렵지 않다. 그냥 생각하는 대로 코드를 짜면 풀리는 것들이다. O(n^2) 으로도 풀리는 것들이 나오고, 뒤의 2문제는 생각하기도 쉽지 않거니와, O(n) 으로 푸는 방법을 생각해야만 하는 문제들이 나왔었다.
난 어찌어찌 해서 4문제 다 풀어서 통과했고.
어제 skype 로 1차 면접을 진행했다. google doc과 비슷한 온라인 코드 공유 사이트를 통해서 문제를 듣고, 스카이프로 얘기를 하면서 코드를 짜면 된다. 오랜만에 영어 말하려니까 입이 안 돌아가서 꽤나 고생했는데, 나중에는 어찌어찌 되었다. 문제는 생각하기 간단한 문제가 나왔는데 역시 O(n^2)으로 풀 수 있는 문제인데 follow up으로 개선하라고 해서 O(n) 으로 풀었다. 좀 아슬아슬 했다. 처음에 생각이 전혀 안나서.. 문제 풀고 시간이 좀 남아서 여러가지 물어보고.. 그리고 끝났다. 어제 6시간 후에 전화로 합격했다고 연락이 왔고, 이번주 목요일에 최종면접 1시간씩 3회 화이트보드 코딩을 한다고 했는데, 내가 논문 때문에 엄청 쫒기고 있어서 날짜를 미뤘다. 담주 화요일에 간다. 도저히 감이 안잡힌다. indeed 라는 단어가 영어 문장에서 자주 쓰이는 것이다 보니 검색이 자꾸 딴게 된다. 미국에서 amazon, google, apple 과 비슷한 레벨은 아닌 거 같다. 코딩 인터뷰 검색해 보면 나오지도 않는다. 어쨌든.. cracking the coding interview 랑 알고리즘 문제 푸는 사이트 풀고, 복습하고 하는 수 밖에 없을 거 같다.
교수가 논문쓰라고 압박 줘가지고 공부할 여유가 없어서 면접 날짜를 미뤄달라고 했었는데 안된다고 그래서. 원래 일정대로 8/3에 면접을 진행햇다. 문제는 쉬웠다. 어렵진 않았음. 근데 일단 그 회사가 미국에서 시작한 회사이고, 일본자본(Recruit holdings)이 사들인 회사인데, 미국의 IT 문화를 남기고 싶어했고 이 회사를 시발점으로 일본의 다른 IT 기업들이 바뀌길 바라고 있었다. 일본의 IT 회사들은 한국 보다는 낫지만, 역시 미국이나 유럽보다는 좀 뒤쳐져 있다. 기술도 그렇고, 급여도 그렇고, 회사안에서의 자유도 라던가.. 그래서 미국의 시스템을 그대로 남겨두려고 하는 거 같다.
어쨌든, 전형 얘기를 해보자면, 첨에 엔트리 시트를 쓰는데 Recruit holdings 의 global engineer 전형으로 집어넣는다. global engineer 말고도 뭐 web engineer, data analysist 등등 많은데 저것들은 Recruit holdings 본사 소속이 되는 거고, global engineer 는 Recruit holdings 의 자회사 indeed tokyo 소속이 되는 거다. 근데, indeed tokyo 가 연봉이 더 높다. 그래서 일본인들한테 인기가 많은데, 회사 공용어가 영어라서(Rakuten 처럼 공용어를 영어로 했지만, 영어를 쓰지 않는 회사와는 달리 구성원의 반 이상이 일본어를 못하는 외국인이어서 영어를 안쓰면 안된다.) 면접을 영어로 진행한다. 영어 못하는 일본인들은 그냥 탈락.
엔트리 시트에 지원동기, 포부 이런거는 안물어보고, 그냥 할 줄 아는 언어가 무엇인지만 묻는다.
그리고 그 후에 온라인 프로그래밍 테스트를 하게 된다. 2시간 동안 4문제.
첫 2문제는 어렵지 않다. 그냥 생각하는 대로 코드를 짜면 풀리는 것들이다. O(n^2) 으로도 풀리는 것들이 나오고, 뒤의 2문제는 생각하기도 쉽지 않거니와, O(n) 으로 푸는 방법을 생각해야만 하는 문제들이 나왔었다.
난 어찌어찌 해서 4문제 다 풀어서 통과했고.
어제 skype 로 1차 면접을 진행했다. google doc과 비슷한 온라인 코드 공유 사이트를 통해서 문제를 듣고, 스카이프로 얘기를 하면서 코드를 짜면 된다. 오랜만에 영어 말하려니까 입이 안 돌아가서 꽤나 고생했는데, 나중에는 어찌어찌 되었다. 문제는 생각하기 간단한 문제가 나왔는데 역시 O(n^2)으로 풀 수 있는 문제인데 follow up으로 개선하라고 해서 O(n) 으로 풀었다. 좀 아슬아슬 했다. 처음에 생각이 전혀 안나서.. 문제 풀고 시간이 좀 남아서 여러가지 물어보고.. 그리고 끝났다. 어제 6시간 후에 전화로 합격했다고 연락이 왔고, 이번주 목요일에 최종면접 1시간씩 3회 화이트보드 코딩을 한다고 했는데, 내가 논문 때문에 엄청 쫒기고 있어서 날짜를 미뤘다. 담주 화요일에 간다. 도저히 감이 안잡힌다. indeed 라는 단어가 영어 문장에서 자주 쓰이는 것이다 보니 검색이 자꾸 딴게 된다. 미국에서 amazon, google, apple 과 비슷한 레벨은 아닌 거 같다. 코딩 인터뷰 검색해 보면 나오지도 않는다. 어쨌든.. cracking the coding interview 랑 알고리즘 문제 푸는 사이트 풀고, 복습하고 하는 수 밖에 없을 거 같다.
피드 구독하기:
글 (Atom)