InterraIT Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Here we can use the concept of "Run length coding" along with encoding H and T.
Consider H -> 1
and T -> 0
In a byte allocate 7 bits to represent value upto 2^7 -> 0 - 127
and last 8th bit to represent H(1) , or T(1)
Then apply run length coding.
Hence HHTTTHHHHHTTTTTHTHTTTT can be represented as.
2H3T5H5THTH4T
2H -> 00000101 -> 3
3T -> 00000110 -> 6
similarly for 5H, 5T etc..
Final data sent is byte stream 3,6,.... Etc..
At receiver end , take each bit, consider first 7 bits for number of times the event (H or T ) is repeated, and last bit for the event itself.
This solution give the best performance when repetitions are frequent.
Here we can use the concept of "Run length coding" along with encoding H and T.
Consider H -> 1
and T -> 0
In a byte allocate 7 bits to represent value upto 2^7 -> 0 - 127
and last 8th bit to represent H(1) , or T(1)
Then apply run length coding.
Hence HHTTTHHHHHTTTTTHTHTTTT can be represented as.
2H3T5H5THTH4T
2H -> 00000101 -> 3
3T -> 00000110 -> 6
similarly for 5H, 5T etc..
Final data sent is byte stream 3,6,.... Etc..
At receiver end , take each bit, consider first 7 bits for number of times the event (H or T ) is repeated, and last bit for the event itself.
This solution give the best performance when repetitions are frequent.
If the probability of H and T are same and outcome is independent of the other outputs, then the entropy of the source will be :
=-(.5log(.5) + .5log(.5)) = 1
And according to source coding theorem, we cannot send one outcome not less than entropy of the source which is 1.
Hence it cannot be compressed.
If the probability of H and T are same and outcome is independent of the other outputs, then the entropy of the source will be :
=-(.5log(.5) + .5log(.5)) = 1
And according to source coding theorem, we cannot send one outcome not less than entropy of the source which is 1.
Hence it cannot be compressed.
If the probability of H and T are same and outcome is independent of the other outputs, then the entropy of the source will be :
=-(.5log(.5) + .5log(.5)) = 1
And according to source coding theorem, we cannot send one outcome not less than entropy of the source which is 1.
Hence it cannot be compressed.
Send the first outcome as it is. From then on send the number representing how many times it have appeared without change during each switch. So for HHTHHHHHTTTTT...
it would be H|2|1|5| where | represents each switching point.
This is a bad solution. If the output is truly random this instead of compressing it will inflate it.
Agreed with anonymous. The thing to realize in this problem is that with very high probability, a random string will be largely incompressible. The best thing is just to encode the data using 1 bit per outcome.
Still holds good
if string is hththt then its sent same
but if it has more than 2h or 2t then its numbered
eg
hhthttth
then its sent as hhtht3h
Then why not send it like, 5432, where the number itself says 5 as Heads then 4 tails and 3 heads and then 2 tails again.???
Typically assume that H=1 and T!=H=0 and set the bit accordingly and send this data using the single string.
- hprem991 November 03, 2011However you gotto set the protocol on both the points for your assumption.