Akamai Interview Question for Quality Assurance Engineers

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use two pointers. Increment one pointer one position at a time and the other pointer two positions at a time. When the fast pointer reaches the end, the slow pointer should be at the middle position.

Comment hidden because of low score. Click to expand.
0

Using two pointers is not one pass.

Comment hidden because of low score. Click to expand.
0

Using 2 pointers is considered one pass..you are surely using 2 pointers but traversing the list only once.

Comment hidden because of low score. Click to expand.
0

I would not consider using two pointers to be one pass. Advancing two pointers through a linked list is the same as traversing it twice.

Comment hidden because of low score. Click to expand.
0

Even if we consider it , what if number of elements in linked list is even ??

Comment hidden because of low score. Click to expand.
0

Isn't that one pass means one loop?

Comment hidden because of low score. Click to expand.
0

I guess different people may mean different things. But advancing two pointers is similar work to looping twice. You access every node twice, and so I would call that two passes.

Comment hidden because of low score. Click to expand.
0

You can do any number of operation on node in a single pass. Doing two operations t->next & t->next->next, is not consider two passes, it is consider as one pass.

Comment hidden because of low score. Click to expand.
0

@tej: We can argue about definitions, but it'll take 2N linked list pointer accesses. That's all I meant.

Comment hidden because of low score. Click to expand.
0

The while loops runs only once... and in that both pointers are incremented, so its one pass.

while(fast != null)
{
(i%2 == 0)
{
}
}

This way slow points to middle at the end. When fast reaches null.

Comment hidden because of low score. Click to expand.
0

``````/**
*  find mid point
*  2 pointers - one more 2 times faste
*/
public void findMidPoint()
{
return;
}
while(true){
if( fast == null || fast.next == null ){
System.out.println("mid point value is: " + slow.data );
break;
}

fast = fast.next.next;
slow = slow.next;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

If you don't want to use 2 pointers.. you can use array to store all values like

``````while(! node->next)
{
a[i++]  = node->deata;
node = node->next;
count++;
}
cout << "moddle one is " << a[count/2];``````

Comment hidden because of low score. Click to expand.
0

I don't think this is the best solution for this problem, the reason they mention that size of list is not known is to give you a hint that size is sufficiently large. Copying data into another list doesn't sound optimal to me.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Type& findMiddleNode()
{
int check = 0;
nodeType *current;
nodeType *mid;

current = first;
mid = first;

while (current != NULL)
{
check = (check + 1) % 2;

if (check == 0)
}

return mid->info;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
return -1;

while( ptr2 && ptr2->next)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return ptr1->data;
}

Comment hidden because of low score. Click to expand.
0

One corner case, which one is the middle one if number of elements is even in linked list ?

Comment hidden because of low score. Click to expand.
0

hahaha... best joke I ve come across in any forums... :D

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void getMiddleElemnet(){
System.out.println();
while (curr!=null && curr.getNext() !=null) {
curr = curr.getNext().next;
curr1 = curr1.getNext();

}
System.out.println(curr1.getData());
}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

I seriously suggest you google for "what is a linked list". LOL

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.