Insert Delete GetRandom O(1) – Duplicates allowed

No Comments

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

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.

remove(val): Removes an item val from the collection if present.

getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
 
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
 
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
 
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
 
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
 
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
 
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

[Problem Link]

The idea here is to use a HashMap and Array. As we insert val’s, we have a mapping of val’s and nodes (containing value and index). We also insert the node into an array. At any point of time if we need a random value, we simply generate a random number (between 1 to length of array) and return the value from the array (in O(1) time).

How do we remove an element in O(1) time? First we use the map, to find the node where this element is stored. We then swap that with the last element and finally remove the last element. This works because when we look for a random number, we don’t care about order of elements in the array.

This wont work if you don’t store index’es in Nodes.

Let’s look at an example for remove. Below is the status of the HashMap and array at some point of the program. Note that, #xxx is the reference to the Node object (where we store index and value).

1 -> [#abc  #def  #ghi]
2 -> [#jkl  #mno]
3 -> [#pqr]
 
[#abc  #def  #mno  #ghi  #jkl  #pqr]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 }
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 5, val: 3 }
 
After remove(2)
 
1 -> [#abc  #def  #ghi]
2 -> [#jkl]
3 -> [#pqr]
 
[#abc  #def  #pqr  #ghi  #jkl]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 } (DELETED)
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 2, val: 3 } (UPDATED INDEX AND POSITION IN ARRAY)

Here is what we need todo to remove(2)

  1. Using the HashMap find positions where ‘2’ is stored. We could pick any position to remove it from (we pick #mno pointing to { idx: 2, val: 2 }).
  2. We then pop the last element (i.e. #pqr pointing to { idx: 5, val: 3 })
  3. We need to replace the reference in the array from #mno to #pqr.
    this.arr[removeNode.idx] = lastNode;
  4. Note, at this point #pqr index is still 5, we simply update that to the correct index
    lastNode.idx = removeNode.idx;
/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.arr = [];
    this.map = {};
    this.Node = function(val, idx) {
        this.val = val;
        this.idx = idx;
    }
};
 
/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    if (!this.map[val]) this.map[val] = [];
    let newNode = new this.Node(val, this.arr.length);
    this.arr.push(newNode);
    this.map[val].push(newNode);
    //console.log('insert', val, this.arr);
    return this.map[val].length === 1;
};
 
/**
 * Removes a value from the collection. Returns true if the collection contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if (!this.map[val] || this.map[val].length === 0) return false;
    let removeNode = this.map[val].pop();
    let lastNode = this.arr.pop();
    if ( removeNode.idx !== lastNode.idx ) {
        lastNode.idx = removeNode.idx;
        this.arr[removeNode.idx] = lastNode;
    }
    //console.log('remove', val, this.map);
    //console.log(this.arr)
    return true;
};
 
/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    if (this.arr.length < 1) return;
    let randomIdx = Math.floor(Math.random() * this.arr.length);
    //console.log('random', randomIdx, this.arr, this.arr.length)
    return this.arr[randomIdx].val;
};
 
/** 
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

[Programming Problem] Closest Binary Search Tree Value I and II

No Comments

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

[Problem Link]

Since this is a BST, if the current node is larger than target, we look in the left subtree, else in the right subtree. In the end we simply return the value we get back from our recursion or the current node value depending on whichever one is closer to target. Remember to account for null values when we encounter a leaf node.

Time complexity is O(lgN)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    if (!root) return null;
 
    let minNext;
    if (root.val > target) minNext = closestValue(root.left, target);
    else minNext = closestValue(root.right, target); 
 
    let minCurrDist = Math.abs(root.val-target);
    let minNextDist = minNext !== null ? Math.abs(minNext-target) : Number.MAX_VALUE;
 
    return minNextDist < minCurrDist ? minNext: root.val;
};

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

[Problem Link]

Traverse the full tree and keep storing closest distances (to target) in a priority queue. In the end, pop k number of elements from the queue and return the result. Note, the priority queue will be ordered based on distance (and not on the node values).

Time complexity will be O(NLgN), insert N items into a heap.
If we decide to keep the heap size k, it goes to O(NLgK).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
class Node implements Comparable<Node> {
    int val;
    double dist;
    public Node(int val, double dist) {
        this.val = val;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist < o.dist ? -1 : 1;
    }
}
 
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        traverseBST(root, target, q);
        List<Integer> ret = new ArrayList<Integer>();
        for ( int i = 0 ; i < k ; i++ ) {
            ret.add(q.poll().val);
        }
        return ret;
    }
 
    public void traverseBST(TreeNode root, double target, PriorityQueue<Node> q) {
        if ( root == null )
            return;
        q.offer(new Node(root.val, Math.abs(root.val - target)));        
        traverseBST(root.left, target, q);
        traverseBST(root.right, target, q);        
    }
}

Another approach would be to traverse (inOrder) through the tree to build a sorted array (i.e. O(n)). Then we use two pointers to get the subarray which has numbers closest to k (i.e. another O(n) time complexity).

Total time complexity for this is: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
 
function inOrder(root, arr) {
    if (!root) return;
 
    inOrder(root.left, arr);
    arr.push(root.val);
    inOrder(root.right, arr);
}
 
var closestKValues = function(root, target, k) {
    let ret = [];
    inOrder(root, ret);
    let i = 0;
    let j = ret.length - 1;
    while ((j-i+1) != k) {
        let iDist = Math.abs(ret[i] - target);
        let jDist = Math.abs(ret[j] - target);
        if ( iDist < jDist ) j--
        else i++
    }    
    let finalRet = [];
    for ( let start = i ; start <= j ; start++ ) finalRet.push(ret[start]);
    return finalRet;
};

[Programming Problem] Daily Temperatures

No Comments

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

[Problem Link]

If you find a decreasing sequence keep moving forward until you find the number that breaks the sequence. Once you find that, move backward to find temperatures lower than that one. We could use a stack for this.

  1. Keep adding temperatures to a stack.
  2. If current temperature is less than or equal to the last element, add this temperature to the stack.
  3. If you find the current temperature is more than the last element on the stack you’ve found the next highest temperature for it (and possibly some temperatures before that). Keep doing this while the topmost element on the stack is less than the current temperature.

Basically when you find a decreasing sequence, just keep adding it to the stack. When that sequence breaks (meaning you find an element higher than the previous one), keep pop-ing elements from the stack to find temperatures that are lesser than the current temperature. We store indexes (and not actual temperatures) on the stack, so that we can calculate the days elapsed as we go.

Time and space complexity for this would be O(N)

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    if ( T.length === 0 ) return [];
    let ret = [];
    let arr = [ 0 ];
    T.forEach(function(curr, i) {
        if ( i === 0 ) return;
        while ( arr.length > 0 && T[arr[arr.length-1]] < curr ) {
            let lastElement = arr.pop();
            ret[lastElement] = i - lastElement;
        }
        arr.push(i);
    });
    if ( arr.length > 0 ) {
        arr.forEach(function(curr) {
            ret[curr] = 0;
        });
    }
    return ret;
};

[Programming Problem] Restore IP Addresses

No Comments

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:
 
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Problem Link

This was an interesting problem. We divide the string into fragments (starting with 4) and return strings at each recursion.

Gotcha 1: for some reason i thought for the final fragment (e.g ‘123’) would return ([‘1’, ‘2’, ‘3’]). if we’re at the last fragment we simply return the string (if its valid).

Gotcha 2: an ip fragment cannot be more than 255 (and it cannot be more than 3 numbers, but if we check if fragment is less than 255, the max char check takes care of itself)

Gotcha 3: Just ‘0’ as a fragment is valid but ‘0xx’ (e.g. ’01’, ‘001’, ‘010’ etc) are not. We need to check for that.

Gotcha 4: an empty ” fragment is invalid! Make sure we check for that and return an empty array.

/**
 * @param {string} s
 * @return {string[]}
 */
 
function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}
 
function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];
 
  let ret = [];
 
  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);      
  }
 
  return ret;
 
}
 
var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};

Time complexity?
https://cs.stackexchange.com/questions/121293/time-complexity-for-the-restore-ip-addresses-problem

[Programming Problem] N-ary Tree Level Order Traversal

No Comments

Given an n-ary tree, return the level order traversal of its nodes’ values.

[Problem Link]

Pretty straightforward BFS traversal logic. Here are some small gotcha’s:

  • Add condition for empty/undefined input.
  • When you return the list of lists, the expectation is to return just values and not the Node object. Notice the last line (ret.map(..)) is doing just that.
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if ( !root || root.length === 0) return [];
    let ret = [[root]];
    let currLevel = 0;
    while (true) {
        let nextLevel = [];
        ret[currLevel].forEach((item) => item.children.forEach((child) => nextLevel.push(child))); 
        if ( nextLevel.length === 0 ) break;
        ret.push(nextLevel);
        currLevel++;
    }    
    return ret.map((arr) => arr.map((item) => item.val))
};

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, "");
    }
}

[Leetcode] Binary Tree Right Side View

No Comments

[Problem Link]

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:
 
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
  • Perform a breath first traversal of the tree also called a level order traversal.
  • Before you start processing any level, add the last node from your Q/list to the return list. That’s the node the user would see from the right side.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        if ( root != null )
            q.add(root);
        while ( q.size() > 0 ) {
            int levelSize = q.size();
            ret.add(q.getLast().val);
            for ( int i = 0 ; i < levelSize ; i++ ) {
                TreeNode curr = q.remove(0);
                if ( curr.left != null )
                    q.add(curr.left);
                if ( curr.right != null )
                    q.add(curr.right);
            }
        }
        return ret;
    }
}

[Leetcode] One Edit Distance

No Comments

[Problem Link]

If you’ve solved the edit distance dynamic programming problem, this problem should be straightforward.

  1. Make sure to return false if both strings are equal. The problem asks us to return true only if they’re one edit distance apart! Proceed if they’re unequal.
  2. Use two pointers set at the end of each string. Find the ‘first’ character thats a mismatch. Keep in mind to stop if either of the pointers reach the end. Even if you exhaust one of the strings and have remaining characters left in the other, its still a mismatch!
  3. Once we’ve found ‘one’ mismatch, we need to simply check if inserting, deleting or replacing a character gives us an equal string. For checking this we create a checkEquals() method.
  4. checkEquals() method simply checks if two (sub) strings are exactly equal! We’ll pass both the strings and ending indexes i and j to this method. Return whatever checkEquals() returns.
class Solution {
    public boolean isOneEditDistance(String s, String t) {
 
        if ( s.equals(t) )
            return false;
 
        int i = s.length() - 1;
        int j = t.length() - 1;
 
        while ( i >= 0 && j >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                break;
            i--; j--;
        }
 
        // check if insert, delete or replace returns a valid string!
        return checkEquals(s, t, i-1, j) || 
                checkEquals(s, t, i, j-1) || 
                    checkEquals(s, t, i-1, j-1);
    }
 
    public boolean checkEquals(String s, String t, int i, int j) {
        if ( i != j )
            return false;
 
        while ( i >= 0 ) {
            if ( s.charAt(i) != t.charAt(j) )
                return false;
            i--; j--;
        }
 
        return true;
    }
}

[Hackerrank] Pairs

No Comments

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

[Problem Link]

  • Add all elements to a Set
  • To figure if an element arr[i] and some X make a pair, we check if
    (arr[i] – Target) is in Set

    why?
    arr[i] – X = Target
    X = arr[i] – Target

    // Complete the pairs function below.
    static int pairs(int k, int[] arr) {
        Set<Integer> arrSet = new HashSet<Integer>();
        for ( int i = 0 ; i < arr.length ; i++ )
            arrSet.add(arr[i]);
 
        int ret = 0;
        for ( int i = 0 ; i < arr.length ; i++ )
            if (arrSet.contains(arr[i]-k))
                ret++;
        return ret;
    }

Older Entries