Qualcomm Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
H representing 0
T representing 1
Your string "HTTHHTTT"(8 bytes of string) becomes a single byte 01100111 !! by which u save 7 bytes of data. and u can achieve maximum throughput..!!
Another idea, compress continuous duplicated chars.
e.g. compress "HHHHTTHTHTHT..." to "H3T1HTHTHT...".
Or using the way eugene.yarovio said and then compress.
Well, why the need to compress
HTHTHTHTHT to H1T1H1T1H1T1.. , it can simply remain HTHTHTHTHT.
We need to compress multiple H's only if the count >2 (with HH -> H2, while HHH -> H3)
How are you planning to send "3" in your output? If you are planning to compress it too, then remember that in your input you have more than two symbols: H, T, 2, 3. Now to compress it you will need 2 bits per symbol. Therefore, HHHT becomes H3T which becomes 001101 where 00 is H, 11 is 3 and 01 is T, and thus you end up using more bits.
- reserve the lowest 3 bits for the count of payload bits, thus allowing numbers 0-7;
- use the rest of the 5 bits in the <char> to communicate the payload data itself;
This solution enables transferring 5 different combinations in a single char,
as well as communicating the actual size of the payload.
- One question that should be asked of the interviewer is the size of the packets being sent over the channel. This in combination with the channel's data rate will allow you to derive channel capacity (I don't know the formula but it's easy enough to look up if you understand the concept). Once the theoretical channel capacity is known, it can be exploited to maximize throughput.
- For the sake of example, we'll assume the packet size is 16 bits. As others have stated, 16 bits can handily represent a string of 16 outcomes. Using 1 bit per outcome is terribly inefficient though...
- Let's use a system where half of the payload represents the number of Heads outcomes, and the other half represents the number of Tails. We are then left with 2 possibilities:
1- Number of coinflips per packet is known in advance (e.g. 65536).
- In this case, we can represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information (a tad more than 16). The primary drawback to this method is that you have to WAIT for all of those flips before sending each packet.
2- Number of coinflips per packet is not known in advance.
- In this case, we need to split up the 16-bit packet into two 8-bit variables, with one representing the number of heads and the other representing the number of tails. Each of these 8-bit counters can represent 0-255, and their sum, which represents the total number of coinflips for each packet, cannot exceed 510 (still quite a bit more than 16). Lower throughput, but the host can be updated on demand instead of having to wait for more flips for the packet to be ready.
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
could you please explain as to what do you mean by " represent H as +1, T as -1, and each (signed) 16-bit packet gives us 65536 coinflips worth of information"
Can we compress the data by using 1 bit per letter? That's probably the best possible here...
- eugene.yarovoi October 26, 2011