DEV Community

loading...

Discussion on: I failed an interview because of an algorithm

Collapse
waffledonkey profile image
waffledonkey

As a self-taught web developer going on 25 years now I am sympathetic and if it helps you out at all I would have failed that question coming at it the way you were coming at it -- but I wouldn't have come at it that way.

Below is a super simple solution, using the Intl.collator; a built-in Javascript comparator. I offer it not to make you feel bad, but because the other questions they asked Object.freeze and requestAnimationFrame sounded to me like they were more interested in your breadth of knowledge over Javascript and some of the more esoteric APIs than computer science; maybe? Don't get me wrong Object.freeze, Request Animation Frame, etc. are all useful but not something I deal with every day or even every year -- not in the corporate space anyway.

const sortVersions = (unsortedVersions) => { 
  return unsortedVersions.sort(new Intl.Collator('en', {numeric: true, sensitivity: 'base'}).compare).reverse() 
}

Strictly speaking I would instantiate the comparator externally, but it looked like they wanted it all inside the function body. ¯_(ツ)_/¯

Collapse
raulfdm profile image
Raul Melo Author

Oh, thanks for sharing. I still haven't used Intl API yet so I couldn't imagine there was such a thing to do this easily.

I'll definitely take a look on it, appreciate that!

Collapse
amejiarosario profile image
Adrian Mejia

Wow, brilliant 1-liner solution! I didn't know anything about Intl.Collator. I investigated a little bit more about it. This also works:

const sortVersions = (unsortedVersions) => { 
  return unsortedVersions.sort((a, b) => b.localeCompare(a, 'en', {numeric: true}));
}

This is the original solution I came up with in 17 min. (I timed myself to make sure I don't go over 30 min)

const sortVersions = (unsortedVersions) => {
  const vers = unsortedVersions.map((ver) =>
    ver.split(".").map((v) => Number(v))
  );
  vers.sort((a, b) => {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      if (a[i] !== b[i]) return b[i] - a[i];
    }
    return a.length > b.length ? -1 : 1;
  });
  return vers.map((v) => v.join("."));
};
Collapse
dannyengelman profile image
Danny Engelman

You are all still thinking in Numbers. (including those who interview)
The localCompare won't sort "2.1.0a" properly

Key is to convert Numbers to Letters, so 2.1.0a becomes cbaa and then sort

explanation:
stackoverflow.com/questions/683259...

Or in one line

const sortVersions = (x, v = (s) => s.match(/(\d+)|[a-z]/g).map(c => c == ~~c ? String.fromCharCode(97 + c) : c)) => x.sort((a, b) =>v(b) < v(a) ? 1 : -1)


`

Thread Thread
luiz0x29a profile image
Real AI

Or just do something like "2.1.0a" becomes " 2 1 0 a", then it will sort correctly.



const sortVersions = (unsortedVersions) => {
  const format = (n) => n.split(/[.a-z]/g).map(c => c.padStart(5)).join("");
  return unsortedVersions.sort((x, y) => {
    return format(x) >= format(y) ? 1 : -1;
  });
};

sortVersions(['2.5.10.4159', '1.0.0', '0.5', '0.4.1', '1', '1.1', '1.1a', '2.5.0', '2a', '1.1a-final', '2.5.10', '10.5', '1.25.4', '1.2.15'])
//["0.4.1","0.5","1","1.0.0","1.1","1.1a","1.1a-final","1.2.15","1.25.4","2a","2.5.0","2.5.10","2.5.10.4159","10.5"]

Thread Thread
dannyengelman profile image
Danny Engelman

Yes, indeed. Same concept: sort characters.
It also shows why tech interviews are required. You need a balanced team of developers to bounce ideas around like a soccer team bounces the ball around and one person (and the whole team) scores. So Raul was declined the job because:
A. He did not fit in the team (they already have enough people who can't sort)
B. They are a company who only want Guru developers (in which case they will eventually fail, because a team of Guru developers will never ask the "stupid" questions that drive innovation) Its the famous Think Different Apple video. You need misfits in a team.