Skip to content

Instantly share code, notes, and snippets.

@m-esm
Created January 23, 2021 19:09
Show Gist options
  • Save m-esm/5abe07930a31975abd5610e5844e5fea to your computer and use it in GitHub Desktop.
Save m-esm/5abe07930a31975abd5610e5844e5fea to your computer and use it in GitHub Desktop.
bolt_tech_interview_2.js
/**
Imagine some photo file names with lowercase letters and/or digits. We want to sort them as a human would consider natural with a function with the following signature.
// return 0 if a = b, <0 if a < b, >0 if a > b
function compareNaturally(a: string, b: string): number {
//TODO implement
}
E.g. input: "photo10", "photo2", "photo1"
abc
ch1pg01
ch1pg02
ch2pg03
ch10pg02
def
1.jpg
a.jpg
defghazzzzzzzzz
defghbb <- greater
Sorting these lexicographically would result in "photo1", "photo10", "photo2".
Instead, we want to sort them as "photo1", "photo2", "photo10" since people don't read the suffix "10" as "1" and "0", but as ten, which is bigger than two, which is bigger than one.
*/
// a => abc
// b => ch1pg01
function compareNaturally(a: string, b: string): number {
const bigString = a.length > b.length ? a : b;
for(let i = 0; i < bigString.length; i++){
const aCode = a.charCodeAt(i);
const bCode = b.charCodeAt(i);
let aValue = 0;
let bValue = 0;
if( aCode !== bCode)
{
if(i + 1 < a.length && a[i].match(/\d/) && a[i + 1].match(/\d/))
aValue = Number(a[i] + a[i + 1]);
else
aValue = Number(a[i]) || 0;
if(i + 1 < b.length && b[i].match(/\d/) && b[i + 1].match(/\d/))
bValue = Number(b[i] + b[i + 1]);
else
bValue = Number(b[i]) || 0;
if(aValue || bValue)
return aValue - bValue;
return aCode - bCode;
}
}
return 0;
}
const result = [
'abc',
'ch1pg01',
'ch1pg02',
'ch2pg03',
'ch10pg02',
'def',
'1.jpg',
'a.jpg',
'defghazzzzzzzzz',
'defghbb',
'a2b1c3',
'a1b1c4',
'a2b1c1',
'z100',
'z103',
'z005',
'z3',
"photo10", "photo2", "photo1"
].sort((a,b) => compareNaturally(a,b));
for(const r of result) {
console.log(r);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment