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());
}
class Node:
def __init__(self, data, next= None):
self.data=data
self.next = next
class LinkList:
def __init__(self):
self.head = None
def show_value(self, node_obj):
if node_obj:
return f'Data:{node_obj.data}, Next:{node_obj.next}'
def add_values(self, node_data):
if not self.head:
self.head = Node(data=node_data)
return self.head
temp = self.head
while temp.next:
temp = temp.next
temp.next = Node(data=node_data)
return temp.next
def find_third_last(self):
if not self.head:
return None
elif not self.head.next.next:
return "Need atleast three elements in list"
pointer2 = self.head.next.next
pointer1 = self.head
while pointer2.next is not None:
pointer1 = pointer1.next
pointer2 = pointer2.next
return self.show_value(pointer1)
x = LinkList()
for i in range(10,90):
x.add_values(i)
print(x.find_third_last())
You can maintain three variable to store the top 3 elements while sweeping the list.
- wdxcn1123 September 04, 2012