Sign in to follow this  
srikanthpv

Help Needed Immediately

Recommended Posts

smallGame    211
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.


Share this post


Link to post
Share on other sites
stimarco    1071
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.)


Share this post


Link to post
Share on other sites
frob    44969
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.

Share this post


Link to post
Share on other sites
VerMan    116
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 pool
unsigned 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[i] = QUEUE_FREE;
}
for(int i=MAX_QUEUE_SIZE; i<MAX_DATA_SIZE; ++i)
{
data[i] = 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[i] == QUEUE_FREE)
{
//queue slot will hold queue number on it [0..MAX_QUEUE_SIZE-1]
data[i] = i;
return &data[i];
}
}
//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[i] == *q)
{
data[i] = 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[i] == 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[i] = *q;
data[i+1] = data[j+1];

//update indices & continue searching
i=j;
}
}
data[i] = *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[i] == *q)
{
data[i] = 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

Share this post


Link to post
Share on other sites
VerMan    116
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 pool
unsigned char data[MAX_DATA_SIZE];

//chunk structure
struct 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 structure
struct 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[i].free = true;
chunk[i].start = i*MAX_CHUNK_SIZE;
chunk[i].end = chunk[i].start + (MAX_CHUNK_SIZE-1);
chunk[i].next = 0;
}

//initialize the queue structure
for(int i=0; i<MAX_QUEUE; i++)
{
queue[i].free = true;
queue[i].start = DATA_EMPTY;
queue[i].end = DATA_EMPTY;
queue[i].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[i].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[i].free = false;
queue[i].start = chunk[j].start;
queue[i].end = chunk[j].start-1;
queue[i].head = j;

return &queue[i];
}
}

//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[i].free = true;
i = chunk[i].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[i].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[i].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[i].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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this