Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
maybe something like that
void Main()
{
var reader = new DiskReader();
reader.Read(700).Dump();
}
public class DiskReader
{
public byte[] Read(int size)
{
const int maxBytesRead = 256;
var numBlocks = size / maxBytesRead;
var lastBlockSize = size % maxBytesRead;
if (lastBlockSize!=0) numBlocks++;
var buffers = new byte[numBlocks][];
var bytesread = 0;
var lastreadBytes = 0;
var blocsRead = 0;
do
{
var data = ReadFromDisk();
buffers[blocsRead] = data;
blocsRead++;
lastreadBytes = data.Length;
bytesread += lastreadBytes;
} while (lastreadBytes==maxBytesRead && bytesread<size);
var totalbytes = Math.Min(size, bytesread);
var totalBytes = new byte[totalbytes];
var pointer = 0;
for(var i=0; i< buffers.Length && pointer<totalbytes; i++)
{
var block = buffers[i];
if (block!=null)
{
for(var j=0; j<block.Length && pointer<totalbytes; j++)
{
totalBytes[pointer] = block[j];
pointer ++;
}
}
}
return totalBytes;
}
// sample ReadFromDisk impl
private byte[] ReadFromDisk()
{
var result = new byte[256];
for(int i=0; i<255; i++) result[i] = (byte)i;
Console.WriteLine("read 256");
return result;
}
}
May be something like this:
If SizeinBytes is same as 256, then no of calls required to ReadFromDisk is 1
if SizeinBytes is < than 256, then no of calls required to ReadFromDisk is still 1, but return only SizeinBytes of the 256 block
if SizeinBytes is > than 256, then no of calls required to ReadFromDisk is SizeinBytes /256. In this case, remainder may be zero, or may not be. If remainder is not zero then apply rule 2, i.e call ReadFromDisk 1 more time, but return remainder# of chars from the 256 block.
public static byte[] ReadEx(int SizeinBytes)
{
if (SizeinBytes == null || SizeinBytes <= 0)
{
return default(byte[]);
}
int NumberofCalls = SizeinBytes/256;
int RemainderBytes = SizeinBytes % 256;
byte[] ReadBlob = new byte[SizeinBytes];
CallReadFromDisk(NumberofCalls, ref ReadBlob);
if(RemainderBytes > 0)
{
byte[] RemainderBlock = new byte[256];
CallReadFromDisk(1,ref RemainderBlock);
int destoffset = NumberofCalls * 256 * sizeof(byte);
for(int i = 0 ; i < RemainderBytes ; i++)
{
ReadBlob[destoffset++] = RemainderBlock[i];
}
}
return ReadBlob;
}
public static void CallReadFromDisk(int numberofCalls, ref byte[] datablob)
{
int sourceoffset = 0;
int destoffset = 0;
while(numberofCalls > 0)
{
byte[] blob = new byte[256];
blob = ReadFromDisk();
System.Buffer.BlockCopy(blob,sourceoffset*sizeof(byte),datablob,destoffset * sizeof(byte),256);
destoffset += 256;
}
}
extern void ReadFromDisc(char* pOut);
void ReadData(int szInBytes, char* pOut)
{
static char buf[256];
static int bufLoc = 0;
while (szInBytes)
{
if (!bufLoc)
ReadFromDisc(buf);
int toRead = std::min(szInBytes, 256);
toRead = std::min(toRead, 256 - bufLoc);
memcpy(pOut, buf + bufLoc, toRead);
pOut += toRead;
bufLoc = (bufLoc + toRead) % 256;
szInBytes -= toRead;
}
}
How about this solution in c++ ?
The idea is to keep track of the current block read and the current position of the byte read in it. Whenever the last position is greater than 255, read a new block and reset the position to 0.
Continue writing in the output buffer until the number of bytes read is smaller than the number of bytes requested.
No pre-calculations needed.
class DiskReader {
private:
char current_block[256];
int head;
public:
DiskReader() :
// head is initialized to 256 to force reading of new block at start
head(256)
{}
char* Read(int bytes) {
// Make sure number of bytes requested is greater than 0.
// Ask recruiter/engineer what to do in this case
assert(bytes > 0);
char buff = new char[bytes];
int nb_bytes_written = 0;
while (nb_bytes_written < bytes) {
if (head > 255) {
ReadBlock(current_block);
head = 0;
}
buff[nb_bytes_read] = current_block[head];
++head;
++nb_bytes_read;
}
return buff;
}
};
The idea is to read chunks of 256 bytes from the file using ReadFromDisk():
- guilhebl March 25, 2015create 2 buffers: one that will hold the final file result, and other that will read temp results from call to ReadFromDisk
1. Calculate numbers of chunks necessary to read entire file: N/256 where N is the size of file in bytes. Let's call this value S.
2. for i to S call ReadFromDisk and store result in temp buffer[] (256 bytes)
3. Read contents and transfer to bigger buffer until you hit End of File.