昨天的F家店面 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

昨天的F家店面

昨天的F家店面# JobHunting - 待字闺中

z*g2012-04-19 07:04

1 楼

给你一个 char* read4096() 的API，一次返回小于或者等于4096个字符。
如果返回是小于4096个字符，意味着已经读到文件末尾 '\0'。
用read4096()这个API，写一个 char* readline() 的function。
要求：
#1 readline（）returns when reading '\n' or '\0';
#2 readline() may be called multiple times on a file, the return value
should be correct.
#3 readline() may return char array longer than 4096 chars.
挣扎了半天，超时了。move on 了。

c*p2012-04-19 07:04

2 楼

版上好像讨论过类似的题目。

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

: 给你一个 char* read4096() 的API，一次返回小于或者等于4096个字符。
: 如果返回是小于4096个字符，意味着已经读到文件末尾 '\0'。
: 用read4096()这个API，写一个 char* readline() 的function。
: 要求：
: #1 readline（）returns when reading '\n' or '\0';
: #2 readline() may be called multiple times on a file, the return value
: should be correct.
: #3 readline() may return char array longer than 4096 chars.
: 挣扎了半天，超时了。move on 了。

z*g2012-04-19 07:04

3 楼

有link吗？

w*x2012-04-19 07:04

4 楼

妈的, 要是15分钟我也超时了
int read4096(FILE* pf);
char buf[4096];
int nLen = 0;
void readline(char* szMem, FILE* pf)
{
assert(szMem);
bool bRet = false;
char* pWrite = szMem;
while(true);
{
int i = 0;
for (; i < nLen; i++)
if (buf[i] == 0 || buf[i] == '\n')
{
bRet = true;
break;
}
int nMove = i+1;
if (!bRet)
nMove = i;
memcpy(pWrite, buf, nMove);
pWrite += nMove;
nLen -= nMove;
memcpy(buf, buf+nMove, nLen);
if (bRet) return;
if (read4096(pf) < 4096)
return;
}
}

p*22012-04-19 07:04

5 楼

你这个signature不对呀。

【在 w****x 的大作中提到】

: 妈的, 要是15分钟我也超时了
: int read4096(FILE* pf);
: char buf[4096];
: int nLen = 0;
: void readline(char* szMem, FILE* pf)
: {
: assert(szMem);
: bool bRet = false;
: char* pWrite = szMem;
: while(true);

c*g2012-04-19 07:04

6 楼

问下电面完多久一般多久有通知阿？

p*22012-04-19 07:04

7 楼

char[] arr=null;
int p=0;

char[] read4096()
{
return new char[0];
}

char[] readLine()
{
StringBuffer sb=new StringBuffer();

NEXT:while(true)
{
if(arr==null)
{
arr=read4096();
if(arr==null)
break;
p=0;
}

while(p{
if(arr[p]!='\0')
sb.append(arr[p]);
else
{
p++;
break NEXT;
}
}

arr=null;
}

return sb.toString().toCharArray();
}

w*x2012-04-19 07:04

8 楼

为啥不对, 说完整啊

【在 p*****2 的大作中提到】

: 你这个signature不对呀。

p*22012-04-19 07:04

9 楼

你看看题目，要返回char*

【在 w****x 的大作中提到】

:
: 为啥不对, 说完整啊

w*x2012-04-19 07:04

10 楼

居然用java, 太没技术含量了

【在 p*****2 的大作中提到】

:
: 你看看题目，要返回char*

p*22012-04-19 07:04

11 楼

java想写对也不容易。我都不知道我这个有没有bug。

【在 w****x 的大作中提到】

:
: 居然用java, 太没技术含量了

w*x2012-04-19 07:04

12 楼

发现一个bug:
int read4096(FILE* pf, char* pBuf);
char buf[4096];
int nLen = 0;
void readline(char* szMem, FILE* pf)
{
assert(szMem);
bool bRet = false;
char* pWrite = szMem;
while(true);
{
int i = 0;
for (; i < nLen; i++)
if (buf[i] == 0 || buf[i] == '\n')
{
bRet = true;
break;
}
int nMove = i+1;
if (!bRet)
nMove = i;
memcpy(pWrite, buf, nMove);
pWrite += nMove;
nLen -= nMove;
memcpy(buf, buf+nMove, nLen);
if (bRet) return;
nLen = read4096(pf, buf);
if (nLen == 0) break;
}
}

f*t2012-04-19 07:04

13 楼

这个是老题了，我以前写过，但没写对

p*22012-04-19 07:04

14 楼

你这个signature要改一下吧。不然没技术含量。

【在 w****x 的大作中提到】

: 发现一个bug:
: int read4096(FILE* pf, char* pBuf);
: char buf[4096];
: int nLen = 0;
: void readline(char* szMem, FILE* pf)
: {
: assert(szMem);
: bool bRet = false;
: char* pWrite = szMem;
: while(true);

b*e2012-04-19 07:04

15 楼

是个烙印问的吗？我同学也遇到过

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

G*e2012-04-19 07:04

16 楼

mark

p*22012-04-19 07:04

17 楼

是烙印。还不断的说这道题特别简单。

【在 b********e 的大作中提到】

: 是个烙印问的吗？我同学也遇到过

w*x2012-04-19 07:04

18 楼

int read4096(FILE* pf, char* pBuf);
char buf[4096];
int nLen = 0;
char* readline(char* szMem, FILE* pf)
{
assert(szMem);
bool bRet = false;
char* pWrite = szMem;
while(true);
{
int i = 0;
for (; i < nLen; i++)
if (buf[i] == 0 || buf[i] == '\n')
{
bRet = true;
break;
}
int nMove = i+1;
if (!bRet)
nMove = i;
memcpy(pWrite, buf, nMove);
pWrite += nMove;
nLen -= nMove;
memcpy(buf, buf+nMove, nLen);
if (bRet) return;
nLen = read4096(pf, buf);
if (nLen == 0) break;
}

return szMem;
}
这题很难啊, 这还简单??

p*22012-04-19 07:04

19 楼

还是不对， function的定义应该是这样的。
char* readline()
算法不难，其实就没有算法的东西。主要是不太确定考点在哪里。当然有一个考点很明
显，其他的考点感觉没太大必要性。一个用PHP的公司，考那些东西我是很想不通。

【在 w****x 的大作中提到】

: int read4096(FILE* pf, char* pBuf);
: char buf[4096];
: int nLen = 0;
: char* readline(char* szMem, FILE* pf)
: {
: assert(szMem);
: bool bRet = false;
: char* pWrite = szMem;
: while(true);
: {

l*a2012-04-19 07:04

20 楼

这题我的印象中在别人google面经里看到过

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

p*22012-04-19 07:04

21 楼

对。好像在guangyi的面经里有。Google出这题make sense。Facebook出就不太懂了。

【在 l*****a 的大作中提到】

: 这题我的印象中在别人google面经里看到过

w*x2012-04-19 07:04

22 楼

char* readline()
楼主可能只是随手写的签名, 这样的签名根本不合理啊, 这是逼着我只能用动态分配内
存并且是在一个函数new,调用函数delete的最搓得设计. 要是就给这个签名首先就说这
个函数签名设计不合理.
是没什么算法的东西, 但是用c写很难写对

j*u2012-04-19 07:04

23 楼

这道题用java写没有意义，因为java 和C/C++ 不同，它屏蔽掉下面的东西
所以用java写只考虑逻辑，不要考虑其他细节。
但是如果是C/C++, 你不考虑就不行。
而且本题给定是 char* readline(), 属于C/C++范畴。
无法想了解编程基本功，比如文件I/O操作，动态内存分配之类的东西。
也奇怪，像F这种公司, 难道有team在做底层的东西?

j*u2012-04-19 07:04

24 楼

如果C/C++的话，会有些问题。
按题意思, readline返回的字符是可以大于4096的
那就是说当在readline内部调用 read4096的时候，
readline 无法预先确认这个文件究竟有多大，所以如果是
java就不用考虑这个问题，只要stringbuffer.append就可以。
但在C/C++, 恐怕要反复重新分配动态数组，同时还要释放。
比如你先申请char *p = new str[4096], 当超过的时候，
你必须要重新分配新的数组，然后拷贝，同时释放旧数组。
应该在一个循环里面解决。
他们考这个够狠的.

p*22012-04-19 07:04

25 楼

就是这个签名

char* readline()楼主可能只是随手写的签名, 这样的签名根本不合理啊, 这是逼着我
只能用动态分配内存并且是在一个函数new,调用函数delete的最搓得设计. 要........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 w****x 的大作中提到】

: char* readline()
: 楼主可能只是随手写的签名, 这样的签名根本不合理啊, 这是逼着我只能用动态分配内
: 存并且是在一个函数new,调用函数delete的最搓得设计. 要是就给这个签名首先就说这
: 个函数签名设计不合理.
: 是没什么算法的东西, 但是用c写很难写对

p*22012-04-19 07:04

26 楼

这题有四个考点如果用java可以避掉两个这要问考官考官允许用java就可以如果考
点不是那两个用java也行由于面试官意志强调这题特别简单易行我要求用j

这道题用java写没有意义，因为java 和C/C 不同，它屏蔽掉下面的东西所以用java
写只考虑逻辑，不要考虑其他细节。但是如果是C/C , 你不考虑就不行。而且本题...
.....
★ Sent from iPhone App: iReader Mitbbs Lite 7.52

【在 j***u 的大作中提到】

: 这道题用java写没有意义，因为java 和C/C++ 不同，它屏蔽掉下面的东西
: 所以用java写只考虑逻辑，不要考虑其他细节。
: 但是如果是C/C++, 你不考虑就不行。
: 而且本题给定是 char* readline(), 属于C/C++范畴。
: 无法想了解编程基本功，比如文件I/O操作，动态内存分配之类的东西。
: 也奇怪，像F这种公司, 难道有team在做底层的东西?

w*x2012-04-19 07:04

27 楼

..
为什么要逼我用stl...
int read4096(FILE* pf, char* pBuf);
char buf[4096];
int nLen = 0;
char* readline(FILE* pf)
{
std::string strRet;
bool bFound = false;
while(true);
{
int i = 0;
for (; i < nLen; i++)
{
if (buf[i] == 0 || buf[i] == '\n')
break;
strRet.append(buf[i]);
}
if (i == nLen)
nLen = 0;
else
{
nLen -= i+1;
memcpy(buf, buf+i+1, nLen);
break;
}
nLen = read4096(pf, buf);
if (nLen == 0) break;
}
char* pRet = new char[strRet.length()+1];
strcpy(pRet, strRet.c_str());
return pRet;
}

【在 p*****2 的大作中提到】

: 就是这个签名
:
: char* readline()楼主可能只是随手写的签名, 这样的签名根本不合理啊, 这是逼着我
: 只能用动态分配内存并且是在一个函数new,调用函数delete的最搓得设计. 要........
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.52

p*22012-04-19 07:04

28 楼

这道题本身是到C语言的题。你想想C怎么做。

【在 w****x 的大作中提到】

:
: ..
: 为什么要逼我用stl...
: int read4096(FILE* pf, char* pBuf);
: char buf[4096];
: int nLen = 0;
: char* readline(FILE* pf)
: {
: std::string strRet;
: bool bFound = false;

w*z2012-04-19 07:04

29 楼

我上一次写C/C++是10年前了，碰到这题，咋整啊？

【在 p*****2 的大作中提到】

:
: 这道题本身是到C语言的题。你想想C怎么做。

c*p2012-04-19 07:04

30 楼

得申个static的变量吧

【在 p*****2 的大作中提到】

:
: 这道题本身是到C语言的题。你想想C怎么做。

p*22012-04-19 07:04

31 楼

没辙呀。我也没想到F会问C语言的问题。class也不让用。

【在 w**z 的大作中提到】

: 我上一次写C/C++是10年前了，碰到这题，咋整啊？

c*p2012-04-19 07:04

32 楼

解TCP的数据包和这个是一个原理吧。

【在 j***u 的大作中提到】

c*p2012-04-19 07:04

33 楼

等我下午有时间的时候写一个

【在 p*****2 的大作中提到】

:
: 没辙呀。我也没想到F会问C语言的问题。class也不让用。

p*22012-04-19 07:04

34 楼

这是一个考点。

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

: 得申个static的变量吧

w*z2012-04-19 07:04

35 楼

靠，F就该问问PHP就好了吗，虽然我也不会。

【在 p*****2 的大作中提到】

:
: 这是一个考点。

p*22012-04-19 07:04

36 楼

变态。好像出这道题的都是烙印。不过这题真没什么意思。要不是C语言的position,
我不知道出这题干嘛。

【在 w**z 的大作中提到】

: 靠，F就该问问PHP就好了吗，虽然我也不会。

d*n2012-04-19 07:04

37 楼

差不多用了30分钟
#define BSZ 4096
char buffer[BSZ];//buffer same size as 4096
int curr=BSZ-1; //current position read in buffer
int eof=0; //eof flag
extern char * read4096();
char *getline(){
char *s; //return string
int i, ssz=0; //size of s
for(;;){
if (!eof){
if (curr==(BSZ-1)) {
strcpy(buffer, read4096()); //read API
curr=0;
if (strlen(buffer)<4096 ) eof=1; //set eof
}
}else break ;
///find the possible end of line or end of EOF
for (i=curr; iif (buffer[i]=='\n' || buffer[i]=='\0') break;
}
ssz+=(i-curr) ; //resizing
s=(char *) realloc(s, sizeof(char)*ssz) ; // resizing
memory
memcpy(s+ssz, buffer+curr, (i-curr) ); // append
curr=i; //reset current position
if(buffer[i]=='\n'|| buffer[i]='\0'){
s[ssz]='\0'; //do last job
return s; //time to returen
}
}
return NULL;
}
~

e*e2012-04-19 07:04

38 楼

public class LineReader {
private int pos = 0;
private List chars = null;

public Character[] readLine() {
if ( chars == null || chars.size() == 0 )
chars = Arrays.asList( read4096() );

List line = new ArrayList();

int i = pos;
while ( i < chars.size() && chars.get(i) != '\n' && chars.get(i) !=
'\0' )
line.add( chars.get(i++) );

if ( chars.get(i) == '\n' ) {
pos = i + 1;
chars = chars.subList( pos, chars.size() );
} else if ( i == chars.size() )
line.addAll( Arrays.asList( new LineReader().readLine() ) );

return line.toArray( new Character[line.size()] );
}

public Character[] read4096() {
return null;
}

public static void main(String[] args) {
new LineReader().readLine();
}

}

H*r2012-04-19 07:04

39 楼

*What if there's multiple '\n'?
*Is there a MAX_LINE_CHAR_NUM given?
Where is the returned memory block supposed to be? Is it dynamically *
allocated in a heap or somewhere appointed before hand?
*how does readline() called when reading a file? For example if there's
several short lines in the file? For example:
"a\nb\nc\nd\n"
would the read4096() return one char* then next time return NULL or
return "a\n" first time and "b\n" and so on?

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

s*f2012-04-19 07:04

40 楼

class MyRead{
static char buf[4096];
char *left, *right;
bool stop;
void read4096(char *buf);
public:
MyRead(){
//memset(buf, 0, 4096);
read4096(buf);
left = buf;
right = buf + 4096;
stop = false;
}
bool Readline(char *dst){
if (stop)
return false;
while (1){
while (left < right){
if (*left != '\n' && *left != '\0')
*dst++ = *left++;
else
break;
}
if (left == right){
read4096(buf);
left = buf;
} else {
if (*left == '\0'){
stop = true;
}
*dst = '\0';
return true;
}
}
return false; //should not reach here;
}
};

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

r*k2012-04-19 07:04

41 楼

有个bug, 当buffer里没有找到'\n'或者'\0'的时候，i的值为BSZ, 这时候你查看
buffer[i]的值，会导致错误的指针。
for (i=curr; i{
if (buffer[i]=='\n' || buffer[i]=='\0') break;
}
...
if(buffer[i]=='\n'|| buffer[i]='\0')
{
s[ssz]='\0'; //do last job
return s; //time to returen
}
不过思路很清晰

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

: 差不多用了30分钟
: #define BSZ 4096
: char buffer[BSZ];//buffer same size as 4096
: int curr=BSZ-1; //current position read in buffer
: int eof=0; //eof flag
: extern char * read4096();
: char *getline(){
: char *s; //return string
: int i, ssz=0; //size of s
: for(;;){

r*k2012-04-19 07:04

42 楼

#define MAX_BUFFER_SIZE 4096
extern char *read4096();
char buffer[MAX_BUFFER_SIZE+1];
char *readline()
{
static int EOF = 0;
static int currentPos = MAX_BUFFER_SIZE;

char *s = NULL;
int i, ssz = 0;

for(;;)
{
if (!EOF)
{
// buffer is not empty, check buffer
if (currentPos != MAX_BUFFER_SIZE)
{
for ( i = currentPos; i < MAX_BUFFER_SIZE; i++)
if (buffer[i] = '\0' || buffer[i] = '\n') break;

int oldsize = (s == NULL) ? 0 : strlen(s);
// copy the buffer into s
ssz += (i - currentPos);
s = (char*) realloc(s, sizeof(char) * (ssz + 1));
memcpy(s + oldsize, buffer + currentPos, i -
currentPos);
s[ssz]='\0';
currentPos = i;
if (i != MAX_BUFFER_SIZE) break;
}
else
{
strcpy(buffer, read4096());
currentPos = 0;
if (strlen(buffer) < 4096)
EOF = 1;
}
}
}
return s;
}

b*n2012-04-19 07:04

43 楼

char* readline()
{
size_t pos=0;
char* first=readline4096();
char* term_pos=0;
char* out=first;
while(!term_pos)
{
term_pos=min(strchr(first,'\n'),strchr(first,'\0'));
if(term_pos)
{
pos+=term_pos-first;
return substr(out, pos);
}
strcat(out,first);
first=readline4096();
}
}

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

l*h2012-04-19 07:04

44 楼

这个题目主要是靠第二点和第三点。
#include
#include
#define BLOCK 40
size_t readblock(FILE *fp, char* buffer){
return fread(buffer,1,BLOCK,fp);
};
size_t readline(FILE *fp, char *buf){
long pos = ftell(fp); // record the currently position
int offset = 0;
int num;
while( num = readblock(fp, buf+offset)){
int i;
for( i=0; ichar c = buf[offset];
if( c == '\0' || c == '\n' ) {
fseek(fp, pos + offset + 1, SEEK_SET);
return offset;
};
};
};
return 0;
};
int main (void){
FILE *fp = fopen("test.txt", "r");
char buf[256];
int num;
while( num = readblock(fp,buf) ) {
buf[num] = 0;
printf("%s",buf);
};
rewind(fp);
printf("\n********\n");
while( num = readline(fp,buf)){
buf[num]=0;
printf("%s %i\n",buf, num);
};
close(fp);
printf("\n");
return 1;
}

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

d*n2012-04-19 07:04

45 楼

谢谢指出。
我正打算写个能运行的。

【在 r****k 的大作中提到】

: #define MAX_BUFFER_SIZE 4096
: extern char *read4096();
: char buffer[MAX_BUFFER_SIZE+1];
: char *readline()
: {
: static int EOF = 0;
: static int currentPos = MAX_BUFFER_SIZE;
:
: char *s = NULL;
: int i, ssz = 0;

j*22012-04-19 07:04

46 楼

http://www.mitbbs.com/article/JobHunting/32043445_0.html

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

: 有link吗？

l*r2012-04-19 07:04

47 楼

我之前fb onsite就挂在这题了，这题在电脑上写都不容易，
在白板上那点空间就更难了。。

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

w*x2012-04-19 07:04

48 楼

是不是F家喜欢搞这种看起来简单做起来难的题啊?