Find if a list is circular with memory constraint

Usually developers when thinking about a solution put their focus on the complexity of the algorithm (O(n), O(n^2) …) rather than the memory consumption, so lets see an example where the constraint is the memory S.
I would like to share the solution to an interesting exercise that I was asked to solve during a technical interview.

Problem

Implement a function which says if a list is circular.
A circular list is made by a sequence of elements, each one connected to the next in sequence where the last must be connected to any of the previous ones.

Examples :

The only constraint for the solution proposal is that it has to use constant memory a.k.a S(1) .

Solution

Let’s consider which are the types of lists that we might be handling:

  1. Empty list
  2. Non empty list
  3. Ciclic list
  4. Closed cyclic list (cyclic list which is not knotted to the first element)

Given the space constraint, the idea is to iterate the list with two pointers, one slow and one fast moving them simultaneously: slow one moves by one element at a time and fast one by two. In this case we use only a constant number of pointers respecting the space constraint.

  • If the given list is EMPTY our function will return False.
  • If fast or slow will become EMPTY while iterating over the list our function will return False.
  • We can consider the list of type 3  as a special case of the list of type 4.
  • If at some point fast , iterating the list more quickly, will be equal to slow the list is cyclic and so our function will return True, this last scenario is graphically explained by the following schema where slow is x and fast is y.

Implementation

The following implementation code is written in Haskell. Find more about that.

List data structure definition

The list in Haskell is recursively defined as EMPTY or a node containing a value connected at the rest of the list.

data List a = Empty | Cons a (List a)

Creating a non empty list of (type 2)

The following code will produce a list like : 1 – 2 – 3 – 4 – EMPTY

simpleList :: List Integer
simpleList = Cons 1 . Cons 2 . Cons 3 . Cons 4 $ Empty

Creating a cyclic list (type 3)

The following code will produce a list like ( 5 – 6 – 5 …) where (5 – 6 – 5 …) is the cyclic part.

loop :: List Integer
loop = Cons 5 knot
where knot = Cons 6 loop

Creating a closed cyclic list (type 4)

The following code will produce a list like 1 – 2 – 3 – 4 – ( 5 – 6 – 5 …) where (5 – 6 – 5 …) is the cyclic part.

closedList :: List Integer
closedList = Cons 1 . Cons 2 . Cons 3 . Cons 4 $ loop

Implementing the algorithm

The isCyclic function matches a list made of at least 2 elements, assign slow and fast (our pointers), otherwise return False because a list shorter than 2  elements is by definition not cyclic.

isCyclic :: List Integer -> Bool
isCyclic (Cons slow (Cons k fast)) = isCyclic` fast (Cons slow . Cons k $ fast)
isCyclic _ = False

The isCyclic’ function returns True whether slow and fast matches, otherwise move the pointers respectively by one e two elements, if fast will became EMPTY our function will return False.

isCyclic` Empty _ = False
isCyclic` (Cons fast (Cons _ fastRest)) (Cons slow slowRest)
| fast == slow = True
| otherwise = isCyclic` fastRest slowRest

Here is the gist if you want to try it by yourself.

Leave a Reply

wpDiscuz