What I've done today is Triangular, pentagonal, and hexagonal in Rust and LRU Cache in JavaScript.

Math

Problem

Triangular, pentagonal, and hexagonal

Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae: | Number | Formula | ... | | ---------- | --------------------- | ---- | --------------------- | | Triangle | Tn=n(n+1)/2 | 1, 3, 6, 10, 15, ... | | Pentagonal | Pn=n(3n−1)/2 | 1, 5, 12, 22, 35, ... | | Hexagonal | Hn=n(2n−1) | 1, 6, 15, 28, 45, ... |

It can be verified that $T_{285}$ = $P_{165}$ = $H_{143}$ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Solution

Brute Force!!!!

Implementation

use std::collections::HashSet;

fn main() {
    let mut trangular: HashSet<usize> = HashSet::new();
    let mut pentagonal:HashSet<usize> = HashSet::new();
    for i in 165..100000 {
        trangular.insert(i*(i+1)/2);
        pentagonal.insert(i*(3*i-1)/2);
    }
    for i in 144..100000 {
        let tmp = i*(2*i-1);
        if trangular.contains(&tmp) && pentagonal.contains(&tmp) {
            println!("Answer is {}", tmp);
            return;
        }
    }
}

Algorithm

Problem

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solution

A map with count will be enough for this problem.

A list will be better, but I don't know it in js.

Leave it for later or... Maybe?

Implementation

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.cap = capacity;
  this.cnt = 0;
  this.container = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  this.cnt += 1;
  if (this.container.has(key)){
    let tmp = this.container.get(key);
    tmp[1] = this.cnt;
    return tmp[0];
  }
  return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  this.cnt += 1;
  this.container.set(key, [value, this.cnt]);
  if (this.container.size > this.cap) {
    let mn = 1e9;
    let index = -1;
    for (const [key, val] of this.container) {
      if (val[1] < mn) {
        mn = val[1];
        index = key;
      }
    }
    this.container.delete(index);
    this.container.set(key, [value, this.cnt]);
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = Object.create(LRUCache).createNew(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */