Akamai Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
1. Start one pointer "fp" and iterate through linkedlist until it reaches 3rd node.
2. When "fp" reaches 3rd element, start another pointer "sp" from head node.
3. From now on, advance both pointers"fp" and "sp", node by node until you reach "fp"pointing to NULL.
4. At this time "sp" is pointing to 3rd element from end of the linked list
5. In other words, iterating a pointer to maintain some gap (here 3 in this example)
/**
* find kth element
* o(n)
*/
public void findKthElement(int k)
{
if( head == null ){ //handle k >= length of list
return;
}
Node<AnyType> fast = head;
Node<AnyType> slow = head;
while(k > 0){
fast = fast.next;
k--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
System.out.println("kth element value is: " + slow.data );
}
Node* findNthToLast(Node* head, int n)
{
Node* temp = head;
Node* nthToLast = NULL;
int count = 0;
while(temp != NULL)
{
count++;
temp = temp->next
if(count == n)
{
nthToLast = head;
}
else if (count > n)
{
nthToLast = nthToLast ->next;
}
}
if(nthToLast == NULL)
{
cout << "Error: List size is smaller than N"<<endl;
}
return nthToLast;
}
public void getNthMinusyElement(int n){
System.out.println();
ListNode curr = head;
ListNode nthToLast = null;
int count = 0;
while(curr != null)
{
count++;
curr = curr.getNext();
if(count == n)
{
nthToLast = head;
}
else if (count > n)
{
nthToLast = nthToLast.getNext();
System.out.println("data==="+nthToLast.getData());
}
}
System.out.println(nthToLast.getData());
}
You can maintain three variable to store the top 3 elements while sweeping the list.
- wdxcn1123 September 04, 2012