|
Google Technical Interviews in Management round: You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Manager Round interview Questions and Answers
(Continued from previous question...)
Google Technical Interviews in Management round: You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
# Solution:
The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.
Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z
Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.
# Questions on my project please be prepare well about your project
# How do you search for a word in a large database.
# How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.
(Continued on next question...)
Other Interview Questions
| 