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:

*Empty list*

*Non empty list*

*Ciclic list*

*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

You must be logged in to post a comment.

You must be logged in to post a comment.