Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
It's too simplified. What if there are two consecutive calls Read(1000) and Read(500). Since original API ReadFromDisk reads next 256 bytes, it's reasonable if Read(int N) behave the same way. In this case you need to track down a position in file and keep buffer that contains remaining of the last returned result.
package com.practice.careercup;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.List;
public class ReadDataInBytes {
public static BlockOfData readData(byte size){
BlockOfData data = new BlockOfData();
if(size > 0){
while (size > data.size()){
data.add(readFromDisk());
}
if(data.size() > size){
data.trim(0, data.size()-size);
}
}
return data;
}
public static class BlockOfData{
List<Byte[]> data = new ArrayList<Byte[]>();
byte size(){
if(!data.isEmpty()){
return (byte) (data.size() * data.get(0).length);
}
return 0;
}
void add(Byte[] e){
data.add(e);
}
void trim(int indexStart, int indexEnd){
if(!data.isEmpty()){
int sizePerBlock = data.get(0).length;
int numberOfBlocks = data.size();
int indexNumberOfBlocks = numberOfBlocks - 1;
int totalBytes = sizePerBlock * numberOfBlocks;
if(indexStart > totalBytes){
//wrong range supplied;
return;
}
int startIndexBlock = getIndexBlock(indexStart, sizePerBlock);;
int endIndexBlock = getIndexBlock(indexEnd, sizePerBlock) - startIndexBlock;
if(startIndexBlock > 0){
for (int i = 0; i < startIndexBlock; i++) {
data.remove(i);
indexNumberOfBlocks--;
}
indexStart = indexStart - (startIndexBlock * sizePerBlock);
//reset the index
startIndexBlock = 0;
}
//index fits in this range of block now the values in this block to start index
Byte[] arr = data.get(startIndexBlock);
for (int j = 0; j < indexStart; j++) {
arr[j] = Byte.MIN_VALUE;
}
if(endIndexBlock < indexNumberOfBlocks){
for (int i = indexNumberOfBlocks; i > endIndexBlock; i--) {
data.remove(i);
}
indexEnd = indexEnd - (endIndexBlock * sizePerBlock);
}
//index fits in this range of block now the values in this block to start index
Byte[] arry = data.get(endIndexBlock);
for (int j = indexEnd; j < sizePerBlock; j++) {
arry[j] = Byte.MIN_VALUE;
}
}
}
protected int getIndexBlock(int index, int sizePerBlock) {
int currentBlockSize = sizePerBlock;
int blockCount = 0;
while(index >= currentBlockSize){
currentBlockSize += sizePerBlock;
blockCount++;
}
return blockCount;
}
}
}
void copy(byte[] dst, int dstFrom, byte[] src, int n) {
for (int s = 0, d=dstFrom; s < n; s++, d++) {
dst[d] = src[s];
}
}
byte[] Read(int sizeInBytes) {
byte[] buffer = new byte[sizeInBytes];
int read = 0, needToRead = sizeInBytes;
byte[] block;
while (needToRead >= 256) {
block = ReadFromDisk();
copy(buffer, read, block, 256);
read += 256;
needToRead -= 256;
}
if (needToRead>0) {
block = ReadFromDisk();
copy(buffer, read, block, needToRead);
}
return buffer;
}
void copy(byte[] dst, int dstFrom, byte[] src, int n) {
for (int s = 0, d=dstFrom; s < n; s++, d++) {
dst[d] = src[s];
}
}
byte[] Read(int sizeInBytes) {
byte[] buffer = new byte[sizeInBytes];
int read = 0, needToRead = sizeInBytes;
byte[] block;
while (needToRead >= 256) {
block = ReadFromDisk();
copy(buffer, read, block, 256);
read += 256;
needToRead -= 256;
}
if (needToRead>0) {
block = ReadFromDisk();
copy(buffer, read, block, needToRead);
}
return buffer;
}
As n can be a number which might not be a multiple of 256, for the remaining r bytes to be read we can get it with one call to ReadFromDisk() and taking the first r bytes
- zingcat April 07, 2015