Created
August 23, 2022 23:08
-
-
Save someodd/dcd2398b59fe25dcdcc3f0a2d9427405 to your computer and use it in GitHub Desktop.
Tesla interview question
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- | |
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