Goldman Sachs Interview Question
Developer Program EngineersEach font id can be stored in 16 bit number => 2 bytes
The size of each geometric instruction set is 4MB => 2^22 bytes
Assume that the index is 0 bytes (for now) so the offset of last instruction set will begin at 2^22 * (2^16 - 1) => 2^38 - 2^22 > 2^37
So the address of an instruction set would require at least 37 bits, we can keep 5 bytes to store this. So each record is 2 + 5 = 7 bytes. Let's make it 8 bytes to align. Size of index = 2^16 * 2^3 = 2^19. Add this to the address of last geometric instruction (lower bound): 2^37 + 2^19 < 2^38, so address would fit in 5 bytes.
Now you just read and keep index in memory and then use dynamic access to seek to the desired address using 64 bit long.
I would like to maintain a small cache array of the fonts of size say 50 in this case, so in the beginning when i have to search for a font then i will use the same linear search but now will move the font in the top, since it was used recently, in this way I will maintain the top most recently used 50 font s on the top of the list and search with that.
- SiD May 03, 2011