CollegeStash

UTF-8 Validation – Java

Post author By Shiva Charan Devabhaktuni
Post date October 7, 2018

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

interview

K Empty Slots – Java

Post author By Shiva Charan Devabhaktuni
Post date September 21, 2018

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

interview

Top K Frequent Elements – Java

Post author By Shiva Charan Devabhaktuni
Post date September 18, 2018

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

interview

Reverse Words in a String – Java

Post author By Shiva Charan Devabhaktuni
Post date September 18, 2018

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

interview

Generate Parenthesis

Post author By Shiva Charan Devabhaktuni
Post date September 17, 2018

JavaScript

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = (n) => {
  const ret = [];
  computeParenthesis(n, n, '', ret);
  return ret;
};

const computeParenthesis = (open, close, str, ret) => {
  if (close === 0) {
    return ret.push(str);
  }
  if (open > 0) {
    computeParenthesis(open - 1, close, str + '(', ret);
  }
  if (close > open) {
    computeParenthesis(open, close - 1, str + ')', ret);
  }
};

Java

class Solution {
    List<String> list;
    public List<String> generateParenthesis(int n) {
        list = new ArrayList<String>();
        genP("", n, n);
        return list;
    }
    
    public void genP(String str, int open, int close) {
        if (close == 0) {
          list.add(str);
          return;
        } 
        if (open > 0) {
          genP(str + '(', open - 1, close);
        }
        if (close > open) {
          genP(str + ')', open, close - 1);      
        }
    }
}

Tags es5, es6, facebook, front end, interview, java, javascript, js, leetcode, optimal, solution

interview

Sort Array by Parity – Java

Post author By Shiva Charan Devabhaktuni
Post date September 17, 2018

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

interview

Two Sum

Post author By Shiva Charan Devabhaktuni
Post date September 14, 2018

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

interview

Search in Rotated Sorted Array

Post author By Shiva Charan Devabhaktuni
Post date September 3, 2018

Solution uses a modified version of Binary Search.
Javascript (ES6)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = (nums, target) => {
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] === target) {
      return mid;
    }
    if (nums[low] <= nums[mid]) {
      // Left half is sorted.
      if (target >= nums[low] && target < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      // Right half is sorted.
      if (target > nums[mid] && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return -1;
};

console.log(search([4, 5, 1, 2, 3], 2)); // 3

Demo

Java

Time: O(nlogn)
Space: O(1)

class Solution {
 public int search(int[] nums, int target) {
  int low = 0, high = nums.length - 1;
  int mid;
  while (low <= high) {
   mid = low + (high - low) / 2;
   if (nums[mid] == target)
    return mid;
   else if (nums[mid] < nums[high]) {
    if (target > nums[mid] && target <= nums[high])
     low = mid + 1;
    else
     high = mid - 1;
   } else {
    if (target >= nums[low] && target < nums[mid])
     high = mid - 1;
    else
     low = mid + 1;
   }
  }
  return -1;
 }
}

Tags backend, es5, es6, full stack, interview, java, javascript, js, leetcode, optimal, solution

interview

String to Integer (atoi) – Java

Post author By Shiva Charan Devabhaktuni
Post date September 3, 2018

class Solution {
 public int myAtoi(String str) {
  int ret = 0;
  int i = 0;
  boolean negative = false;
  String retString = "";
  // Without using trim()
  // while(i<str.length() && str.charAt(i) == ' ')
  //     i++;
  str = str.trim();
  if (i >= str.length() || Character.isLetter(str.charAt(i)))
   return ret;
  if (str.charAt(i) == '-') {
   negative = true;
   i++;
  } else if (str.charAt(i) == '+') {
   i++;
  }
  while (i < str.length() && Character.isDigit(str.charAt(i))) {
   retString += str.charAt(i++);
  }
  if (retString != "") {
   try {
    ret = (negative ? -1 * Integer.parseInt(retString) : Integer.parseInt(retString));
   } catch (Exception e) {
    ret = (negative ? Integer.MIN_VALUE : Integer.MAX_VALUE);
   }
  }
  return ret;
 }
}

interview

Merge Intervals

Post author By Shiva Charan Devabhaktuni
Post date September 3, 2018

Javascript (ES6)

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const ret = [];
  let prev = null;
  for (const interval of intervals) {
    if (prev != null) {
      if (interval[0] > prev[1]) {
        ret.push(prev);
        prev = interval;
      } else {
        // Merge case.
        prev[1] = Math.max(interval[1], prev[1]);
      }
    } else {
      prev = interval;
    }
  }
  if (prev !== null) {
    ret.push(prev);
  }
  return ret;
};

console.log(merge([
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18]
])); // [[1,6],[8,10],[15,18]]

Demo

If “n” is the length of the input list, then the “Time Complexity” is O(nlogn).

/**
 * 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 Solution {
 public List < Interval > merge(List < Interval > intervals) {
  // Sort the input list by the start times.
  Collections.sort(intervals, (a, b) -> a.start - b.start);
  List < Interval > ret = new ArrayList < Interval > ();
  Interval prev = null;
  for (Interval curr: intervals) {
   if (prev == null) {
    prev = curr;
   } else {
    if (curr.start <= prev.end) {
     prev.end = Math.max(curr.end, prev.end);
    } else {
     ret.add(prev);
     prev = curr;
    }
   }
  }
  if (prev != null) {
   ret.add(prev);
  }
  return ret;
 }
}

Tags amazon, backend, es5, es6, facebook, fullstack, google, interview, java, javascript, js, leetcode, medium, optimal, solution