Simplify Path

No Comments

[Problem Link]

  • Tokenize the string with ‘/’ as a delimiter.
  • Create a graph where nodes have pointers to parent nodes.
  • Keep moving up(& down) the graph depending on the directory.
  • If you see a directory, create (or move) to the node (depending on if it exists or not)!
  • Make sure you don’t move above the root node because “Going one level up from the root directory is a no-op”.
  • When you’re done, traverse up to the root node (while creating the path).
  • If the path is empty, return “/”
/**
 * @param {string} path
 * @return {string}
 */
 
function node(val, parent) {
  this.val = val;
  this.parent = parent;
  this.children = [];
 
  this.findChild = function(val) {
    var result = this.children.filter((child) => child.val === val);
    return result && result.length === 1 && result[0];
  }
}
 
var simplifyPath = function(path) {
  var root = new node('', null);
  path.split("/").forEach((dir) => {
    if ( dir ) {
      if ( dir === '..' ) {
        if (root.parent) {
          root = root.parent;
        }
      } else if ( dir !== '.' ) {
        var child = root.findChild(dir);
        if (!child) {
          child = new node('/' + dir, root);
          root.children.push(child);
        }
        root = child;
      }
    }
  })
 
  var ret = '';
  var curr = root;
  while (curr) {
    ret = curr.val + ret;
    curr = curr.parent;
  }
 
  return ret ? ret : '/';
};

Integer to English Words

No Comments

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

[Problem Link]

  1. Create a list of numbers for which you have to know the text. For example, there is no way you could come up with text for 1-9, 10-20, 30, 40… without knowing them!
  2. Create a subroutine that solves this problem for 3 digit numbers (up-to 999). If you find the number in the above map return string, else build it. For eg. 123
    1            2 0          3
    - - -      | - - -      | - - -
    ^ Hundred    ^ Twenty     ^ There
  3. Use the above routine to convert digits in batches of 3. Depending on the batch, add Thousand, Million and/or Billion to the converted batch of 3 digits. E.g. to convert 2,190,876,001
    0 0 2          1 9 0        8 7 6         0 0 1
    - - -        | - - -      | - - -       | - - -
    ^ Billion    ^ Million    ^ Thousand

Gotcha’s

  • If num is 0 output “Zero”. This is the only case you will use zero.
  • If any of the 3 digits in the batches are 0, output nothing! E.g. 1000123, make sure you don’t output an extra Thousand anywhere, meaning something like “One Million Thousand One Hundred Twenty Three”.
class Solution {
 
    Map<Integer, String> num2wordsMap = new HashMap<Integer, String>() {{
        put(1, "One");
        put(2, "Two");
        put(3, "Three");
        put(4, "Four");
        put(5, "Five");
        put(6, "Six");
        put(7, "Seven");
        put(8, "Eight");
        put(9, "Nine");
        put(10, "Ten");
        put(11, "Eleven");
        put(12, "Twelve");
        put(13, "Thirteen");
        put(14, "Fourteen");
        put(15, "Fifteen");
        put(16, "Sixteen");
        put(17, "Seventeen");
        put(18, "Eighteen");
        put(19, "Nineteen");
        put(20, "Twenty");
        put(30, "Thirty");
        put(40, "Forty");
        put(50, "Fifty");
        put(60, "Sixty");
        put(70, "Seventy");
        put(80, "Eighty");
        put(90, "Ninety");
        put(100, "One Hundred");
        put(200, "Two Hundred");
        put(300, "Three Hundred");
        put(400, "Four Hundred");
        put(500, "Five Hundred");
        put(600, "Six Hundred");
        put(700, "Seven Hundred");
        put(800, "Eight Hundred");
        put(900, "Nine Hundred");
    }};
 
    public String numberToWords(int num) {
        if (num == 0)
            return "Zero";
 
        String ret = "";
        int index = 0;
        while ( num > 0 ) {
            int lastThree = 0;
            lastThree += (num % 10);
            num /= 10;
            lastThree += ((num % 10)*10);
            num /= 10;
            lastThree += ((num % 10)*100);
            num /= 10;
 
            if (lastThree==0) {
                index++;
                continue;
            }
 
            String threeDigitRet = threeDigitNumberToWords(lastThree);
            if ( index == 0 ) {
                ret = threeDigitRet;
            } else if ( index == 1 ) {
                ret = threeDigitRet + " Thousand " + ret;
            } else if ( index == 2 ) {
                ret = threeDigitRet + " Million " + ret;
            } else if ( index == 3 ) {
                ret = threeDigitRet + " Billion " + ret;
            }
 
            index++;
        }
        return ret.trim();
    }
 
    /**
    * convert 3 numbers to text
    */
    public String threeDigitNumberToWords(int num) {
        int units = num % 10;
        int tens = (num/10) % 10;
        int hundreds = (num/100) % 10;
        int tensNum = tens*10 + units;
 
        String ret = "";
        if (!numberToWordsMap(num).equals("")) {
            ret += numberToWordsMap(num);
        } else {
            ret += hundreds != 0 ? numberToWordsMap(hundreds) + " Hundred " : "";
            if (!numberToWordsMap(tensNum).equals("")) {
                ret += numberToWordsMap(tensNum);
            } else {
                ret += (tens != 0 ? numberToWordsMap(tens*10) + " " : "");
                ret += numberToWordsMap(units);
            }
        }
 
        return ret;
    }
 
    public String numberToWordsMap(int n) {
        return num2wordsMap.getOrDefault(n, "");
    }
}