Collective Interview Question


Country: India




Comment hidden because of low score. Click to expand.
0
of 0 vote

First translate the 8 bit to 4 bit since it only 16 colors. Then if he needs lossless, try zip.

- chenlc626 February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use run length encoding by compressing similar bytes. Compare byte by byte data for similar bytes first record the byte then number of times the byte is repeated. If you are. Using byte compression, the maximum number limit will be 255. If you encounter this situation write the Same byte again and then the number of bytes following it until you encounter different byte. In worst case scenario none of the adjacent byte is repeated then In that case don't write the count just copy byte as is. The worst case will be that you will achieve no compression else you will achieve some compression, how much compression will be achieved will be dependent on the image. But this way will guarantee you a lossless compression.

There are other compression techniques that you can use. Most common one used is LZMA which is dictionary compression, but is harder to implement. But using LZMA will guarantee you the best compression.

- Anonymous February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LZMA doesn't guarantee the best possible compression.

in your first paragraph, if you don't put the count when none of the adjacent bytes are repeated, how will you later determine whether 11 10 encodes a pixel whose value is 11 and then a second pixel whose value is 10, or 10 pixels all of whose values are 11?

- eugene.yarovoi February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Usually, image compression is done in a lossy way, meaning information is lost during the compression process. Formats that do lossy compression, such as JPEG, retain the information that is in some sense most critical to the overall visual perception of the image and lose details that contribute less. Huge space savings are often attained this way.

There are also formats that are lossless, meaning that you can recover the exact, unaltered original from the compressed version. These usually also exploit certain properties that are frequently true about image data. For example, adjacent pixels often have similar colors, so to take a very simple scheme as an example, you could store an image as a series of mostly small numbers indicating the change in the color from one pixel to the next. Suppose you have a row of pixels whose values are 123 125 124. You can compress this by writing the values as 123 2 -1. 2 and -1 require fewer bits to represent than 125 and 124. This example is just a very simple compression scheme and more complicated schemes are possible.

Even with no special image properties to exploit, you can halve the use of space because the image in this question only has 16 colors. If a pixel can have one of 16 colors, it can be represented with 4 bits per pixel (since there are 16 different possible sequences of 0 and 1 of length 4). However, we're told in the problem that the image is presently represented with 1 byte (8 bits) per pixel instead. We can re-encode the image to use 4 bits per pixel to halve the space usage.

- eugene.yarovoi February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think Hoffman coding can solve this problem!
maximum color frequency required lest number of bit compare to 4 bit.
Average should be less that 4 bit per color.

- kkmaurya March 02, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More