code-reviews 2019-10-05 | Slack Archive

hey guys, need some help the problem is quite simple:

Given two unsorted arrays team-a and team-b. They may contain duplicates. 
For each element in team-b count elements less than or equal to it in array team-a

my solution was:

(defn solution [team-a team-b]
    (let [steam-a  (sort team-a)
          search #(java.util.Collections/binarySearch steam-a %1)
          mapper  (comp inc search)]
       (mapv #(Math/abs (mapper %1)) team-b)))

the problem is , for huge inputs 100K items for team-a and 100K items for team-b array, the solution is taking ~ 150s the time limit is only 8s, how can I improve the solution ?

jaihindhreddy12:10:07

If (count (distinct team-a)) is small, you can use frequencies and buildup another array with cumulative sums, and make it bit faster.

tdantas17:10:10

the bottleneck here is the binarySearch, is taking around 1 ~2 millisecond per call

dominicm22:10:44

You might want to turn on reflection checks. It might indicate a lot of time figuring it out. Alternatively, use async-clj-profiler to pinpoint it exactly

tdantas22:10:24

Gonna try this @dominicm . Let you know what I found

2019-10-05

Channels