1337

1337.js

May Challenge: https://gist.github.com/wovalle/a86a76bc20d8c886342040f54875f291

// https://leetcode.com/problems/two-sum/
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const hash = {}
    
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i]
        const rest = target - num
        
        if(hash[num] !== undefined) {
            return [hash[num], i]
        } else {
            hash[rest] = i
        }   
    }
};

// https://leetcode.com/problems/word-pattern/
/**
 * @param {string} pattern
 * @param {string} str
 * @return {boolean}
 */
var wordPattern = function(pattern, str) {
    const lettersInPattern = pattern.split('')
    const wordsInStr = str.split(' ')
    const patternHash = {}
    const stringHash = {}
    
    if(lettersInPattern.length !== wordsInStr.length) {
        return false
    } 
    
    
    for (let i = 0; i < lettersInPattern.length; i++) {
        const word = wordsInStr[i]
        const letter = lettersInPattern[i]
        // the two ifs can be optimized, aint nobody got time for that
        if (patternHash[letter] === undefined) {
            patternHash[letter] = wordsInStr[i]
        } else {
            if(patternHash[letter] !== word) {
                return false
            }
        }
        
        if(stringHash[word] === undefined) {
            stringHash[word] = letter
        } else {
            if(stringHash[word] !== letter) {
                return false
            }
        }
    }
    
    return true
}

// https://leetcode.com/problems/web-crawler/
/**
 * // This is the HtmlParser's API interface.
 * // You should not implement it, or speculate about its implementation
 * function HtmlParser() {
 *
 *		@param {string} url
 *     	@return {string[]}
 *     	this.getUrls = function(url) {
 *      	...
 *     	};
 * };
 */


// this entire function can be optimized by doing some fors instead
const getHostName = (url) => {
    const urlWithoutProtocol = url.replace('http://', '')
    let hostNameEnd = urlWithoutProtocol.indexOf('/')
    
    if (hostNameEnd === -1) {
        hostNameEnd = urlWithoutProtocol.length
    }
    

    return urlWithoutProtocol.slice(0, hostNameEnd)
        .split('.')
        .slice(-2)
        .join('.')
}

const sanitizeUrl = (url) => {
    return url
}

/**
 * @param {string} startUrl
 * @param {HtmlParser} htmlParser
 * @return {string[]}
*/
const crawl = (startUrl, htmlParser) => {
    const queue = [startUrl]
    const found = new Set([startUrl])
    const visited = new Set()
    const startHostName = getHostName(startUrl)
    
    while(queue.length) {
        const currentUrl = queue.shift()
        const rawUrls = htmlParser.getUrls(currentUrl)
        const urls = rawUrls.filter(url => getHostName(url) === startHostName)
            
        // filter by non-visited and push them to the queue
        urls
            .filter(url => !visited.has(url))
            .forEach(url => queue.push(url))
        
        // filter by not found, sanitize em and save it as found
        urls
            .filter(url => !found.has(url))
            .map(url => sanitizeUrl(url))
            .forEach(url => found.add(url))
        
        visited.add(currentUrl)
    }
    
    return Array.from(found)
};

// https://leetcode.com/problems/find-duplicate-file-in-system
/**
 * @param {string[]} paths
 * @return {string[][]}
 */
var findDuplicate = function(paths) {
  const tree = {}
  
  paths.forEach(p => {
    const [folder, ...files] = p.split(' ')
    
    for(let file of files) {
      const [name, content] = file.split('(')
      const key = content.slice(0,-1)
      
      tree[key] = (tree[key] || []).concat(`${folder}/${name}`) 
    }
  })
  
  console.log(tree)
  return Object.entries(tree).filter(e => e[1].length > 1).map(e => e[1])
};

// https://leetcode.com/problems/minimum-path-sum/submissions/
var minPathSum = function (grid) {
  const columns = Array.from({ length: grid[0].length }, () => Infinity);
  const answers = Array.from({ length: grid.length }, () => [...columns]);
  
  answers[0][0] = grid[0][0];

  for (let y = 0; y < answers.length; y++) {
    for (let x = 0; x < answers[0].length; x++) {
      if (y < answers.length - 1)
        answers[y + 1][x] = Math.min(answers[y + 1][x], answers[y][x] + grid[y + 1][x]);
      if (x < answers[0].length - 1)
        answers[y][x + 1] = Math.min(answers[y][x + 1], answers[y][x] + grid[y][x + 1]);
    }
  }

  return answers[answers.length -1][answers[0].length -1];
};

// https://leetcode.com/problems/game-of-life/submissions/
/**
 * @param {number[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
const countNeighbors = (arr, y, x) => {
  let count = 0;

  for (let yp = Math.max(y - 1, 0); yp <= Math.min(y + 1, arr.length - 1); yp++) {
    for (let xp = Math.max(x - 1, 0); xp <= Math.min(x + 1, arr[0].length - 1); xp++) {
      if (yp === y && xp === x) continue;
      if (arr[yp][xp] === 1 || arr[yp][xp] === -1) {
        count++;
      }
    }
  }

  return count;
};

var gameOfLife = function (arr) {
  // -1 was 1 now 0
  // 0 was 0 now 0
  // 1 was 1 now 1
  // 2 was 0 now 1

  for (let y = 0; y < arr.length; y++) {
    for (let x = 0; x < arr[0].length; x++) {
      const neighbors = countNeighbors(arr, y, x);

      if (neighbors < 2) {
        arr[y][x] = arr[y][x] === 1 ? -1 : 0;
      } else if (neighbors <= 3) {
        // if alive and n === 2 or 3, stay alive
        if (arr[y][x] === 0 && neighbors === 3) {
          arr[y][x] = 2;
        }
      } else if (neighbors > 3) {
        arr[y][x] = arr[y][x] === 1 ? -1 : 0;
      }
    }
  }

  for (let y = 0; y < arr.length; y++) {
    for (let x = 0; x < arr[0].length; x++) {
      arr[y][x] = arr[y][x] > 0 ? 1 : 0;
    }
  }

  return arr;
};

// https://leetcode.com/problems/design-phone-directory
class PhoneDirectory {
  constructor(maxNumbers) {
    this.currentNumber = 0;
    this.maxNumber = maxNumbers;
    this.released = [];
  }

  get = function () {
    if (this.currentNumber < this.maxNumber) {
      this.currentNumber++;
      return this.currentNumber - 1;
    } else if (this.released.length > 0) {
      return this.released.pop();
    }

    return -1;
  };

  check = function (number) {
    return (
      this.released.indexOf(number) > -1 ||
      (number >= this.currentNumber && number < this.maxNumber)
    );
  };

  release = function (number) {
    if (number < this.currentNumber && this.released.indexOf(number) === -1) {
      this.released.push(number);
      this.released.sort((a, b) => b - a);
    }
  };
}

// https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/
const letterCombinations = (str) => {
  if (str.trim() === '') return []
  
  const map = {
    1: '',
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
    0: " ",
    "#": "^",
    "*": "+"
  }
  
  const phoneNumbersArray = str.split('')
  const phoneNumbersMap = phoneNumbersArray.map(n => map[n])
  let result = ['']
  
  for (const position of phoneNumbersMap) {
    let localResult = []
    
    for (const resultCombination of result) {
      for (const currentLetter of position) {
          localResult.push(resultCombination + currentLetter)
      }
    }
    
      
    result = localResult
  }
  
  return result
}

// https://leetcode.com/problems/lru-cache
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity
        this.keys = new Set()
        this.store = new Map()
    }

    get(key) {
        if (this.keys.has(key)) {
            this.keys.delete(key)
            this.keys.add(key)
            return this.store.get(key)
        }
        else {
            return -1
        }

    }

    put(key, value) {
        if (this.get(key) !== -1) {
            this.store.set(key, value)
            return;
        }
        
        if (this.keys.size === this.capacity) {
            const nextKey = this.keys.values().next().value
            this.keys.delete(nextKey)
            this.store.delete(nextKey)
        }
        
        this.keys.add(key)
        this.store.set(key, value)
    }
}