Microsoft Interview Question
Software Engineer / Developersvoid isHead( struct node *nodeArray[], int n)
{
int i,j;
struct node *curr, *checHead;
Bool ishead = false;
for(i =0; i<n;i++)
{
curr = array[i];
for(j=0;j<n;j++)
{
chekHead = array[j];
if(curr == checkHead->next || checkHead->next == null )
{
break; // exist from inner loop as the address is some nodes next so it cant be head.
}
else
{
isHead = true; // node
}
}
}
if (isHead)
break;
}
}
we can work our way down the index in array and for each index we should traverse in the link list. now trick here is to mark the nodes which we have traversed. we can use a similar size array of int/char. and when we jump to the next pointer in a node we should set int/char array on that index as one. we can calculate indices by using pointer arithmetics. (index of next pointer = index of node + node-.>next - node) we can do it because it is all part of an array
traverse the array, and put all next pointer into an hashset. traverse again, see whether current node is in hashset, if no, it is the header
- Anonymous July 18, 2012