페북 온사이트 코딩퀴즈

  • #3371932
    code 73.***.92.145 1661

    오늘 페이스북(오큘라스) 온사이트에서 코딩퀴즈를 했는데
    잘못 대답한다듯 하여 혹시 아시는 분있으시면 코멘트 부탁드립니다.

    SW engineer 이 아니라 computer vision 분야 경력자이긴 하지만 학부가 CS 아님

    1. A^B
    1.1 complexity: O(n) linear라고 대답했는데, 다른답을 유도 하는 것 같은데, 넘어갔음
    1.2 코딩1
    function(float A, int n){
    if (!–n) return 1;
    return A * function(A.n);
    }

    1.2 스피디 코딩 요구
    제가 좀 헤매기에 유도해서 hint 주었습니다
    :
    LUT[0] = 1;
    LUT[1] = A;
    while(i < n){
    LUT[k] = LUT[k-1]*LUT[k-1];
    k++;
    i *= i;
    }
    if(n-i){
    ….
    LUT[k-1] *= LUT[k-2]*LUT[k-3]….}
    return LUT[k-1];

    2. Anxm 입력에서 ROI(관심 로컬 사각지역) 데이터 summation total
    처음에 좀 이해를 못하기에, 3×3로 example해줌
    **pre-processing 사용하라는 코멘트로 아래와 같이(여러번 시도후)
    for (int y = 1; y< rows; y++) SUM[y][0] = A[y][0] + SUM[y-1][0] ;
    for (int x = 1; x <cols; x++) SUM[0][x] = A[0][x] + SUM[0][x-1]

    for (int y = 1; y < rows; y++)
    for(int x = 1; x < cols; x++)
    SUM[y][x] = A[y][x] + SUM[y-1][x] + SUM[y][x-1] -SUM[y-1][x-1];

    return SUM[roi_y2][roi_x2] – SUM[roi_y1][roi_x2] – SUM[roi_y2][roi_x1] + SUM[roi_y1][roi_x1];

    3.입력이 uchar cByte 인데, each bit에 몇개의 1 있는지 카운팅
    if(cByte & 1)n++;
    if(cByte & 2)n++;
    if(cByte & 4)n++;
    :
    if(cByte & 124)n++;
    8번 하면 카운팅 가능하다고 했는데, oneshot 할수 있냐? lut(룩업테이블)이용하여…
    끝내 대답 못했음
    ******지금 생각해보니 256개 LUT 만들면 한번에 해결될듯 하네요 -.-

    대체적으로 쉬운 코딩퀴즈 였는데, 컴쌰학부가 아니다 보니
    좀 해매긴 했습니다. 좋은 커멘트 부탁 드립니다

    • llll 209.***.188.153

      1. 1.2에서 하신 것처럼 자리수 하나하나 놓고 하면 선형이 아니죠. Int64같이 총 자리수가 고정될 때 선형인데, Exponential 꼴에서 자리수가 고정이라고 가정하는건 좀 협소한 풀이인듯요. 1.2 에서의 복잡도를 요구했을거에요.

      2. Running sum 쓰는 전형적인 접근이고 잘 하신 듯…
      3. 검색해보면 나오는 유명한 문제인데 보통 이렇게 외워서 풀 수 있는 유명한 문제 안 내는데 인터뷰어가 빡대가리인듯요. 아니면 하드웨어쪽에서는 자주 쓰는 비트 연산인가요?

    • code 73.***.92.145

      답장 감사합니다.

      여전히 complexity concept를 잘 모르겠군요. 일반적으로 말하는 유튜브에서 볼땐 쉬운 것 같은데, 1번 경우는 여전히 모르겠군요. 더 심도 있게 공부할 추천 사이트 있으신지요?

      빠르게 계산방식(인터뷰 장소에서 제가 코딩한것임)은 대충 맞는듯 합니다.

      문제는 모든 질문에서 두세번 코드로 점점 improve되어서 최종이 나온 것이라 않좋은 이미지를 줄것 같군요.

      워낙 컴뷰터비젼 알고리즘 수학만 집중 하다보니, 이런 기본적인 것을 잘 모릅니다. 비트연산쪽에서 이런 유명 문제가 있군요.

      하나더 생각나는 질문중에서 2번 코딩후 cpu에 각 어땋게 작동 하는지 물어보더군요. 어떻게 설명해야 할지 궁뜨게 설명을 못하니, 현재 cpu가 점유하고 있는 메모리와 점푸하여 먼지역 메모리접근시 어떻게 되냐고 물어 보길레, 먼지역은 다른코어가 접유할수 있기에 memory unlock 될때까지 기다려야 한다고 대답했음.. 맞죠?

    • 잉여인간 39.***.48.119

      일단 1번은 메모라이즈 쓰면 좋아요
      단순히 값을 계속 구하면 이미 전에 했던 계산을 또하게 되서 낭비가 발생합니다.

      그리고 A^b * A^c = A^(b+c) 인것도 활용하면 로그시간에 해결 가능하구요.

      재귀방식은 처음에 답으로 제시했다가 반복문으로 바꿔주면 가점 줍 니다
      재귀가 보기에 직관적이지만 값이 커지면 스택터지는 경우가 있어서 큰 값이 들어올경우에는 반복문을 쓰면 좋다~ 이러면 좋죠

    • .. 24.***.9.125

      3번은 uchar면 table도 가능하지만,
      큰 type에서는 Brian Kernighan 방법을 쓰면 ‘1’외 갯수만큼의 iteration으로 풀 수 있겠네요.
      cnt = 0;
      while (n)
      n = n & (n-1); // 가장 덜 중요한 (LSB) ‘1’을 지우는 과정. loop cnt
      ++cnt;

    • K 149.***.62.131

      1번은 logN 을 원했을 거예요.
      반씩 쪼개서 대칭을 이용하기 그런거요.
      컴플렉시티가 그렇게 어려운 건 아닌데 이해하는 사람과 안 하는 사람과 솔류션의퀄리티가 달라서요.
      요즘은 워낙 큰 데이타셋을 가지고 일해서 스케일 되냐 안 되냐가 너무 중요해서요.
      보통 인터뷰에서 모르면 바로 필터되는 그런 문제가 됩니다.

      • code 174.***.40.21

        아 이제 감이 오는군요. 감사합니다.
        제가 스피팅하게 처리하는 코딩이 결국 logN 이었군요.
        (이미계산한것을 재 사용하는 개념으로 코뎅하려 한것이 결국 log N)