Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to read chunks of 256 bytes from the file using ReadFromDisk():

create 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.

- guilhebl March 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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; 
	}
}

- tym March 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;   
   }
}

- monacobiscut March 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
   }
}

- tjcbs2 March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
      }
};

- Ben June 14, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More