Microsoft Interview Question
Country: United States
Then what do you mean by saying "Sort them such that all the similar number nodes are cluster together", any sort anyways will give you the same valued nodes together..
If there is no problem in using additional data structure, I would use a treemap <<value, linkedlist of nodes>> . For some value ->key, node will be linked to the linked list. Since it is a treemap, values will be sorted. So after checking all values, and stroing them in the treemap, we can simply output the nodelist in order.
template <class T>
void SLList<T>::JoinSimilar()
{
LLNode<int> *pCur = pHead;
if(!pCur || !pCur->pNext) return;
const int TABLE_SIZE = 10;
SLList<SLList<int>*> **AggList = new SLList<SLList<int>*>*[TABLE_SIZE]; // hash-table
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
{
AggList[ind_table] = new SLList<SLList<int>*>; // each element of the table is
} // a pointer to the list of lists
LLNode<int> *pCurTblListNode = NULL, *pTmp = NULL;
LLNode<SLList<int>*> *pCurTblList = NULL, *pNewTblList = NULL;
while(pCur)
{
pCurTblList = AggList[pCur->iData%10]->pHead; // fill the table element
while(pCurTblList)
{
pCurTblListNode = (pCurTblList->iData)->pHead; // each element is the list of the lists of numbers,
if(pCurTblListNode->iData == pCur->iData) // which end with the same digit, e.g.
{ // 5->5->5->NULL
pTmp = pCur->pNext; // 35->35->NULL
pCur->pNext = pCurTblListNode; // 275->NULL
(pCurTblList->iData)->pHead = pCur; // NULL
pCur = pTmp;
break;
}
pCurTblList = pCurTblList->pNext;
}
if(!pCurTblList)
{
pNewTblList = new LLNode<SLList<int>*>;
pNewTblList->iData = new SLList<int>;
pNewTblList->pNext = AggList[pCur->iData%10]->pHead;
AggList[pCur->iData%10]->pHead = pNewTblList;
(pNewTblList->iData)->pHead = pCur;
pTmp = pCur->pNext;
pCur->pNext = NULL;
pCur = pTmp;
}
};
LLNode<int> *pFisrt = NULL, *pLast = NULL, *pLastTblList = NULL;
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++) // join all the lists into one single list
{ // and then set the head of the base list to the
pCurTblList = AggList[ind_table]->pHead; // new joint list
while(pCurTblList)
{
if(!pFisrt)
{
pFisrt = (pCurTblList->iData)->pHead;
}
pLast = (pCurTblList->iData)->pHead;
if(pLastTblList)
{
pLastTblList->pNext = pLast;
}
while(pLast->pNext)
{
pLast = pLast->pNext;
};
if(pCurTblList->pNext)
{
pLast->pNext = ((pCurTblList->pNext)->iData)->pHead;
pLastTblList = NULL;
}
else
{
pLastTblList = pLast;
}
pCurTblList = pCurTblList->pNext;
}
}
pHead = pFisrt;
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
{
delete AggList[ind_table];
}
@bhardwaj.ankit
- Learner September 02, 2012According to the question "Sort them such that all the similar number nodes are cluster together". Don't you think that sorting the series will automatically cluster same numbers together? Do let me know if sorting is the requirement or not.