Long night or lone night

I finished things earlier, or not, I just need to find something to do before I finish my wine. My life is a mess, research, paper, jobs, interviews, smiles, tears, everything can happen in one single day. I feel sorry to those who care about me, who ask if I am ok, and, parents. Right, I haven't called them for a while, and I let them figure out visa and everything by themselves.

Somehow I am just looking for peace, being with someone I really like, do something I really like (write some code, debug, solve some hard but interesting problems, whatever), but I don't know, I have hope in one day, but feel desperation in the other, like a roller coaster, so much fun. Matt said, you will get a good job, you just want that particular one. Probably true, I waste five years doing something I don't care, only because I wasn't mature enough to figure out what I want, now I am paying the price. I don't want to, and can't afford to waste another couple years, life is short.

I am thinking of some one, or ones, they like me, they don't like me, or whatever. It is hard to overcome those guilty feelings, or put your dignity aside (yeah, why do I need that now? ),  but everything is about "doing the right thing". Or maybe I am just making the excuse, I am selfish.

People say what they want to say, and assume the counterpart doesn't know, that makes them feel smart, probably it's better not to say anything, and let the counterpart assume what he or she assumes.

Words are wind, you need it, and you don't need it.

Good night.

Determine if two line segments intersect

Write a function to tell if two line segments intersect or not

This is a very interesting geometry problem. To solve this problem, first let's consider several cases:

Intersect, not parallel

Intersect, parallel

Intersect, q lies on rs

Not intersect, not parallel

Not intersect, parallel

So, the problem becomes :
1. determine if any end point on one lines lies on the other line, if there is one, then of course two lines intersect
2. determine if two lines are parallel

For the second problem, we need to introduce a new notion: orientation. Orientation of an ordered triplet of point on a plane can be:

• clockwise;
• counterclockwise;
• parallel

Figure source: http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

Two lines intersect if one of these conditions are satisfied:

1. (p, q, r) and (p, q, s) have different orientations AND (r, s, p) and (r, s, q) have different orientations;

Different orientation, intersect

Same orientation, not intersect

Determine the orientation, we need to use a little bit our high school or college math: cross product.

 Ok, now the problem becomes very clear. 

/**
  * check if two line segments pq and rs intersect with each other
  * @param p
  * @param q
  * @param r
  * @param s
  * @return
  */
 public static boolean hasIntersection(Point p, Point q, Point r, Point s) {
  if (p == null || q == null || r == null || s == null)
   throw new NullPointerException("Null points!");
  if (p.equals(q) || r.equals(s))
   throw new IllegalArgumentException("Not a line!");
  int ori1 = orientation(p, q, r);
  int ori2 = orientation(p, q, s);
  int ori3 = orientation(r, s, p);
  int ori4 = orientation(r, s, q);
  if (ori1 != ori2 && ori3 != ori4)
   return true;
  if (ori1 == 0 && isOnSegment(p, q, r))
   return true;
  if (ori2 == 0 && isOnSegment(p, q, s))
   return true;
  if (ori3 == 0 && isOnSegment(r, s, p))
   return true;
  if (ori4 == 0 && isOnSegment(r, s, q))
   return true;
  return false;
 }
 /**
  * check if point r is on line segment pq
  * @param p
  * @param q
  * @param r
  */
 private static boolean isOnSegment(Point p, Point q, Point r) {
  return r.x <= Math.max(p.x, q.x) && r.x >= Math.min(p.x, q.x) 
    && r.y <= Math.max(p.y, q.y) && r.y >= Math.min(p.y, q.y);
 }
 /**
  * return the orientation of the triplet
  * 0: parallel
  * 1: clockwise
  * 2: counterclockwise
  * cross product
  * http://en.wikipedia.org/wiki/Cross_product
  * pq & pr
  * @param p
  * @param q
  * @param r
  * @return
  */
 private static int orientation(Point p, Point q, Point r) {
  double orientation = (p.x - q.x) * (p.y - r.y) - (p.y - q.y) * (p.x - r.x);
  if (orientation == 0)
   return 0;
  return orientation > 0 ? 1 : 2;
 }

Repeated DNA Sequences

The tricky part of this problem is that we cannot simply use a set to store or substrings: it will exceed memory limit. A smarter way is to use integers instead of strings. I use the rolling hash method, which is also used in the implement strStr() problem (see that problem for detail).

public class RepeatedDNA {
    private static final Map dna = new HashMap ();
    static {
        dna.put('A', 0);
        dna.put('C', 1);
        dna.put('G', 2);
        dna.put('T', 3);
    }
    private final int base = 29;
    public List findRepeatedDnaSequences(String s) {
        if (s == null)
            throw new NullPointerException("Null String!");
        //avoid duplicate sequence
        List rst = new ArrayList ();
        if (s.length() == 0)
            return rst;
        Set sequence = new HashSet ();
        long hashS = 0;
        for (int i = 0; i  < s.length(); i++) {
            if (i > 9) {
                hashS -= (long)Math.pow(base, 9) * dna.get(s.charAt(i - 10));
            }
            hashS = hashS * base + dna.get(s.charAt(i));
            if (i > 8 && !sequence.add(hashS)) {
                if (!rst.contains(s.substring(i - 9, i + 1)))
                    rst.add(s.substring(i - 9, i + 1));
            }
                
        }
        return rst;
    }
}

Implement queue with stack

This is a brilliant question with a brilliant answer: use two stacks!

public class Queue {
 private Stack in;
 private Stack out;
 public Queue () {
  in = new Stack();
  out = new Stack ();
 }
 public void add(E ele) {
  in.push(ele);
 }
 public E poll() {
  if (out.isEmpty()) {
   while (!in.isEmpty())
    out.push(in.pop());
  }
  if (out.isEmpty())
   throw new NullPointerException("No element left!");
  return out.pop();
 }

 public static void main(String[] args) {
  Queue q = new Queue();
  q.add(1);
  q.add(2);
  q.add(3);
  System.out.println(q.poll());
  q.add(4);
  System.out.println(q.poll());
  System.out.println(q.poll());
  q.add(5);
  System.out.println(q.poll());
  q.add(6);
  System.out.println(q.poll());
  System.out.println(q.poll());
  //System.out.println(q.poll());
 }

}

implement atof()

It is a little bit different from Java's parseFloat:

The function first discards as many whitespace characters (as in isspace) as necessary until the first non-whitespace character is found. Then, starting from this character, takes as many characters as possible that are valid following a syntax resembling that of floating point literals (see below), and interprets them as a numerical value. The rest of the string after the last valid character is ignored and has no effect on the behavior of this function.

If you are not sure about if a number is valid, open your Microsoft Excel and try it. :)

https://github.com/shirleyyoung0812/Facebook/blob/master/src/facebookCoding/Atof.java

public class Atof {
 public static float atof(String in) throws NumberFormatException{
  if (in == null)
   throw new NumberFormatException("Null String!");
  boolean isNegative = false;
  in = in.trim();
  if (in.length() == 0)
   throw new NumberFormatException("Empty string!");
 
  if (in.charAt(0) == '+' || in.charAt(0) == '-') {
   if (in.charAt(0) == '-')
    isNegative = true;
   in = in.substring(1);
  }
  //case that input is "NaN"
  if (in.charAt(0) == 'N') {
   char[] nan = {'N', 'a', 'N'};
   if (in.length() != nan.length)
    return 0.0f;
   for (int i = 0; i < nan.length; i++) {
    if (in.charAt(i) != nan[i])
     return 0.0f;
   }
   return (float)(Double.NaN);
  }
  //case that input is "infinity"
  if (in.charAt(0) == 'I') {
   char[] infinity = {'I', 'n', 'f', 'i', 'n', 'i', 't', 'y' };
   if (in.length() != infinity.length)
    return 0.0f;
   for (int i = 0; i < infinity.length; i++) {
    if (in.charAt(i) != infinity[i])
     return 0.0f;
   }
   return isNegative ? (float)(Double.NEGATIVE_INFINITY) : (float)(Double.POSITIVE_INFINITY);
  }
 
  //Discard leading zeros
  int indexZ = 0;
  while (indexZ < in.length() && in.charAt(indexZ) == '0') {
   indexZ++;
  }
  //System.out.println(indexZ);
  in = in.substring(indexZ);
  if (in.length() == 0)
   return 0.0f;
  //discard trailing non-digit characters, invalid if 'e' is the last character
  int notDigit = in.length() - 1;
  while (notDigit > 0 && in.charAt(notDigit)  != '.' && !Character.isDigit(in.charAt(notDigit))) {
   notDigit--;
  }
  if (notDigit == 0)
   return 0.0f;
  in = in.substring(0, notDigit + 1);
  //System.out.println("Before parsing: " + in);
  boolean dot = false;
  boolean exp = false;
  int expSignPos = -1;
  boolean isExpNegative = false;
  int dotPos = 0;
  int expPos = 0;
  //check if the string is valid, if any invalid character occurs, parse the valid prefix string
  for (int i = 0; i < in.length(); i++) {
   //System.out.println(in.charAt(i));
   if (Character.isDigit(in.charAt(i)))
    continue;
   //. must be before e
   else if (in.charAt(i) == '.') {
    if (exp || dot) {
     if (in.charAt(i - 1) == 'e' || in.charAt(i - 1) == 'E') {
      exp = false;
      in = in.substring(0, i - 1);
     }
     else
      in = in.substring(0, i);
     break;
    }
    dot = true;
    dotPos = i;
    //System.out.println("dotPos: " + dotPos);
   }
   else if (in.charAt(i) == 'e' || in.charAt(i) == 'E') {
    //e cannot be at the first position
    if (i == 0)
     return 0.0f;
    if (exp) {
     in = in.substring(0, i);
     break;
    }
    expPos = i;
    exp = true;
   }
   else if (in.charAt(i) == '+' || in.charAt(i) == '-') {
    if (i == 0 || (in.charAt(i - 1) != 'e' && in.charAt(i - 1) != 'E')) {
     in = in.substring(0, i);
     break;
    }
    if (in.charAt(i) == '-')
     isExpNegative = true;
    expSignPos = i;
   }
   else {
    in = in.substring(0, i);
    break;
   }
  }
  if (in.length() == 0 || in.equals("."))
   return 0.0f;
  float rst = 0.0f;
  if (dot) {
   if (!exp) {
    rst = parseDot(in, dotPos);
   }
   else {
    rst = parseDot(in.substring(0, expPos), dotPos);
    rst = parseExp(rst, in, expPos, expSignPos, isExpNegative);
   }
  }
  else if (exp) {
   float b4exp = (float)Integer.parseInt(in.substring(0, expPos));
   rst = parseExp(b4exp, in, expPos, expSignPos, isExpNegative);
  }
  else {
   rst = (float)Integer.parseInt(in);
  }
  return isNegative ? -rst : rst;
  
 }
 private static float parseDot(String in, int dotPos) {
  float rst;
  int b4dot = 0;
  if (dotPos != 0)
   b4dot = Integer.parseInt(in.substring(0, dotPos));
  if (dotPos == in.length() - 1)
   return (float)b4dot;
  float aftdot = (float)Integer.parseInt(in.substring(dotPos + 1));
  int pos = in.length() - dotPos - 1;
  while (pos > 0) {
   aftdot /= 10;
   pos--;
  }
  rst = (float)b4dot + aftdot;
  return rst;
  }
 private static float parseExp(float rst, String in, int expPos, int expSignPos, boolean isExpNegative) {
  //System.out.println(expPos);
  int pos = 0;
  if (expSignPos != -1) {
   pos = isExpNegative ? (-Integer.parseInt(in.substring(expSignPos + 1))) :
    (Integer.parseInt(in.substring(expSignPos + 1)));
  }
  else 
   pos = Integer.parseInt(in.substring(expPos + 1));
  if (pos < 0) {
   while (pos < 0) {
    rst /= 10;
    pos++;
   }
  }
  else if (pos > 0) {
   while (pos > 0) {
    rst *= 10;
    pos--;
    if ((long)rst >= (Long.MAX_VALUE / 10))
     return (float)Double.POSITIVE_INFINITY;
   }
  }
  return rst;
 }
 public static void main(String[] args) {
  System.out.println(atof("3.14f"));
  System.out.println(atof("3.14e+03"));
  System.out.println(atof("000314.5e-02dfgf"));
  System.out.println(atof("45346gfbfd.4"));
  System.out.println(atof("5643..23"));
  System.out.println(atof("5643.e03"));
  System.out.println(atof("5241e.03"));
  System.out.println(atof("09590004e.05"));
  System.out.println(atof("--4343"));
  System.out.println(atof("6v4v"));
  System.out.println(atof("-v6"));
  System.out.println(atof("+3.5e-2"));
  System.out.println(atof(".03e1"));
  System.out.println(atof("1e1"));
  System.out.println(atof("0.0"));
  System.out.println(atof("10E5"));
  

 }

}

Arrange words

"Given a file with 3-letter words, print all 3x3 with each row, column and diagonal
being one of the words from given file"

I stole the idea from Stackflow,  but implemented it using Java. Basically, create two new dictionaries, the first one store all first prefix of all words in the dictionary (singleL), and the second one store all first and second prefixes of all words(doubleL). Since all words in the matrix are words in the dictionary, there must be words that share same prefixes, thus maps are used for these two new dictionaries.

1. Choose a word X from the dictionary, if any character (X1, X2, X3) is not in the singleL, select another word. 
2. Choose the second word Y from the dictionary, if any string([X1, Y1], [X2, Y2], [X3, Y3], [X1, Y2], [X3, Y2] (diagonal)) is not in the doubleL, select another word. If all words have been visited, go back to 1. 
3. Choose the third word Z from the dictionary, if any word([X1, Y1, Z1], [X2, Y2, Z2], [X3, Y3, Z3], [X1, Y2, Z3], [X3, Y2, Z1]) is not in the dictionary, select another word. If all words have been visited, go back to 2.

The following code assumes there is only one such arrangement exists.

import java.util.*;
public class ArrangingWords {
 public static List arrangeWords(Set dicts) {
  if (dicts == null || dicts.size() == 0)
   throw new IllegalArgumentException("Invalid input!");
  Map singleL = new HashMap ();
  Map doubleL = new HashMap ();
  for (String s : dicts) {
   if (!singleL.containsKey(s.substring(0, 1)))
    singleL.put(s.substring(0, 1), 1);
   else
    singleL.put(s.substring(0, 1), singleL.get(s.substring(0, 1)) + 1);
   if (!doubleL.containsKey(s.substring(0, 2))) 
    doubleL.put(s.substring(0, 2), 1);
   else
    doubleL.put(s.substring(0, 2), doubleL.get(s.substring(0, 2)) + 1);
  }
  Map words = new HashMap ();
  List rst = new ArrayList ();
  boolean found = false;
  for (String s1 : dicts) {
   for (int i = 0; i < 3; i++) {
    String tmp = s1.substring(i, i + 1);
    if (!isValid(tmp, words, singleL))
     continue;
   }
   rst.add(s1);
   for (String s2 : dicts) {
    if (s2.equals(s1))
     continue;
    for (int i = 0; i < 3; i++) {
     String tmp = s1.substring(i, i + 1) + s2.substring(i, i + 1);
     if (!isValid(tmp, words, doubleL))
      continue;
    }
    String d1 = s1.substring(0, 1) + s2.substring(1, 2);
    if (!isValid(d1, words, doubleL))
     continue;
    String d2 = s1.substring(2, 3) + s2.substring(1, 2);
    if (!isValid(d2, words, doubleL))
     continue;
    rst.add(s2);
    for (String s3 : dicts) {
     if (s3.equals(s1) || s3.equals(s2))
      continue;
     for (int i = 0; i < 3; i++) {
      String tmp = s1.substring(i, i + 1) + s2.substring(i, i + 1) + s3.substring(i, i + 1);
      if (!dicts.contains(tmp))
       continue;
     }
     String dia1 = s1.substring(0, 1) + s2.substring(1, 2) + s3.substring(2, 3);
     String dia2 = s1.substring(2, 3) + s2.substring(1, 2) + s3.substring(0, 1);
     if (!dicts.contains(dia1) || !dicts.contains(dia2))
      continue;
     found = true;
     rst.add(s3);
     break;
    }
    if (found)
     break;
    rst.remove(s2);
   }
   if (found)
    break;
   rst.remove(s1);
  }
  if (rst.size() < 3)
   return new ArrayList ();
  return rst;
 }
 private static boolean isValid(String word, Map words, Map prefixes) {
  if (!prefixes.containsKey(word))
   return false;
  if (!words.containsKey(word))
   words.put(word, 1);
  else
   words.put(word, words.get(word) + 1);
  if (words.get(word) > prefixes.get(word))
   return false;
  return true;
 }
 

 public static void main(String[] args) {
  Set dicts = new HashSet ();
  dicts.add("abc");
  dicts.add("def");
  dicts.add("ghi");
  dicts.add("adg");
  dicts.add("beh");
  dicts.add("cfi");
  dicts.add("aei");
  dicts.add("ceg");
  dicts.add("acg");
  dicts.add("dgh");
  dicts.add("iok");
  dicts.add("pkm");
  for (String s : arrangeWords(dicts)) {
   System.out.println(s);
  }

 }

}

Find the interval that intersects with most intervals in a list of intervals

 Giving lots of intervals [ai, bi], find the interval (point) which intersects with the most number of intervals

 This is an interesting problem. The start point of the interval that intersects with the most number of intervals must be a start point of some interval in the list and the end point of it must be an end point of an interval in the list.

An interval

A point

So, the algorithm goes as follows: 

1. Sort the start and end points of all intervals in the list, this require an array or a list of 2 * size of the interval list. 

2. Go through the array/list of the start and end points, if we meet a start, increment count, if we meet an end, decrement the count. Why? Each time we encounter a start point, we have one more intersection, and each time we meet an end point, we lose an intersection, thus the position with the maximum count is the start point of the interval with the most intersections and the next position is the end point of it. 

Note the overlapping of the start and end point will not affect the count, since each start and end point will have a different index in the array.