## A9 Interview Question for abcs

Country: United States
Interview Type: In-Person

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

Have two pointers pointing to the linked list incrementing at different pace. Ptr1 increments each node and ptr2 increments every two nodes. If there is a cycle, eventually ptr1 == ptr2.

``````#include <iostream>
#include <list>

using namespace std;

#define MAX 5

template<class T>
class Node {
public:

Node(): next(NULL) {};
Node(T d): data(d), next(NULL) {};
T data;
Node *next;
};

template <class T>
bool hasCycle(Node<T> *n, Node<T> **me = 0) {

if (n == NULL) return false;
Node<T> *ptr1 = n;
Node<T> *ptr2 = n->next;

while (ptr2 && (ptr2->next)) {
if (ptr1 == ptr2) {
*me = ptr1;
return true;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
}
return false;
}

int main() {

Node<int> *tmp = head, *tmp1 = NULL;
Node <int> **me = NULL;

// Case 1: NULL
cout << "Case 1 cycle: " << hasCycle<int>(tmp1) << "\n";

// Case 2: 0 -> NULL
cout << "Case 2 cycle: " << hasCycle<int>(tmp) << "\n";

// Case 3: 0 -> 1 -> NULL
for (int i=1; i<2; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
}
cout << "Case 3 cycle: " << hasCycle<int>(tmp) << "\n";

// Case 4: 0 loops
tmp->next = tmp;
cout << "Case 4 cycle: " << hasCycle<int>(tmp, &tmp1) << " at: " << tmp1->data << "\n";

// Case 5: 0 -> 1 -> loops to 0
for (int i=1; i<2; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}

cout << "Case 5 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";

// Case 6: 0 -> 1 -> 2 -> loops to 1
for (int i=1; i<3; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}

cout << "Case 6 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";

// Case 7: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> loops to 5
for (int i=1; i<11; i++) {
tmp1 = new Node<int>(i);
tmp->next = tmp1;
tmp = tmp->next;
}

cout << "Case 7 cycle: " << hasCycle<int>(head, &tmp1) << " at: " << tmp1->data << "\n";

return 0;``````

}

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.