Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Challenge I saw on HackerNews, "Most candidates cannot solve this interview problem."
{-
I saw this posted on HackerNews:
"Most candidates cannot solve this interview problem."
https://twitter.com/Al_Grigor/status/1357028887209902088
> Most candidates cannot solve this interview problem:
> Input: "aaaabbbcca"
> Output: [("a", 4), ("b", 3), ("c", 2), ("a", 1)]
I honestly solved it very quickly with Haskell! So I thought
I would do a few methods.
-}
import Data.List (group)
import Control.Arrow ((&&&))
theInput = "aaaabbbcca"
expectedOutput = [('a', 4), ('b', 3), ('c', 2), ('a', 1)]
-- First solution. I was able to do this very quickly (under a couple minutes).
firstSolution = map (\x -> (head x, length x)) . group
-- This solution took a while longer because I accidentally messed up a pattern match!
-- The point of this solution was to implement group myself.
secondSolution =
map (\x -> (head x, length x)) $ reverse $ foldl (\acc x -> appendToGroup x acc) [] theInput
where
appendToGroup :: Eq a => a -> [[a]] -> [[a]]
appendToGroup x (g:gs) = if x `elem` g then (x:g):gs else [x]:g:gs
appendToGroup x [] = [[x]]
-- I thought of this solution later on because I recently used this function...
thirdSolution = map (head &&& length) . group
-- My friend challenged me to do this without using any "fancy" functions.
startSolution4 (x:xs) = solution4 xs (x, 1) []
where
solution4 (x:xs) (c, i) acc
| x == c = solution4 xs (c, i + 1) acc
| otherwise = solution4 xs (x, 1) (acc ++ [(c, i)])
solution4 [] (c, i) as = as ++ [(c, i)]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment