Most efficient way to create a sorted array of frequencies

[kravmaguy]

Im looking to create a sorted array of frequencies

https://www.facebook.com/codingcompetitions/hacker-cup/2013/qualification-round/problems/A

here is what I did:

interview

im thinking its not as efficient as possible. I know on line 29 I can just use .sort method instead of insertion. I think it uses quicksort or mergesort (not sure which one). Also, is it really necessary to do all this work? can the sorting be done above, like already from line 17 start to build a sorted array?

at least am I correct about the approach that I should end up with a sorted array of frequencies?

[JeremyLT]

Why sort? You just need the biggest value.

Edit: Ah, I see. I would use the built in sort, but for this few values, a hashmap will be slow.

[kravmaguy]

@JeremyLT

Why sort? You just need the biggest value.

not sure what you mean can you please expound?

the biggest value would be 26 (multiplied by frequencies of occurance of the letter) then 25 (multiplied by the frequencies of the next letter) etc…

basically would multiply the highest frequency by 26 then the next highest by 25 etc…

[kravmaguy]

what you mean hashmap is slow? its instantaneous lookup… (if there isnt more than one val at the same hash, which there isnt in this case)

well how would you do it then if you want to write the best code?

for reference I had the above for some recorded online interview, that is what I submitted, and they failed me

[JeremyLT]

Hashing is slower than indexing. Hashing functions are never instantaneous. If you have a fixed number of keys and you know them in advance, indexing into a fixed length array will be faster.

[JeremyLT]

I would count the number of occurrences in a fixed length array.

I would not re-invent sort but instead use the built in sorting method.

Overall I’d work to simplify your code.

[kravmaguy]

@JeremyLT

I would count the number of occurrences in a fixed length array.

i still have to make the array of frequencies.

@JeremyLT

I would not re-invent sort but instead use the built in sorting method.

is this even necessary?

@JeremyLT

Overall I’d work to simplify your code.

I was under time limit.

can I just use priority Q ?

[JeremyLT]

An array is cheaper to make than a hashmap. I can make an array with fewer lines, and it will be faster than your current code. In your title you explicitly ask for a more efficient approach.

I would reject a candidate for rolling their own sorting, personally. You won’t get better performance than the built-in sort.

Sure, you were under the time limit. But your code is still too complex. I would reject that level of unnecessary complexity in code review.

Why use a priority queue? That is not simpler. Think simpler. Only use fancy tools when you must. Simpler code is easier to read. Simpler code is easier to maintain. Only do something fancy if you know you need to.

Edit: Lots of answers are out there, so what the heck. This is my fast hack at a solution:

Spoilers

SUPER SPOILERS

Actual Spoilers

const arr = [
  "ABbCcc",
  "Good luck in the Facebook Hacker Cup this year!",
  "Ignore punctuation, please :)",
  "Sometimes test cases are hard to make up.",
  "So I just go consult Professor Dalves",
]

// Utilities
const numLetters = 26;
const charCodeA = "a".charCodeAt(0);
const charCodeZ = "z".charCodeAt(0);
function isAlpha(lowerCharCode) {
  // Char code comparison is cheaper than regex
  return lowerCharCode >= charCodeA &&
         lowerCharCode <= charCodeZ;
}

// Beauty computation
function findMaxBeauty(line) {
  // Count occurrences of each letter
  const occurrences = Array(numLetters).fill(0);
  line
    .toLowerCase()
    .split("")
    .filter(char => isAlpha(char.charCodeAt(0)))
    .forEach(char => occurrences[char.charCodeAt(0) - charCodeA]++);
  // Maximum possible beauty
  return occurrences
    .sort((a, b) => a - b)
    .reduce((beauty, count, indx) => beauty + count*(indx + 1), 0);
}

// Convert line to beauty value
function displayMaxBeauty(line, indx) {
  return "Case #" + (indx + 1) + ": " + findMaxBeauty(line);
}

// Convert inputs to output string
const output = arr
  .map((line, indx) => displayMaxBeauty(line, indx))
  .join("\n");

// Look at the good work
console.log(output);