## Amazon Interview Question for Quality Assurance Engineers

Country: United States
Interview Type: In-Person

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

start two pointer from starting point of the list and increase 1st pointer by one and 2nd by two if they pointer meet on same point than the list is circular list else not.

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

There are several approach to check whether link list is circular or not:-
1st Approach :
Take a flag bit at each node and make it zero initially. While visiting each node make the flag bit as one if it is zero. If already flag bit found as one then loop exist that is circular list.
If somebody ask how we can take the flag bit at each node by own then you just give answer as while doing programming we always take some extra bit for future purpose.so we make it as flag bit. If they also not satisfied then just say i will take resize function to increase the size of node and then we use the flag bit. Time complexity= O(n).

2nd Approach :

Take an array. Store the 1st node next address and go to second node. while go to next node just check whether next address is already stored in array........and so on .Time complexity =O(square of n)

3rd approach:

start with two pointer from starting point of the list and increase 1st pointer by one and 2nd by two if the pointer meet on same point then the list is circular list else not.
Time complexity = O(n). This is the best algorithm. Its time complexity is asymptotically order of n but actually on an average it is n/2.

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

Your 2nd approach's Time complexity is O(N) and Space complexity is O(N), since you are using an array to store each node's address and you are visiting each node exactly once.

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

Start from a given node and traverse the linked list. Validate for null or start node point condition while traversing the linkedlist . In case we find node->next = null at any time then LL is not circular in nature. In case we encounter starting node address again then it means it is circular LL.

Thanks,

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

Question is to give boundary test cases.
1. So point to the last node and then traverse to see if you return to first node
2. If it is a circular queue implementation using linked lists & list not full and rear is pointing to the last node then on Enqueue the first node shall be used

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

-- If node -> next = NULL, in this case the length of the LL is 1 and its never a circular LL, if this condition true here, further execution will not happen. We can use it as validation criteria here.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Start with any node and loop through the list if you reach the same node again the list is circular.

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.