CareerCup

Isn't the starting node just the first node where isVertex=true and the ending node just the last node where isVertex=true?

Feels like I misunderstand the question because it looks too easy.

vertex could be anywhere in the linked list, any number of vertex might be there, we have to find the max sum between 2 vertex.

Start iterating the linked list and store the sum as you reach a vertex .. cotinue this for all the vertices and whichever sum is bigger set that in the sum variable . Is this what the interviewer is looking for ?

Traverse the array, and let the vertex node be a start node only if the sum between it and the last start node is negative. Record the maximum distance we've seem. T.C. = O(n), S.C. = O(1)

what does vertex mean in this q..I think i am misinterpreting this question.

I would have a function that calculates the max subsequence sum between two nodes and apply that over all the consequitive vertexes found. But as a poster above said, this seems too easy.

The description for the question is not clear at all, I think you need do better than this to get a job at Microsoft.

i haven't tested it

void getMaxSequence(lnode* head)
{
lnode* cur = head;

while(cur && !cur->isVert)  //skip till finding the first vrtx
	cur = cur->nxt;
if(!cur)
	return;

lnode* strt_pve = cur;
lnode* last_pve = cur;

int sum_pve = 0;
int sum_nve = 0;
int sum_vrtx = 0;

while(1)
{

if(cur->isVert)
{
	if(sum_vrtx < 1)
	{
		sum_nve += sum_vrtx;
	}
	else
	{
		if(sum_nve != 0)
		{
			if(sum_pve + sum_nve < 1)
			{
				strt_pve = cur;
			}
			else
			{
				sum_pve += sum_nve;
			}
			sum_nve = 0;
		}
		else
		{
			sum_pve += sum_vrtx;
		}
		last_pve = cur;
	}
	sum_vrtx = 0;
}

sum_vrtx += cur->data;

cur = cur->next;
if(!cur)
	break;


}

//path will be between strt_pve & last_pve with sum equals sum_pve

}

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;
                
            }
            
            
        }
    }
}