Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I wrote the code in Java.
The method signature might be a bit different from what's given in c++ form, but I guess the idea is same.
If you have any idea of improvement, please let me know! Thanks.
String buffer = null;
int p = 0;
public String read(int n) {
if (n < 0) {
return null;
} else if (n == 0) {
return "";
}
StringBuilder sb = new StringBuilder();
while (n > 0) {
// there is (LENGTH - p) chars left in the local buffer
if (buffer == null || p == buffer.length()) {
// no char left in buffer, update buffer
buffer = GoogleApi.read4096();
p = 0;
if (buffer.length() == 0) {
// finish reading the file (no more input chars)
break;
}
} else {
int numChars = buffer.length() - p;
if (numChars >= n) {
sb.append(buffer.substring(p, p + n));
p = p + n;
n = 0;
} else {
sb.append(buffer.substring(p));
p = buffer.length();
n -= numChars;
}
}
}
return sb.toString();
}
since this read API 'int Read(char *buf)' doesn't take any arg to say the number of bytes to be read, should we assume to read the whole file?
Any reasonable API would tell you how many bites to read, after all the buffer may not be large enough to hold the entire file, so I think there shouldn't be any problem if you take another integer input as no. of bytes to be read.
#define FOURKB 4096
int Read(char* buf, int count)
{
int bytesToRead=count,bytesRead=0,min;
while(bytesToRead>0)
{
if(bytesToRead<FOURKB)
{
//last read, take care of the potential buffer overflow
char temp[FOURKB];
bytesRead=Read4096(temp);
min = bytesRead<bytesToRead?bytesRead:bytesToRead;
memcpy(buf,temp, min);
bytesToRead -=min;
break;
}
bytesRead = Read4096(buf);
bytesToRead -= bytesRead;
if(bytesRead<FOURKB)
//file ended
break;
}
return count-bytesToRead;
}
I haven't modified the original Read4096 API and haven't assumed anything about what happens if you try calling Read4096 on a file after Read4096 has read it completely.
sorry to miss that. There is another argument to say how may chars need to be read in Read().
This sln seems to read all the data out of the file, and return the total number of bytes. However, I am not sure whether the question is asking for reading a specified number of bytes ( reads any number of chars from the file).
Anyway, the suggested API doesn't contain any argument taking in the desired number of bytes to read.
int Read4096(char* buf);
char* g_buf[4096];
int g_idxCur = 0;
int g_idxEnd = -1;
int Read(char* buf, int n)
{
//argument validation
if (n==0) return 0;
int idxbuf = 0;
int cReadFromFile = INT_MAX;
//if more to read, call Read4096
while(idxbuf<n && cReadFromFile>0)
{
int cCh = g_idxEnd - g_idxCur + 1;
if(cCh > 0)
{
int cRead = (n-idxbuf < cCh ) ? n-idxbuf : cCh;
for (int i=0; i<cRead; ++i)
{
buf[idxbuf++]=g_buf[g_idxCur++];
}
if (cReadFromFile<4096)
{
break;
}
}
else
{
cReadFromFile = Read4096(g_buf);
g_idxCur = 0;
g_idxEnd = cReadFromFile-1;
}
}
return idxbuf;
}
Another solution:
int ReadChar4096(char *buf);
char g_buf[4096]; //global buffer to save the data read by ReadChar4096.
int ReadChar(char *buf, int n)
{
int n1,n2;
bool isEnd=false;
n1=(int)n/4096;
n2=n%4096;
int pos = 0;
for(int i=0;i<n1;++i)
{
int cRead = ReadChar4096(g_buf);
copy(buf, g_buf, pos, cRead);
pos+=cRead;
if(cRead<4096)
{
isEnd = true;
break;
}
}
if(!isEnd && n2)
{
int cRead = ReadChar4096(g_buf);
int cNeeded = cRead < n2 ? cRead : n2;
copy(buf, g_buf, pos, cNeeded);
pos+=cNeeded;
}
return pos;
}
Given:
int Read4096(char *buf);
Solution:
We Assume that Main Program Has char buf[n] to store Read data
int Read(char *buf, int n){
static char temp[4096], *ptr= temp-1;
int r, l=0;
if(ptr>= temp){
if(n> 4096- ptr){
strcat(buf, ptr);
n-= 4096- ptr;
l+= 4096- ptr;
ptr= temp;
}else{
strncat(buf, ptr, n);
ptr+= n;
l= n;
n= 0;
return l;
}
}
while(n>= 4096){
r= Read4096(temp);
strncat(buf, temp, r);
l+= r;
n= n-r;
}
if(n){
r= Read4096(temp);
strncat(buf, temp, n);
l+= n;
ptr= temp+ n;
}
return l;
}
void copy(char* buf, char*des, int n)
{
if( n <= 0 ) return n;
while( *buf && n > 0 )
{
*des++ = *buf++;
n--;
}
}
int Read(char* buf, int n)
{
int count = 0;
int remain = n;
char* buf = new char[n+1];
buf[n] = '\0';
while( remain <= count )
{
char* buf = new char[4096];
int res = Read4096(tmp);
if( res < 4096 )
{
if( res > remain )
{
copy(tmp, buf+count, remain);
count += remain;
break;
}
else
{
copy(tmp, buf+count, res);
count += res;
buf[count+1] = '\0';
break;
}
}
else
{
if( res > remain )
{
copy(tmp, buf+count, remain);
count += remain;
break;
}
else
{
copy(tmp, buf+count, 4096);
count += 4096;
remain -= 4096;
}
}
}
return count;
}
int Read(char* buf)
{
int cnt=0,total=0;
char tmpbuf[4096]={0};
do
{
cnt = Read4096(tmpbuf);
total = +cnt;
strcat(buf,tmpbuf);
}while(cnt == 4096); // break when we read less than 4096 chars (including 0)
return total;
}
To avoid extra copy cost here, while n >= 4096, Read4096 must be called on the input buffer and not on a temp buffer. each time Read4096 is called, n should be decreased as the read amount (read amont can be less than 4096 if eof reached).
if n gets less than 4906 after some k reads. then an internal buffer should be used otherwise, using Read4096 on input buffer will cause overflow..
int read(char* buf, int n){
int num_it = n / 4096;
int remain = n % 4096;
int total = 0;
while(num_it--){
int num_read = read4096(buf);
if(num_read == 0) break;
buf += num_read;
total += num_read;
}
if(total != n-remain) return total;
char readbuf[4096];
int num_read = read4096(readbuf);
int num_copy = min(num_read, remain);
copy(readbuf, readbuf + num_copy, buf);
total += num_copy;
return total;
}
#include <string.h>
int Read4096(char * buf);
int Read(char * buf, int n) {
static int s = 0; // points to the beginning of the data in internal buffer
static int e = 0; // points to the end of the data in internal buffer
static char buffer[4096] = {0, };
if(!e) // internal buffer empty, read data:
e = Read4096(buffer);
int k = 0; // bytes copied to the client buf
// until we copy all requested data or until Read4096 returns 0, do:
while (n || e) {
// there is enough data in internal buffer, so just copy it and adjust
// s pointer, k and n:
if(n < e - s) {
memcpy(buf, buffer + s, e - s);
s += n;
k += n;
n = 0; // we are done!
}
// client requested mored data than present in the internal buffer.
// 1) copy the data present in the buffer
// 2) obtain more data by calling Read4096
// 3) update s & e pointers, k and n
else if(n >= e -s ) {
// copy data that's present in internal buffer
memcpy(buf + k, buffer + s, e - s);
// adjust pointers, k and n:
k += e - s; // update number of bytes copied to the client buff
n -= e - s; // if n falls to 0, we are done
s = 0; // set s to the beginning of the internal buffer
e = Read4096(buffer); // if Read4096 returns 0, we are done
}
}
return k;
}
#include <string.h>
int Read4096(char * buf);
int Read(char * buf, int n) {
static int s = 0; // points to the beginning of the data in internal buffer
static int e = 0; // points to the end of the data in internal buffer
static char buffer[4096] = {0, };
if(!e) // internal buffer empty, read data:
e = Read4096(buffer);
int k = 0; // bytes copied to the client buf
// until we copy all requested data or until Read4096 returns 0, do:
while (n || e) {
// there is enough data in internal buffer, so just copy it and adjust
// s pointer, k and n:
if(n < e - s) {
memcpy(buf, buffer + s, e - s);
s += n;
k += n;
n = 0; // we are done!
}
// client requested more data than present in the internal buffer.
// 1) copy the data present in the buffer
// 2) obtain more data by calling Read4096
// 3) update s & e pointers, k and n
else if(n >= e -s ) {
// copy data that's present in internal buffer
memcpy(buf + k, buffer + s, e - s);
// adjust pointers, k and n:
k += e - s; // update number of bytes copied to the client buff
n -= e - s; // if n falls to 0, we are done
s = 0; // set s to the beginning of the internal buffer
e = Read4096(buffer); // if Read4096 returns 0, we are done
}
}
return k;
}
int Read4096(char* buf);
int Read(char *buf, int numBytes)
{
if (!buf || numBytes == 0) { return 0; }
static int prevRem = 0;
static char[] prev = null;
if (numBytes <= prevRem)
{
Copy(buf, prev, numBytes);
int newRem = prevRem - numBytes;
char[] temp = new char[newRem];
Copy(temp, prev+numBytes, newRem);
delete[] prev; prev = temp;
prevRem = newRem;
return numBytes;
}
//else
int numBytesRemToRead = numBytes;
Copy(buf, prev, prevRem);
buf += prevRem;
numBytesRemToRead -= prevRem;
int total = prevRem;
prevRem = 0;
if (prev)
{
delete[] prev; prev = null;
}
int bytesRead = -1;
char[] temp = new temp[4096];
while (numBytesToRead > 0 && bytesRead != 0)
{
bytesRead = Read4096(temp);
if (bytesRead > numBytesToRead)
{
copy(buf, temp, numBytesToRead);
prevRem = bytesRead - numBytesToRead;
prev = new char[ prevRem ];
copy(prev, temp + numBytesToRead, prevRem);
total += numBytesToRead;
numBytesToRead = 0;
}
else
{
copy(buf, temp, bytesRead);
buf += bytesRead;
total += bytesRead;
numBytesToRead -= bytesRead;
}
}
delete[] temp;
return total;
}
int Read4096(char* buf);
int Read(char *buf, int numBytes)
{
if (!buf || numBytes == 0) { return 0; }
static int prevRem = 0;
static char[] prev = null;
if (numBytes <= prevRem)
{
Copy(buf, prev, numBytes);
int newRem = prevRem - numBytes;
char[] temp = new char[newRem];
Copy(temp, prev+numBytes, newRem);
delete[] prev; prev = temp;
prevRem = newRem;
return numBytes;
}
//else
int numBytesRemToRead = numBytes;
Copy(buf, prev, prevRem);
buf += prevRem;
numBytesRemToRead -= prevRem;
int total = prevRem;
prevRem = 0;
if (prev)
{
delete[] prev; prev = null;
}
int bytesRead = -1;
char[] temp = new temp[4096];
while (numBytesToRead > 0 && bytesRead != 0)
{
bytesRead = Read4096(temp);
if (bytesRead > numBytesToRead)
{
copy(buf, temp, numBytesToRead);
prevRem = bytesRead - numBytesToRead;
prev = new char[ prevRem ];
copy(prev, temp + numBytesToRead, prevRem);
total += numBytesToRead;
numBytesToRead = 0;
}
else
{
copy(buf, temp, bytesRead);
buf += bytesRead;
total += bytesRead;
numBytesToRead -= bytesRead;
}
}
delete[] temp;
return total;
}
int Read(int toRead, char* buf)
{
int readSoFar = 0;
int remaining = toRead;
char* intBuf = new char[4096];
while (remaining)
{
int current = Read4k(intBuf);
if (current == 0)
break;
int bytesToCopy = remaining >= current ? current : remaining;
memccpy(buf + readSoFar, intBuf, bytesToCopy);
readSoFar += bytesToCopy;
remaining -= bytesToCopy;
}
delete[] intBuf;
return readSoFar;
}
I loved asking this questions in Google interviews, it's a shame those of us that ask it will have to switch to asking something (maybe harder) now that this is discussed here.
FWIW none of the answers above are great. A couple look like they're probably correct but overly complex. In any interview I'd encourage you to focus on reducing a problem to it's essentials and solving it as simply as possible - that's the best way to demonstrate true understanding and minimizing the risk of bugs.
Same thought why is everyone writing such complex code? Now, I am unsure of my solution, is that even correct? How can it be so simple?
```java
public int read(char[] buf, int n) {
if (n <= 0) {
return 0;
}
int readCharCount = 0, chars = n;
while (readCharCount < n) {
int charCount = read4096(buf);
readCharCount += Math.min(n - readCharCount, charCount);
// charCount will be 4096 or < 4096. If less than 4096 we cannot continue after this.
if (charCount < 4096) {
break;
}
}
return readCharCount;
}
```
public int read(char[] buf, int n) {
if (n <= 0) {
return 0;
}
int readCharCount = 0, chars = n;
while (readCharCount < n) {
int charCount = read4096(buf);
readCharCount += Math.min(n - readCharCount, charCount);
// charCount will be 4096 or < 4096. If less than 4096 we cannot continue after this.
if (charCount < 4096) {
break;
}
}
return readCharCount;
}
// I wrote this in Java to prove my logic using ByteBuffers
// Probably could have done similar with char[] or String
// It builds and executes correctly.
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Paths;
import java.nio.file.Path;
import java.nio.BufferOverflowException;
public class MyMain {
public static void main(String[] args) {
// Read input from file to have some test data in buffer
Path path = Paths.get("testfile13.jpg"); // 13.1k
FileChannel fileChannel = null;
try
{
fileChannel = fileChannel.open(path);
}
catch (IOException e)
{
System.out.println("File open failed");
return;
}
ByteBuffer fbuffer = ByteBuffer.allocateDirect(1024 * 50);
int nbytesfromfile = 0;
try
{
nbytesfromfile = fileChannel.read(fbuffer);
fileChannel.close(); // clean up and close file handle
}
catch (IOException e)
{
System.out.println("File read to fbuffer failed");
return;
}
System.out.println("Num bytes read from file = " + nbytesfromfile);
// Allocate more than enough mybuffer to read everything that came in from file
ByteBuffer mybuffer = ByteBuffer.allocate(2 * nbytesfromfile);
// Read data from fbuffer into mybuffer
// Note position is kept by the byteBuffer object and incremented on puts
// Assumes -1 comes back on error and 0 returns when done
int nBytes = 5 * 1024; // 5k as our number of byte we want (could be any N > 0)
int nread = 0;
int total = 0;
// FLIP sets the buffer limit to the current position and moves position to zero
// We need to start at beginning of buffer and have lower levels know when at end.
// the rewind() function does not set the limit, so would not work for us here.
fbuffer.flip();
// Keep reading until we hit end
while(total < nbytesfromfile )
{
nread = myRead(nBytes, fbuffer, mybuffer);
if(nread == -1)
{
System.out.println("ERROR: Failed to read all bytes.");
System.out.println("ERROR: Nbyte read = " + total);
break;
}
total += nread;
}
// Total should equial nbytesfromfile ... if code works as expected
System.out.println("Total number of copied to mybuff = " + total);
return;
}
public static int myRead(int nbytesToRead, ByteBuffer inbuff, ByteBuffer outbuff)
{
// Constraint that we use myRead4k
// Figure out how many calls to myRead4k required
int ncalls = (nbytesToRead / 4096) + 1; // Always need at least 1
int total = 0;
int nread = 0;
for(int i = 0; i<ncalls; i++)
{
nread = myRead4k(inbuff, outbuff);
if(nread == -1)
{
System.out.println("Error in myRead");
return -1;
}
total += nread;
}
// Need to rewind when 4k chunks go further than needed
if(total > nbytesToRead)
{
int nrewind = total - nbytesToRead;
int inpos = inbuff.position();
inbuff.position(inpos-nrewind);
int outpos = outbuff.position();
outbuff.position(outpos-nrewind);
total = nbytesToRead;
}
// else it was either perfect fit or we hit EOF
return total;
}
public static int myRead4k(ByteBuffer inbuff, ByteBuffer outbuff)
{
/* As defined during the interview, this will ready in 4k chunks
* and return less then 4k when hitting final partial chuck of
* input buffer. Number of bytes read is returned and can be
* anything from 0 to 4096.
*/
int nbytesToRead = 4096; // fixed 4k chunks
// Only go to end of input if it does not contain 4096
// Assumes limit of the inbuff has been set to desired stopping point
if(inbuff.remaining() < nbytesToRead)
{
nbytesToRead = inbuff.remaining();
}
// copy
int cnt = 0;
for(; cnt<nbytesToRead; cnt++)
{
// position in both buffers in object instance
try { outbuff.put(inbuff.get()); }
catch (BufferOverflowException e)
{
System.out.println("Error in myRead4k");
System.out.println("Ran past end of output buffer");
return -1;
}
}
return cnt;
}
}
int read_n(char *buf, int len, FILE *fd)
{
static char read[4];
static int read_len = 0;
int copy_len = 0;
if (len == 0) return len;
if (read_len == 0)
read_len = read_4(read, fd);
if (read_len == 0)
return read_len;
if (read_len <= len) {
copy_len = read_len;
read_len = 0;
} else {
copy_len = len;
read_len -= len;
}
memcpy(buf, read, copy_len);
buf += copy_len;
memcpy(read, read+copy_len, read_len);
return (copy_len + read_n(buf, len-copy_len, fd));
}
int read_n(char *buf, int len, FILE *fd)
{
static char read[4];
static int read_len = 0;
int copy_len = 0;
if (len == 0) return len;
if (read_len == 0) {
read_len = read_4(read, fd);
}
if (read_len == 0) {
return read_len;
}
if (read_len <= len) {
copy_len = read_len;
read_len = 0;
} else {
copy_len = len;
read_len -= len;
}
memcpy(buf, read, copy_len);
buf += copy_len;
memcpy(read, read+copy_len, read_len);
return (copy_len + read_n(buf, len-copy_len, fd));
}
int read_n(char *buf, int len, FILE *fd)
{
static char read[4096];
static int read_len = 0;
int copy_len = 0;
if (len == 0) return len;
if (read_len == 0)
read_len = read_4(read, fd);
if (read_len == 0)
return read_len;
if (read_len <= len) {
copy_len = read_len;
read_len = 0;
} else {
copy_len = len;
read_len -= len;
}
memcpy(buf, read, copy_len);
buf += copy_len;
memcpy(read, read+copy_len, read_len);
return (copy_len + read_n(buf, len-copy_len, fd));
}
int read_n(char *buf, int len, FILE *fd)
{
static char read[4];
static int read_len = 0;
int copy_len = 0;
if (len == 0) return len;
if (read_len == 0)
read_len = read_4(read, fd);
if (read_len == 0)
return read_len;
if (read_len <= len) {
copy_len = read_len;
read_len = 0;
} else {
copy_len = len;
read_len -= len;
}
memcpy(buf, read, copy_len);
buf += copy_len;
memcpy(read, read+copy_len, read_len);
return (copy_len + read_n(buf, len-copy_len, fd));
}
we will need to keep an internal buffer as well as a pointer indicating up to which position the internal buffer is used:
Note that the following code most likely won't compile, especially considering I am not entirely sure if memcpy works that way, but the logic should be correct, and you should be able to see what I am trying to achieve with the memcpy calls
- airfang613 August 21, 2012