Skip to main content
gamedev.net
🔒 Locked

Help Needed Immediately

Started by srikanthpv 6 replies 1.7k views
Original Post
srikanthpv
srikanthpv
[Edited by - srikanthpv on November 20, 2008 4:02:29 PM]
smallGame
smallGame
I have just failed to a technical test interview, however I had to do it from home:

Instructions

------------------------------------------------------------------------

As a pre-interview, we're asking development candidates to send in a
solution to a programming problem. We apologize for the imposition -- if
you've ever tried to fill a programming position, you understand that
resumes are not an ideal way to evaluate programming ability. Please
send your solution as well as a current resume to jobs@mindwarestudios.com.

We are not expecting you to spend more than an hour or two on your
solution. If you would like clarifications on the problem, feel free to
send mail to jobs@mindwarestudios.com.


Problem Statement

------------------------------------------------------------------------

The problem is to write a set of functions to manage a variable number
of byte queues, each with variable length, in a small, fixed amount of
memory. You should provide implementations of the following four functions:

Q * createQ(); // Creates a FIFO byte queue, returning a handle to it.
void destroyQ(Q * q); // Destroy an earlier created byte queue.
void enQ(Q * q, unsigned char b); // Adds a new byte to a queue.
unsigned char deQ(Q * q); // Pops the next byte off the FIFO queue.


So, the output from the following set of calls:

Q * q0 = createQ();
enQ(q0, 0);
enQ(q0, 1);
Q * q1 = createQ();
enQ(q1, 3);
enQ(q0, 2);
enQ(q1, 4);
printf("%d ", deQ(q0));
printf("%d\n", deQ(q0));
enQ(q0, 5);
enQ(q1, 6);
printf("%d ", deQ(q0));
printf("%d\n", deQ(q0));
destroyQ(q0);
printf("%d ", deQ(q1));
printf("%d ", deQ(q1));
printf("%d\n", deQ(q1));
destroyQ(q1);

should be:

0 1
2 5
3 4 6

You can define the type Q to be whatever you want.

Your code is not allowed to call malloc() or other heap management
routines. Instead, all storage (other than local variables in your
functions) should be done in a provided array:

unsigned char data[2048];

Memory efficiency is important. On average while your system is running,
there will be a dozen or so queues with an average of 80 or so bytes in
each queue. Your functions may be asked to create a larger number of
queues with less bytes in each. Your functions may be asked to create a
smaller number of queues with more bytes in each.

If you are unable to satisfy a request due to lack of memory, your code
should call a provided failure function, which will not return:

void onOutOfMemory();

If the caller makes an illegal request, like attempting to deQ a byte
from an empty queue, your code should call a provided failure function,
which will not return:

void onIllegalOperation();

Worst-case performance when adding and removing bytes is more important
than average-case performance.

There may be spikes in the number of queues allocated, or in the size of
an individual queue. Your code should not assume a maximum number of
bytes in a queue (other than that imposed by the total amount of memory
available, of course!) You can assume that no more than 64 queues will
be created at once.


What To Send Us

------------------------------------------------------------------------

* A short discussion (a paragraph or two) about the possible
solutions you see to the problem, and why you chose the approach
you did.
* Implementations of the solution in C/C++.

Send your solution to jobs@mindwarestudios.com.


stimarco
stimarco
Quote:
Original post by srikanthpv

This is Sri,I found this forum as a part of browsing for my preparation for a Game programmer Interview....The company which is interviewing me is Cryptic Studios, CA....I am fresh Graduate Student with 6months of System Administrator work Ex....I am not sure of what kinda questions will appear in the Technical interview...What the company people did is they sent me a link and a code which i have to click and start writing the exam...Going through the company profile i think the interview is going to be in C, and C++....I dont know watelse are going to appear in the interview....
I would be thankful if you kindly send me some tips or links from where i can get some programming questions and things like that...SO that i can prepare quickly and take the test.....
Any kinda of help would be appreciated...My email id is
srikanthpv.npu@gmail.com


The purpose of a job interview is to find out if you're good enough to do the job. If you cannot answer the questions yourself, you probably shouldn't be applying for the role in the first place.

(I'd also advise working on your English. Contrary to popular belief -- and a shocking amount of evidence to the contrary -- the native language of the United States of America is, allegedly, English.)


Sean Timarco Baggaley (Est. 1971.)Warning: May contain bollocks.
frob
frob
Some of your interviewers may be reading this post, or might do a quick web search for your name just prior to your interview. There's a fair chance that they'll spot this post, and see exactly what you are trying to do.


When interviewing, it is very easy to ask progressively harder questions and identify the depth of a person's knowledge. No amount of cramming will prepare you for that.


They're interviewing a bunch of people. Based on that fact alone you should be prepared for a no-hire. The best thing you can do is try to relax.
bronxbomber92
bronxbomber92
I think the OP has all ready taken the test and has failed.

@OP
Perhaps you should post here what you sent in so we can help you see where you went wrong.
VerMan
VerMan
Hi, I jumped into this post after reading this one.
I made the same exercise for a job interview... however I was kicked in the a$$.

What went wrong?
well... I submitted a discussion of two possible solutions, however I did code only one: the easiest:

#include <stdio.h>#include <ctime>#include <sys/types.h>#include <time.h>#include <windows.h>#define MAX_DATA_SIZE	2048	//2K maximum memory#define MAX_QUEUE_SIZE	64		//64 bytes used to store queues#define QUEUE_FREE		0xFF#define DATA_FREE		0xF0#define Q unsigned char//memory poolunsigned char data[MAX_DATA_SIZE];//-----------------------------------------------------------------------------//Function prototypes//-----------------------------------------------------------------------------void Initialize();Q* CreateQ();void DestroyQ(Q *q);void EnQ(Q *q, unsigned char b);unsigned char DeQ(Q *q);void OnIllegalOperation();void OnOutOfMemory();//-----------------------------------------------------------------------------//Main function//-----------------------------------------------------------------------------void main(){	Initialize();	Q *q0 = CreateQ();	EnQ(q0, 0);	EnQ(q0, 1);	Q *q1 = CreateQ();	EnQ(q1, 3);	EnQ(q0, 2);	EnQ(q1, 4);	printf("%d ", DeQ(q0));	printf("%d\n", DeQ(q0));	EnQ(q0, 5);	EnQ(q1, 6);	printf("%d ", DeQ(q0));	printf("%d\n", DeQ(q0));	DestroyQ(q0);	printf("%d ", DeQ(q1));	printf("%d ", DeQ(q1));	printf("%d\n", DeQ(q1));	DestroyQ(q1);}//-----------------------------------------------------------------------------//Initializes data & queue pools//@return no value is returned//-----------------------------------------------------------------------------void Initialize(){	//initialize data pool, the first 64 bytes belong to the queue pool	for(int i=0; i<MAX_QUEUE_SIZE; ++i)	{		data = QUEUE_FREE;	}	for(int i=MAX_QUEUE_SIZE; i<MAX_DATA_SIZE; ++i)	{		data = DATA_FREE;	}}//-----------------------------------------------------------------------------//Creates a new ByteQueue object//@return handle to a ByteQueue object//-----------------------------------------------------------------------------Q* CreateQ(){	//find a free queue within the queue pool	for(int i=0; i<MAX_QUEUE_SIZE; ++i)	{		if(data == QUEUE_FREE)		{			//queue slot will hold queue number on it [0..MAX_QUEUE_SIZE-1]			data = i;			return &data;		}	}	//no more queues can be created	OnIllegalOperation();}//-----------------------------------------------------------------------------//Destroys a ByteQueue object//@param q handle to a ByteQueue object//@return no value is returned//-----------------------------------------------------------------------------void DestroyQ(Q *q){	//check if queue is valid	if(!q)	{		OnIllegalOperation();	}	//free memory used by the queue	for(int i=MAX_QUEUE_SIZE; i<MAX_DATA_SIZE; i+=2)	{		if(data == *q)		{			data = DATA_FREE;	//queue number			data[i+1] = DATA_FREE;	//actual data		}	}	//finally, free queue slot	*q = QUEUE_FREE;	q = 0;}//-----------------------------------------------------------------------------//Enqueues a byte value. //Each value is stored in memory pool as a pair [..., qNum, qVal,...]//@param q handle to a ByteQueue object//@returns no value is returned//-----------------------------------------------------------------------------void EnQ(Q *q, unsigned char b){	//check if q is valid	if(!q)	{		OnIllegalOperation();	}	//find a free memory slot and arrange queue values in a FIFO order	for(int i=MAX_QUEUE_SIZE; i<MAX_DATA_SIZE; i+=2)	{		if(data == DATA_FREE)		{			//search for more values of current queue and re-arrange			for(int j=i; j<MAX_DATA_SIZE; j+=2)			{				if(data[j] == *q)				{					//move found queue data to front					data = *q;					data[i+1] = data[j+1];					//update indices & continue searching					i=j;				}			}			data = *q;	//store the queue number			data[i+1] = b;	//store the queue value			return;		}	}	//no free memory	OnOutOfMemory();}//-----------------------------------------------------------------------------//Dequeues a byte value//@param q handle to a ByteQueue object//@return unsigned char value (front of the queue)//-----------------------------------------------------------------------------unsigned char DeQ(Q *q){	//check if q is valid	if(!q)	{		OnIllegalOperation();	}	//get the first (active, i.e. non dequeued) value in queue	for(int i=MAX_QUEUE_SIZE; i<MAX_DATA_SIZE; i+=2)	{		if(data == *q)		{			data = DATA_FREE;			return data[i+1];		}	}	//queue is empty	OnIllegalOperation();}//-----------------------------------------------------------------------------//Function called when some illegal operation occurs//e.g. trying to deque an empty queue, etc.//-----------------------------------------------------------------------------void OnIllegalOperation(){	//TODO}//-----------------------------------------------------------------------------//Function called when we run out of memory//e.g. trying to enqueue when no memory is available.//-----------------------------------------------------------------------------void OnOutOfMemory(){	//TODO}


Use the whole memory pool without any split but saving 2 bytes per data per queue. i.e. the 1st byte keeps track of the queue it belongs to and the 2nd byte holds the data itself. I implemented this solution using the first 64 bytes of the memory pool as a queue pool to keep track of queue numbers. Each queue points to a location in our queue pool so EnQ and DeQ know what queue number we're trying to access (and search for that number when enqueing/dequeing within the memory pool).

Since in average we're going to have a dozen of queues with 80 bytes, that makes 160 bytes per queue = 1920 bytes in total + 64 bytes as queue pool that makes 1984 bytes < 2048. In general, the worst case scenario, we could have 64 queues of 15 elements each before running out of memory.

So.. I flunk
VerMan
VerMan
afterward I decided to code the second solution I proposed:

Divide the memory pool into chunks of data (e.g. 64 chunks of 32 bytes) but in this case we need to make a linked list of memory chunks that belong to each queue and keep track of the start & end of each chunk. We might need as well 2 indices for the start & end of queue data between memory chunks.

#include <stdio.h>#define MAX_DATA_SIZE	2048	//2K maximum memory#define MAX_CHUNK_SIZE	32		//so we can have up to 64 chunks of 32 bytes each#define MAX_CHUNKS		2048/32	//i.e. 64 chunks#define MAX_QUEUE		64#define DATA_EMPTY		-1#define Q queue_type//memory poolunsigned char data[MAX_DATA_SIZE];//chunk structurestruct chunk_type{	bool free;	//true if the chunk is free to use, false otherwise	char start;	//start offset within data	char end;	//end offset within data	char next;	//chunk # if there's a chunk linked to this one, 0 otherwise}chunk[MAX_CHUNKS];//queue structurestruct queue_type{	bool free;	//true if the queue is free to use, false otherwise	char start;	//start offset of queue	char end;	//end offset of queue	char head;	//chunk # that belongs to the queue (first in list)}queue[MAX_QUEUE];//-----------------------------------------------------------------------------//Function prototypes//-----------------------------------------------------------------------------void Initialize();Q* CreateQ();void DestroyQ(Q *q);void EnQ(Q *q, unsigned char b);unsigned char DeQ(Q *q);void OnIllegalOperation();void OnOutOfMemory();//-----------------------------------------------------------------------------//Main function//-----------------------------------------------------------------------------void main(){	Initialize();	Q *q0 = CreateQ();	EnQ(q0, 0);	EnQ(q0, 1);	Q *q1 = CreateQ();	EnQ(q1, 3);	EnQ(q0, 2);	EnQ(q1, 4);	printf("%d ", DeQ(q0));	printf("%d\n", DeQ(q0));	EnQ(q0, 5);	EnQ(q1, 6);	printf("%d ", DeQ(q0));	printf("%d\n", DeQ(q0));	DestroyQ(q0);	printf("%d ", DeQ(q1));	printf("%d ", DeQ(q1));	printf("%d\n", DeQ(q1));	DestroyQ(q1);}//-----------------------------------------------------------------------------//Initializes data & queue pools//@return no value is returned//-----------------------------------------------------------------------------void Initialize(){	//initialize the chunks structure	for(int i=0; i<MAX_CHUNKS; i++)	{		chunk.free = true;		chunk.start = i*MAX_CHUNK_SIZE;		chunk.end = chunk.start + (MAX_CHUNK_SIZE-1);		chunk.next = 0;	}	//initialize the queue structure	for(int i=0; i<MAX_QUEUE; i++)	{		queue.free = true;		queue.start = DATA_EMPTY;		queue.end = DATA_EMPTY;		queue.head = DATA_EMPTY;	}}//-----------------------------------------------------------------------------//Creates a new ByteQueue object//@return handle to a ByteQueue object//-----------------------------------------------------------------------------Q* CreateQ(){	//find a free queue slot	for(int i=0; i<MAX_QUEUE; i++)	{		if(queue.free)		{			//find a free memory chunk of data			for(int j=0; j<MAX_CHUNKS; j++)			{				if(chunk[j].free)				{					//mark chunk as used					chunk[j].free = false;					chunk[j].next = DATA_EMPTY;					//mark queue as used					queue.free = false;					queue.start = chunk[j].start;					queue.end = chunk[j].start-1;					queue.head = j;										return &queue;				}			}			//not enough memory to allocate			OnOutOfMemory();		}	}	//no more queues can be created	OnIllegalOperation();}//-----------------------------------------------------------------------------//Destroys a ByteQueue object//@param q handle to a ByteQueue object//@return no value is returned//-----------------------------------------------------------------------------void DestroyQ(Q *q){	//check if queue is valid	if(!q)	{		OnIllegalOperation();	}	//free memory used by the queue	unsigned i = q->head;	do	{		chunk.free = true;		i = chunk.next;	}	while(i != DATA_EMPTY);	//finally, free the queue slot	q->free = true;}//-----------------------------------------------------------------------------//Enqueues a byte value. //@param q handle to a ByteQueue object//@returns no value is returned//-----------------------------------------------------------------------------void EnQ(Q *q, unsigned char b){	//check if q is valid	if(!q)	{		OnIllegalOperation();	}	//get last chunk id in list	char i = q->end >> 5;	//get next enque-able position	q->end++;	if(q->end > chunk.end)	{		//we need to find a new chunk of memory		for(int j=0; j<MAX_CHUNKS; j++)		{			if(chunk[j].free)			{				q->end = chunk[j].start;				chunk[j].free = false;				chunk.next = j;			}		}		//we ran out of memory		OnOutOfMemory();	}	//store the data	data[q->end] = b;}//-----------------------------------------------------------------------------//Dequeues a byte value//@param q handle to a ByteQueue object//@return unsigned char value (front of the queue)//-----------------------------------------------------------------------------unsigned char DeQ(Q *q){	//check if q is valid	if(!q)	{		OnIllegalOperation();	}	//check that q is not empty!	if(q->start > q->end)	{		OnIllegalOperation();	}	//get the first value in queue	unsigned char value = data[q->start];	//get new start position	q->start++;	if( (q->start > chunk[q->head].end) || (q->start > q->end) )	{		//check if we have another chunk linked		char i = chunk[q->head].next;		if(i != DATA_EMPTY)		{			//free unused chunk			chunk[q->head].free = true;			chunk[q->head].next = DATA_EMPTY;			q->start = chunk.start;			q->head = i;		}		else		{			//queue is now empty, reset positions			q->start = chunk[q->head].start;			q->end = chunk[q->head].start-1;		}	}	return value;}//-----------------------------------------------------------------------------//Function called when some illegal operation occurs//e.g. trying to deque an empty queue, etc.//-----------------------------------------------------------------------------void OnIllegalOperation(){	//TODO}//-----------------------------------------------------------------------------//Function called when we run out of memory//e.g. trying to enqueue when no memory is available.//-----------------------------------------------------------------------------void OnOutOfMemory(){	//TODO}


Is it any better? I believe in the average case EnQ/DeQ have now complexity of O(c).

[Edited by - VerMan on December 13, 2008 11:00:12 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.