question 6
// we are going to use double-link-list to implement deque
template<class T>
class Node
{
public:
	Node* next;
	Node* prev;
	T value;
	Node()
	{
		next = prev = NULL;
	}
};

template<class T>
class Deque
{
public:
	Node<T>* head;
	Node<T>* tail;
	int theSize;
	Deque()
	{
		head = tail = NULL;
		theSize = 0;
	}
	bool push_front(const T& val)
	{
		Node<T>* node = new Node<T>;

		if (node == NULL)
		{
			return false;
		}
		node->value = val;

		if (head == NULL || tail == NULL)
		{
			// first time initialize
			head = tail = node;
			head->next = head->prev = tail->next = tail->prev = NULL;
		}
		else
		{
			// insert a node
			node->next = head;
			head->prev = node;
			head = node;
		}
		theSize ++;
		return true;
	}

	bool push_back(const T& val)
	{
		Node<T>* node = new Node<T>;

		if (node == NULL)
		{
			return false;
		}
		node->value = val;

		if (head == NULL || tail == NULL)
		{
			// first time initialize
			head = tail = node;
			head->next = head->prev = tail->next = tail->prev = NULL;
		}
		else
		{
			//insert node
			node->prev = tail;
			tail->next = node;
			tail = node;
		}
		theSize ++;
		return true;
	}

	bool pop_front(T& val)
	{
		Node<T>* node = NULL;

		if (head == NULL)
		{
			return false;
		}
		val = head->value;
		
		// this is more straight forward as we would NOT use circular-double-link-list
		//head->next->prev = head->prev;
		head->next->prev = NULL;

		node = head;
		head = head->next;
		delete node;
		theSize --;
		return true;
	}

	bool pop_back(T& val)
	{
		Node<T>* node = NULL;
		if (tail == NULL)
		{
			return false;
		}
		node = tail;
		val = tail->value;
		// this is more straight forward as we would NOT use circular-double-link-list
		//tail->prev->next = tail->next;
		tail->prev->next = NULL;

		tail = tail->prev;
		delete node;
		theSize --;
		return true;
	}
	int size()
	{
		return theSize;
	}

};


question 7

// Largest fit has higher chances of failure when "big" request comes.
// best fit may generate more "smaller" fragment which is essentially useless....
// so maybe we should choose largest fit

class Node
{
public:
	bool isFree;
	char* ptr;
	int size;
	Node* prev;
	Node* next;
};

class MemMgr
{
private:
	Node* head;
	int nTotalFree;
	int nTotalSize;

	// make it private as this won't be used by outsider
	void uninit() //clean up
	{
		Node* node = NULL;
		while (head != NULL)
		{
			node = head->next;
			delete head;
			head = node;
		}		
	}


	Node* largestFit(int size)
	{
		Node* node = head, *result = NULL;
		int nLargest = 0;
		while (node != NULL)
		{
			if (node->isFree && node->size >= size)
			{
				if (nLargest < node->size - size)
				{
					nLargest = node->size - size;
					result = node;
				}
				// the best perfect fit
				if (nLargest == 0)
				{
					return result;
				}
			}
			node = node->next;
		}
		return result;


	}

	Node* bestFit(int size)
	{
		Node* node = head, *result = NULL;
		int nSmallest = nTotalFree;
		while (node != NULL)
		{
			if (node->isFree && node->size >= size)
			{
				if (nSmallest > node->size - size)
				{
					nSmallest = node->size - size;
					result = node;
				}
				// the best perfect fit
				if (nSmallest == 0)
				{
					return result;
				}
			}
			node = node->next;
		}
		return result;
	}

	// firstFit is only faster, and has no help for reducing fragments

public:
	
	bool init(char* ptr, int size)
	{
		Node* node = new Node;
		if (node == NULL)
		{
			return false;
		}
		uninit();
		head = node;
		head->isFree = true;
		head->ptr = ptr;
		head->size = size;
		nTotalFree = nTotalSize = size;
		return true;
	}

	char* my_malloc(int size)
	{
		Node* node = NULL, *newNode = NULL;
		if (size > nTotalFree)
		{
			return NULL;
		}
		//here we can implement different flavour of searching to minimize the mem fragment
		// the "best fit" or "largest fit"
		// as far as I remember, largest fit may help reducing fragment when "Big" mem requests are fewer
		// Largest fit has higher chances of failure when "big" request comes.
		// best fit may generate more "smaller" fragment which is essentially useless....
		// so maybe we should choose largest fit

		//node = bestFit(size);
		node = largestFit(size);

		if (node == NULL)
		{
			return NULL;
		}
		if (node->size == size)
		{
			// the perfect fit is always welcome
			// no need for new split node
			return node->ptr;
		}
		// create
		newNode = new Node;
		if (newNode == NULL)
		{
			return NULL;
		}
		newNode->isFree = false;
		newNode->ptr = node->ptr;
		newNode->size = size;
		newNode->prev = node->prev;
		newNode->next = node;
		// modify the old node
		node->size -= size;
		node->ptr = newNode->ptr + newNode->size;
		node->prev = newNode;
		// modify the total size
		nTotalFree -= size;
		return newNode->ptr;
	}

	void my_free(char* ptr)
	{
		// suppose we cannot find it, should we return fail?
		Node* node = head;
		while (node != NULL)
		{
			if (node->ptr == ptr)
			{			
				// three cases happens
				// 1. merge with prev only, delete node
				// 2. merge with prev and next, delete node and next node
				// 3. no merge happens and no delete, simply reset usage flag

				// now we need to merge prev
				if (node->prev && node->prev->isFree)
				{
					// case ONE
					// merge with prev
					node->Prev->size += node->size + node->next->size;
					// it is possible we even merge with next
					if (node->next && node->next->isFree)
					{
						// merge with next
						// case TWO
						node->prev->size += node->next->size;

						// short-cut the link between prev with next->next
						node->prev->next = node->next->next;
						node->next->next->prev = node->prev;
						// need to delete next
						delete node->next;
												
					}
					else
					{
						// no merge
						node->prev->next = node->next;
						node->next->prev = node->prev;
					}	
					// no matter whether merge happens, we need to delete node
					delete node;
				}
				else
				{
					// try to merge with next
					if (node->next && node->next->isFree)
					{
						// only merge no delete
						node->next->size += node->size;
						
						node->next->prev = node->prev;
						node->prev->next = node->next;	
						delete node;
					}
					else
					{
						// case THREE
						// this is the case no merge happens and we need to reset the flag of node only
						node->isFree = true;
					}
				}
				// always add this
				nTotalFree += node->size;				
				break;
			}
			node = node->next;
		}
	}
};


question 8

void quicksort(char* array);
void doQuickSort(char* array, char pivat, int len);
// the pivat is chosen in the middle of subarray, and 
void doQuickSort(char* array, char pivat, int len)
{
	char* pLeft = NULL, *pRight = NULL;
	char ch;
	int leftLen = 0, rightLen = 0;

	if (len <= 1)
	{
		return;
	}
	pLeft = array;
	pRight = array + len - 1;

	while (pRight > pLeft)
	{
		while (*pRight >= pivat)
		{
			pRight -- ;
		}
		while (*pLeft <= pivat)
		{
			pLeft ++;
		}
		// now swap
		ch = *pRight;
		*pRight = *pLeft;
		*pLeft = ch;
	}
	// this may happen 
	if (pRight < pLeft)
	{
		// now swap
		ch = *pRight;
		*pRight = *pLeft;
		*pLeft = ch;
	}

	// now recursion
	leftLen = len/2;
	rightLen = len - leftLen;
	// the pivat is chosen in the middle of subarray, and 
	doQuickSort(array, array[leftLen/2], leftLen);
	doQuickSort(array + leftLen, array[leftLen + rightLen/2], rightLen);
}


question 9
//recursion version of binary_search
bool numExists_recursion(int array[], int array_len, int num)
{
	int len = 0;
	// make sure the array_len is at least 3

	// for optimization, we do all cases of under 2
	if (array_len == 0)
	{
		return false;
	}
	if (array_len == 1)
	{
		return array[0] == num;
	}
	if (array_len == 2)
	{
		if (array[0] == num)
		{
			return true;
		}
		else
		{
			return array[1] == num;
		}
	}
	len = array_len/2;

	if (array[len] == num)
	{
		return true;
	}
	//actually I think we can even optimize here by "checking array_len" BEFORE entering recursion
	// to save all those overhead of function calls during recursion.
	if (array[len] > num)
	{
		return numExists_recursion(array + len + 1, array_len - len - 1, num);
	}
	else
	{
		return numExists_recursion(array, len, num);
	}
}


//iteration version of binary_search
bool numExists_iteration(int array[], int array_len, int num)
{
	int start = 0, int end = array_len, len = array_len, int index = 0;

	if (array_len <= 0)
	{
		return false;
	}

	do
	{
		index = start + len / 2;

		if (array[index] == num)
		{
			return true;
		}
		if (array[index] < num)
		{
			//right
			start = index + 1;
		}
		else
		{
			// left
			end = index - 1;
		}
		len = end - start;
	}
	while (len > 2);
	
	// for optimization, we do all cases of under 2

	if (len <= 0)
	{
		return false;
	}
	if (len == 1)
	{
		return array[start] == num;
	}
	if (len == 2)
	{
		if (array[start] == num)
		{
			return true;
		}
		else
		{
			return array[start+1] == num;
		}
	}
	// cannot reach here
}



question 10

// I think there are two potential problems here.
// 1. how to prevent overflow/underflow of result. The maximum number of digits should not be more than 10
// or 0x7fff ffff, 
// 2. how to return failure?
bool atoi(char*str, int* i)
{
	int result = 0;
	char digit = 0;
	bool isNegative = false, bFirst = true;
	char* ptr = NULL;
	int counter = 0;

	if (ptr == NULL)
	{
		return false;
	}
	ptr = str;
	// first we need to check if there is char for sign
	if (*ptr == '-')
	{
		isNegative = true;
		ptr ++;
	}

	while (*ptr != '\0')
	{
		digit = *ptr - '0';
		if (digit > 9 || digit < 0)
		{
			return false;
		}
		
		result = result * 10 + digit;
		if (bFirst)
		{
			bFirst = false;
			if (isNegative)
			{
				result *= -1;
			}
		}
		counter ++;
		if (counter >11)
		{
			return false;
		}
		ptr ++;

	}
	return true;
}

question 11
// basically there are a few ways to implement singleton.
// 1. The first way is what we deal with COM objects when any instance is solely created with
// a global function called "CreateInstance" with different "classid" to return resultant instance.
// By using this universal function to create instance, you can control how singleton is implemented.
// 

class Singleton
{   ...
};

Singleton* singlePointer = NULL;

HRESULT CreateInstance(ISHELL* piShell, CLASSID clsid, void** ppResult)
{
	switch (clsid)
	{
	case CLASSID_MYSINGLETON:
		// here we need to make it thread-safe
		Enter_Critical_Section();
		//here we need to prevent multi-thread checking of possible race-condition
		if (singlePointer == NULL)
		{
			//then create it and ONLY once
			singlePointer = new Singleton;
			// add reference to the object instance, and check success of resultants.
		}
		*ppResult = singlePoint;
		Leave_Critical_Section();
		break;
		...
	}
	...
}

// 2. Another method is to declare the constructor inside its "protected" part, so that
// no outsider can access this constructor EXCEPT its derived class.

class Base
{
protected:
	Base();
};

Base* Derived::pBase = NULL;

class Derived : public Base
{
private:
	static Base* pBase;
public:
	Base* createBase()
	{
		//
		Enter_Critical_Section();
		// here we need to prevent multi-thread checking of possible race-condition
		if (pBase == NULL)
		{
			pBase = new Base();
		}
		return pBase;
		Leave_Critical_Section();
	}
};