Tech Interview Questions

Algorithms and Tech interview questions

[techquestions-blog]

Game of Boggle

Question:

Given a Boggle grid and a dictionary of words, write a program to identify all the dictionary words present in the boggle grid.

Solution:

// Game of Boggle #include <string> #include <iostream> #include <vector> #include <hash_set> using namespace std; typedef unsigned long ULONG; typedef long LONG; typedef bool BOOLEAN; typedef struct _BOGGLE_WORD { ULONG Begin[2]; ULONG End[2]; wstring strWord; }BOGGLE_WORD; typedef vector<BOGGLE_WORD> BOGGLE_WORD_LIST; typedef hash_set<wstring> DICTIONARY; typedef vector<vector<wchar_t>> BOGGLE_GRID; class CBoggle { private: BOGGLE_WORD_LIST CheckRow( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Row ); BOGGLE_WORD_LIST CheckColumn( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Column ); BOGGLE_WORD_LIST CheckForwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ); BOGGLE_WORD_LIST CheckBackwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ); public: BOGGLE_WORD_LIST FindWordsinBoggle( __in DICTIONARY Dictionary, __in BOGGLE_GRID BoggleGrid ); void PrintBoggleWords( __in BOGGLE_WORD_LIST BoggleWordList ); }; void CBoggle::PrintBoggleWords( __in BOGGLE_WORD_LIST BoggleWordList ) { for (ULONG WordIter = 0; WordIter < BoggleWordList.size(); WordIter++) { wcout<<"("<<BoggleWordList[WordIter].Begin[0]<<","<<BoggleWordList[WordIter].Begin[1]<<") to "; wcout<<"("<<BoggleWordList[WordIter].End[0]<<","<<BoggleWordList[WordIter].End[1]<<") "; wcout<<BoggleWordList[WordIter].strWord.data()<<endl; } } BOGGLE_WORD_LIST CBoggle::CheckRow( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Row ) { BOGGLE_WORD_LIST BoggleWordList; wstring strRow = L""; for (ULONG Column = 0; Column < BoggleGrid[Row].size(); Column++) { strRow += BoggleGrid[Row][Column]; } for (ULONG Begin = 0; Begin < strRow.size(); Begin++) { for (ULONG End = Begin; End < strRow.size(); End++) { wstring strSub = strRow.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row; BoggleWord.Begin[1] = Begin; BoggleWord.End[0] = Row; BoggleWord.End[1] = End; BoggleWord.strWord = strSub; // wcout<<"Row: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row; BoggleWord.Begin[1] = End; BoggleWord.End[0] = Row; BoggleWord.End[1] = Begin; BoggleWord.strWord = strSub; // wcout<<"Row Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckColumn( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Column ) { BOGGLE_WORD_LIST BoggleWordList; wstring strColumn = L""; for (ULONG Row = 0; Row < BoggleGrid.size(); Row++) { strColumn += BoggleGrid[Row][Column]; } for (ULONG Begin = 0; Begin < strColumn.size(); Begin++) { for (ULONG End = Begin; End < strColumn.size(); End++) { wstring strSub = strColumn.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Begin; BoggleWord.Begin[1] = Column; BoggleWord.End[0] = End; BoggleWord.End[1] = Column; BoggleWord.strWord = strSub; // wcout<<"Column: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = End; BoggleWord.Begin[1] = Column; BoggleWord.End[0] = Begin; BoggleWord.End[1] = Column; BoggleWord.strWord = strSub; // wcout<<"Column Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckForwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ) { BOGGLE_WORD_LIST BoggleWordList; ULONG Row = (ULONG)(std::max<int>(BoggleGrid.size() - 1 - Dist, 0)); ULONG Column = (ULONG)(std::max<int>(Dist - BoggleGrid.size() + 1, 0)); wstring strDiag = L""; ULONG RowIter = Row; ULONG ColIter = Column; while (true) { if (RowIter >= BoggleGrid.size() || ColIter >= BoggleGrid[Row].size()) { break; } strDiag += BoggleGrid[RowIter++][ColIter++]; } for (ULONG Begin = 0; Begin < strDiag.size(); Begin++) { for (ULONG End = Begin; End < strDiag.size(); End++) { wstring strSub = strDiag.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + Begin; BoggleWord.Begin[1] = Column + Begin; BoggleWord.End[0] = Row + End; BoggleWord.End[1] = Column + End; BoggleWord.strWord = strSub; // wcout<<"Forward diag: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + End; BoggleWord.Begin[1] = Column + End; BoggleWord.End[0] = Row + Begin; BoggleWord.End[1] = Column + Begin; BoggleWord.strWord = strSub; // wcout<<"Forward Diag Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckBackwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ) { BOGGLE_WORD_LIST BoggleWordList; ULONG Row = std::max<LONG>(Dist - BoggleGrid[0].size() - 1, 0); LONG Column = 0; if (Dist >= BoggleGrid[0].size()) { Column = BoggleGrid[0].size()-1; } wstring strDiag = L""; ULONG RowIter = Row; LONG ColIter = Column; while (true) { if (RowIter >= BoggleGrid.size() || ColIter < 0) { break; } strDiag += BoggleGrid[RowIter++][ColIter--]; } for (ULONG Begin = 0; Begin < strDiag.size(); Begin++) { for (ULONG End = Begin; End < strDiag.size(); End++) { wstring strSub = strDiag.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + Begin; BoggleWord.Begin[1] = Column - Begin; BoggleWord.End[0] = Row + End; BoggleWord.End[1] = Column - End; BoggleWord.strWord = strSub; // wcout<<"Backward Diag: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + End; BoggleWord.Begin[1] = Column - End; BoggleWord.End[0] = Row + Begin; BoggleWord.End[1] = Column - Begin; BoggleWord.strWord = strSub; // wcout<<"Backward diag reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::FindWordsinBoggle( __in DICTIONARY Dictionary, __in BOGGLE_GRID BoggleGrid ) { BOGGLE_WORD_LIST BoggleWordList; BOGGLE_WORD_LIST AppendWordList; for (ULONG Row = 0; Row < BoggleGrid.size(); Row++) { AppendWordList = CheckRow(BoggleGrid, Dictionary, Row); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Column = 0; Column < BoggleGrid[0].size(); Column++) { AppendWordList = CheckColumn(BoggleGrid, Dictionary, Column); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Dist = 0; Dist < BoggleGrid.size()+BoggleGrid[0].size()-1; Dist++) { AppendWordList = CheckForwardDiag(BoggleGrid, Dictionary, Dist); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Dist = 0; Dist < BoggleGrid.size() + BoggleGrid[0].size()-1; Dist++) { AppendWordList = CheckBackwardDiag(BoggleGrid, Dictionary, Dist); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } PrintBoggleWords(BoggleWordList); return BoggleWordList; }

[techquestions-blog]

Smart Pointer

Question:

Write an implementation for a reference counted Auto/Smart pointer.

Solution:

TO DO: Make it thread-safe.

// Reference Counted Smart Pointer typedef unsigned long ULONG; template<class T> class CSharedPtr { protected: T* m_pT; ULONG *m_pRefCount; virtual void AddRef() { if (m_pRefCount == NULL) { m_pT = new(T); m_pRefCount = new(ULONG); *m_pRefCount = 0; } (*m_pRefCount)++; } virtual void Release() { if (m_pRefCount && --(*m_pRefCount) == 0) { delete m_pT; m_pT = NULL; delete m_pRefCount; m_pRefCount = NULL; } } public: CSharedPtr() { m_pT = NULL; m_pRefCount = NULL; AddRef(); } CSharedPtr(T* pValue) { m_pT = pValue; m_pRefCount = NULL; AddRef(); } CSharedPtr(const CSharedPtr<T>& SharedPtr) { m_pT = SharedPtr.m_pT; m_pRefCount = SharedPtr.m_pRefCount; AddRef(); } ~CSharedPtr() { Release(); } T* operator-> () { return m_pT; } T& operator* () { return *m_pT; } CSharedPtr<T>& operator= (const CSharedPtr<T>& SharedPtr) { if (this != &SharedPtr) { delete m_pT; delete m_pRefCount; m_pT = SharedPtr.m_pT; m_pRefCount = SharedPtr.m_pRefCount; AddRef(); } return *this; } };

[techquestions-blog]

Generic Heap

Question:

Write an implementation for a Generic Heap.

Solution:

// Generic Heap #include <vector> using namespace std; typedef unsigned long ULONG; template<class T> class TMin { public: bool operator() (T First, T Second) { return (First < Second); } }; template<class T> class TMax { public: bool operator() (T First, T Second) { return (First > Second); } }; template<class T, template<class U> class CompareU> class CHeap { private: vector<T> m_Heap; void PushDown( __in ULONG CurrentIndex ) { CompareU<T> Compare; ULONG HeapSize = m_Heap.size(); ULONG ChildIndex = GetLeftIndex(CurrentIndex); ULONG RightIndex = GetRightIndex(CurrentIndex); if (RightIndex < HeapSize && Compare(m_Heap[RightIndex], m_Heap[ChildIndex])) { ChildIndex = RightIndex; } if (ChildIndex < HeapSize) { T temp = m_Heap[ChildIndex]; m_Heap[ChildIndex] = m_Heap[CurrentIndex]; m_Heap[CurrentIndex] = temp; } } void PushUp( __in ULONG ChildIndex ) { CompareU<T> Compare; ULONG CurrentIndex = ChildIndex; ULONG ParentIndex = CurrentIndex >> 1; while (CurrentIndex != ParentIndex && Compare(m_Heap[CurrentIndex], m_Heap[ParentIndex])) { T temp = m_Heap[ParentIndex]; m_Heap[ParentIndex] = m_Heap[CurrentIndex]; m_Heap[CurrentIndex] = temp; CurrentIndex = ParentIndex; ParentIndex = CurrentIndex >> 2; } } ULONG GetLeftIndex( __in ULONG CurrentIndex ) { return (CurrentIndex << 1) + 1; } ULONG GetRightIndex( __in ULONG CurrentIndex ) { return (CurrentIndex << 1) + 2; } public: CHeap() { } ~CHeap(){} void Insert( __in T elem ) { m_Heap.push_back(elem); PushUp(m_Heap.size() - 1); } void Delete( __in T elem ); T GetTop() { T Top = m_Heap[0]; m_Heap[0] = m_Heap[m_Heap.size()-1]; m_Heap.pop_back(); PushDown(0); return Top; } };

[techquestions-blog]

Generic Binary Search Tree

Question:

Write an implementation for a Generic Binary Search Tree

Solution:

This still needs Balancing

// Generic Binary Search Tree typedef unsigned long ULONG; template<class T> struct BINARY_TREE_NODE { T Key; BINARY_TREE_NODE *pParent; BINARY_TREE_NODE *pLeft; BINARY_TREE_NODE *pRight; BINARY_TREE_NODE() { pParent = NULL; pLeft = NULL; pRight = NULL; } }; template<class T> class CBinarySearchTree { private: BINARY_TREE_NODE<T> *m_pRoot; void Clear( __in BINARY_TREE_NODE<T> *&pCurrentNode ); void SwapKeys( __in BINARY_TREE_NODE<T>* pFirstNode, __in BINARY_TREE_NODE<T>* pSecondNode ); public: CBinarySearchTree() { m_pRoot = NULL; } ~CBinarySearchTree() { Clear(m_pRoot); } BINARY_TREE_NODE<T> *GetRoot() { return m_pRoot; } void InsertNode( __in T key, __in_opt BINARY_TREE_NODE<T>* pRootNode = NULL ); void DeleteNode( __in T key, __in BINARY_TREE_NODE<T>* pRootNode ); BINARY_TREE_NODE<T>* SearchNode( __in T key, __in_opt BINARY_TREE_NODE<T>* pRootNode = NULL ); ULONG GetHeight( __in_opt BINARY_TREE_NODE<T>* pRootNode = NULL ); }; template<class T> void CBinarySearchTree<T>::Clear( __in BINARY_TREE_NODE<T> *&pCurrentNode ) { if (pCurrentNode == NULL) { return; } if (pCurrentNode->pLeft != NULL) { Clear(pCurrentNode->pLeft); } if (pCurrentNode->pRight != NULL) { Clear(pCurrentNode->pRight); } delete pCurrentNode; pCurrentNode = NULL; } template<class T> void CBinarySearchTree<T>::SwapKeys( __in BINARY_TREE_NODE<T>* pFirstNode, __in BINARY_TREE_NODE<T>* pSecondNode ) { if (pFirstNode == NULL || pSecondNode == NULL) { // throw or log error; return; } T TempKey = pFirstNode->Key; pFirstNode->Key = pSecondNode->Key; pSecondNode->Key = TempKey; } template<class T> void CBinarySearchTree<T>::DeleteNode( __in T key, __in BINARY_TREE_NODE<T>* pRootNode ) { if (pRootNode == NULL) { return; } if (pRootNode->Key == key) { BINARY_TREE_NODE<T>* pTempNode = pRootNode; while (true) { if (pTempNode->pLeft == NULL && pTempNode->pRight == NULL) { if (pTempNode->pParent != NULL) { (pTempNode->pParent->pLeft == pTempNode)?(pTempNode->pParent->pLeft = NULL):(pTempNode->pParent->pRight = NULL); } if (pRootNode == pTempNode) { if (m_pRoot == pRootNode) { m_pRoot = NULL; } delete pRootNode; } else { delete pTempNode; } return; } if (pTempNode->pLeft != NULL) { SwapKeys(pTempNode, pTempNode->pLeft); pTempNode = pTempNode->pLeft; } else { SwapKeys(pTempNode, pTempNode->pRight); pTempNode = pTempNode->pRight; } } } else if (pRootNode->Key < key) { DeleteNode(key, pRootNode->pRight); } else { DeleteNode(key, pRootNode->pLeft); } } template<class T> void CBinarySearchTree<T>::InsertNode( __in T key, __in_opt BINARY_TREE_NODE<T>* pParent ) { if (pParent == NULL) { pParent = m_pRoot; } if (pParent == NULL) { BINARY_TREE_NODE<T> *pNode = new BINARY_TREE_NODE<T>; pNode->Key = key; m_pRoot = pNode; return; } if (pParent->Key < key) { if (pParent->pLeft == NULL) { BINARY_TREE_NODE<T> *pNode = new BINARY_TREE_NODE<T>; pNode->Key = key; pNode->pParent = pParent; pParent->pLeft = pNode; } else { InsertNode(key, pParent->pLeft); } } else if (pParent->Key > key) { if (pParent->pRight == NULL) { BINARY_TREE_NODE<T> *pNode = new BINARY_TREE_NODE<T>; pNode->Key = key; pNode->pParent = pParent; pParent->pRight = pNode; } else { InsertNode(key, pParent->pRight); } } } template <class T> ULONG CBinarySearchTree<T>::GetHeight( __in_opt BINARY_TREE_NODE<T> *pCurrentNode ) { if (pCurrentNode == NULL) { pCurrentNode = m_pRoot; } if (pCurrentNode == NULL) { return 0; } if (pCurrentNode->pLeft == NULL && pCurrentNode->pRight == NULL) { return 1; } if (pCurrentNode->pRight == NULL) { return GetHeight(pCurrentNode->pLeft)+1; } if (pCurrentNode->pLeft == NULL) { return GetHeight(pCurrentNode->pRight)+1; } return max(GetHeight(pCurrentNode->pLeft), GetHeight(pCurrentNode->pRight))+1; } template <class T> BINARY_TREE_NODE<T>* CBinarySearchTree<T>::SearchNode( __in T key, __in_opt BINARY_TREE_NODE<T>* pCurrentNode ) { if (m_pRoot == NULL) { return m_pRoot; } if (pCurrentNode == NULL) { pCurrentNode = m_pRoot; } if (pCurrentNode->Key == key) { return pCurrentNode; } if (pCurrentNode->Key < key) { if (pCurrentNode->pRight != NULL) { return SearchNode(key, pCurrentNode->pRight); } return NULL; } if (pCurrentNode->Key > key) { if (pCurrentNode->pLeft != NULL) { return SearchNode(key, pCurrentNode->pLeft); } return NULL; } }

[techquestions-blog]

Generic Queue

Question:

Write an implementation for a Generic Queue.

Solution:

Take a look at the post Generic Stack for a stack implementation.

// Generic Queue template <typename T> class CQueue { private: CStack<T> m_EnqueueStack; CStack<T> m_DequeueStack; public: CQueue(){} ~CQueue(){} void Enqueue(T elem) { m_EnqueueStack.Push(elem); } T Dequeue() throw (...) { if (m_DequeueStack.GetSize() != 0) { return m_DequeueStack.Pop(); } if (m_EnqueueStack.GetSize() == 0) { throw L"Error empty queue"; } ULONG TransSize = m_EnqueueStack.GetSize(); for (ULONG TransIter = 0; TransIter < TransSize; TransIter++) { m_DequeueStack.Push(m_EnqueueStack.Pop()); } return m_DequeueStack.Pop(); } ULONG GetSize() { return (m_EnqueueStack.GetSize() + m_DequeueStack.GetSize()); } };

[techquestions-blog]

Generic Stack

Question:

Write a generic stack implementation with push and pop routines.

Solution:

// Generic Stack Implementation typedef unsigned long ULONG; template <typename T> struct CLinkedListNode { T m_Key; CLinkedListNode* m_pNext; }; template <typename T> class CStack { CLinkedListNode<T>* m_pTop; ULONG m_Size; public: CStack() { m_Size = 0; m_pTop = NULL; } ~CStack() { CLinkedListNode<T> *pTempNode = m_pTop; while (pTempNode != NULL) { m_pTop = pTempNode->m_pNext; delete pTempNode; pTempNode = m_pTop; } m_Size = 0; } void Push(T elem) { CLinkedListNode<T> *pTempNode = new CLinkedListNode<T>; if (pTempNode == NULL) { wprintf(L"Error: OOM ", __FUNCTION__); return; } pTempNode->m_Key = elem; pTempNode->m_pNext = m_pTop; m_pTop = pTempNode; m_Size++; } T Pop() throw (...) { if (m_pTop == NULL || m_Size == 0) { throw L"Error Stack Empty"; } CLinkedListNode<T> *pTempNode = m_pTop; m_pTop = pTempNode->m_pNext; m_Size--; T retVal = pTempNode->m_Key; delete pTempNode; return retVal; } ULONG GetSize() { return m_Size; } };

[techquestions-blog]

Princess in a Maze

Question:

The princess has been hidden in a multiple-level maze by Jaffer and the prince has to find the shortest path to the princess to save her from being eaten away by dragons. You are given that the maze can be multiple levels and each level can be of any shape. There are pillars in the maze which the prince cannot pass through. Design a class to find the shortest path that leads the prince to the princess.

Sample Maze:

1 . . o o . . . . o o o . . o . o o o o o o . . o . 2

'1' - Prince, '2' - Princess, 'o' - Pillar/Obstruction, '.' - Freeway

Solution:

// Jaffer's Maze #include <iostream> #include <string> #include <vector> using namespace std; typedef unsigned long ULONG; typedef bool BOOLEAN; // enum indicating what is present in each location in the maze typedef enum LOCATION_INFO_SINGLE_POINT { LOCATION_ID_PRINCE, LOCATION_ID_FREE, LOCATION_ID_PILLAR, LOCATION_ID_PRINCESS, LOCATION_ID_INVALID }; // Vectors containing all location information typedef vector<LOCATION_INFO_SINGLE_POINT> LOCATION_INFO_SINGLE_ROW; typedef vector<LOCATION_INFO_SINGLE_ROW> LOCATION_INFO_SINGLE_LEVEL; typedef vector<LOCATION_INFO_SINGLE_LEVEL> LOCATION_INFO_MULTIPLE_LEVEL; // enum representing each location visited/not visited by the prince typedef enum VISIT_INFO_SINGLE_POINT { VISIT_ID_NOT_VISITED, VISIT_ID_VISITING, VISIT_ID_VISITED, VISIT_ID_INVALID }; // Vectors containting all visit information typedef vector<VISIT_INFO_SINGLE_POINT> VISIT_INFO_SINGLE_ROW; typedef vector<VISIT_INFO_SINGLE_ROW> VISIT_INFO_SINGLE_LEVEL; typedef vector<VISIT_INFO_SINGLE_LEVEL> VISIT_INFO_MULTIPLE_LEVEL; // Definition of a location point in the maze typedef struct MAZE_LOCATION { ULONG Level; ULONG Row; ULONG Column; MAZE_LOCATION() { Level = 0; Row = 0; Column = 0; } MAZE_LOCATION(ULONG _Level, ULONG _Row, ULONG _Column) { Level = _Level; Row = _Row; Column = _Column; } void Init(ULONG _Level, ULONG _Row, ULONG _Column) { Level = _Level; Row = _Row; Column = _Column; } int operator == (MAZE_LOCATION InputLocation) { return ((Level == InputLocation.Level) && (Row == InputLocation.Row) && (Column == InputLocation.Column)); } }MazeLocation; // A path in the maze as a vector of maze location points typedef vector<MAZE_LOCATION> MAZE_PATH; class CJaffersMaze { // All location information for the maze LOCATION_INFO_MULTIPLE_LEVEL m_LocationInfo; // All visit information for the maze VISIT_INFO_MULTIPLE_LEVEL m_VisitInfo; // Prince's Initial Location MazeLocation m_LocationPrince; // Princess's location MazeLocation m_LocationPrincess; // Used to see if the maze has been parsed completely BOOLEAN m_bLastLevelRead; // Will contain a shortest path to princess MAZE_PATH m_ShortestPathToPrincess; // Length of the shortest path to princess ULONG m_ShortestPathLength; public: CJaffersMaze() { m_bLastLevelRead = false; m_ShortestPathLength = 0; } ~CJaffersMaze() {} // Parse one level at a time for location information void ParseSingleLevel( __in ULONG CurrentLevel ); // Parse all levels in maze for location information void ParseAllLevels(); // Print all level location information void PrintAllLevelInfo(); // Initializing routine to start the rescue pricess void StartRescuePrincess(); // Finds the shortest path to the princess void RescuePrincessFast( __in MAZE_LOCATION CurrentLocation, __in ULONG PathLength, __out BOOLEAN &bAddToPath ); }; void CJaffersMaze::PrintAllLevelInfo() { wprintf(L"Level Info:\n"); for (unsigned long LevelIter = 0; LevelIter < m_LocationInfo.size(); LevelIter++) { wprintf(L"Level %d:\n", LevelIter+1); for (unsigned long RowIter = 0; RowIter < m_LocationInfo[LevelIter].size(); RowIter++) { for (unsigned int ColumnIter = 0; ColumnIter < m_LocationInfo[LevelIter][RowIter].size(); ColumnIter++) { wprintf(L"%d ", (LOCATION_INFO_SINGLE_POINT)m_LocationInfo[LevelIter][RowIter][ColumnIter]); } wprintf(L"\n"); } } } void CJaffersMaze::ParseSingleLevel( __in ULONG CurrentLevel ) { LOCATION_INFO_SINGLE_LEVEL LocationInfoSingleLevel; VISIT_INFO_SINGLE_LEVEL VisitInfoSingleLevel; wstring strRow; ULONG CurrentRow = 0; BOOLEAN bEntered = false; while (getline(wcin, strRow)) { bEntered = true; LOCATION_INFO_SINGLE_ROW LocationInfoSingleRow; VISIT_INFO_SINGLE_ROW VisitInfoSingleRow; if (strRow.length() == 0) { // Level done break; } ULONG CurrentColumn = 0; for (ULONG CharIterator = 0; CharIterator < strRow.size(); CharIterator++) { if (strRow[CharIterator] == L' ') { continue; } switch (strRow[CharIterator]) { case L'1': m_LocationPrince.Init(CurrentLevel, CurrentRow, CurrentColumn); LocationInfoSingleRow.push_back(LOCATION_ID_PRINCE); break; case L'.': LocationInfoSingleRow.push_back(LOCATION_ID_FREE); break; case L'o': LocationInfoSingleRow.push_back(LOCATION_ID_PILLAR); break; case L'2': m_LocationPrincess.Init(CurrentLevel, CurrentRow, CurrentColumn); LocationInfoSingleRow.push_back(LOCATION_ID_PRINCESS); break; default: break; } VisitInfoSingleRow.push_back(VISIT_ID_NOT_VISITED); CurrentColumn++; } LocationInfoSingleLevel.push_back(LocationInfoSingleRow); VisitInfoSingleLevel.push_back(VisitInfoSingleRow); CurrentRow++; bEntered = false; } if (!bEntered) { // All level location info gathered m_bLastLevelRead = true; } m_LocationInfo.push_back(LocationInfoSingleLevel); m_VisitInfo.push_back(VisitInfoSingleLevel); } void CJaffersMaze::ParseAllLevels() { ULONG CurrentLevel = 0; while (!m_bLastLevelRead) { ParseSingleLevel(CurrentLevel); CurrentLevel++; } // PrintAllLevelInfo(); } void CJaffersMaze::RescuePrincessFast( __in MAZE_LOCATION CurrentLocation, __in ULONG PathLength, __out BOOLEAN &bAddToPath ) { if ((CurrentLocation == m_LocationPrince) && ((m_ShortestPathLength == 0) || (m_ShortestPathLength > PathLength))) { // Found a path or a path shorter than the previous m_ShortestPathLength = PathLength; // Clear previously saved path m_ShortestPathToPrincess.clear(); // Add location to path m_ShortestPathToPrincess.push_back(CurrentLocation); bAddToPath = true; wprintf(L"Prince Location:(%d, %d, %d)\n", CurrentLocation.Level, CurrentLocation.Row, CurrentLocation.Column); return; } m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column] = VISIT_ID_VISITING; bool bAddToPathLeft = false; bool bAddToPathRight = false; bool bAddToPathFront = false; bool bAddToPathBack = false; bool bAddToPathUp = false; bool bAddToPathDown = false; if ((CurrentLocation.Level > 0) && (m_VisitInfo[CurrentLocation.Level-1][CurrentLocation.Row][CurrentLocation.Column] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level-1][CurrentLocation.Row][CurrentLocation.Column] != LOCATION_ID_PILLAR)) { // Look Below RescuePrincessFast(MazeLocation(CurrentLocation.Level-1, CurrentLocation.Row, CurrentLocation.Column), PathLength+1, bAddToPathDown); } if ((CurrentLocation.Row > 0) && (m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row-1][CurrentLocation.Column] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level][CurrentLocation.Row-1][CurrentLocation.Column] != LOCATION_ID_PILLAR)) { // Look Behind RescuePrincessFast(MazeLocation(CurrentLocation.Level, CurrentLocation.Row-1, CurrentLocation.Column), PathLength+1, bAddToPathBack); } if ((CurrentLocation.Column > 0) && (m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column-1] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column-1] != LOCATION_ID_PILLAR)) { // Look Left RescuePrincessFast(MazeLocation(CurrentLocation.Level, CurrentLocation.Row, CurrentLocation.Column-1), PathLength+1, bAddToPathLeft); } if ((CurrentLocation.Level+1 < m_LocationInfo.size()) && (m_VisitInfo[CurrentLocation.Level+1][CurrentLocation.Row][CurrentLocation.Column] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level+1][CurrentLocation.Row][CurrentLocation.Column] != LOCATION_ID_PILLAR)) { // Look Above RescuePrincessFast(MazeLocation(CurrentLocation.Level+1, CurrentLocation.Row, CurrentLocation.Column), PathLength+1, bAddToPathUp); } if ((CurrentLocation.Row+1 < m_LocationInfo[CurrentLocation.Level].size()) && (m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row+1][CurrentLocation.Column] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level][CurrentLocation.Row+1][CurrentLocation.Column] != LOCATION_ID_PILLAR)) { // Look Ahead RescuePrincessFast(MazeLocation(CurrentLocation.Level, CurrentLocation.Row+1, CurrentLocation.Column), PathLength+1, bAddToPathFront); } if ((CurrentLocation.Column+1 < m_LocationInfo[CurrentLocation.Level][CurrentLocation.Row].size()) && (m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column+1] == VISIT_ID_NOT_VISITED) && (m_LocationInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column+1] != LOCATION_ID_PILLAR)) { // Look Right RescuePrincessFast(MazeLocation(CurrentLocation.Level, CurrentLocation.Row, CurrentLocation.Column+1), PathLength+1, bAddToPathRight); } m_VisitInfo[CurrentLocation.Level][CurrentLocation.Row][CurrentLocation.Column] = VISIT_ID_NOT_VISITED; if (bAddToPathUp || bAddToPathDown || bAddToPathLeft || bAddToPathRight || bAddToPathFront || bAddToPathBack) { // Current Location on way to shortest path m_ShortestPathToPrincess.push_back(CurrentLocation); bAddToPath = true; if (PathLength == 0) { wprintf(L"Princess Location: (%d, %d, %d)\n", CurrentLocation.Level, CurrentLocation.Row, CurrentLocation.Column); } else { wprintf(L"Intermediate Location:(%d, %d, %d)\n", CurrentLocation.Level, CurrentLocation.Row, CurrentLocation.Column); } } } void CJaffersMaze::StartRescuePrincess() { ParseAllLevels(); BOOLEAN bAddToPath = false; wprintf(L"Shortest Path to the Princess:\n"); RescuePrincessFast(m_LocationPrincess, 0, bAddToPath); }

[techquestions-blog]

Write a Check

Question:

Write a module that takes an amount as a number and returns it in words.

Solution:

// Write a Check #include <string> using namespace std; #define PARSE_SIZE 1000 typedef unsigned long ULONG; // Stings representing units place digits static const wstring UnitsStrings[]= { L"", L"One ", L"Two ", L"Three ", L"Four ", L"Five ", L"Six ", L"Seven ", L"Eight ", L"Nine " }; // String representing 11 to 19 static const wstring SpecialStrings[]= { L"", L"Eleven ", L"Twelve ", L"Thirteen ", L"Fourteen ", L"Fifteen ", L"Sixteen ", L"Seventeen ", L"Eighteen ", L"Nineteen " }; // String representing tens place digits static const wstring TensStrings[]= { L"", L"Ten ", L"Twenty ", L"Thirty ", L"Forty ", L"Fifty ", L"Sixty ", L"Seventy ", L"Eighty ", L"Ninety " }; // String representing hundreds place digits static const wstring HundredsStrings[]= { L"", L"One Hundred ", L"Two Hundred ", L"Three Hundred ", L"Four Hundred ", L"Five Hundred ", L"Six Hundred ", L"Seven Hundred ", L"Eight Hundred ", L"Nine Hundred " }; // Strings representing different blocks of 3 digits each static const wstring AppendStrings[]= { L"", L"Thousand ", L"Million ", L"Billion ", L"Trillion " }; // Parses each block of 3 digits wstring ParseBlock( __in ULONG Input, __in ULONG AppendIndex ) { wstring strOutput = L""; if (Input == 0) { return strOutput; } ULONG Hundreds = Input/100; ULONG Tens = (Input%100)/10; ULONG Units = (Input%100)%10; if (Tens == 1 && Units != 0) { // Numbers ending with 11 to 19 strOutput += HundredsStrings[Hundreds] + SpecialStrings[Units] + AppendStrings[AppendIndex]; } else { strOutput += HundredsStrings[Hundreds] + TensStrings[Tens] + UnitsStrings[Units] + AppendStrings[AppendIndex]; } return strOutput; } wstring WriteCheck( __in ULONG InputAmount ) { wstring strCheckAmount; ULONG CurrentBlock = 0; ULONG AppendIndex = 0; // Parcing one block of 3 digits at a time while (true) { CurrentBlock = InputAmount%PARSE_SIZE; if (CurrentBlock == 0) { break; } strCheckAmount = ParseBlock(CurrentBlock, AppendIndex) + strCheckAmount; AppendIndex++; InputAmount /= PARSE_SIZE; } return strCheckAmount; }

[techquestions-blog]

Lucky Number

Question:

A lottery defined a lucky number as a number where the sum of digits is the most significant half is equal to the sum of digits in the least significant half.

Assume that all the lottery tickets have even number of digits.

Consider two 6-digit numbers - 123456, 123600

For 123456

Sum of Most Significant Digits = 1 + 2 + 3 = 6

Sum of Least Significant Digits = 4 + 5 + 6 = 15

So 123456 is not a lucky number.

For 123600

Sum of Most Significant Digits = 1 + 2 + 3 = 6

Sum of Least Significant Digits = 6 + 0 + 0 = 6

So 123600 is a lucky number.

Solution:

typedef unsigned long ULONG; typedef bool BOOLEAN; BOOLEAN CheckLuckyTicket( __in ULONG TicketNumber, __in ULONG NDigits ) { ULONG LSDSum = 0; ULONG MSDSum = 0; for (ULONG DigitIter = 0; DigitIter < NDigits; DigitIter++) { if (DigitIter < NDigits/2) { // Adding the Least Significant Digits LSDSum += TicketNumber%10; } else { // Adding the Most Significant Digits MSDSum += TicketNumber%10; } // Removing the Least Significant Digit TicketNumber /= 10; } return (LSDSum == MSDSum); }

[techquestions-blog]

Anagrams

Question:

Write a program that takes a list of strings and groups all the anagrams together.

Solution:

// Anagrams #include <string> #include <vector> using namespace std; #define MAX_LENGTH 256 #define NUM_ALPHABET 26 typedef bool BOOLEAN; typedef long LONG; typedef unsigned long ULONG; typedef wchar_t WCHAR; typedef vector<wstring> STRING_LIST; typedef STRING_LIST::iterator STRING_LIST_ITERATOR; class CAnagram { private: // Coded string contains the anagram code // Code contains the number of instances of each letter from the // alphabet in the string ULONG m_CodedString[NUM_ALPHABET]; // Length of the string ULONG m_StringLength; // List of all anagrams with the same code STRING_LIST m_StringList; public: CAnagram() { m_StringLength = 0; for (ULONG CodedIterator = 0; CodedIterator < NUM_ALPHABET; CodedIterator++) { m_CodedString[CodedIterator] = 0; } } ~CAnagram() { } void InitAnagram( __in wstring pstrInput ); BOOLEAN CheckAnagram( __in wstring pstrInput ); }; void CAnagram::InitAnagram( __in wstring pstrInput ) { // Initializing the string code for (ULONG CharIterator = 0; CharIterator < pstrInput.length(); CharIterator++) { LONG CurrentCode = tolower(pstrInput[CharIterator]) - L'a'; if (CurrentCode >= 0 && CurrentCode < NUM_ALPHABET) { m_CodedString[CurrentCode]++; } } m_StringLength = pstrInput.length(); m_StringList.push_back(pstrInput); } BOOLEAN CAnagram::CheckAnagram( __in wstring pstrInput ) { BOOLEAN bRetVal = false; ULONG CodedIterator = 0; ULONG CodedString[NUM_ALPHABET] = {0}; // Initial check if (pstrInput.length() != m_StringLength) { goto End; } // Creating the string code for (ULONG CharIterator = 0; CharIterator < pstrInput.length(); CharIterator++) { LONG CurrentCode = tolower(pstrInput[CharIterator]) - L'a'; if (CurrentCode >= 0 && CurrentCode < NUM_ALPHABET) { CodedString[CurrentCode]++; } } // Checking the input code with current anagram code for (CodedIterator = 0; CodedIterator < NUM_ALPHABET; CodedIterator++) { if (CodedString[CodedIterator] != m_CodedString[CodedIterator]) { // No Match break; } } // Anagram Match if (CodedIterator == NUM_ALPHABET) { m_StringList.push_back(pstrInput); bRetVal = true; } End: return bRetVal; } typedef vector<CAnagram> ANAGRAM_LIST; typedef ANAGRAM_LIST::iterator ANAGRAM_ITERATOR; class CAnagramListWrapper { private: ANAGRAM_LIST m_AnagramList; public: void InitAnagrams( __in STRING_LIST InputList ); }; void CAnagramListWrapper::InitAnagrams( __in STRING_LIST InputList ) { for (ULONG StringIter = 0; StringIter < InputList.size(); StringIter++) { ULONG AnagramIter = 0; for (AnagramIter = 0; AnagramIter < m_AnagramList.size(); AnagramIter++) { if (m_AnagramList[AnagramIter].CheckAnagram(InputList[StringIter])) { // Anagram Match break; } } if (AnagramIter == m_AnagramList.size()) { // New string CAnagram Anagram; Anagram.InitAnagram(InputList[StringIter]); m_AnagramList.push_back(Anagram); } } }

[techquestions-blog]

Palindrome

Question:

Write a function to check if a given string is a palindrome.

Solution:

// Palindrome #include <string> using namespace std; typedef bool BOOLEAN; typedef unsigned long ULONG; BOOLEAN IsPalindrome( __in wstring pstrInput ) { // The return value indicating whether the input string is a palindrome // initialized to false BOOLEAN bRetVal = false; // Iterators starting at either end of the input string ULONG ForwardIterator = 0; ULONG BackwardIterator = pstrInput.size()-1; while (true) { // Breaking condition if (ForwardIterator >= BackwardIterator) { // Palindrome bRetVal = true; break; } if (pstrInput[ForwardIterator] != pstrInput[BackwardIterator]) { // Not a palindrome goto End; } // Moving the iterators ForwardIterator++; BackwardIterator--; } End: return bRetVal; }

[techquestions-blog]

Missing Number

Question:

You are given a list of \( N-1 \) distinct numbers ranging from \( 1 \) through \( N \) in no particular order. Find the missing number in the range.

Solution:

//Missing Number #include "stdio.h" #include <iostream> #include <vector> using namespace std; typedef unsigned long ULONG; typedef vector<ULONG> NUMBER_LIST; int MissingNumber( __in ULONG MaxNumber, __in NUMBER_LIST NumberList ) { ULONG MissingNumber = 0; // Ensure you have MaxNumber - 1 numbers in the list ASSERT(NumberList.size() == MaxNumber-1) for (ULONG NumIter = 0; NumIter < NumberList.size(); NumIter++) { // XOR current iterator, current number and XORs so far MissingNumber ^= (NumberList[IdIter]^(IdIter+1)); } // The final XOR with MaxNumber MissingNumber ^= MaxNumber; return MissingNumber; }

[techquestions-blog]

Rank array

Question:

Given an array \( A[1 ... N] \), the rank of \( k^{th} \) element \( A[k] \) of the array is defined as the number of elements \( A[i] \) such that \( i < k \) and \( A[i] < A[k] \). An array \( R[1 ... N] \) is called the rank array of \( A \) if \( R[k] \) is the rank of \( A[k] \) for \( 1 \le k \le N \).

You are given that \( A[1 ... N] \) is an array that contains numbers 1 through N in some permutation. Given the rank array R of A, devise and algorithm to create the Array A from R.

Solution:

What does R[k] = r mean?

It means that A[k] has r elements before it such that A[i] < A[k].

R[k] = 0 means that there are no elements before A[k] that are smaller than A[k].

A -> 2 4 6 5 3 1

R -> 0 1 2 2 1 0

We can see from the example above that the rank matrix can have many elements with the same rank. The only immediate information we can decode from the rank array is that the last 0 in the array defines the smallest element in the original array.

Algorithm for creating array A from array R

1. Find the last zero in the rank array. That defines the smallest element in A. Set the corresponding element in array A to the smallest element to be found.

2. Subtract 1 from each of the ranks after the last zero in the rank array.

3. Set the rank to -1 for the last zero found in the Rank array.

4. Repeat steps 1 through 3 to find each of the next smallest elements till you find the place for all the elements in array A.

[techquestions-blog]

Data Structures - Arrays

Operation Complexity:

Insertion: O(1) for insertion at an index

Deletion: O(n) since deleting an element at an index would require moving the rest of the elements after it one step forward

Search/Update: O(1) based on the index. O(n) for an unsorted array.

Advantages:

1. Allows random access to the elements based on index.

2. Very compact structures with not much additional storage requirements.

3. Easy to access data quickly due to their sequential arrangement; give better performance than linked lists for search operations.

Disadvantages:

1. The number of elements need to be known in advance.

2. Do not easily grow to any size, since they require sequential arrangement.

3. Deletion of an intermediate element requires moving forward all the data after it.

4. Arrays are not inherently thread-safe. You need additional synchronization mechanisms to share arrays across threads.

Variations:

Dynamic Arrays:

These arrays start with an initial default size and re-size as the number of elements increase.

Advantages:

1. The dynamic arrays try to provide the random access of arrays and the dynamic growth of linked lists, in a way the best of both worlds.

Disadvantages:

1. Re-sizing the dynamic array requires all the elements to be moved to a different location which is an O(n) operation.

2. They cannot grow indefinitely as you might not be able to find enough contiguous space for the size required by the array.

[techquestions-blog]

Loop in a Linked List

Question:

Given a linked list with a loop in it, find the beginning of the loop.

Solution:

The linked list with a loop would look like the structure below.

H --- LB --- L --- LB

H - head of the list

LB - beginning of the loop

L - elements of the loop.

We can see that the linked list goes on from H to LB, the loop L starts with LB and the last element in the loop points back to LB completing the loop.

Consider a scenario with two pointers. First pointer traverses the list one node at a time, and the second pointer traverses the list two nodes at a time. These two pointers will meet somewhere in the loop. Let us say they meet at a distance y from LB the loop.

Let us define the following measures

\( x \) - number of nodes to traverse from H to LB

\( k \) - size of the loop

\( y \) - number of nodes in the loop from LB where the two pointers meet

Number of nodes traversed by the first pointer = \( x + y \)

Number of nodes traversed by the second pointer = \( x + nk + y \)

Since the second pointer moves twice as fast as the first one, we have

\( 2*(x + y) = x + nk + y \)

\( => x = nk - y \)

From the above equation, we can see that if we traverse \( nk-y \) nodes from the point the two pointers meet, you will end up at the beginning of the loop, since you are already \( y \) ahead in the loop. How do we measure \( nk-y \)? This is equal to \( x \) which is the distance of the beginning of the loop from the head of the list.

Final Algorithm:

1. Use two pointers to traverse the list, first pointer at one node at a time and second pointer at two nodes at a time.

2. Let the node where these two points meet be P. Move the first pointer back to head.

3. Move the two pointers now one node at a time, first pointer starting at head and the second pointer at P.

4. The two pointers meet at the beginning of the loop.

[techquestions-blog]

Data Structures - Linked Lists

Operation Complexities:

Insertion: O(1) - Insertion is usually done at the head of the list

Deletion: O(N) - Deletion a node requires traversal to that node and then delete

Search/Update: O(N) - Search/Update requires traversal through the list to the appropriate node before returning or updating it.

Advantages:

1. Easy to grow as the number of nodes increases

2. Better than arrays in cases where inserts and deletes happen more frequently than searches/updates.

3. Efficient for multi-threaded programming environments as the updates are usually done locally to nodes and do not affect the rest of the list, allowing many threads the access the list simultaneously.

Disadvantages:

1. Does not allow random access to the elements. As we can see search and delete are O(N) operations

2. Even in case of sequential access, lists are slower than arrays due to the locality difference between the elements in the linked list.

3. The references in each node require additional storage space for the structure.

Variations:

Doubly Linked List:

The doubly linked list has a pointer not just to the next node, but also to the previous node, allowing you to traverse in both directions along the list.

1. The doubly linked list increases the additional storage space required since it carries two references compared to one reference in a singly linked list.

2. The insertion and deletion operations are more expensive than singly linked list as you need to set two references here.

3. The doubly linked list will be better than the singly linked list if you need to traverse in either direction.

Circular Linked List:

The circular linked list has the last element of the list point back to the head, thus completing a loop with the list elements.

1. The prime advantage I can think of for the circular list is the ability to wrap back and get to previous elements without starting again from the head.