Sliding Window - How to Succeed in Algorithms Interview


Sliding window - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Applications of Sliding Window

  • window of size k
  • Shortest/longest Subarray with xxx
  • continuous subarrays or substrings

How to Implement Sliding Window

  • expand (end pointer) the window until it meets the criteria
  • reset value when it violates
  • shrink (start pointer) to make it smallest
  • maintain states when expand and shrink: put in a map/set
  • use together with queue or monotone queue

Implementation Detail

Multiple List

public int lengthOfLongestSubstring(String s) {
     if (s.length()==0) return 0;
     HashMap<Character, Integer> map = new HashMap<Character, Integer>();
     int max=0;
     for (int i=0, j=0; i<s.length(); ++i){
         if (map.containsKey(s.charAt(i))){
             j = Math.max(j,map.get(s.charAt(i))+1);
         }
         map.put(s.charAt(i),i);
         max = Math.max(max,i-j+1);
     }
     return max;
 }
public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> map = counter(p);
    int match = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) == 0) {
                match++;
            }
        }
        if (i >= p.length()) {
            c = s.charAt(i - p.length());
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
                if (map.get(c) == 1) {
                    match--;
                }
            }
        }
        if (match == map.size()) {
            result.add(i - p.length() + 1);
        }
    }
    return result;
}

Window class

  • LeetCode 992 - Subarrays with K Different Integers
    public int subarraysWithKDistinct(int[] A, int K) {
    Window window1 = new Window();
    Window window2 = new Window();
    int ans = 0, left1 = 0, left2 = 0;
    for (int right = 0; right < A.length; ++right) {
      int x = A[right];
      window1.add(x);
      window2.add(x);
      while (window1.different() > K)
        window1.remove(A[left1++]);
      while (window2.different() >= K)
        window2.remove(A[left2++]);
      ans += left2 - left1;
    }
    return ans;
    }

    Jumping Window + Fixed Size

  • LeetCode 683 - K Empty Slots
    public int kEmptySlots(int[] flowers, int k) {
      int[] days = new int[flowers.length];
      for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1;
      int left = 0, right = k + 1, result = Integer.MAX_VALUE;
      for (int i = 0; right < days.length; i++) {
          if (days[i] < days[left] || days[i] <= days[right]) {
              if (i == right)
                  result = Math.min(result, Math.max(days[left], days[right]));
              left = i;
              right = k + 1 + i;
          }
      }
      return (result == Integer.MAX_VALUE) ? -1 : result;
    }

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)