This is a failed application for a game development job. I'm posting it here to display it on my blog.

Container.h

/* Rules
 * Write the implementation in Container.h, do not change ContainerTest.cpp.
 * No memory allocation is allowed (implicit or explicit).
 * Use of the STL (Standard Template Library) is not allowed.
 * You can add member functions and variables.
 * All storage management data structures must use the buffer memory, not additional member variables.
 * You must test your solution in debug (or any configuration that have asserts enabled) so that the requirements are tested.
 * Your solution must be efficient and scalable.
 * Try to maximize the number of elements in the given buffer, and also perform well whether you have ten elements or thousands.
 * Optionally, you can uncomment the _ADVANCED macro at the top of ContainerTest.cpp and implement the sorting algorithm.
 * Please provide a time log for your solution as well as a small paragraph describing why your solution is good.
 * Clarity and comments will also be evaluated.
 * The return address must be consistent for the lifetime of the object.
 * You can limit the capacity to 65536 elements if this makes your implementation easier.
*/

//24/7/2014: 6:30pm to 7:00pm (interrupted)
//24/7/2014: 7:40pm to 10:40pm (coffee run)
//24/7/2014: 11:00pm to 12:00am (basics finished)

//26/7/2014: 10:20pm - 11L20pm (could not replicate assert error, line 145)
//26/7/2014: 11:20pm - 27/7/2014 3:50am (bug hunting, failed)

/* Plan
 * Since I've decided to attempt the sorting algorithm, there are several
 * important rules that I need to take into consideration:
 * 
 * 1. All storage management data structures must use the buffer.
 * 2. All return addresses must remain the same; requiring no data movement.
 * 3. Implement the sorting algorithm; requiring element movement.
 * 4. It must be scalable and efficient; operator[] is used in various loops.
 * 5. Maximize the number of elements possible, but 65536 is acceptable.
 * 
 * Rules 2 and 3 here are an interesting conundrum, But I do believe I have a
 * solution. My plan is to partition the buffer space into two sections, based
 * on it's size. The first section is a lookup table for the elements, which
 * are stored in the second section.
*/

#include <assert.h>
#include <utility>

template<typename T>
class CContainer {
public:
	CContainer(char* apBuffer, unsigned int anBufferSize) {
		pBuffer = apBuffer;
		nBufferSize = anBufferSize;

		nCount = 0;
		nMaximum = nBufferSize / (sizeof(T)+2);

		//use the allowed maximum
		assert(nMaximum > 0 && nMaximum <= 65536);

		//determine the starting positions of each section
		pTable = reinterpret_cast<unsigned short*>(apBuffer);
		pElements = reinterpret_cast<T*>(pTable + nMaximum);

		//Index each element
		for (int i = 0; i < nMaximum; ++i) {
			pTable[i] = i;
		}
	}
	~CContainer() {
		//deconstruct all elements
		for (int i = 0; i < nCount; ++i) {
			pElements[pTable[i]].~T();
		}
	}

	T* Add() {
		assert(nCount < nMaximum);

		//get the address to allocate the new object
		T* pRet = &pElements[pTable[nCount++]];

		//construct and return a new element
		return new(pRet) T; //placement new
	}

	void Remove(T* apRem) {
		//only dealing with the elements
		assert(apRem >= pElements && apRem <= pElements + nMaximum);

		//find the argument's index within the element array
		unsigned short nIndex = apRem - pElements;

		//find where it's index is currently stored; time complexity O(n)
		unsigned short nPos = nMaximum;
		for (unsigned short i = 0; i < nCount; ++i) {
			if (pTable[i] == nIndex) {
				nPos = i;
				break;
			}
		}

		//if I've failed to find the element within the container
		assert(nPos < nCount);

		//switch nPos with the top of the "stack"
		Swap(pTable[nPos], pTable[nCount-1]);

		//delete the argument and move the index pointer
		apRem->~T();
		--nCount;
	}

	unsigned int Count() const {
		//Number of elements currently in the container.
		return nCount;
	}
	unsigned int Capacity() const {
		//Max number of elements the container can contain.
		return nMaximum;
	}

	bool IsEmpty() const {
		//Is container empty?
		return nCount == 0;
	}
	bool IsFull() const {
		//Is container full?
		return nCount == nMaximum;
	}

	T const* operator [] (unsigned nIndex) const {
		//Returns the n th element of the container [0..Count -1].
		return &pElements[pTable[nIndex]];
	}
	T* operator [] (unsigned nIndex) {
		//Returns the n th element of the container [0..Count -1].
		return &pElements[pTable[nIndex]];
	}

#ifdef _ADVANCED
	void Sort(int (* compare)(T const * pX, T const * pY)) {
		//Sort the elements using a function pointer for the comparison.
		QuickSort(0, nCount-1, compare);
	}
#endif

private:
#ifdef _ADVANCED
	void QuickSort(int nStart, int nEnd, int (* compare)(T const * pX, T const * pY)) {
		//NOTE: nStart & nEnd represent table positions to be sorted, inclusive
		if (nEnd - nStart < 2) {
			return;
		}

		int nPivot = nEnd;

		//iterate backwards through the partition
		for (int i = nEnd-1; i >= nStart; --i) {
			if (compare(&pElements[pTable[i]], &pElements[pTable[nPivot]]) > 0) {
				//move the current "checked" element next to the pivot
				Swap(pTable[i], pTable[nPivot-1]);
				//swap the pivot and the "checked" element
				Swap(pTable[nPivot-1], pTable[nPivot]);
				--nPivot;
			}
		}

		//pass the two partitions onwards
		QuickSort(nStart, nPivot, compare);
		QuickSort(nPivot+1, nEnd, compare);
	}
#endif
	inline void Swap(unsigned short& lhs, unsigned short& rhs) {
		//For simple swaps (XOR swap)
		//NOTE: this allows you to swap an element with itself
		lhs = (lhs ^ rhs);
		rhs = (lhs ^ rhs);
		lhs = (lhs ^ rhs);
	}

	//buffer
	char* pBuffer;
	unsigned int nBufferSize;

	//container data
	unsigned int nCount;
	unsigned int nMaximum;

	//the partitioned sections
	unsigned short* pTable;
	T* pElements;
};

ContainerTest.cpp

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <new>

//#define _STATS
//#define _ADVANCED

#include "container.h"

static unsigned gs_nBufferSize = 0;
static char * gs_pBuffer = NULL;

//-------------------------------------------------------------------------
//
class CTestClass
{
	size_t			m_nAddr;
	unsigned		m_nAllocNum;
	static bool		ms_bAllowAdd;

public:
	CTestClass()
	{
		assert(ms_bAllowAdd);
		m_nAddr		= (size_t)this;
		m_nAllocNum = 0;
	}

	~CTestClass()
	{
		m_nAddr		= 0;
		m_nAllocNum = 0;
	}

	void SetAllocNum(unsigned nNumAlloc)
	{
		m_nAllocNum = nNumAlloc;
	}

	unsigned GetAllocNum() const
	{
		return m_nAllocNum;
	}

	size_t GetAddress() const
	{
		return m_nAddr;
	}

protected:
	static void AllowAdd(bool bAllowed)
	{
		ms_bAllowAdd = bAllowed;
	}

	friend void StressTest(CContainer<CTestClass> & oContainer, unsigned const nNumAllocs);
};

bool CTestClass::ms_bAllowAdd = false;

//-------------------------------------------------------------------------

inline bool IsInBuffer(void const * pAddr)
{
	return ((char const *)pAddr >= gs_pBuffer) && ((char const *)pAddr <= (gs_pBuffer + gs_nBufferSize - sizeof(CTestClass)));
}

//-------------------------------------------------------------------------

#ifdef _ADVANCED
int CompareTestClass(CTestClass const * pX, CTestClass const * pY)
{
	if (pX->GetAllocNum() < pY->GetAllocNum())
	{
		return -1;
	}
	else if (pX->GetAllocNum() > pY->GetAllocNum())
	{
		return 1;
	}

	return 0;
}
#endif

//-------------------------------------------------------------------------

void StressTest(CContainer<CTestClass> & oContainer, unsigned const nNumAllocs)
{
	int nSeed = 0;
	unsigned const nCapacity = oContainer.Capacity();

	unsigned nNballocs = 0;
	unsigned nNbFrees = 0;
#ifdef _STATS
	unsigned nNbEmpty = 0;
	unsigned nNbFull = 0;
	unsigned nMaxSize = 0;
#endif
	srand(nSeed);

	///======	pre-fill up 3/4 of the container.
	CTestClass::AllowAdd(true);
	for (unsigned i = 0; i < 3 * nCapacity / 4; ++i)
	{
		CTestClass * pObj = oContainer.Add();
		pObj->SetAllocNum(nNballocs);
		nNballocs++;
	}
	CTestClass::AllowAdd(false);

	///======	loop until we reach a certain number of allocations
	while (nNballocs < nNumAllocs)
	{
		///======	randomly add or remove object from the managed container
		bool bAdd = ((rand() & 0x1f) >= 16)  ? true : false;	

		if (bAdd && oContainer.IsFull())
		{
			bAdd = false;
		}
		else if (!bAdd && oContainer.IsEmpty())
		{
			bAdd = true;
		}

		if (bAdd)
		{
			CTestClass::AllowAdd(true);
			CTestClass * pObj = oContainer.Add();
			CTestClass::AllowAdd(false);

			assert(IsInBuffer(pObj));
			pObj->SetAllocNum(nNballocs);
			assert(pObj->GetAddress() == (size_t)pObj);	///======	sanity check
			nNballocs++;
		}
		else
		{
			int nIndex = (oContainer.Count() > 1) ? rand() % (oContainer.Count() - 1) : 0;

			CTestClass * pObj = oContainer[nIndex];
			assert(pObj->GetAddress() == (size_t)pObj);	///======	sanity check
			oContainer.Remove(pObj);
			assert(pObj->GetAddress() == 0);			///======	if this assert trips then you haven't called the destructor.
			nNbFrees++;
		}

#ifdef _STATS
		nMaxSize = oContainer.Count() > nMaxSize ? oContainer.Count() : nMaxSize;
		if (oContainer.IsEmpty())
		{
			++nNbEmpty;				
		}
		else if (oContainer.IsFull())
		{
			++nNbFull;
		}
#endif

		if ((nNballocs & 32767) == 0)
		{
			printf("Container => %d allocs, %d frees\r", nNballocs, nNbFrees);
		}
	}

#ifdef _STATS
	printf("\nMaxSize: %d (seed %d), Nb full containers: %d, Nb empty containers: %d\n", nMaxSize, nSeed, nNbFull, nNbEmpty);
#endif

#ifdef _ADVANCED
	oContainer.Sort(CompareTestClass);

	///======	sanity check after the sort
	for (unsigned i = 0; i < oContainer.Count() - 1; ++i)
	{
		assert(oContainer[i]->GetAllocNum() < oContainer[i + 1]->GetAllocNum());
	}
#endif

	///======	clean up
	while (oContainer.Count() > 0)
	{
		CTestClass * pObj = oContainer[0];
		assert(pObj->GetAddress() == (size_t)pObj);	///======	sanity check
		oContainer.Remove(pObj);
	}
	assert(oContainer.Count() == 0);
}

//-------------------------------------------------------------------------

int main(int argc, char* argv[])
{
	if (argc < 2)
	{
		printf("Usage:\nTest.exe buffersize (in KB)\n");
		return EXIT_FAILURE;
	}

	assert(sizeof(CContainer<CTestClass>) < 256);	///======	this is an arbitrary, but why should we need more?

	gs_nBufferSize = atoi(argv[1]) * 1024;
	gs_pBuffer = new char[gs_nBufferSize];

	CContainer<CTestClass> * pContainer = new CContainer<CTestClass>(gs_pBuffer, gs_nBufferSize);

	printf("Managed Container Capacity: %d\n", pContainer->Capacity());

	clock_t oStartTime = clock();
	StressTest(*pContainer, 20000000);
	clock_t oEndTime = clock();

	double fElapsedTime = (double)(oEndTime - oStartTime) / CLOCKS_PER_SEC;

	printf("\nTime elapsed: %f seconds\n", fElapsedTime);

	delete pContainer;
	pContainer = NULL;

	delete[] gs_pBuffer;

	return EXIT_SUCCESS;
}