Author: Shiva Charan Devabhaktuni

Sometimes, we would like to wait a certain minimum time period before successive method calls. For example in events like onscroll(), onresize(), this can go a long way in terms of optimizing the page performance as a whole.

The wrapping of the methods using a Debounce method is a simple way to achieve the desired result.

const debounce = (fn, interval) => {
  let timeout;
  return (...rest) => {
    if (timeout)
      clearTimeout(timeout);
      timeout = setTimeout(() => {
        fn.apply(this, rest);
      }, interval);
  };
}

const test = (inp) => {
  console.log(inp);
};

const db = debounce(test, 1000);
const cb = () => {
  db('test');
};
const button = document.createElement('button');
button.innerHTML = 'fire';
document.body.appendChild(button);
button.addEventListener('click', cb);

Demo

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

Time O(nlogn)
Space O(n)

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        if (flowers.length == 1 && k == 0) return 1;
        TreeSet < Integer > set = new TreeSet < Integer > ();
        for (int i = 0; i < flowers.length; i++) {
            int curr = flowers[i];
            Integer higher = set.higher(curr);
            if (higher != null && higher - curr == k + 1) {
                return i + 1;
            }
            Integer lower = set.lower(curr);
            if (lower != null && curr - lower == k + 1) {
                return i + 1;
            }
            set.add(curr);
        }
        return -1;
    }
}

Runtime O(nlogn)

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> times = new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++) {
            if(times.get(nums[i])!=null) {
                times.put(nums[i], times.get(nums[i])+1);
            } else {
                 times.put(nums[i], 1);
            }
        }
        List<Integer> list = new ArrayList<Integer>(times.keySet());
        list.sort((a,b)->times.get(b)-times.get(a));
        return list.subList(0,k);
    }
}

(more…)

Using a Stack
Uses O(n) memory and time.

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        Stack<String> track = new Stack<String>();
        String word = "";
        int i=0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                track.push(word);
                word = "";
                while(i<s.length() && s.charAt(i) == ' ')
                    i++;
                continue;
            }
            word +=s.charAt(i++);
        }
        if (word != "") {
            track.push(word);
        }
        s = "";
        while(!track.isEmpty()) {
            s+= track.pop()+" ";
        }
        
        return s.trim();
    }
}

(more…)

This solution runs in 0(n) time (linear) and uses O(1) space (constant) and is based on the Dutch National Flag Problem.

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int low = 0, mid = 0, high = A.length - 1;
        int temp;
        while (mid <= high) {
            if (A[mid] == 0) {
                temp = A[mid];
                A[mid] = A[low];
                A[low] = temp;
                low++;
                mid++;
            } else if (A[mid] % 2 == 0) {
                mid++;
            } else {
                temp = A[mid];
                A[mid] = A[high];
                A[high] = temp;
                high--;
            }
        }
        return A;
    }
}

Optimized for runtime.
Time O(n)
Memory O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        HashMap < Integer, Integer > map = new HashMap < Integer, Integer > ();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) != null) {
                ret[0] = map.get(nums[i]);
                ret[1] = i;
                return ret;
            }
            map.put(target - nums[i], i);
        }
        return ret;
    }
}