Coding interview, haskell example

Recently I've been looking for a job and as usual in the IT field, I got lots of tests and programming quizz (more on this in another post). Since I wanted to flex my haskell muscles, I tried to solve one of the problem I got with it.

Count harmonic slices

Here's the problem: Given an array A of integer count the number of harmonic slices in this array. An harmonic array is an array where all consecutive elements differ only by the same constant. For example [-1, 1, 3] is harmonic as well as [-1, -1, -1] but [-1, 1, 1] is not. If the array's length is less than 2, it's defined as non harmonic. An harmonic slice is a sub array: A.slice(i, j).

So for example, the array A = [-1, 1, 3, 3, 3, 2, 1, 0] has 5 harmonic slices defined by the indices: (0, 2) (2, 4) (4, 6) (4, 7) (5, 7).

Classical solution

I'll not spoil the solution here, but it fairly easy to come up with a O(n) time complexity, and O(1) space complexity. And btw, the platform used for the test did not allow haskell anyway.

Haskell solution

I first started to replicate the classical solution using Haskell. While it would have lead to a more efficient algorithm, it was not very educational in learning Haskell. So I switched to a very declarative approach:

Get all potential slices

First, given a list of Int, return all the potential slices for this list. This is easily achieved with list comprehension:

subLists :: [Int] -> [[Int]]
subLists xs = [(take a) . (drop b) $ xs | a <- [3..n],
                                          b <- [0..n],
                                          a+b <= n
              ]
              where n = length xs

Check if a slice is harmonic

This one had me thinking a lot. I tried various approach using recursion or foldl trying to replicate a for loop approach I would've used in other languages but with limited success. A declarative approach is actually easier. The trick is to zip the list with itself (minus the first element) to be able to compare an element with the next one.

isHarmonic :: [Int] -> Bool
isHarmonic xs
  | length xs < 3 = False
  | otherwise = allEqual $ zipWith (-) xs $ drop 1 xs
  
-- takes a list and return true iff all elements are equals
allEqual :: [Int] -> Bool
allEqual xs = and $ zipWith (==) xs $ drop 1 xs

Putting it all together

The end result is given by the length of the filtered list:

countHarmonicSlices :: [Int] -> Int
countHarmonicSlices = length $ filter isHarmonic $ subLists

Which gives in ghci:

λ: countHarmonicSlices [-1, 1, 3, 3, 3, 2, 1, 0]
5

yeah!

Final thoughts

Reasoning about space complexity in Haskell is very hard because of lazyness. For the same reason, time complexity is also harder to evaluate. I would tend to think though that this algorithm is vastly less efficient and most surely not O(n) since I'm actually evaluating all possible slices.

I'm not convinced "regular" Haskell is a good tool for this kind of task, but that wasn't the point of the exercise anyway.