Some error occured while loading page for you. Please try again.
Sort 9 Discussions, By:
Please Login in order to post a comment
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
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.
Do not sort the lists. Some test cases are too long that sorting the lists would take up too much time.
sorting is O(n log n) so I can't image sorting ever being too slow in this problem
"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)
testcase 2 failing.
checked test case.
Test Case:(array1 1000 elements,
array2 1009 element,
but result 8 elements)
Am i missing something or test case in wrong, as resulting difference should be 9 elements not eight
The same element could be missing multiple times. You only have to print it once.
Thanx, i thought that wasn't the case
Pretty easy with Erlang, just some IO and: List2 -- List1
I am not sure Testcase 1 does not looks correct.
My output is 3670 3674 3677 3684 3685 3685 3695 3714 3720
but testcase shows 3670 3674 3677 3684 3685 3695 3714 3720
I have downloaded the testcase1 the second string have "3685" 9 times as comapred first one which have 7 times.
Would you please look?
You have to print each missing number only one time, even if they are missing multiple number of times.
i can not see c or c++ language for coding
Hi, this track is for functional languages only.
I cannot see java as well.
@ashikachhabda wiki page -> Functional language
No more comments