Karl Coder

면접 대비

시간 제한1초메모리 제한1024 MB

요약
0이 아닌 문자열이 앞에 저장된 2N 크기 버퍼에서 0 바이트 영역의 한 위치씩만 확인해 문자열 길이 N을 찾는다.
난이도

보통10점 중 6점

유형
이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

Karl is an aspiring C programmer, and is excited by the risks and rewards of low-level manual memory management. In the program he currently develops, he stores a string containing NN non-zero bytes into a buffer named "buf". By mistake he accidentally made the buffer 2N2 N bytes in size. The last NN bytes of the buffer consists of only zero-bytes.

Now Karl needs to know the value NN, the size of the string, in a separate part of the program. Traditionally you would recover the length of a string using the strlen-function, which reports the position of the first zero-byte in the provided buffer using a linear scan. However, Karl finds that this is much too slow, and that it defeats the advantage of using C in the first place. Can you help Karl efficiently recover NN without crashing his program?

The contents of the buffer in sample interaction 3 are shown here.

예제3

  1. 예제 1

    입력
    
65

0
    예상 출력
    buf[1]

buf[2]

strlen(buf) = 2

  2. 예제 2

    입력
    
50

0

Segmentation fault (core dumped)
    예상 출력
    buf[1]

buf[5]

buf[7]

  3. 예제 3

    입력
    
78

67

80

67

Too many reads
    예상 출력
    buf[0]

buf[1]

buf[2]

buf[3]

buf[4]