[Clavas]

You are programming a sideways scrolling shooter. This used 2D cell based maps that are very long (over 100,000 characters per row long, 24 rows of 40 characters on screen), and the only way you can get them to fit in memory is to compress each row of the map using run length encoding and to decompress each new column of the map on the right of the screen as the background moves from right to left. You maintain a list of pointers into the RLE data for each row of the screen. Columns that are scrolled off the left are discarded. This works very well and the game only just fits in the available memory. Suddenly the game designer decides that the game should also be able to scroll from left to right at any point, and for any duration. Stunned and dismayed, you explain to him that RLE compression only works in one direction, but he’s adamant. Figure out a way of doing what he wants without using much (no more that 1K of) extra memory. Explain the algorithm used for decompressing in both directions. (assume the RLE algorithm used is: a positive byte N followed by a byte B, indicates a run of N copies of B, a negative byte -N followed by N bytes indicates that those bytes should be copied directly. For example, the sequence 2,2,2,2,5,1,2,9,9,9,9,9 would be coded 4,2, -3,5,1,2, 5,9.)

So my question is how can I compress the information? My first thought was making a change to the RLE compression but i gave up on that thinking it wasn't possible. Any push into the right direction would help me out tons. Thanks.

[ButchDean]

Using compression/decompression on data during runtime is a bad idea anyway that you should not have suggested in the first place.

What is the problem with partitioning your map and loading the appropriate sections when they are entered? Pretty much common practice.

[Clavas]

Well i have to answer the problem with some type of compression/decompression

[ButchDean]

Oh, it's a school exercise? Damn, that's bad.

You have no idea at all how to approach it? Given that it's an exercise I don't want to just give you an answer.

[Clavas]

Well i dont need an exact answer just a push into the right direction. Also i didnt mean to put school exercise it's actually a interview question.

[ButchDean]

You're going to need to put some ideas up. Interview questions are meant to be solved by the candidate, and not on a forum.

[Clavas]

Im not looking for a straight up answer just a little help since this is something I've never really learned or worked on before. In your opinion if you had to compress and decompress the data would you make a change to the RLE algorithm or find a whole new compression method like huffman ect.

[ButchDean]

The purpose of a technical test at interview is to partly determine:

1. Your comprehension - Do you understand the problem at hand?
2. Your knowledge - Do you have the background to be able to perform your duties at the job?
3. Your skill - Can you formulate an elegant solution to the problem?

So far, to me you're not demonstrating any of these, and I don't believe I am doing you or your prospective employer any favors in even doing part of the test for you. You should be asking the employer for clarification.

Good luck.

[Clavas]

Well I'm going to be blunt with you. I graduated school from full sail almost 2 years ago and since then out of the 50+ applications I've sent out I've only gotten 1 test for an interview and that was almost a year ago. Since i graduated I've been forced to work 2 dead end jobs for the last 2 years just to pay off loans. I was pretty much to the point of giving up looking for any job in the gaming field. This is the first test i got from an application i sent out months and month ago and it sorta rekindled my fire after a very good phone interview. I'm stuck on the last question of it and don't want to take to long to send it back and definitively don't want to send an unanswered question knowing that will probably decide if I get the job or even continue in this field at all. All i asked for was just some push into the right direction so i can figure out the rest on my own. My ineptitude to the question im asking is simply because I am out of practice from anything c++ since it has been so long. I'm not saying all this to get pity from you but from what you said its very disheartening from what you said because you assume i don't know anything and you don't know the struggles I've been through.

[ButchDean]

Everybody goes through struggles. I've recently worked with Full Sail graduates who turned out to be very good programmers. The fact that you've graduated two years ago and only made 50 applications is not a lot. Secondly, you will quickly learn that there are no pity parties in the games industry - it's either you can do the work or you can't; they don't care what else has gone on with your life.

To be honest, if you went to Full Sail I would have expected you to at the very least be able to give a complete answer to this question without prompting. Full Sail is a good game school.

I am not trying to be disheartening here, nor do I want to give you a false picture. What is most likely happening here is:

1. Getting your foot in the door with games is nightmare. Studios actively seek out people with experience over those without.
2. The way that you present yourself to studios is something that you gain with experience. Judging from your responses in this thread I honestly get the feeling that because you graduated you feel the industry owes you a job. Guess what? You couldn't be further from the truth! If you don't put the effort in to impress as a person, and continually improve your skill set, you're not getting a games job.
3. From me deciding to work in games to actually getting the job took four years! And you think two is a long time?! />

Now, the first thing you need to do is avoid ranting, it's making you look bad. Attempt the test as best you can and submit it. No-one gets everything in every test right, so don't feel bad about it. It's a learning experience if nothing else.

This post has been edited by ButchDean: 05 March 2013 - 10:20 PM

[emmalovato]

Strange place to be doing this. Did either of you ever come up with a good hint for starting? I'm have been thinking about this question, and I'm not really getting anywhere.

My problem is a conceptual one--how can RLE work multidirectionally? The information contained in the compressed data has to be read from left to right, otherwise it will produce incorrect output. Any hints?

[emmalovato]

Hmm. Maybe I could store the data compressed in both directions, moving to the different strands when the scroll changes direction. I'm not sure if that would keep my added memory under the required 1K... especially if the data that scrolls off the screen has to be re-compressed.

Sorry, just thinking out loud here.