Month: October 2018

Categories
interview

Minimum Window Substring – Java

The brute force method would be calculate all the substrings, which would be inefficient.

Runtime Complexity O(m + n)

Space Complexity O(m+n)

class Solution {
    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        if (tLen > sLen)
            return "";
        int[] pattern = new int[256];
        int[] given = new int[256];
        for (int i = 0; i < tLen; i++)
            pattern[t.charAt(i)]++;
        int mstart = 0, size = 0, start = 0, min = sLen + 1;
        for (int j = 0; j < s.length(); j++) {
            char curr = s.charAt(j);
            if (given[curr] < pattern[curr])
                size++;
            given[curr]++;
            if (size == tLen) {
                while (given[s.charAt(start)] > pattern[s.charAt(start)]) {
                    given[s.charAt(start)]--;
                    start++;
                }
                int len = j - start + 1;
                if (len < min) {
                    min = len;
                    mstart = start;
                }
            }
        }
        if (size < tLen)
            return "";
        return s.substring(mstart, mstart + min);
    }
}
Categories
interview

UTF-8 Validation – Java

Hint UTF-8 ranges between 1 to 4 bytes (8-bits).

Runtime: O(n)

class Solution {
    public boolean validUtf8(int[] data) {
        int n = data.length;
        int skip = 0b10000000;
        int check = 0;
        for (int currByte: data) {
            if (check > 0) {
                if ((currByte & skip) == skip)
                    check--;
                else
                    return false;
            } else {
                check = getHeadType(currByte);
                if (check < 0) return false;
            }
        }
        return check == 0;
    }

    public int getHeadType(int num) {
        if ((num & 0b11110000) == 0b11110000 && (num & 0b00001000) != 0b00001000) return 3;
        if ((num & 0b11100000) == 0b11100000 && (num & 0b00010000) != 0b00010000) return 2;
        if ((num & 0b11000000) == 0b11000000 && (num & 0b00100000) != 0b00100000) return 1;
        if ((num & 0b10000000) == 0b10000000) return -1; //error
        return 0;
    }
}