Categories
interview

Top K Frequent Elements – Java

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

Reverse Words in a String – Java

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

Generate Parenthesis

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

Categories
interview

Sort Array by Parity – Java

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

 

Categories
interview

Two Sum

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

Search in Rotated Sorted Array

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

String to Integer (atoi) – Java

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

Merge Intervals

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

Product of Array Except Self – Java

Time – O(n)
Space – 0(1)  – Neglecting the output array that is expected to be returned.

class Solution {
 public int[] productExceptSelf(int[] nums) {
  int n = nums.length;
  int[] output = new int[n];
  int temp = 1;
  // product from left to right excluding nums[i]
  for (int i = 0; i < n; i++) {
   output[i] = temp;
   temp *= nums[i];
  }
  temp = 1;
  // product from right to left excluding nums[i]
  for (int i = n - 1; i >= 0; i--) {
   output[i] *= temp;
   temp *= nums[i];
  }
  return output;
 }
}
Categories
interview

Copy List with Random Pointer (Reference) – Java

This method doesn’t use a HashMap.

Copy List with Random Pointer

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
 public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null)
   return null;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}