Wednesday, December 31, 2014

Binary Search Tree Iterator

mplement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Use a stack to store all left child of the tree (pushNode()). When calling next() method, pop() the tail of the stack. If the node has a right child, store all left children of the right child (pushNode(right)).




public class BSTIterator {
    
    private Stack stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack ();
        pushNode(root);
        
    }
    private void pushNode(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
    

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        if (stack.isEmpty()) {
            throw new Error("All nodes have been visited");
        }
        TreeNode curr = stack.pop();
        if(curr.right != null) {
            pushNode(curr.right);
        }
        return curr.val;
    }
}

Tuesday, December 30, 2014

All about bit manipulation


Check if a string has all unique characters


public boolean isUnique(String s) {
  if (s == null)
   throw new NullPointerException("Null string!");
  if (s.length() == 0)
   return true;
  int check = 0;
  for (int i = 0; i < s.length(); i++) {
   int val = Character.getNumericValue(s.charAt(i));
   if ((check & (1 << val)) > 0) 
    return false;
   check |= (1 << val);
  }
  return true;
 }

Insert bits

You are given two 32-bit numbers, N and M, and two bit positions, i and j.Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).

Set all positions after j to zero
Set all positions after i back to 1
get the mask where all bits between i to j is cleared
put m into n from ith position

public int insertBitnumber(int m, int n, int posi, int posj) {
  //32 bit of 1s == -1;
  int max = ~0;
  /* e.g., posj = 3
   * 1 << posj = 1000
   * (1 << posj) - 1 = 111
   * max - that will leave all bits after j = 0;
   */
  int left = max - ((1 << posj) - 1);
  int right = (1 << posi) - 1;
  //this operation will leave all positions between posi and posj equals zero
  int mask = left | right;
  //mask & n will clear all bits between i and j in n
  // then we put m in those positions
  return (mask & n) | (m << posi);
  
 }


Decimal To Binary

Given a (decimal - e.g.3.72) number that is passed in as a string, print the binary representation.If the number can not be represented accurately in binary, print “ERROR” . 

Given an binary integer, we know that 1001 = 1 * 2^ 3 + 0 * 2 ^ 2 + 0 * 2 ^ 1 + 1 * 2^0 = 9. So if we keep doing mod operation and divide the number by 2, we can get the binary representation of the integer.
Analogously, 0.101 = 1 * (1/2)^1 + 0 * (1/2)^2 + 1 * (1/2)^3 = 0.625. Thus if we multiply the number by 2, we get 1 * (1/2)^0 + 0 * (1/2)^1 + 1 * (1/2)^2 = 1.25(10)  = 1.01(2). So if the result is greater than 1, we know that there should be 1 follows "." in the decimal part. We can do the same operation for every digit.


public class DecimalToBinary {
 public String decimalToBinary (String s) {
  if (s == null) 
   throw new NullPointerException("Null string");
  int intPart = Integer.parseInt(s.substring(0, s.indexOf('.')));
  double deciPart = Double.parseDouble(s.substring(s.indexOf('.')));
  
  String rst = "";
  while (intPart > 0) {
   rst = String.valueOf(intPart % 2) + rst;
   intPart >>= 1;
  }
  rst += ".";
  String decim = "";
  while (deciPart > 0) {
   if (decim.length() > 32) {
    return "Error";
   }
   if (deciPart == 1) {
    decim += "1";
    break;
   }
   double d = deciPart * 2;
   if (d >= 1) {
    decim += "1";
    deciPart = d - 1;
   }
   else {
    decim += "0";
    deciPart = d;
   }
  }
  return rst + decim;
 }

}

Next Largest and Smallest number that has the same number of 1 bits

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

Ok, this is interesting. So basically, given a binary number, 11100110, if we want to find the next largest one that has the same number of 1 bits, we first switch the first 0 to 1, which gives us 11101110, then we switch the next 1 after that 0 to 0, and results in 11101010. Since we want the next largest, we would want to  shift all the 1s after that to the most right side, and the result is: 11101001, yep, here is the solution.

The next smallest number is similar. Reversely, we switch the first 1 to 0 and the next 0 to 1. Using another example 110011 would result in 101011, and shifts, and the answer is: 101110.


public class NextBitNumber {
 private int setBit(int n, int index, boolean toOne) {
  int rst;
  if (toOne)
   rst = n | (1 << index);
  else {
   int mask = ~ (1 << index);
   rst = n & mask;
  }
  return rst;
 }
 private boolean getBit(int n, int index) {
  return (n & (1 << index)) > 0;
 }
 public int nextLargest(int n) {
  if (n <= 0)
   return -1;
  int index = 0;
  int countOnes = 0;
  while (!getBit(n, index))
   index++;
  while(getBit(n, index)) {
   index++;
   countOnes++;
  }
  n = setBit(n, index, true);
  index--;
  n = setBit(n, index, false);
  countOnes--;
  index--;
  for (int i = index; i > index - countOnes; i--) 
   n = setBit(n, i, false);
  for (int i = 0; i < countOnes; i++)
   n = setBit(n, i, true);
  return n;
 }
 public int nextSmallest(int n) {
  if (n <= 0)
   return -1;
  int index = 0;
  int countZeros = 0;
  while (getBit(n, index)) {
   index++;
  }
  while (!getBit(n, index)) {
   index++;
   countZeros++;
  }
  n = setBit(n, index, false);
  index--;
  n = setBit(n, index, true);
  index--;
  countZeros--;
  for (int i = index; i > index - countZeros; i--)
   n = setBit(n, i, true);
  for (int i = 0; i < countZeros; i++)
   n = setBit(n, i, false);
  return n;
 }

}

What does (n & (n - 1)) == 0 used for? 

Check if n == 0 or power of 2!
For example, 100 and 11;

Bits needed to convert a number to another number

Write a function to determine the number of bits required to convert integer A to integer B.
Input: 31, 14
Output: 2 

Count the number of different bits in a number by using XOR.


public class BitsNeededToConvert {
 public int bitsNeeded(int a, int b) {
  if (a == b)
   return 0;
  int count = 0;
  for (int c = a ^ b; c >= 0; c = c>> 1) {
   count += c & 1;
  }
  return count;
 }

}


Something about Hexadecimal

In Unix shells, and C programming language:
prefix 0x for numeric constants represented in hex. e.g., 0x5A3 (144310).
Character and string constants may express characters codes in hexadecimal with the prefix \x followed by two hex digits: \x1B (Esc control character)
Unicode standard:
A character value is represented with U+ followed by the hex value, e.g., U+20AC (euro sign)

Convert hexadecimal to binary

Swap odd and even bits in a number

Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

shift all odd bits left for 1 position and shift all even bits right for 1 position

public class SwapBits {
 public int swapBits (int n) {
   //0xaaaaaaaa = 10101010...10
   // 0x55555555 = 1010101...01
   return (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1;
 }
}

Isomorphic Strings

Given two (dictionary) words as Strings, determine if they are isomorphic. Two words are called isomorphic 
if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all 
occurrences of it with another letter while the ordering of the letters remains unchanged. No two letters 
may map to the same letter, but a letter may map to itself. 

Example: 
given "foo", "app"; returns true 
we can map 'f' -> 'a' and 'o' -> 'p' 
given "bar", "foo"; returns false 
we can't map both 'a' and 'r' to 'o' 

given "turtle", "tletur"; returns true 
we can map 't' -> 't', 'u' -> 'l', 'r' -> 'e', 'l' -> 'u', 'e' -'r' 

given "ab", "ca"; returns true 
we can map 'a' -> 'c', 'b'

Click here for the original problem.
I implement two methods, the first one map the character to the first occurred index for both strings, and check if the encodings are the same for both strings. The second one is more traditional, map characters in the first string to the same index one in the second string. However, both methods require two maps.


import java.util.*;
public class IsomorphicString {
 //map index
 public boolean isIsomorphic(String a, String b) {
  if (a.length() != b.length()) 
   return false;
  a = a.toLowerCase();
  b = b.toLowerCase();
  
  Map amap = new HashMap ();
  Map bmap = new HashMap ();
  
  for (int i = 0; i < a.length(); i++) {
   if (!amap.containsKey(a.charAt(i)))
    amap.put(a.charAt(i), i);
   if (!bmap.containsKey(b.charAt(i))) 
    bmap.put(b.charAt(i), i);
  }
  for (int i = 0; i < a.length(); i++) {
   if (amap.get(a.charAt(i)) != bmap.get(b.charAt(i)))
    return false;
  }
  return true;
 }
 //map character
 public boolean isIsomorphic2 (String a, String b) {
  if (a.length() != b.length()) 
   return false;
  a = a.toLowerCase();
  b = b.toLowerCase();
  
  Map amap = new HashMap ();
  Map bmap = new HashMap ();
  
  for (int i = 0; i < a.length(); i++) {
   if (amap.containsKey(a.charAt(i))) {
    if(amap.get(a.charAt(i)) != b.charAt(i))
     return false; 
   }
   if (bmap.containsKey(b.charAt(i))) {
    if (bmap.get(b.charAt(i)) != a.charAt(i))
     return false;
   }
   amap.put(a.charAt(i), b.charAt(i));
   bmap.put(b.charAt(i), a.charAt(i));
  }
  return true;
 }

}

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.

I was thinking about using recursion, then I had some problem dealing with extra zeros in cases such as n = 15...

So, I googled, and here comes my favorite Wikipedia:

The number of trailing zeros in the decimal representation of n!, the factorial of a non-negative integer n, is simply the multiplicity of the prime factor 5 in n!. This can be determined with this special case of de Polignac's formula:[1]
f(n) = \sum_{i=1}^k \left \lfloor \frac{n}{5^i} \right \rfloor =
\left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + \left \lfloor \frac{n}{5^3} \right \rfloor + \cdots + \left \lfloor \frac{n}{5^k} \right \rfloor, \,
where k must be chosen such that
5^{k+1} > n,\,
and \lfloor a \rfloor denotes the floor function applied to a. For n = 0, 1, 2, ... this is
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, ... (sequence A027868 in OEIS).
For example, 53 > 32, and therefore 32! = 263130836933693530167218012160000000 ends in
\left \lfloor \frac{32}{5} \right \rfloor + \left \lfloor \frac{32}{5^2} \right \rfloor = 6 + 1 = 7\,
zeros. If n < 5, the inequality is satisfied by k = 0; in that case the sum is empty, giving the answer 0.
The formula actually counts the number of factors 5 in n!, but since there are at least as many factors 2, this is equivalent to the number of factors 10, each of which gives one more trailing zero.

It is as easy as you can imagine.

Math, ha!

Update: 2015 - 03 - 01


public int trailingZeroes(int n) {
       if (n < 5)
            return 0;
        int zeros = 0;
        int k = 1;
        while (n >= Math.pow(5, k)) {
            zeros += n / Math.pow(5, k);
            k++;
        }
        return zeros;
    }


The reason is that it looses precision after certain positions. The following code will not gives us the correct answer for very large n. Use the above code.
public class TrailingZeros {
    public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        int zeros = 0;
        int five = 5;
        while (n >= five) {
            zeros += n / five;
            five *= 5;
        }
        return zeros;
    }
}


Update: 2015 - 01 -15

I realize that the above code will exceed time limit, but I couldn't figure the reason.


public int trailingZeroes(int n) {
        if (n < 5)
            return 0;
        if (n == 5)
            return 1;
        int k = 0;
        while (Math.pow(5, k) <= n)
            k++;
        k--;
        int zeros = 0;
        while (k > 0) {
            zeros += n / Math.pow(5, k);
            k--;
        }
        return zeros;
    }


Monday, December 29, 2014

Next Character

/** 
* Return the smallest character that is strictly larger than the search character, 
* If no such character exists, return the smallest character in the array 
* @param sortedStr : sorted list of letters, sorted in ascending order. 
* @param c : character for which we are searching. 
* Given the following inputs we expect the corresponding output: 
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c' 
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f' 
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p' 
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case 
* ['c', 'f', 'k'], 'f' => 'k' 
* ['c', 'f', 'k'], 'c' => 'f' 
* ['c', 'f', 'k'], 'd' => 'f' 
*/
Click here for the original problem.
The problem doesn't clarify if duplicates are allowed in the array. So I wrote two.


public class SmallestCharacter {
 public char nextChar(char[] list, char c) {
  if (list == null || list.length == 0)
   throw new IllegalArgumentException("Null or empty list!");
  int start = 0;
  int end = list.length - 1;
  if (c < list[0] || c >= list[list.length - 1])
   return list[0];
  while (start < end) {
   int mid = (start + end) / 2;
   if (c == list[mid]) {
    //System.out.println(mid + ": " + list[mid]);
    return list[mid + 1];
   }
   else if (c < list[mid]) {
    //System.out.println("smaller: " + mid);
    end = mid - 1;
   }
   else {
    //System.out.println("greater: " + mid);
    start = mid + 1;
   }
  }
  if (list[start] == c)
   return list[start + 1];
  return list[start];
 }
}


Duplicates are allowed (not much difference though...)


public char nextChar2(char[] list, char c) {
  if (list == null || list.length == 0)
   throw new IllegalArgumentException("Null or empty list!");
  int start = 0;
  int end = list.length - 1;
  if (c < list[0] || c >= list[list.length - 1])
   return list[0];
  while (start < end) {
   int mid = (start + end) / 2;
   if (c == list[mid]) {
    if (list[mid + 1] > c)
     return list[mid + 1];
    else 
     start = mid + 1;
   }
   else if (c < list[mid]) {
    end = mid - 1;
   }
   else
    start = mid + 1;
  }
  if (list[start] == c)
   return list[start + 1];
  return list[start];
 }

Find all the repeating sub-string sequence

Find all the repeating sub-string sequence of specified length in a large string sequence. The sequences returned i.e. the output must be sorted alphabetically. 

For e.g. 

Input String: "ABCACBABC" 
repeated sub-string length: 3 

Output: ABC 

Input String: "ABCABCA" 
repeated sub-string length: 2 

Output: AB, BC, CA

Click here for the original problem.
Ha, very interesting problem. I was wondering why all the add() methods returns boolean type. Now I  know, since Set doesn't allow duplicate values,  if add() returns false, it means the set fails to add the value, which probably imply there already exists the value. And in this problem, we are utilizing this feature.


import java.util.*;
public class RepeatingSubstring {
 public ArrayList repeatSubstring (String s, int length) {
  if (s == null)
   throw new NullPointerException("Null array");
  ArrayList rst = new ArrayList ();
  if (s.length() == 0)
   return rst;
  HashSet nonRepeating = new HashSet ();
  TreeSet repeating = new TreeSet ();
  for (int i = 0; i + length <= s.length(); i++) {
   if (!nonRepeating.add(s.substring(i, i + length)))
    repeating.add(s.substring(i, i + length));
  }
  rst = new ArrayList (repeating);
  return rst;
 }

}

Sunday, December 28, 2014

Nearest Neighbor on a plane

Fill in the following methods:
public interface PointsOnAPlane {

    /**
     * Stores a given point in an internal data structure
     */
    void addPoint(Point point);

    /**
     * For given 'center' point returns a subset of 'm' stored points that are
     * closer to the center than others.
     *
     * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
     *
     * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3)
     */
    Collection<Point> findNearest(Point center, int m);

}
Click here for the original problem:
The last is always the best. Look how much time I spent on debugging this... -_-|||
This is actually very interesting. It reminds me of the Nearest Neighbor in unsupervised learning.

Anyway, basically I use a priorityQueue to store the m closest points to the center. The comparator compares the the distance between all points and the center. I use an arrayList to store all points added to the class. When calling findNearest() method, the array needs to be sorted. Since the array is sorted, the time complexity is O(nlog(n)).

import java.util.*;
public class Point {
 double x;
 double y;
 
 public Point() {
  this.x = 0.0;
  this.y = 0.0;
 }
 public Point(double x, double y) {
  this.x = x;
  this.y = y;
 }
 public double getX() {
  return x;
 }
 public double getY() {
  return y;
 }
 public boolean equals(Point p) {
  return (this.x == p.x && this.y == p.y);
  
 }
 public double distanceFrom(Point p) {
  return Math.sqrt(Math.pow(p.y - this.y, 2) + Math.pow(p.x - this.x, 2));
 }
 public String toString() {
  return "(" + x + ", " + y + ")";
 }
 
}
public class ThisPointsOnAPlane implements PointsOnAPlane{
 private ArrayList points;
 
 public ThisPointsOnAPlane() {
  points = new ArrayList();
 }
 public void addPoint(Point p) {
  points.add(p);
 }
 
 public PriorityQueue findNearest(Point center, int m) {
  if (center == null)
   throw new NullPointerException("Null center!");
  PointComparator pc = new PointComparator(center);
  PriorityQueue nearestNeighbor = new PriorityQueue (m, pc);
  if (m == 0) {
   nearestNeighbor.add(center);
   return nearestNeighbor;
  }
  Collections.sort(points, pc);
  Point last = null;
  for (Point p : points) {
   if (p.equals(center))
    continue;
   if (nearestNeighbor.size() < m) {
    nearestNeighbor.add(p);
    last = p;
   }
    
   else {
    if (p.distanceFrom(center) < last.distanceFrom(center)) {
     nearestNeighbor.remove(last);
     nearestNeighbor.add(p);
     last = p;
    }
   }
  }
  return nearestNeighbor;
 }
 public String toString () {
  String rst = "{ ";
  for (Point p : points) {
   rst += "(" + p.x + ", " + p.y +"), ";
  }
  rst = rst.substring(0, rst.length() - 2) + " }";
  return rst;
 }
 
 
 private class PointComparator implements Comparator {
  Point center;
  public PointComparator(Point center) {
   this.center = center;
   //System.out.println(center.x + ", " + center.y);
  }
  public int compare(Point a, Point b) {
   if (a.distanceFrom(center) - b.distanceFrom(center) < 0) {
    return -1;
   }
    
   else if (a.distanceFrom(center) - b.distanceFrom(center) > 0) {
    return 1;
   }
    
   return 0;
  }
 }
}
//Test class
public class NNTester {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  ThisPointsOnAPlane tpoap = new ThisPointsOnAPlane();
  tpoap.addPoint(new Point(0, 0));
  tpoap.addPoint(new Point(0, 2));
  tpoap.addPoint(new Point(0, 1));
  tpoap.addPoint(new Point(0, 4));
  tpoap.addPoint(new Point(0, 3));
  tpoap.addPoint(new Point(1, 3));
  tpoap.addPoint(new Point(1, 1));
  tpoap.addPoint(new Point(1, 1));
  Point center = new Point(0, 0);
  int m = 3;
  PriorityQueue nearestNeighbor = tpoap.findNearest(center, m);
  for (int i = 0; i < m; i++) {
   Point p = nearestNeighbor.poll();
   System.out.println("(" + p.x +", " + p.y +")");
  }

 }

}


However, I do see there is a comment saying using Quickselect, we can reduce the time complexity to  O(n). I am gonna think about this tomorrow.

Update about Quick select method. It won't work. First, we need an extra array to store the distances to the center of all points to do quick select. And second, we need a map to store <distance, point> pairs because after swap, the order will not be the same. So even though the the time complexity can reduce to O(n), we need O(2*n) (ah.. if you want to say O(n), is fine) extra space.

And here comes third, which actually fails the method, is that map doesn't allow duplicate key - value pairs. I am not sure if there are other containers that allow me to do that, but so far, I will stick to the priority queue method. Here is the quick select code:




public ArrayList findNearest2 (Point center, int m) {
  if (center == null)
   throw new NullPointerException("Null center!");
  ArrayList rst = new ArrayList ();
  if (m == 0) 
   return rst;
  double[] distance = new double[points.size()];
  HashMap hm = new HashMap();
  for (int i = 0; i < points.size(); i++) {
   distance[i] = points.get(i).distanceFrom(center);
   hm.put(distance[i], points.get(i));
   System.out.println(points.get(i).toString() + ": " + distance[i]);
  }
  quickSelect(distance, 0, distance.length - 1, m + 1);
  for (int i = 0; i <= m; i++) {
   if (distance[i] == 0)
    continue;
   rst.add(hm.get(distance[i]));
  }
  return rst;
 }
 
 private void quickSelect(double[] array, int start, int end, int k) {
  if (start > end)
   return;
  double pivot = array[(start + end) / 2];
  int left = start;
  int right = end;
  while (left < right) {
   if (array[left] >= pivot) {
    swap(array, left, right);
    right--;
   }
   else {
    left++;
   }
  }
  if (array[left] > pivot) 
   left--;
  if (k - 1 == left)
    return;
  else if (k - 1 < left)
   quickSelect(array, start, left - 1, k);
  else
   quickSelect(array, left + 1, end, k);
 }
 private void swap (double[] array, int left, int right) {
  double tmp = array[left];
  array[left] = array[right];
  array[right] = tmp;
 }

Influence Finder

public interface InfluencerFinder { 

/** 
* Given a matrix of following between N LinkedIn users (with ids from 0 to N-1): 
* followingMatrix[i][j] == true iff user i is following user j 
* thus followingMatrix[i][j] doesn't imply followingMatrix[j][i]. 
* Let's also agree that followingMatrix[i][i] == false 

* Influencer is a user who is: 
* - followed by everyone else and 
* - not following anyone himself 

* This method should find an Influencer by a given matrix of following, 
* or return -1 if there is no Influencer in this group. 
*/ 
int getInfluencer(boolean[][] followingMatrix)

Click here for the original problem. 
Probably the most interesting problem I have met today.

If I understand correctly, if there exists an influencer in a matrix, it should be like this: 


The desired method should return 1 as the influencer. Moreover, since the influencer is followed by everyone yet is not following anyone (arrogant guy), there exists only one influencer in a given matrix. 

So, here comes my code. Technically, it's O(n^2). I first check if a person is following herself, which immediately excludes her from the candidate list. Then I check rows and columns simultaneously, if the candidate is so into another person and follows him or her, she is out, or if this guy is not popular enough that everyone wants to follow him, he is out. So, after trimmed lots of unnecessary loops, the solution should be better than O(n^2). 

However, I am still looking for better solution... 


public class InfluenceFinder {
 public int getInfluencer (boolean[][] followingMatrix) {
  if (followingMatrix == null) 
   throw new NullPointerException ("Null matrix? Are you kidding me?"); //This is a joke...
  if (followingMatrix.length == 0) 
   return -1;
  boolean isInfluencer = true;
  for (int cand = 0; cand < followingMatrix.length; cand++) {
   if (followingMatrix[cand][cand] == true) {
    continue;
   }
   for (int i = 0; i < followingMatrix.length; i++) {
    if (i == cand)
     continue;
    if (followingMatrix[i][cand] == false || followingMatrix[cand][i] == true) {
     isInfluencer = false;
     break;
    }
   }
   if (isInfluencer)
    return cand;
   isInfluencer = true; 
  }
  return -1;   
 }

}

Self Excluding Product

/**
 * Implement a method which takes an integer array and returns an integer array (of equal size) in
 * which each element is the product of every number in the input array with the exception of the
 * number at that index.
 *
 * Example:
 *   [3, 1, 4, 2] => [8, 24, 6, 12]
 */
public int[] selfExcludingProduct(int[] input) {
    // implementation...
}
Click here for original problem.


Update 2016-10-05

A neater solution. Go through the array twice. First time get the product of all numbers previous to current number, second time get products after current number.


    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] rst = new int[len];
        if (len == 0) {
            return rst;
        }
        rst[0] = 1;
        for (int i = 1; i < len; i++) {
            rst[i] = rst[i - 1] * nums[i - 1];
        }
        int p = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rst[i] *= p;
            p *= nums[i];
        }
        return rst;
    }


public class SelfExcludingProduct {
 public int[] selfExcludingProduct (int[] input) {
  if (input == null) 
   throw new NullPointerException ("Null input array!");
  int[] productArray = new int[input.length];
  if (input.length == 0) 
   return productArray;
  int product = 1;
  int numOfZeros = 0;
  for (int i = 0; i < input.length; i++) {
   if (input[i] != 0)
    product *= input[i];
   else
    numOfZeros++;
   if (numOfZeros >= 2) {
    return productArray;
   }
  }
  for (int i = 0; i < input.length; i++) {
   if (numOfZeros == 0) {
    productArray[i] = product / input[i];
   }
   else {
    if (input[i] == 0) 
     productArray[i] = product;
    else
     productArray[i] = 0;
   }
    
  }
  
  return productArray;
   
 }

}

Word wrap / Text Justification

Word Wrap / String Justification algorithm. 
Given a set of words and a length. 
You are required to print the words such that the words on each line end almost on the same column and the number of trailing spaces at the end is minimized. 


Given aaa bb cc ddddd and length is 5 print the following output. 



aaa 
bb cc 
ddddd

Click here for the original problem. 
This one is similar to LeetCode's Text Justification. Apparently the question is not clear, the length of each line should be 5, but there is one space after "bb" and one space after "cc", which makes the total length of that line 6. I am not sure if there should be no space between "bb" and "cc" or no space after "cc". The common sense tells me there should be one space between two strings and based on "the number of trailing spaces at the end is minimized", I go with the second way.

In case the guy who posted this problem remembers the question wrong and this should be the same as the Text Justification. I include that code as well. 

Text Justification


public class Solution {
    public ArrayList fullJustify(String[] words, int L) {
        if (words == null)
            throw new NullPointerException("Null string array!");
        ArrayList rst = new ArrayList ();
        if (words.length == 0)
            return rst;
        int maxLength = words[0].length();
        for (int i = 0; i < words.length; i++) {
            maxLength = Math.max(maxLength, words[i].length()); 
        }
        if (maxLength > L)
            return rst;
            
        int prev_start = 0;
        int currSum = 0;
        int countWord = 0;
        for (int i = 0; i <= words.length; i++) {
            if (i == words.length || (currSum + words[i].length() + countWord > L)) {
                int totalSpace = L - currSum;
                String tmp = "";
                if (i == words.length || countWord == 1) {
                    for (int j = prev_start; j < i; j++) {
                        tmp += words[j];
                        if (j != i - 1)
                            tmp += " ";
                    }
                    tmp = appendSpace(tmp, L - tmp.length());
                }
                else {
                    int spaceEachWord = totalSpace / (countWord - 1);
                    int extraSpace = totalSpace % (countWord - 1);
                    for (int j = prev_start; j < i - 1; j++) {
                        tmp += words[j];
                        if (j != i - 1) {
                            tmp = appendSpace(tmp, spaceEachWord);
                            }
                        
                        if (extraSpace > 0) {
                            tmp += " ";
                            extraSpace--;
                        }
                    }
                    tmp += words[i - 1];
                }
                rst.add(tmp);
                if (i == words.length)
                    break;
                prev_start = i;
                currSum = words[i].length();
                countWord = 1;
            }
            else {
            currSum += words[i].length();
            countWord++;
            }
        }
        return rst;
        
    }
    private String appendSpace(String s, int space) {
        String rst = s;
        for (int i = 0; i < space; i++)
            rst += " ";
        return rst;
    }
}


Word Wrap


import java.util.ArrayList;


public class TextJustification {
 public ArrayList fullJustify(String[] words, int L) {
        if (words == null)
            throw new NullPointerException("Null string array!");
        ArrayList rst = new ArrayList ();
        if (words.length == 0)
            return rst;
        int maxLength = words[0].length();
        for (int i = 0; i < words.length; i++) {
            maxLength = Math.max(maxLength, words[i].length()); 
        }
        if (maxLength > L)
            return rst;
            
        int prev_start = 0;
        int currSum = 0;
        int countWord = 0;
        for (int i = 0; i <= words.length; i++) {
            if (i == words.length || (currSum + words[i].length() + countWord > L)) {
                int totalSpace = L - currSum;
                String tmp = "";
                if (i == words.length || countWord == 1) {
                    for (int j = prev_start; j < i; j++) {
                        tmp += words[j];
                        if (j != i - 1)
                            tmp += " ";
                    }
                    tmp = appendSpace(tmp, L - tmp.length());
                }
                else {
                    int spaceEachWord = totalSpace / (countWord - 1);
                    int extraSpace = totalSpace % (countWord - 1);
                    for (int j = prev_start; j < i - 1; j++) {
                        tmp += words[j];
                        if (j != i - 1) {
                            tmp = appendSpace(tmp, spaceEachWord);
                            }
                        
                        if (extraSpace > 0) {
                            tmp += " ";
                            extraSpace--;
                        }
                    }
                    tmp += words[i - 1];
                }
                rst.add(tmp);
                if (i == words.length)
                    break;
                prev_start = i;
                currSum = words[i].length();
                countWord = 1;
            }
            else {
            currSum += words[i].length();
            countWord++;
            }
        }
        return rst;
        
    }
    private String appendSpace(String s, int space) {
        String rst = s;
        for (int i = 0; i < space; i++)
            rst += " ";
        return rst;
    }

}

Find range of a target number

Given a sorted array with duplicates and a number, find the range in the 
form of (startIndex, endIndex) of that number. For example, 

find_range({0 2 3 3 3 10 10}, 3) should return (2,4). 
find_range({0 2 3 3 3 10 10}, 6) should return (-1,-1). 
The array and the number of duplicates can be large.

Click here for the original problem.
Now that I realize when dealing with searching problem, I should try to get an O(log(n)) solution. Yeah, binary search.


public class FindRange {
 public int[] findBound(int[] num, int target) {
  if (num == null)
   throw new NullPointerException("Null array");
  int[] bound = {-1, -1};
  if (num.length == 0)
   return bound;
  findRange(0, num.length - 1, bound, num, target);
  return bound;
  
 }
 private void findRange(int start, int end, int[] bound, int[] num, int target) {
  if (start > end)
   return;
  int mid = (start + end) / 2;
  if (num[mid] == target) {
   if (start == mid || num[mid - 1] != num[mid]) {
    if (bound[0] == -1 || mid < bound[0])
     bound[0] = mid;
   }
    
   else {
    findRange(start, mid - 1, bound, num, target);
   }
   if (end == mid || num[mid + 1] != num[mid]) {
    if (mid > bound[1])
     bound[1] = mid;
   }
   else {
    findRange(mid + 1, end, bound, num, target);
   }
  }
  else if (num[mid] < target)
   findRange(mid + 1, end, bound, num, target);
  else
   findRange(start, mid - 1, bound, num, target);
 }

}

Find Range

Given a list of tuples representing intervals, return the range these intervals 
covered. 
e.g: 
[(1,3), (2,5),(8,9)] should return 5

Click here for original question.
I am not a big fan to use fancy containers for problems like this. To me, the primary goal is to reduce time complexity to <= O(n) if possible and maintain constant space complexity. The only reason to use containers is to reduce the time complexity, which is at the expense of space complexity.

Here is an O(n) solution with nothing, just a single loop.



import java.util.*;
public class FindRange {
 public int findRange (ArrayList intervals) {
  if (intervals == null)
   throw new NullPointerException();
  if (intervals.size() == 0)
   return 0;
  Collections.sort(intervals, new IntervalComparator());
  int min_start = intervals.get(0).start;
  int max_end = intervals.get(0).end;
  int range = 0;
  int index = 1;
  while (index <= intervals.size()) {
   if (index == intervals.size()) {
    range += (max_end - min_start);
    break;
   }
   if (intervals.get(index).start <= max_end) {
    max_end = Math.max(max_end, intervals.get(index).end);
    index++;
    continue;
   }
   range += (max_end - min_start);
   min_start = intervals.get(index).start;
   max_end = intervals.get(index).end;
   //index++;
  }
  return range;
  
 }
 
 private class IntervalComparator implements Comparator {
  public int compare(Interval a, Interval b) {
   return a.start - b.start;
  }
 }

}
public class Interval {
  int start;
  int end;
 public Interval() {
  this.start = Integer.MIN_VALUE;
  this.end = Integer.MAX_VALUE;
 }
 public Interval(int start, int end) {
  this.start = start;
  this.end = end;
  if (!isValid()) 
   throw new IllegalArgumentException("invalid input!");
 }
 private boolean isValid() {
  return start <= end;
 }

}

Saturday, December 27, 2014

First Common Ancestor

public interface FirstCommonAncestor { 

/** 
* Given two nodes of a tree, 
* method should return the deepest common ancestor of those nodes. 

* A 
* / \ 
* B C 
* / \ \ 
* D E M 
* / \ 
* G F 

* commonAncestor(D, F) = B 
* commonAncestor(C, G) = A 
*/ 

public Node commonAncestor(Node nodeOne, Node nodeTwo) 





class Node { 

final Node parent; 
final Node left; 
final Node right; 
final data;

public Node(Node parent, Node left, Node right, data) { 
this.parent = parent; 
this.left = left; 
this.right = right; 
this.data = data 


boolean isRoot() { 
return parent == null; 

}

Using a, actually two stacks to store the node while traversing the tree from each node to the root. After that, pop the node and check if the next node in both stacks are equal (stackOne.peek() == stackTwo.peek()), if not, or if one of the stacks is empty, which means the last node in the empty stack is an ancestor/parent of the other stack, return the node.

My code doesn't specifically "implement" the interface for the sake of testing, but the algorithm is the same.



import java.util.*;
public class FirstCommonAncestor {
 public Node commonAncestor(Node nodeOne, Node nodeTwo) {
  if (nodeOne == nodeTwo)
   return nodeOne.parent;
  Stack stackOne = new Stack ();
  Stack stackTwo = new Stack ();
  Node one = nodeOne;
  Node two = nodeTwo;
  while(one != null && two != null) {
   stackOne.push(one);
   stackTwo.push(two);
   one = one.parent;
   two = two.parent;
  }
  while (one != null) {
   stackOne.push(one);
   one = one.parent;
  }
  while (two != null) {
   stackTwo.push(two);
   two = two.parent;
  }
  while(!stackOne.isEmpty() && !stackTwo.isEmpty()) {
   Node head1 = stackOne.pop();
   stackTwo.pop();
   if ((stackOne.isEmpty() || stackTwo.isEmpty()) || stackOne.peek() != stackTwo.peek()) {
    return head1;
   }
  }
   
  return null;
 }
}
public class Node {
 Node parent; 
 Node left; 
    Node right; 
    Object data;

 public Node(Object data) {
  this.parent = null;
  this.left = null;
  this.right = null;
  this.data = data;
 }

 public Node(Node parent, Node left, Node right, Object data) { 
  this.parent = parent; 
  this.left = left; 
  this.right = right; 
  this.data = data; 
  } 

 boolean isRoot() { 
  return parent == null; 
 } 

}

Find minimum distance between words

/* This class will be given a list of words (such as might be tokenized
 * from a paragraph of text), and will provide a method that takes two
 * words and returns the shortest distance (in words) between those two
 * words in the provided text. 
 * Example:
 *   WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
 *   assert(finder.distance("fox","the") == 3);
 *   assert(finder.distance("quick", "fox") == 1);
 * /

Click here for the original question.
O(n) complexity and O(1) space complexity.




public class DistanceFinder {
 public int WordDistance(String[] words, String word1, String word2) {
  if (words == null || word1 == null || word2 == null) 
   throw new NullPointerException("Null array or words");
  if (words.length == 0)
   return Integer.MAX_VALUE;
  if (word1.equals(word2))
   return 0;
  int index1 = -1;
  int index2 = -1;
  int minDistance = Integer.MAX_VALUE;
  for (int i = 0; i < words.length; i++) {
   if (words[i] == word1) {
    index1 = i;
   }
   if (words[i] == word2) {
    index2 = i;
   }
   if ((words[i] == word1 || words[i] == word2) && (index1 != -1 && index2 != -1)) {
    minDistance = Math.min(minDistance, Math.abs(index1 - index2));
   }
  }
  if (index1 == -1 && index2 == -1)
   throw new IllegalArgumentException ("Cannot find the word!");
  return minDistance; 
 }

}

Generate all permutations

Given a string array ex: [1, 2, 3], find the permutation in best time.

Implement Next Permutation method.
Because we are doing in place permutation, be careful when pass to the result list.


import java.util.*; 
import org.apache.commons.lang3.ArrayUtils;
public class Permutation {
 public ArrayList generatePermutation (String[] array) {
  ArrayList rst = new ArrayList ();
  if (array == null)
   throw new NullPointerException("Null array!");
  if (array.length == 0)
   return rst;
  //I don't like to modify the original array;
  String[] input = new String[array.length];
  System.arraycopy(array, 0, input, 0, array.length);
  Arrays.sort(input);
  rst.add(ArrayUtils.addAll(input));
  while (nextPermutation(input)){
   /* if you don't want to use external library, 
    * change nextPermutation() return type to String[] and do arraycoppy
    * String[] output = new String[input.length];
    * System.arraycopy(input, 0, output, 0, input.length);
    * rst.add(output);*/
   rst.add(ArrayUtils.addAll(input));
   
  };
  return rst;
  
 }
 private boolean nextPermutation(String[] array) {
  int index = array.length - 1;
  while (array[index - 1].compareTo (array[index]) >= 0) {
   index--;
   if (index <= 0)
    return false;
  }
  int pivot = index - 1;
  index = array.length - 1;
  while (index > pivot && array[index].compareTo (array[pivot]) <= 0) {
   index--;
  }
  swap(array, pivot, index);
  reverse(array, pivot + 1, array.length - 1);
  return true;
 }
 private void swap(String[] array, int i, int j) {
  String tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
 }
 private void reverse (String[] array, int start, int end) {
  for (int i = start, j = end; i < j; i++, j--) {
   swap(array, i, j);
  }
 }

}



Friday, December 26, 2014

Find Common Characters

Write a program that gives count of common characters presented in an array of strings..(or array of character arrays) 

For eg.. for the following input strings.. 

aghkafgklt 
dfghako 
qwemnaarkf 

The output should be 3. because the characters a, f and k are present in all 3 strings. 

Note: The input strings contains only lower case alphabets

Another Linkedin question. There are various of solutions on Careercup. Overall, the idea is the same: count the existence of each character in each string, if the count equals the length of the input string array, then the character exists in all strings.

I really like one solution using bitset, but there is one comment saying "it doesn't work if there are more than 32 input strings". I tested it, the commenter was correct. And considering all the corner cases I need to take care of, I am using my favorite method: A hash map (I am so in to hash map may be only because my friend said he failed a data scientist because she didn't know how to use a hash map...)!

My solution is based on the same idea as all other solutions. The map size is the number of unique characters in the first string in the array. Because we have to go through the array and check every string, the time complexity is O(mn), where m is the average string length in the array and n is the array length. I don't think we can beat this complexity, can we?
BTW, my solutions works when the array length is 36...



public class CommonCharacters {
 public int getNumOfCommonChars(String[] inputs) {
  if (inputs == null || inputs.length < 2)
   return 0;
  HashMap hm = new HashMap();
  
  for (int i = 0; i < inputs[0].length(); i++) {
   if (hm.containsKey(inputs[0].charAt(i)))
    continue;
   else
    hm.put(inputs[0].charAt(i), 1);
  }
  for (int i = 1; i < inputs.length; i++) {
   String tmp = inputs[i];
   for (int j = 0; j < tmp.length(); j++) {
    if (!hm.containsKey(tmp.charAt(j)))
     continue;
    if (hm.get(tmp.charAt(j)) == i + 1) 
     continue;
    hm.put(tmp.charAt(j), hm.get(tmp.charAt(j)) + 1);
   }
  }
  int count = 0;
  for (Integer ele : hm.values()) {
   if (ele == inputs.length){
    count++;
   } 
  }
  return count;
 }
}