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.
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.
The only constraint for the solution proposal is that it has to use constant memory a.k.a S(1) .
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.
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.