Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You have a singly-linked list and want to check if it contains a cycle.

A singly-linked list is built with nodes, where each node has:

  • node->getNext()—the next node in the list.
  • node->getValue()—the data held in the node. For example, if our linked list stores people in line at the movies, node->getValue() might be the person's name.

For example:

class LinkedListNode { private $value; private $next = null; public function __construct($value) { $this->value = $value; } public function getNext() { return $this->next; } public function setNext($next) { $this->next = $next; } public function getValue() { return $this->value; } public function setValue($value) { $this->value = $value; } }

A cycle occurs when a node’s next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Write a function containsCycle that takes the first node in a singly-linked list and returns a boolean indicating whether the list contains a cycle.

Careful—a cycle can occur in the middle of a list, or it can simply mean the last node links back to the first node. Does your function work for both?

We can do this in time and space!

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

time and space.

The runtime analysis is a little tricky. The worst case is when we do have a cycle, so we don't return until $fastRunner equals $slowRunner. But how long will that take?

First, we notice that when both runners are circling around the cycle $fastRunner can never skip over $slowRunner. Why is this true?

Suppose $fastRunner had just skipped over $slowRunner. $fastRunner would only be 1 node ahead of $slowRunner, since their speeds differ by only 1. So we would have something like this:

[ ] -> [s] -> [f]

What would the step right before this "skipping step" look like? $fastRunner would be 2 nodes back, and $slowRunner would be 1 node back. But wait, that means they would be at the same node! So $fastRunner didn't skip over $slowRunner! (This is a proof by contradiction.)

Since $fastRunner can't skip over $slowRunner, at most $slowRunner will run around the cycle once and $fastRunner will run around twice. This gives us a runtime of .

For space, we store two variables no matter how long the linked list is, which gives us a space cost of .

  1. How would you detect the first node in the cycle? Define the first node of the cycle as the one closest to the head of the list.
  2. Would the program always work if the fast runner moves three steps every time the slow runner moves one step?
  3. What if instead of a simple linked list, you had a structure where each node could have several "next" nodes? This data structure is called a "directed graph." How would you test if your directed graph had a cycle?

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Reset editor

Powered by qualified.io

. . .