Skip to content

Instantly share code, notes, and snippets.

@someodd
Created August 23, 2022 23:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save someodd/dcd2398b59fe25dcdcc3f0a2d9427405 to your computer and use it in GitHub Desktop.
Save someodd/dcd2398b59fe25dcdcc3f0a2d9427405 to your computer and use it in GitHub Desktop.
Tesla interview question
{-
My attempt at a Tesla interview question:
Minimum number of characters to delete from a string so that each character
appears unique number of times. Note: You can delete all occurances of
characters.
eg: "aaaabbbb" -> 1 "a" or 1"b" would make "a" and "b" appear unique number of
times.
-}
import Data.List (group, sort)
answer :: String -> Int
answer s = occurListSum - (progressionSum biggest (biggest - (occurListLength - 1)))
where
occurList' = occurList s
(biggest, occurListLength, occurListSum) =
foldl (\(b, l, su) x -> (max x b, l+1, su+x)) (0,0,0) occurList'
progressionSum big small = (((big - small + 1) * (small + big)) `div` 2)
-- A list of character occurrence counts.
occurList :: String -> [Int]
occurList = map length . group . sort
tests :: Bool
tests = and $ map tester testCases
where
tester :: (String, Int) -> Bool
tester (input, correctAnswer) = do
let response = answer input
if response == correctAnswer
then True
else error $ show (input, correctAnswer, response)
-- (input, answer)
testCases :: [(String, Int)]
testCases =
[ ("aaaabbbbba", 1)
, ("ab", 1)
, ("aabbc", 2)
, ("eaaaabbbbbaeeee", 3)
, ("aaaabbbbcccceeee", 6)
, ("aaaaabbbbbccccceeeee", 6)
, ("aaaaabbbbbccccceeezz", 5)
, ("aaaaaabbbbbcccccdddddzzzz", 5)
]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment