bolt_tech_interview_2.js

gistfile1.txt

/**

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);
}