Round 1 (Online coding round)

I got a call from Akamai recruiter for a Senior Software Engineer role. Then a face to face interview round was scheduled for testing my DSA skills.

Find minimum required chunks

You are given a function with parameters totalPackets (int) and uploadedChunks(array of pair of integers vector<vector<int,int>). The packets can be grouped into chunks. the size of each chunk increases with the power of 2.

int minChunksRequired(int totalPackets, vector<vector<int,int>>) {}

There will be sequence of packets from [1, totalPackets] and there will be a list of pairs of integers which are the uploaded chunks. Each pair in the uploaded chunks is a starting and ending number for the range of packets that are already uploaded.

Test case

totalPackets = 10

uploadedChunks = [[1,2],[9,10]]

This is our sequence of packets (total packets is 10)
[1,2,3,4,5,6,7,8,9,10]

packets starting from 1 and ending in 2 and packets starting from 9 and ending at 10 are already uploaded. We have to find minimum number of chunks of packets that's required to upload the remainging packets. The size of chunks increase in the power of 2. You can have chunks of size (1, 2, 4, .. 2 ^ n).

in our test case packets 1,2,9,10 are already uploaded. The remaining packets are 3,4,5,6,7,8 (total 6 packets). So we can split them into 2 chunks (3,4,5,6) and (7,8). We have 2 chunks of size 4 and 2.

hence the minimum number of chunks required to 
upload the packets is 2