Interview questions. – 같이 한번 풀어보시죠..

  • #155282
    좝찾는이 69.***.114.41 7559

    오늘 뉴욕 Brooklyn에 있는 한 회사와 phone 인터뷰를 했습니다.
    문제를 3문제밖에 내질 않아서 좀 황당하긴 했습니다.
    오늘 중에 onsite를 할지 안할지를 결정내리겠지요. 떨리는 마음으로 기다리고 있습니다.

    1. difference between call by value and call by reference
    trying to explain some general about them
    and saying java only provides call by value. So
    it’s not easy to write swap function without using wrapper class.
    여기까진 대채로 맞은것 같은데…
    그럼 list를 parameter로 pass하면 어쩌구 하면서
    제가 제대로 다음질문엔 제대로 답변을 못한것 같습니다.

    2. how to accomplish modularify and less coupling
    I answered this question saying
    ” we should use abstraction and encapsulation “
    abstraction: it allows other components to see this api at only a cerntain level of details.
    Encapsulation: it prevents other components from looking at this api at some level of details

    3. write a function that takes array and int x and if array has any two value whose sum is equal to x, then return true
    1. first get first data(a) from arrray
    2. x – a = b
    3. inside the for loop
    try to look for b in array
    if there’s b, return true
    else return false
    4. 위에 알고리즘이 worst O(n) 이라고 얘기했습니다.

    같이 한번 답을 맞춰 보시죠…

    • 흠.. 216.***.112.21

      3번 문제 제시하신 솔루션은 O(n^2) 아닌가요?

    • BR 128.***.114.224

      3번문제, 먼저 Sorting을 한 다음에 양쪽에서 Linear Search를 하면 어떨까요? Sorting방법에 따라서 Complexity는 결정될 것이구요.

    • 원글 69.***.114.41

      처음에 Array에서 random하게 하나의 data(a)를 가져온후, for loop를 n 돌면서 b ( x-a)를 찿으면 되니까, bigO(n)아닌가요? 한개의 for loop로 array에 b가 있는지 없는지를 알수 있으니까. O(n) 아닌가요?

    • 원글 67.***.178.171

      sorry, my bad. it’s O(n^2)

    • IT 69.***.58.47

      BR 말씀이 맞는 것 같네요. 보통 Sort 는 O(n logn) 간주되니 Complexity는 O(n logn).

    • 궁금이 69.***.114.41

      Sort한후에 또 Search해야 하지 않나요? Sort만 끝나면 바로 알수 있나요?
      제 생각에는 어차피 또 Search해야 하기때문에 O(nlogn + n^2) 가 되지 않나요?

    • 흠… 75.***.87.205

      Sorted array 라면 index 를 2개 써서 O(n) 에 가능하네요.

      Array 의 양 끝값 합을 S 라고 한후 X 보다 작으면 앞 index를 옮겨서 S를 업데이트하고, X 보다 크면 뒤 index 를 앞으로 옮겨서 S를 업데이트하면서 찾으면 되네요.

    • 원글 69.***.114.41

      Array는 unsorted이구요. 다시 한번 로직을 생각해보니까 위에 for loop안에 hashtable을 넣어서 key에 각각의 array값을 넣고, value에 diff = x – 각각의 value를 해가면서 if 조건문에 array에서 꺼낸값이 hashtable에 diff가 key값으로 존재하면, 그때 return true를 하면 되니까, O(n)으로 가능할것 같습니다. Hashtable롸직이 빠졌네요 ㅠㅠ