h**o
发帖数: 548 | 1 usually there are two FAQ about this topic, sometimes readN(char* dst, int
size) is asked during interview, given read4096(char* buf); sometimes
readLine(char* dst) is asked, given read4096(char* buf). I am writing both. |
|
h**o
发帖数: 548 | 2 usually there are two FAQ about this topic, sometimes readN(char* dst, int
size) is asked during interview, given read4096(char* buf); sometimes
readLine(char* dst) is asked, given read4096(char* buf). I am writing both. |
|
n****e
发帖数: 678 | 3 Implement readline using read4096
这道题之前版上有讨论过，不知道有没有标准的解答codes
网上搜了搜，感觉网上贴的codes都不太对。
多谢！ |
|
n****e
发帖数: 678 | 4 Implement readline using read4096
这道题之前版上有讨论过，不知道有没有标准的解答codes
网上搜了搜，感觉网上贴的codes都不太对。
多谢！ |
|
f******4
发帖数: 51 | 5 FG以前都面过的题目，貌似出现概率不低。搜索+论坛考古之后实在没有研究出满意的
答案，
原题如下：
Given API:
int Read4096(char* buf);
It reads data from a file and records the position so that the next time
when it is called it reads the next 4k chars (or the rest of the file,
whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.
有没有大牛甩个python解法 |
|
q********c
发帖数: 1774 | 6 这道题挺有意思，不难但是要考虑几种情况, 试了一下：
int Read(char* buf, int n)
{
int total = 0;
while(true) {
total += Read4096(buf);
if(total == n || total < 4096) { break; }
if(total > n) {
total = n; buf += total;
break;
}
}
return total;
} |
|
f******4
发帖数: 51 | 7 FG以前都面过的题目，貌似出现概率不低。搜索+论坛考古之后实在没有研究出满意的
答案，
原题如下：
Given API:
int Read4096(char* buf);
It reads data from a file and records the position so that the next time
when it is called it reads the next 4k chars (or the rest of the file,
whichever is smaller) from the file.
The return is the number of chars read.
Todo: Use above API to Implement API
"int Read(char* buf, int n)" which reads any number of chars from the file.
有没有大牛甩个python解法 |
|
q********c
发帖数: 1774 | 8 这道题挺有意思，不难但是要考虑几种情况, 试了一下：
int Read(char* buf, int n)
{
int total = 0;
while(true) {
total += Read4096(buf);
if(total == n || total < 4096) { break; }
if(total > n) {
total = n; buf += total;
break;
}
}
return total;
} |
|
t*******e
发帖数: 274 | 9 电面那题，网上看到一种解法，这是正解么？
我有点不明白的是假如只有200bytes, 通过read4096之后是不是应该返回200（<4096）
作为结果?
public class read_4096_bytes {
public int read4096(char[] buf) {
return 4096;
}
public int read(int n, char[] buf) {
int totalRead = 0;
for (int i = 0; i < n / 4096; ++i) {
char[] tbuf = new char[4096];
int tRead = read4096(tbuf);
totalRead += copyTo(buf, totalRead, tbuf, tRead);
if (tRead < 4096) {
return totalRead;
... 阅读全帖 |
|
s*******f
发帖数: 1114 | 10 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... 阅读全帖 |
|
A*****i
发帖数: 3587 | 11 完全裸考，根本没想过G家，奈何人家年年骚扰这都第三年了唉……
感觉G家每次给我出题都不难，结果每次都答不好NND
一个函数叫int Read4096(char * buf)
每次从stream里面读4Kbytes，如果stream小于4K就读到stream末尾，读出结果放在buf
里面
返回值是读了多少bytes，比如buf长度1Kbytes， 那么返回值就是1024
大于4K的stream连续调用就能自动读到底
要求是写一个int ReadBytes(char * buf, num_bytes)
作为Read4096的wrapper，可以在里面直接用Read4096，num_bytes是任意数目，返回值
也是buf的长度，buf就是结果，简单点就是能读任意长度stream的wrapper
挺简单的，结果处理边界和各种判断条件栽了，写了那么久node根本把C++的数组忘干
净了…… |
|
z**********g
发帖数: 209 | 12 给你一个 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 了。 |
|
w****x
发帖数: 2483 | 13 妈的, 要是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, bu... 阅读全帖 |
|
p*****2
发帖数: 21240 | 14 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.app... 阅读全帖 |
|
w****x
发帖数: 2483 | 15 发现一个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);
... 阅读全帖 |
|
w****x
发帖数: 2483 | 16 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);
... 阅读全帖 |
|
w****x
发帖数: 2483 | 17
..
为什么要逼我用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);
... 阅读全帖 |
|
d****n
发帖数: 1637 | 18 差不多用了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 ) e... 阅读全帖 |
|
e****e
发帖数: 418 | 19 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' ) {
... 阅读全帖 |
|
r****k
发帖数: 21 | 20 #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] = '... 阅读全帖 |
|
h********0
发帖数: 74 | 21 how about this, a java version
static int BLOCKSIZE = 4096;
/*
* 内部有个静态文件指针，只能向文件末尾移动,每次只能读取4K的block到buf里，
* 返回读取的字节数（除非到文件尾，否则总是4K）
*/
private int read4096(byte[] buf) {
//this is a fake
return Math.random() > 0.9 ? 1024 : 4096;
}
/**
* read bytes and fill in the contain of 'output'
*
* Testcases:
* 1 just want to read 3k, it < 4k, and the file is enough
* 2 just want to read 5k, 4k < it < 8k, and the file is enough
* 3 want too much, read all rem... 阅读全帖 |
|
z*s
发帖数: 209 | 22 上个月中旬面的试，在Mountain View。由于之前在学校进行了校园面试（2*45分钟）
，所以这一次on site只有三个人，每个人还是45分钟；外加一个人带着吃午饭，没有
反馈。
一、二叉树中给定一个节点，查找按照中序遍历顺序它的后继节点，要求写代码，并给
出复杂度；二叉树中查找中序遍历顺序中的第k个节点，如果每个节点都添加了子树中
节点个数这个变量，如何在插入、删除和旋转时更新这个值（旋转是为了保证logn的复
杂度而要使二叉树保持平衡）。
二、C++概念题，包括虚函数、多继承、私有的构造、析构函数、重载的new运算符等；
以前的project问题；开放性问题，跟网络有关，包括了分组交换、拥塞控制、流控制
、多播等等知识点；最后问了一个编程题，跟quad tree有关，不太常见，但不是很难
，我觉得考查了函数的递归。
三、一道编程题，大意是给定一个类read1，它有一个函数read4096，每次调用它可以
从文件中读取4K个字节，同时移动文件指针4K个位置（若文件中剩余数据不足4K，则读
取剩下的所有数据），这个函数返回实际读取的字节数，int型；要求实现另一个类
read2... 阅读全帖 |
|
g*********s
发帖数: 1782 | 23 use a buffer with size 4k. use read4096 to fill out the buffer. |
|
z*s
发帖数: 209 | 24 我申请的职位是Software Engineer New Grad。
第一个人的寻找后继节点问题，可以使用parent指针；关于二叉树的旋转，只需要描述
一下过程就行了，不需要写代码。面试官当时只让我描述了一种旋转的情况（我只学过
AVL tree，一共有四种旋转的情况）。
关于网络方面的知识，我也很意外；我觉得开放性问题并没有标准答案，而且就我的能
力，当时只能想到一些网络方面的东西，所以就说了；面试官当时也没有提出反对的意
见。
第三个人的问题我是在read2类中定义了一个char buffer[]，表示缓冲区；同时定义两
个整型变量start和end，表示缓冲区中数据的起止位置；read函数每次先从缓冲区中读
取数据；若读完后还不够需要的字节数，再调用read4096，此时要先将读出的数据写入
这个自定义的缓冲区，在读取需要的字节数。 |
|
j***u
发帖数: 16 | 25 如果C/C++的话，会有些问题。
按题意思, readline返回的字符是可以大于4096的
那就是说当在readline内部调用 read4096的时候，
readline 无法预先确认这个文件究竟有多大，所以如果是
java就不用考虑这个问题，只要stringbuffer.append就可以。
但在C/C++, 恐怕要反复重新分配动态数组，同时还要释放。
比如你先申请char *p = new str[4096], 当超过的时候，
你必须要重新分配新的数组，然后拷贝，同时释放旧数组。
应该在一个循环里面解决。
他们考这个够狠的. |
|
H****r
发帖数: 2801 | 26 *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? |
|
f*******t
发帖数: 7549 | 27 F
电面和onsite都是在西雅图本地面的。此分部是在downtown附近租的两层，有近360度
的景观，十分漂亮。分部总共有不到200人，很多是从微软来的，从A挖来的倒不多，原
因不明。午饭质量不错，小分部就不指望有中餐咯。
电面
1. 国人大哥，问了几个常见题，最难的题具体细节记不清了，大概是01矩阵上的DFS，
随便聊了会儿直接拿到onsite。
Onsite
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB
。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单
题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体
的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算
法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
3. 午饭不算正式面试，跟一个呆了六七年的fron... 阅读全帖 |
|
i**********d
发帖数: 105 | 28 求问这个题目怎么做啊？
6. 50岁老美，工作内容是往搜索结果里加与用户隐私信息相关的内容，态度很和蔼。
问了一道老题，给一个一次只能读4k字节的函数int read4096(byte *buff)，要求实现
能读任意字节数的int read(byte *buff, int n_bytes)。他说如果愿意的话可以用
java写，我想了想，java的IO根本不会，还不如用C++呢。本来一年多几乎没碰过C++，
只是面试前在leetcode上拿几道练了下手，写的过程却意外地顺利，写完后跑了一个普
通test case，没看出问题。
他又追问，加一个让文件指针返回到文件头部的函数reset()，要求实现把文件指针移
到任意字节处的函数seek(int n_bytes)。在原来的基础上改改，倒不算难。我发现有
edge case没处理好，他看时间不多就说不用再改，结束了面试。 |
|
i**********d
发帖数: 105 | 29 int nRead = read4096(block_buffer);
这一句block_buffer是新建的。里面应该没有数据吧。你怎么读？
我觉得要读也应该读output吧。 |
|
h********0
发帖数: 74 | 30 int read4096(byte[] block_buffer) 是出题人提供的一个方法, 它每次从文件里读出
4k的数据放到 block_buffer里, 有时候没有4k, 所以需要用方法返回值记录 实际有的
byte number. |
|
r****m
发帖数: 70 | 31
byte[] buffer = new byte[4096];
int bufStart = 0;
int bufSize = 0;
int randomRead(byte output[], int size){
int i = 0;
while(i < size){
if(bufStart == bufSize){
bufSize = read4096(buffer);
bufStart = 0;
if(bufSize == 0) break;
}
for(int j = bufStart; j < bufSize && i < size; j++, i++){
output[i] = buffer[j];
}
}
return i;
... 阅读全帖 |
|
z*********8
发帖数: 2070 | 32 貌似比用Read4096实现readline要容易些 |
|
w*******e
发帖数: 395 | 33 这道题里的block是什么意思？跟那道用read4096()实现readline()有什么区别？
谢谢
as |
|
|
d**********x
发帖数: 4083 | 35 i think the standard way should be to maintain an internal buffer.
what's the solutions from internet? |
|
h**o
发帖数: 548 | 36 贴个我的吧：
#define FOURK 4096
class readbuf{
readbuf(){nsize = 0; ptr = 0;}
char buf[FOURK];
int ptr;
int nsize;
int readN(char*dst, int n);
int readLine(string& s);
};
int readbuf::readN(*dst, int n){
if (!dst) return 0;
int bytes = 0;
while(n>0){
if (nsize==0) {nRead = read4K(buf); nsize = nRread; ptr = 0;}
min = min(n, nsize);
bytes+=memcpy(dst+bytes, buf, min);
ptr+=min; n-=min; nsize-=min;
if (nRead0 or ==0... 阅读全帖 |
|
s**x
发帖数: 7506 | 37 readN is not called anywhere? |
|
s**x
发帖数: 7506 | 38 I see.
"bytes+=memcpy(dst+bytes, buf, min); "
buf should be ptr here? |
|
h**o
发帖数: 548 | 39 yeah. bytes+=memcpy(dst+bytes, buf+ptr, min);
thanks |
|
|
d**********x
发帖数: 4083 | 41 i think the standard way should be to maintain an internal buffer.
what's the solutions from internet? |
|
s**x
发帖数: 7506 | 42 readN is not called anywhere? |
|
s**x
发帖数: 7506 | 43 I see.
"bytes+=memcpy(dst+bytes, buf, min); "
buf should be ptr here? |
|
h**o
发帖数: 548 | 44 yeah. bytes+=memcpy(dst+bytes, buf+ptr, min);
thanks |
|
|
A*****i
发帖数: 3587 | 46 上个月刚被G家问过
这个主要就是考虑边界吧，ptr没有什么tricky的问题好像 |
|
y***n
发帖数: 1594 | 47 readN 和 readLine 都是一个思路吗？ |
|
d*******r
发帖数: 23 | 48
buf
如果Read4096（）已经读了4k，ReadBytes() 每次就读1 byte呢？第二次进ReadBytes(
)，原来没用完的buffer怎么办？难道他允许你用global 或者 static variable？那不
make sense啊。起码不thread safe。是不是题目还有更多条件没说完？ |
|
l***m
发帖数: 16 | 49 1.1 回来搜了一下read4096就有很多讨论了
1.2 对称就是比如1001110100100001->1000010010111001
2.2 假设有一个网格，格点坐标都是整数，像素就是边长为1的方块。例子：给定圆心
是0,0 半径是5，要把圆经过的所有像素找出来。比如(2,2)(2,3)(3,3)(3,2)这4个点
就是像素的4个顶点，这个像素符合被圆经过的条件。 |
|
y***n
发帖数: 1594 | 50 read4096 有没有好的link share 一下，谢谢。 |
|
