인터뷰를 마치고… 궁금해서

  • #153945
    죽쑨이 75.***.243.30 8308

    이차로 in- person 인터뷰를 했는데 망친것 같습니다. 기술적인건 묻지도 않고 대뜸 brain teaser 하나를 주고 답을 말하라는데 당황해서 제대로 답을 못했습니다.

    제가 인터뷰를 나름 많이 해서 그 의도가 뭔지 알지만 그걸로 사람을 평가한다는것이 참 황당했습니다.

    hiring manager, director, developer 이렇게 만나봤는데 hiring manager 와는 전화로 이미 자세히 얘기할 기회가 있어서 그냥 그 사람의 애로사항을 들어주는걸로 끝났고 director 와 developer 가 그런식으로 인터뷰를 끌어가더라구요. developer 는 딱 그 문제 하나만 묻고 그냥 휭 나가고…

    아무튼 죽 쑨 문제는 이거였습니다. He used word ‘touched’ and not ‘opened’.

    복도 한쪽에 100개의 문이 있는데 그 문의 상태는 닫혀지거나 열어진것 두가지 상태로만 되지만 현재 닫혀 있다. 각 문에 1번부터 100번까지 번호가 붙었다. 복도가 시작하는 곳에는 100마리의 원숭이들이 우리에 들어있는데 1번원숭이부터 우리에서 나와서 1,2,3,4,5번의 문을 만졌고, 2번원숭이는 1,2 4, 6, 8, 10 이런식으로 만졌고, 3번은 1, 3,6, 9,이런식, 50번은 1, 50, 이런식, 67번은 1, 67, 이런식으로 문을 만졌는데 그럼 100번째 원숭이가 만졌을때 1번부터 100번까지의 문은 어떤 상태인가?

    • 초보 192.***.94.106

      열린 걸 만지면 닫히고 닫힌 문을 만지면 열린다고 가정을 하면, 어떤 숫자의 약수 개수가 짝수이면 최종 상태는 닫힌 게 되고 어떤 숫자의 약수 개수가 홀수이면 최종 상태는 열린 게 되겠네요. 1은 항상 방문하니까 마지막 상태는 닫힌 게 되고요.

    • 키히 118.***.214.137

      설명으로 미루어 짐작건대 ‘만진다’=’상태를 바꾼다; 열려있으면 닫고 닫혀있으면 열고’인 것 같군요.

      각 번호의 문은 해당 숫자의 소인수 — 영어로 prime factor던가요? 편의상 여기서는 1도 포함시키겠습니다 — 개수가 짝수면 닫혀 있고, 홀수면 열려 있게 됩니다. 예외로 1번 문은 닫혀 있게 됩니다.

    • 아이고 150.***.222.4

      아 전 초보님과 키히님 글 읽어봐도 확 안와닿네요. 본격적으로 풀어봐야겠네요.

    • jason 88.***.235.52

      You could seperate the problem to each case such as 1, prime numbers, and non-prime numbers.

      definition : odd touch is open and even touch is close.

      case 1. the door number 1 will be close since the door had 100 touches that result in close by the definition.

      case 2. the doors having prime number between 1 and 100 will be close by applying prime factorization. i.e prime numbers are 2, 3, 5, 7, 11, and so on. therefore, there will be only 2 touches at each prime door- the very first monkey touched every single door so each prime number will have 2 touches that means close by the definition.

      case 3. the condition of rest of doors having non-prime number will be depending on the number of divisors. i.e. 4: d(n) = 3: (1, 2, 4), 6: d(n) = 4: (1, 2, 3, 6), and so on. Thus, the door number 4 will be open, 6 will be close by the definition. you can figure out of the door 8 in this way. guesss what.

      take it easy..

    • 위에 192.***.75.30

      님께서 잘 설명해 주셨는데 첨언하지만
      예를 들어 8번 문 경우를 따져 보면
      처음엔 닫혀 있고
      1번 원숭이에 의해서 열리게 되고(1,2,3,4,5,6,7,8번 터치)
      2번 원숭이에 의해서 닫히게 되고(1,2,4,6,8번 터치)
      4번 원숭이에 의해서 열리게 되고(1,4,8번 터치)
      8번 원숭이에 의해서 닫히게 됩니다(1,8번 터치)
      그리고 더 이상 8번은 원숭이에 의해서 안 만져지죠.

      9번 같은 경우엔
      1번 원숭이에 의해 열리고(1,2,3,4,5,6,7,8,9번 터치)
      3번 원숭이에 의해 닫히고(1,3,9번 터치)
      9번 원숭이에 의해 열리게 됩니다.(1,9번 터치)
      그리고 9번 문은 더 이상 원숭이에 의해 안 만져지게 되죠.

      8의 약수는 1,2,4,8로 약수의 갯수는 짝수이고
      9의 약수는 1,3,9로 약수의 갯수는 홀수개가 됩니다.

      같은 식으로 따지면 모든 숫자에 대해서 구할 수 있을 겁니다. :)

    • jason 88.***.235.52

      good, but we can probably use a magic number without visiting each door for the next step. here is my magic number x.

      look at below pattern..
      4 9 16 25 36 49 64 81 100
      5 7 9 11 13 15 17 19
      i will assign variable y for the first line, which can be doors left open. the next line will be the sequence of numbers popped out of my magic number, which is variable x.

      For its proof,
      I will look for y for doors open and x that will become my magic numbers

      For the base case, when y > 3
      case 1. y = 4, i got 4: (1, 2, 4)
      case 2. x = 5,
      y = 4+x, i got 9: (1, 3, 9)

      For the inductive case, when y > 9
      x = x + 2
      y = y + x

      consequently, i can get 5, 7, 9, 11, 13, 15, 17, and 19 for xs AND 4, 9, 16, 25, 36, 49, 64, 81, and 100 for ys. thuse, those ys are door number left open and the rest of doors will be left close.

      let me know if i missed anything.

    • IT 24.***.86.243

      저도 잡 찾을 때 할 수 없이 많이 풀어보긴 했지만, 이런 문제를 물어보는 것이 무슨 도움이 되는지… 어찌됐건 관련된 링크 올립니다. 요즘 왠만한 인터뷰 문제는 인터넷 찾아보면 거의 대부분 나오니까요. 첫번째 Door 만 제외하면 같은 문제입니다.

      olimu.com/notes/Monkeys&Doors.htm