|
Find the maximum subsequence sum in a linked list. Consider the node as shown be .....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Find the maximum subsequence sum in a linked list. Consider the node as shown be .....
Question:
Find the maximum subsequence sum in a linked list. Consider the node as shown below.This node class has a extra item isvertex which determines whether the node is a vertex r not.
so find the longest distance between any 2 vertex in the linked list.
Node SLL{
int data;
Node n;
bool isVertex;
}
maybe an answer:
void findLongest(Node *header, Node **v1,Node **v2)
{
is(header)
{
int maximum=0;
int currentsum=0;
int tempsum=0;
while(!header -> isVertex && header->next)
{
header = header ->next;
}
if(header->isVertex)
{
Node *currentV1=header;
Node *currentV2=header;
while(header->next)
{
if(header->isVertex)
{
tempsum+=header->data;
currentsum+=tempsum;
if(currentsum>maximum)
{
maximum=currentsum;
currentV2=header;
v1=currentV1;
v2=currentV2;
}
else if(currentsum<0)
{
currentsum=0;
currentV1=header->next;
}
tempsum=0;
}
else
{
tempsum+=header->data;
}
header=header->next;
}
}
}
}
(Continued on next question...)
Other Interview Questions
| 