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

3. Longest Substring Without Repeating Characters

public class Solution {

 public static int lengthOfLongestSubstring(String s) {

        if (s == null) {

            return 0;

        }

           

        char[] chars = s.toCharArray();

        int longestSoFar = 0;


        HashMap<Character, Integer> numToIdx = new HashMap<Character, Integer>();


        for (int i = 0; i < chars.length; i++) {

            if (!numToIdx.containsKey(chars[i])) {

                numToIdx.put(chars[i], i);

            } else {

                longestSoFar = Math.max(longestSoFar, numToIdx.size());

                i = numToIdx.get(chars[i]);

                numToIdx.clear();

            }

        }


        return Math.max(longestSoFar, numToIdx.size());

    }

}

17. Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

This is a classic recursion problem.

Solution:

• Use an array to store mapping of digits to Strings as seen in the telephone keypad. The mapping would be {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
• If the input String is a digit (2 <= digit <= 9), then we would add each character in the mapped String to the output and return the letter combinations (e.g the letter combinations of 2 are {"a", "b", "c"}
• If there is more than 1 digit in the input, then we would apply the following steps
• Get mapped String "digitLetters" for first character
• Get letter combinations for remaining substring (starting from the 2nd character in input)
• For each letter combination in the combinations for the remaining substring
• For each character c in digitLetters, concatenate c and letter combination
• Add the resulting new letter combination to the output list 

public class Solution {
  String[] digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  
  public List<String> letterCombinations(String digits) {
    List<String> letterCombo = new ArrayList<String>();
    if (digits.length() == 0) {
      return letterCombo;
    }
    
    String digitLetters = digitMap[digits.charAt(0) - '0'];
    if (digits.length() == 1) {
      for (int i = 0; i < digitLetters.length(); i++) {
        letterCombo.add(String.valueOf(digitLetters.charAt(i)));
      }
      return letterCombo;
    } else {
      List<String> subLetterCombo = letterCombinations(digits.substring(1));
      for (String s : subLetterCombo) {
        for (int i = 0;i < digitLetters.length(); i++) {
          letterCombo.add(digitLetters.charAt(i) + s);
        }
      }
      return letterCombo;
    }
  }
}

38. Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Solution:

• An iterative solution is intuitive
• Since we have to generate the n-th sequence for an integer, it is useful to write a helper that takes a String and generates it's count - and - say sequence
• Initialize starting sequence to "1"
• To generate the n-th sequence for a number n, call the helper n - 1 times and keep updating the sequence

public class Solution {
    public String countAndSay(int n) {
        String curSeq = "1";
        
        for (int p = 2; p <= n; p++) {
            curSeq = countAndSayIt(curSeq);
        }
        return curSeq;
    }
    
    private String countAndSayIt(String curSeq) {
        int pos = 0;
        int N = curSeq.length();
        String countAndSaySeq = "";
        
        while (pos < N) {
            char c = curSeq.charAt(pos);
            int freq = 1;
            pos++;
            
            // check if c repeats consecutively and update freq
            while (pos < N && curSeq.charAt(pos) == c) {
                freq++;
                pos++;
            }
            
            countAndSaySeq += (freq + "" + c);
        }
        
        return countAndSaySeq;
    }
}

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Solution:
Ref: http://www.programcreek.com/2012/12/leetcode-word-ladder/

This problem can be solved using BFS. 

• The first step is to create a data structure that can hold a word and the number of steps needed to get to this word from the start word. WordNode is the data structure we'd use here.
• Create a queue of WordNode objects
• Add a node for the start word with number of steps = 1
• While the queue is not empty, poll and check if the removed node is to the end word
• If yes, return the number of steps
• Otherwise, we start a BFS transformation
• BFS:
• In order to generate the transformation sequence or ladder, we know that only one character can be changed at a time
• Therefore, loop over each character of current word and attempt to replace it with each letter in [a,z]. 
• If the transformed word formed by the step above is present in the dictionary,  add a WordNode for the new word to the queue. The number of steps = number of steps for current word + 1
• Remember to reset the replaced character in current word to continue the transformation sequence with the next character in current word
• In this process, if any transformation sequence terminates in end word, we would return the length of the ladder
• If there is no such transformation sequence, we wind up and return 0 per requirements in the question

class WordNode{
    String word;
    int numSteps;
 
    public WordNode(String word, int numSteps){
        this.word = word;
        this.numSteps = numSteps;
    }
}

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Queue<WordNode> queue = new LinkedList<WordNode>();
        queue.add(new WordNode(beginWord, 1));
        
        while (!queue.isEmpty()) {
            WordNode node = queue.poll();
            String currentWord = node.word;
            
            if (currentWord.equals(endWord)) {
                return node.numSteps;
            }
            
            char[] currentWordChars = currentWord.toCharArray();
            
            for (int i = 0; i < currentWordChars.length; i++) {
                for (char c = 'a'; c <= 'z'; c++){
                    char temp = currentWordChars[i];
                    if (currentWordChars[i] != c) {
                        currentWordChars[i] = c;
                    }
                    
                    String newWord = new String(currentWordChars);
                    if (wordDict.contains(newWord)) {
                        queue.add(new WordNode(newWord, node.numSteps + 1));
                        wordDict.remove(newWord);
                    }
                    currentWordChars[i] = temp;
                }
            }
        }
        return 0;
    }
}