Discussion on: Javascript Sock Merchant Challenge - Solution 2

View post

My own solution would be:

function stockAndCount( n, arr ) {
  let pairs = 0
  const unpaired = new Set()

  for (const color of arr)
    if (unpaired.has(color)) {
      pairs++
      unpaired.delete(color)
    } else unpaired.add(color)

  return pairs
}

This doesn't iterate again over the colors encountered, and uses the minimal memory required for the task: The running total of pairs and the unpaired colors, encountering which again would be the completion of a pair.

Ady Ngom • Apr 27 '19 • Edited

Hello Mihail and thank you for both of your detailed inputs. I have a final episode and webinar coming up to allow us in taking a detail look at why one solution over the other. If you go the Hacker Rank site you will in fact find numbers of way that this one challenge is solved. So it will be pretentious from me to say that this one is the best one of all the possible ones. But when it comes to the first solution provided in episode 1 and this one, this is by far a better solution as far as approach and performance.

I have added the two functions you have provided and run all three against a simple benchmark to see how each performs against a set of 10,000 items. Check the screenshot below:

// First solution episode 1
$node sockMerchant.js 
4997
Sort And Count: 74.724ms

// This solution episode 2
$node sockMerchant.js 
4997
Stock And Count: 16.788ms

// Your first solution
$node sockMerchant.js 
4997
Stock And Count 2: 49.022ms

// Your second solution
$node sockMerchant.js 
4997
Stock And Count 3: 77.768ms

I have call and run each of those separately running the setup below:

I really like the points you raised regarding side effects and type coercion. I will make sure that those are addressed during the webinar.

It will be great if you could join and offer some insights.

Cheers :)

Mihail Malo • May 3 '19

Yup, my "highly scientific" browser benchmark also makes it seem that Set is slower:

function socks_set(arr) {
  let pairs = 0
  const unpaired = new Set()

  for (const color of arr)
  if (unpaired.has(color)) {
      pairs++
      unpaired.delete(color)
    } else unpaired.add(color)

  return pairs
}
function socks_obj(ar) {
  const colors = {}
  let pairs = 0
  for (const color of ar) pairs += !(colors[color] = !colors[color])

  return pairs
}
function* good() {
  let i = 0
  while (i < 100000000) yield i++ >> 1
  return i >> 1
}
function* bad() {
  let i = 0
  while (i < 10000000) yield i++
  return i
}

console.log(socks_set(good()))
console.log(socks_obj(good()))
console.time("good Set")
socks_set(good())
console.timeEnd("good Set")
console.time("good Obj")
socks_obj(good())
console.timeEnd("good Obj")
console.time("good Set")
socks_set(good())
console.timeEnd("good Set")
console.time("good Obj")
socks_obj(good())
console.timeEnd("good Obj")

console.log(socks_set(bad()))
console.log(socks_obj(bad()))
console.time("bad Set")
socks_set(bad())
console.timeEnd("bad Set")
console.time("bad Obj")
socks_obj(bad())
console.timeEnd("bad Obj")
console.time("bad Set")
socks_set(bad())
console.timeEnd("bad Set")
console.time("bad Obj")
socks_obj(bad())
console.timeEnd("bad Obj")