Sort 15 Discussions, By:
Please Login in order to post a comment
Dear Hackerrank team,Please increase time limit for F# (Fsharp) programming language. You give Haskell 5s, Clojure 8s, Scala 7s, Erlang 12s. And you give F# just for 4s??? IT IS NOT FUNNY!
" Can you find the missing numbers from A without messing up his order?"
I didn't understand the meaning of this statement in the problem description
I think it's a reference to the first sentence about comparing the lists without sorting.
First, I use strict IntMap's to efficiently count the number of occurrences of each element in both lists.
import qualified Data.IntMap.Strict as M
buildMap :: M.IntMap Int -> [Int] -> M.IntMap Int
buildMap m  = m
buildMap m (x:xs) = let count = M.lookup x m
m' = update m x count
in buildMap m' xs
update :: M.IntMap Int -> Int -> Maybe Int -> M.IntMap Int
update m x Nothing = M.insert x 1 m
update m x (Just cnt) = M.insert x (cnt + 1) m
Then, I define a function to compare both IntMap's by (unique) keys.
cmp num cnt1 cnt2 = if cnt1 > cnt2 then Just num else Nothing
It means, if a number num occurs more times in the first list than in the second one, then we are looking for it.
Finally, the program is simple:
main = do
-- Build the first IntMap
_ <- getLine
a <- (buildMap M.empty . map read . words) <$> getLine
-- Build the second IntMap
_ <- getLine
b <- (buildMap M.empty . map read . words) <$> getLine
-- Find the differences
let diffs = M.differenceWithKey cmp b a
putStrLn . unwords . map (show . fst) . M.toList $ diffs
"Sometimes you need to compare lists of number, but sorting each one normally will take too much time. Instead you can use alternative methods to find the differences between each list."
Probably me missing the point... Isn't the quickest method to sort a and b and then do a scan difference between the two lists. You can sort in O(n log n) then scan diff in O(n) whereas if you diff without sorting first you are O(n squared).
Like I say, I may have totally missed the point (or got my times completely wrong). I don't understand the why we are told not to sort each one normally.
Incedently, I did sort a and b before implementing my diff, and it passed.
because there is an algorithm that runs in O(n+m)
Pretty easy with Erlang, just some IO and: List2 -- List1