2
\$\begingroup\$

Yesterday, I gave an interview after a long time, and I was asked a question which I couldn't solve on the spot.

I had to implement a sort function for a Array of strings in JavaScript, with the following requirements:

  • The Array will always contain Strings
  • For sorting, Upper Case has higher priority than Lowe Case Letters, with Numbers having the Least.
  • Assume that Array.sort() cannot be used
  • The performance of the sorting is not a factor; i.e. Bubble sort is fine.

I was thinking of the solution today, and came up with this:

function sortArray(items) {
  let itemcount = items.length;
  for (var i = 0; i < itemcount; i++) { //number of passes
    for (var j = 0; j < (itemcount - 1 - i); j++) { //for checking all pairs in a given pass
      let a = items[j];
      let b = items[j + 1];
      if (compareCaseSenitiveStrings(a, b) < 0) {
        console.log("Switch", a, b)
        items[j + 1] = a;
        items[j] = b;
      }
    }
  }
  //return
  return items;
}


//Function to compare two given strings, and return the index of the higher priority one
function compareCaseSenitiveStrings(a, b) {

  //Inner functions
  function compareCharacters(a, b) {
    //check the case first()
    if (a.getFirstCase() == b.getFirstCase()) {
      let charDiff = a.codePointAt(0) - b.codePointAt(0);
      return -Math.sign(charDiff)
    } else {
      //different cases
      //We need to pass the id of the one which is higher;
      let requiredCaseOrder = ["NONE", "LOWER", "UPPER"];
      return requiredCaseOrder.indexOf(a.getFirstCase()) - requiredCaseOrder.indexOf(b.getFirstCase());
    }
  }

  function isNumeric(n) {
      return !isNaN(parseFloat(n)) && isFinite(n);
    }
    //End of inner functions
    //===============================================

  //Start of function here

  //First check if both are numbers
  if (isNumeric(a) && isNumeric(b)) {
    //return the index of smaller number (since it has higher priority)
    return -Math.sign((parseFloat(a) - parseFloat(b)));
  }

  //Now check that lengths of both is greater than 0
  if ((a.length > 0) && (b.length > 0)) {
    //check the first elements of this string
    let result = compareCharacters(a[0], b[0]);
    if (result != 0) {
      //this means one input has higher priority, lets return that
      return result;
    } else {
      //both are equal
      //get the result of remaining characters
      return compareCaseSenitiveStrings(a.substring(1), b.substring(1));
    }
  } else {
    //length of atleast one of these strings is zero.
    //return the index of the longer element
    let lengthDiff = a.length - b.length;
    return Math.sign(lengthDiff);
  }
}

String.prototype.getFirstCase = function() {
  let caseEnum = ["LOWER", "NONE", "UPPER"];
  var caseIndex = 1;
  if (this == this.toLowerCase()) {
    caseIndex--;
  }
  if (this == this.toUpperCase()) {
    caseIndex++;
  }
  return caseEnum[caseIndex];
};

Is this code readable enough? Are there any other Design Patterns that could be applied? Any other points which could be improved?

\$\endgroup\$
  • \$\begingroup\$ Lose the redundant comments \$\endgroup\$ – psaxton Jul 12 '16 at 22:02
2
\$\begingroup\$

Sorting is hard.

  • console.log( sortArray([ '123', '9' , '1' , '11' ]) ); returns ["1", "9", "11", "123"], that does not sound good. After removing the numeric test I get ["11", "123", "1", "9"] which is better but not intuitive, I would have expected the 1 up front. This shows that you cannot just write the code, you need to build a set of tests to validate your code. Especially during interviews.

  • String.prototype.getFirstCase is very cute, but it needs commenting for lesser readers.

  • You are mixing var and let, I am not too excited about that

  • If you remove the numeric test, then you no longer need isNumeric as well

  • compareCaseSenitiveStrings should be compareCaseSensitiveStrings

  • I would convert 2 line comments to 1 line comment for readability, and an overall review of what comments really add value

  • Other than the code was very readable

\$\endgroup\$
  • \$\begingroup\$ Thanks for your comments. Maybe I wasn't clear in the requirements, but the requirement, as I understood, was that pure numbers should be arranged in increasing order of their value; But I can see that something like '221B Baker' will be arranged with the least priority. \$\endgroup\$ – Devdatta Tengshe Jul 13 '16 at 3:37
1
\$\begingroup\$
function sortArray(items) {
  let itemcount = items.length;
  switches = 1 // dummy variable to enter the while loop
  while (switches) { // while there were switches made in the previous iteration
        switches = 0;

        // this while loop will stop when there are no switches, i.e. the array has already been sorted
    for (var j = 0; j < (itemcount - 1); j++) { //for checking all pairs in a given pass
      let a = items[j];
      let b = items[j + 1];
      if (compareCaseSenitiveStrings(a, b) < 0) {
        console.log("Switch", a, b); // semi-colon added 
        items[j + 1] = a;
        items[j] = b;
        switches += 1;
      }
    }
  }
  //return
  return items;
}

(In the future, use !== to compare to 0). Personally, I would change the sorting algorithm as above, because I think this method would require fewer iterations, although I haven't timed it.

\$\endgroup\$
  • \$\begingroup\$ I can't figure out two things in this code: 1) when does switches become zero? I can only see us incrementing it 2) What does i in line 6 represent? \$\endgroup\$ – Devdatta Tengshe Jul 13 '16 at 3:42
  • \$\begingroup\$ Sorry - both errors have been corrected \$\endgroup\$ – codecademic800 Jul 13 '16 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.