shailrshah

private static final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private static final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};

public String numberToWords(int n) {
    if(n == 0) return "Zero"

    StringBuilder sb = new StringBuilder();
    for(int i = 0; n > 0; n /= 1000, i++) {
        int modThousand = n % 1000;

shailrshah

/*
    3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \

shailrshah

public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<>();
    backtrack(list, new StringBuilder(), 0, 0, n);
    return list;
}

private static void backtrack(List<String> list, StringBuilder sb, int open, int close, int n) {
    if(sb.length() == 2*n){
        list.add(sb.toString());
        return;

shailrshah

// if A knows B -> A is definately not a celeb, B is a candidate
// 1. Finalize on a candidate
// 2. Confirm that everyone knows him and candidate knows no one

public int findCelebrity(int n) {
    int candidate = 0;

    for(int i = 0; i < n; i++) 
        candidate = knows(candidate, i) ? i : candidate;

shailrshah

/*
To find: A range i..j such that nums[i] + nums[i+1] + ... + nums[j] = sum(i, j) = k
sum(i, j) = sum(0, j) - sum(0, i-1) since for [1 2 3 4], sum(1, 3) = sum(0, 3) - sum(0, 0);
sum(0, j) - sum(0, i-1) = k,  or sum(0, i-1) = sum(0, j) - k 
For each sum(0, j), check if there was a sum(0, i-1) such that it equals sum(0, j) - k.
*/

public int maxSubArrayLen(int[] nums, int k) {
    int sum = 0, max = 0;
    Map<Integer, Integer> map = new HashMap<>();

shailrshah

public String minWindow(String s, String t) {      
    Map<Character, Integer> map = new HashMap<>();

    for(Character ch : t.toCharArray())
        map.put(ch, map.getOrDefault(ch, 0) + 1);

    int start = 0, end = 0, toBeFound = t.length();
    int minStart = 0, minLen = Integer.MAX_VALUE;

    while(end < s.length()) {

shailrshah

public int minMeetingRooms(Interval[] intervals) {
    if(intervals == null || intervals.length == 0)
        return 0;

    Arrays.sort(intervals, (i1, i2) -> i1.start - i2.start);
    PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (i1, i2) -> i1.end-i2.end);  

    queue.offer(intervals[0]);                  // start with a room 

    for(int i = 1; i < intervals.length; i++) {

shailrshah

// [1,3],[2,6],[8,10],[15,18] -> [1,6],[8,10],[15,18]
public List<Interval> merge(List<Interval> intervals) {
    Collections.sort(intervals, (i1, i2) -> i1.start - i2.start);

    List<Interval> mergedIntervals = new ArrayList<>();

    for(int i = 0; i < intervals.size(); i++) {
        int start = intervals.get(i).start;
        int end = intervals.get(i).end;

shailrshah

public static void swap(int x, int y) {
	if(x == y) return;
	x = x ^ y; // x = A ^ B, y = B
	y = x ^ y; // x = A ^ B, y = A ^ (B ^ B) = A ^ 0 = A
	x = x ^ y; // y = A, x = A ^ B ^ A = B ^ (A ^ A) = B ^ 0 = B
}

shailrshah

public int longestConsecutive(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    int max = 0;

    for(int i = 0; i < nums.length; i++) {
        if(map.containsKey(nums[i]))
            continue;

        int left = map.getOrDefault(nums[i]-1, 0);
        int right = map.getOrDefault(nums[i]+1, 0);