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 로 이동을 한다.

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 번째의 색상을 고를 때에는 칠할 수 있는 두가지 색상중에서 최저가격을 고르면 되는 것이다.

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  만들어서 넣는다. 이런식으로 진행을 한다.

교토대학 오픈캠퍼스

공부에 쓰려고 노트를 사러 학교 매점에 갔다 왔다.

교토대학 상품을 하나도 가지고 있지 않기 때문에(하나 있다. 학교로고가 그려진 이력서, 근데 손으로 써야 해서 나같은 외국인에게는 ㅈㅈ), 교토대학이 적힌 노트라도 사서 공부해볼까.. 해서 갔는데 너무 비쌌다. 일반 노트가 좋은건 120엔 그냥 대충 쓰는건 90엔 정도 하는데, 교토대학 이름 적혀 있는건 250엔 정도했다. 비싸서 안샀다. 90엔짜리 사서 나옴. 학교가 방학 시작했는데, 교토대학 적혀져 있는 쇼핑백 같은거 들고 있는 애들도 많고 고딩들이 너무 많아서 좀 의아했다.

평소에도 관광으로 오는 사람들이 많긴 한데.. 특별히 더 많았다.

오픈캠퍼스 였다.

대충 이런 느낌이었다. 나도 하나 받을까 했는데, 받아봤자 짐만 늘고 그냥 관뒀다.

그리고 교토역으로 신칸센 티켓을 사러 갔다왓다.

PriorityQueue 를 이용한 merge K list.
4:00 AM

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 랑 알고리즘 문제 푸는 사이트 풀고, 복습하고 하는 수 밖에 없을 거 같다.