fb面试题【转】 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

fb面试题【转】

fb面试题【转】# JobHunting - 待字闺中

h*g2012-02-12 08:02

1 楼

Implement a function
char* readLine();
which returns single lines from a buffer. To read the buffer, you can makes
use of a function
int read(char* buf, int len)
which fills buf with upto len chars and returns the actual number of chars
filled in. Function readLine can be called as many times as desired. If
there is no valid data or newline terminated string available, it must block
. In order to block, it can use read function which in turn will block when
it doesn't have anything to fill the buf.
这题得咋整呢？

h*w2012-02-12 08:02

2 楼

int read(char* buf, int len) returns the number of chars? it's weird, most
time the return value should be same same the len parameter, are you sure
you give the clear explanation about this question?
Anyway, mark and wait answer

c*n2012-02-12 08:02

3 楼

char* readLine(){
static char[BUFSIZE] buf;
static char* ptr = buf;
static int bufSize = 0;
int outputSize = 0;
char *output = NULL;

while (1){
int pos = getNewLinePos(ptr, bufSize);
if (pos > 0){
// found new line char in the buffer
output = realloc(output, outputSize+pos+1); // one extra char for '
\0'
// TODO: check realloc return value
memcpy (output + outputSize, ptr, pos);
output[outputSize + pos] = '\0';
ptr += pos;
bufsize -= pos;
return output;
}else{ // no new line char in the buffer, push all data in buffer
// to the output and read from underneath buffer
// TODO: check if bufSize == 0 (?)
output = realloc(output, outputSize + bufSize);
memcpy(output+outputSize, ptr, bufSize);
ptr = buf;
bufSize = 0;
bufSize = read(ptr, BUF_SIZE);
}
}
}
int getNewLinePos(char *p, int len){
int i = 0;
while (i < len){
if (*(p+i) == '\n')
return (i+1);
i++;
}
return 0;
}

n*s2012-02-12 08:02

4 楼

readline()内部要有一个buffer来缓存以减少IO operation.
assume 该缓存是
static char buff[MAX]
static int size ; // current bond of the data in buffer
static int index ; // index of current reader pointer in the buffer
static char resultBuff[MAX]
另外几个case需要考虑到
(1) there is a '\n' between index and size : just copy them out and return.
and update index.
(2) no '\n' between index and size, now things get complicated
no matter what, need to save the current data between index and max to
resultBuffer, set index to 0
(2.1) if size == MAX
size = read(buf, MAX) ; // call read again.
(2.2) if size < MAX
size = read(buf, MAX);
return readline() // then recursively call

h*g2012-02-12 08:02

5 楼

多谢你的解答觉得 //1 处的outputSize 应该时刻更新吧？
char* readLine(){
static char[BUFSIZE] buf;
static char* ptr = buf;
static int bufSize = 0;
int outputSize = 0;
char *output = NULL;

while (1){
int pos = getNewLinePos(ptr, bufSize);
if (pos > 0){
// found new line char in the buffer
output = realloc(output, outputSize+pos+1); // one extra char for '
\0'
// TODO: check realloc return value
memcpy (output + outputSize, ptr, pos);
output[outputSize + pos] = '\0';
ptr += pos;
bufsize -= pos;
return output;
}else{ // no new line char in the buffer, push all data in buffer
// to the output and read from underneath buffer
// TODO: check if bufSize == 0 (?)
output = realloc(output, outputSize + bufSize); //1
memcpy(output+outputSize, ptr, bufSize);
ptr = buf;
bufSize = 0;
bufSize = read(ptr, BUF_SIZE);
}
}
}
int getNewLinePos(char *p, int len){
int i = 0;
while (i < len){
if (*(p+i) == '\n')
return (i+1);
i++;
}
return 0;
}

【在 c*****n 的大作中提到】

: char* readLine(){
: static char[BUFSIZE] buf;
: static char* ptr = buf;
: static int bufSize = 0;
: int outputSize = 0;
: char *output = NULL;
:
: while (1){
: int pos = getNewLinePos(ptr, bufSize);
: if (pos > 0){

c*n2012-02-12 08:02

6 楼

Thanks for pointing it out. I updated the code.

【在 h*****g 的大作中提到】

: 多谢你的解答觉得 //1 处的outputSize 应该时刻更新吧？
: char* readLine(){
: static char[BUFSIZE] buf;
: static char* ptr = buf;
: static int bufSize = 0;
: int outputSize = 0;
: char *output = NULL;
:
: while (1){
: int pos = getNewLinePos(ptr, bufSize);