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;
    }
}

59. Spiral Matrix II

Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Solution: http://www.programcreek.com/2014/05/leetcode-spiral-matrix-ii-java/

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = n - 1;
        int k = 1;
        
        while (k <= n * n) {
            for (int i = left; i <= right; i++) {
                result[top][i] = k;
                k++;
            }
            
            top++;
            
            for (int i = top; i <= bottom; i++) {
                result[i][right] = k;
                k++;
            }
            
            right--;
            
            for (int i = right; i >= left; i--) {
                result[bottom][i] = k;
                k++;
            }
            
            bottom--;
            
            for (int i = bottom; i >= top; i--) {
                result[i][left] = k;
                k++;
            }
            
            left++;
        }
        
        return result;
    }
}

6. Zig Zag Conversion

Question: https://leetcode.com/problems/zigzag-conversion/

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Ref: Zig Zag conversion solution

/*n=numRows
Δ=2n-2    1                           2n-1                         4n-3
Δ=        2                     2n-2  2n                    4n-4   4n-2
Δ=        3               2n-3        2n+1              4n-5       .
Δ=        .           .               .               .            .
Δ=        .       n+2                 .           3n               .
Δ=        n-1 n+1                     3n-3    3n-1                 5n-5
Δ=2n-2    n                           3n-2                         5n-4
*/

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        
        int step = 2 * numRows - 2;
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < numRows; i++) {
            if (i == 0 || i == numRows - 1) { // first and last rows
                for (int j = i; j < s.length(); j = j + step) {
                     sb.append(s.charAt(j));
                }
            } else {
                // handle  middle rows
                int j = i;
                boolean flag = true;
                int step1 = 2 * (numRows - 1 - i);
                int step2 = step - step1;
                
                while (j < s.length()) {
                    sb.append(s.charAt(j));
                    if (flag) {
                        j = j + step1;
                    } else {
                        j = j + step2;
                    }
                    flag = !flag;
                }
            }
        }
        return sb.toString();
    }
}