Insert Delete GetRandom O(1) - Duplicates allowed

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

public class RandomizedCollection {
    List<Integer> nums;
    Map<Integer, Set<Integer>> numsToIdxs;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList<Integer>();
        numsToIdxs = new HashMap<Integer, Set<Integer>>();
        rand = new Random();
    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean isValPresent = numsToIdxs.containsKey(val);
        if (!isValPresent) {
            numsToIdxs.put(val, new LinkedHashSet<Integer>());
        }
        
        numsToIdxs.get(val).add(nums.size());
        nums.add(val);
        return !isValPresent ;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean isValPresent = numsToIdxs.containsKey(val);
        if (!isValPresent) {
            return false;
        }

        int idxOfVal = numsToIdxs.get(val).iterator().next();
        numsToIdxs.get(val).remove(idxOfVal);
        
        // since we removed one of the numbers, we have to check whether we removed the last number or not.
        // if we did not remove the last number in the list nums (which reflects insertion order), then we run into the scenario         // where numToIdx of the remaining nums at indices > idxOfVal is no longer correct. In order 
        // to fix this, we can remove the last element in nums and add it at idxOfVal. Update numToIdxs so that numAtLastIdx has 
        // its new index. Also remove idxOfVal from the list of indices for val / remove val from numToIdx if it had no 
        // duplicates.
        int lastIdx = nums.size() - 1;
        if (idxOfVal < lastIdx) {
            int numAtLastIdxInList = nums.get(lastIdx);
            nums.set(idxOfVal , numAtLastIdxInList);
            numsToIdxs.get(numAtLastIdxInList).remove(lastIdx);
            numsToIdxs.get(numAtLastIdxInList).add(idxOfVal);
        }
        nums.remove(lastIdx);

        if (numsToIdxs.get(val).isEmpty()) {
            numsToIdxs.remove(val);
        }
        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}

Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

import java.util.Random;

public class RandomizedSet {

    /** Initialize your data structure here. */
    Map<Integer, Integer> numToIdx;
    Map<Integer, Integer> idxToNum;
    
    public RandomizedSet() {
        numToIdx = new HashMap<>();
        idxToNum = new HashMap<>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (numToIdx.containsKey(val)) {
            return false;
        }
        
        int idxForInsertion = numToIdx.size();
        numToIdx.put(val, idxForInsertion);
        idxToNum.put(idxForInsertion, val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!numToIdx.containsKey(val)) {
            return false;
        }
        
        int idxOfVal = numToIdx.get(val);
        numToIdx.remove(val);
        idxToNum.remove(idxOfVal);
        
        if (numToIdx.size() == 0) {
            return true;
        }
        
        if (idxOfVal == numToIdx.size()) {
            return true;
        }
        
        // val was neither the only element, nor the last element.
        // after val was removed, we have to fill val's idx.
        // remove the last element in idxToNum and add it at idxOfVal instead.
        // the idx of the last element is idxToNum.size() as there were idxToNum.size() + 1 numbers
        // before val was removed and the last element had idx idxToNum.size()
        int numAtLastIdx = idxToNum.get(idxToNum.size());
        numToIdx.put(numAtLastIdx, idxOfVal);
        idxToNum.remove(idxToNum.size());
        idxToNum.put(idxOfVal, numAtLastIdx);
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        if (numToIdx.size() == 0) {
            return -1;
        }
        
        if (numToIdx.size() == 1) {
            return idxToNum.get(0);
        }
        
        return idxToNum.get(new Random().nextInt(numToIdx.size()));
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Longest Palindrome Substring

Top k frequent queries from n machines

Let's say we have web search queries for a time window logged across n different servers. Design an algorithm to compute the top k most frequently searched queries.

• Define a tuple with key and value
• Get top k tuples from all the n machines
• We would get > k tuples
• Merge all the top k results from the n machines and build a frequency map
• Find the k-th most frequent element. Let's say that tuple has key K and frequency F_K
• Now your global top k list will have the kth key with frequency >= F_K
• For any key K with frequency F_K, at least one machine should have frequency >= (F_K / n)
• Ask all machines for keys with frequency >= (F_K / n)
• Union the set of keys.
• The keys for the top k most frequent elements would be within the above set
• Query all the machines for keys in the above key set.
• Aggregate results and find the keys with the top k frequencies.
• The bottleneck in this problem is network - If you send distributed hashtables from n machines into a single machine, it is a lot of network activity and a lot of unnecessary work.

Obstacle Grid - II

This is a backtracking problem and pretty similar to the "Rat in a maze" problem in geeksforgeeks

package basic;

/**
 * Grid of 0s and 1s where 0s are obstacles. Given the grid and a point (x, y). Check if there is a path to (x, y)
 * Backtracking / DFS will help solve this problem
 * Note: This problem cannot be solved using dynamic programming with a 2D solution array.
 * To get to cell (0, 0), the valid moves are going left from (0, 1) and going up from (1, 0). We cannot initialize the number of ways to get to (0,0) to 1
 * since we do not know the number of ways to get to cells (0, 1) and (1, 0). Dynamic programming would be useful only when the allowed directions are down and right.
 * In that case, it would be possible to initialize dp[0][0] = 1.
 *
 * This class has a backtracking based solution to solve the obstacle grid problem
 */
public class ObstacleGridAllDirections {
    private final int M;
    private final int N;
    private final int[][] grid;

    public ObstacleGridAllDirections(int[][] grid) {
        this.grid = grid;
        if (grid == null) {
            M = 0;
            N = 0;
        } else {
            M = grid.length;
            N = grid.length == 0 ? 0 : grid[0].length;
        }
    }

    private boolean isValid(int x, int y) {
        return x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == 1;
    }

    public boolean dfs(int i, int j, int destinationX, int destinationY, boolean[][] visited) {
        if (i == destinationX && j == destinationY) {
            visited[i][j] = true;
            return true;
        }

        if (isValid(i, j) && !visited[i][j]) {
            visited[i][j] = true;

            if (dfs(i + 1, j, destinationX, destinationY, visited)) {
                return true;
            }

            if (dfs(i - 1, j, destinationX, destinationY, visited)) {
                return true;
            }

            if (dfs(i, j - 1, destinationX, destinationY, visited)) {
                return true;
            }

            if (dfs(i, j + 1, destinationX, destinationY, visited)) {
                return true;
            }

            return false;
        }
        return false;
    }
}

56. Merge Intervals

https://leetcode.com/problems/merge-intervals/
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Interval {
 int start;
 int end;
 
 Interval() {
  start = 0;
  end = 0;
 }
 
 Interval(int s, int e) {
  start = s;
  end = e;
 }
}
 
public class Solution {
 public List<Interval> merge(List<Interval> intervals) {
  if (intervals == null || intervals.size() <= 1) {
   return intervals;
  }
 
  // sort intervals by using self-defined Comparator
  Collections.sort(intervals, new IntervalComparator());
 
  List<Interval> result = new ArrayList<Interval>();
 
  Interval prev = intervals.get(0);
  for (int i = 1; i < intervals.size(); i++) {
   Interval curr = intervals.get(i);
 
   if (hasIntersection(prev, curr)) {
    // merged case
    Interval merged = merge(prev, curr);
    prev = merged;
   } else {
    result.add(prev);
    prev = curr;
   }
  }
 
  result.add(prev);
 
  return result;
 }
 
 public Interval merge(Interval a, Interval b) {
        return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
    }
    
    
    public boolean hasIntersection(Interval a, Interval b) {
        //a.end intersects with [b.start, b.end] or vice versa
        return (a.end >= b.start && a.end <= b.end)
        || (b.end >= a.start && b.end <= a.end); 
    }
}

class IntervalComparator implements Comparator<Interval> {
 public int compare(Interval i1, Interval i2) {
  return i1.start - i2.start;
 }
}

54. Spiral Matrix

https://leetcode.com/problems/spiral-matrix/

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

http://www.programcreek.com/2013/01/leetcode-spiral-matrix-java/

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
         List<Integer> result = new ArrayList<Integer>();
        if (matrix==null || matrix.length == 0 || matrix[0].length == 0) { 
            return result;
        }
 
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right=n - 1;
        int top = 0;
        int bottom = m - 1;
        
        while (result.size() < m * n) {
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            
            top++;
            
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            
            right--;
            
            // prevent duplicate row
            if (bottom < top) {
                break;
            }
            
            for (int i = right; i >= left; i--) {
                result.add(matrix[bottom][i]);
            }
            
            bottom--;
            
            // prevent duplicate column
            if (right < left) {
                break;
            }
            
            for (int i = bottom; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            
            left++;
        }
        
        return result;
    }
}