Optimized Algoritms

Question 1

canPermutePalindrome:

Given a string, determine if a permutation of the string could form a palindrome.

For example,
“code” -> False, “aab” -> True, “carerac” -> True.

Answer 1

var canPermutePalindrome = function(s) {
    var result = 0;
    var map = {};
    for(let i = 0; i < s.length; i++){
        if(map[s[i]] === undefined){
            map[s[i]] = 1;
            result++;
        }
        else if(map[s[i]] === 1){
            map[s[i]] = 0;
            result--;
        }
        else if(map[s[i]] === 0){
            map[s[i]] = 1;
            result++;
        }
    }
    if(result <= 1) return true;
    else return false;
};

Question 2

wordPattern = function(pattern, str)

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Answer 2

var wordPattern = function(pattern, str) {
    var strArr = str.split(' '), mapPattern={}, mapStr={};

if(pattern.length !== strArr.length) return false;

for(let i=0;i

Question 3

Insert Delete GetRandom 0(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Answer 3

var RandomizedSet = function() {
    this.set = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(!this.set.includes(val)){
        this.set.push(val);
        return true;
    };
    return false;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.set.includes(val)){
        let idx = this.set.indexOf(val)
        this.set.splice(idx,1);
        return true;
    };
    return false;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
  var l = this.set.length;
    return this.set[random(l)];

    function random(l) {
        return Math.floor((Math.random() * l));
    }
};

Question 4

MinStack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

Answer 4

var MinStack = function () {
this.st = [];
this.stMin = [];
};

MinStack.prototype.push = function(x){
    this.st.push(x);
    if (this.stMin.length > 0) {
        var min = this.stMin[this.stMin.length - 1];
        if (x <= min) this.stMin.push(x);
    }
    else {
        this.stMin.push(x);
    }
};

MinStack.prototype.pop = function(){
    if (this.st.length > 0) {
        var num = this.st.pop();
        var min = this.stMin[this.stMin.length - 1];
        if (num == min) this.stMin.pop();
    }
};

MinStack.prototype.top = function () {
    if (this.st.length > 0) {
        return this.st[this.st.length - 1];
    }
    else return null;
};

MinStack.prototype.getMin = function () {
    if (this.stMin.length > 0) {
        var min = this.stMin[this.stMin.length - 1];
        return min;
    }
    else return null;
};