Google | L3 | Bangalore, India | May 2021 [Rejected]
Anonymous User
1655

Round 1:
Find the smallest missing byte in a 4GB file.
Follow up question:

  1. How is data kept in the file can you explain?
    Ans: In form of common seperation e.g: {0x00, 0xFF .... so on}.
  2. Is there any max length limit?
    Ans: No limit whole file can we just a single word that is 4GB file has 1 byte sequence combination which start from beginning and end at EOF, so answer would be 0x00 in this becasue 0x00 is smallest byte which is missing in that kind of file.
    My Solution:
    Give that 4GB and we need to find smallest missing byte let say it's x:
    Now what can be the range of x, since I'm asssuming x is smallest missing that means everything from 0x00 to x-1 exist in file. Now to maximise the range of x I'm assuming they exist only once in the file how let's calculate the memory used ....

Since 4GB is 2^32 byte:
2^32 = 2^82^82^8*2^8
So max length element will be of 4 byte length.

Now, I said: let assume our in-memory is > 4GB so I can hash all the words in the file and loop around the file starting from 0x00 to all set 4 byte number and find which is missing in the hashMap.

I was rejected wanted to know how to solve this problem?

Comments (4)