dynamic_cast vs static_cast

In c++, it's legal to assign a derived class object to a base class object. This is because the relation of inheritance is "is-a". Derived class object is a base class object as well. Of course, doing so may cause object slicing. Assume we have BaseClass and DerivedClass defined like this.

class BaseClass{
    int x;
};

class DerivedClass : public BaseClass {
    int y;
};

Here are some examples of valid and invalid operations.

DerivedClass derived_class;
BaseClass& base_class = derived_class; // Valid operation
cout<<base_class.x; // Valid operation
cout<<base_class.y; // Invalid, y belongs to DerivedClass and is sliced off
DerivedClass new_derived_class = base_class; // Invalid 1)
DerivedClass& new_derived_class = base_class; // Invalid 2)
DerivedClass* new_derived_class = base_class; // Invalid 3)

Sometimes, we know the reference/pointer of the base class object actually holds the derived class object. When we want to assign it to a derived class object, it's required to explicitly call cast. Both dynamic_cast and static_cast are suitable for the conversion. They can downcast reference and pointer of base class object to derived class object. The differences of the two casts are as follows.

dynamic_cast

• The base class needs to be polymorphic (There is at least one virtual member function in the class).
• There is run-time check to make sure the base class object can be casted to derived class object.
• The run-time incurs run-time overhead.

static_cast

• The bass class is not required to be polymorphic. The compiler runs the check at compile time and the compiler assumes the user is aware that the cast is always valid.
• Since there is no run-time check, it still compiles even when the cast is invalid.

Some examples to illustrate the above characteristics. 

DerivedClass& new_derived_class = static_cast<DerivedClass&>(base_class); // Valid
DerivedClass* new_derived_class = static_cast<DerivedClass*>(base_class); // Valid

DerivedClass& new_derived_class = dynamic_cast<DerivedClass&>(base_class); // Invalid, BaseClass is not polymorphic
DerivedClass* new_derived_class = dynamic_cast<DerivedClass*>(base_class); // Invalid, BaseClass is not polymorphic

If we make BaseClass polymorphic by adding a virtual function in it, the two dynamic_cast lines above will also become valid.

class BaseClass{
    virtual ~BaseClass() {}
    int x;
};

When using static_cast, it's the user's responsibility to guarantee the conversion is valid. To the contrast, dynamic_cast runs run-time check to make sure the conversion is valid.

BaseClass base_class;
/* The following two lines compile and run perfectly,
 * though the output value doesn't make any sense,
 * since we are assigning a real BaseClass object to
 * DerivedClass object.
 */
DerivedClass& derived_class = static_cast<DerivedClass&>(base_class);
cout<<derived_class.y;

/* The following one line compiles correctly, but will generate
 * run time exception since dynamic_cast has run-time check.
 */
DerivedClass& derived_class = dynamic_cast<DerivedClass&>(base_class);

Java read from file and write to file

   /* File fin = new File(<Absolute path of the file>); */  
   public void fileRead(File fin) {  
     try {  
       FileInputStream fis = new FileInputStream(fin);  
       BufferedReader br = new BufferedReader(new InputStreamReader(fis));  
       String line = null;  
       while((line=br.readLine()) != null) {  
         System.out.println(line);  
       }  
       br.close();  
     } catch (IOException e) {  
       System.err.println(e.getMessage());  
     }  
   }  
   public void fileWrite(File fout, String line) {  
     try {  
       System.out.println(line);  
       FileOutputStream fos = new FileOutputStream(fout);  
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos));  
       bw.append(line);  
       fos.close();  
     } catch (IOException e) {  
       System.err.println(e.getMessage());  
     }  
   }  

Rotate Image and Spiral Matrix

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Suffered from this problem for a long time. Finally came up with an elegant solution.

Complete code,

1:  public class Solution {  
2:    public void rotate(int[][] matrix) {  
3:      int n = matrix.length;  
4:      if(n <= 1)  
5:        return;  
6:      for(int i = 0; i < n/2; i++) {  
7:        for(int j = i; j < n-i-1; j++) {  
8:          int tmp = matrix[i][j];  
9:          matrix[i][j] = matrix[n-1-j][i];  
10:          matrix[n-1-j][i] = matrix[n-1-i][n-1-j];  
11:          matrix[n-1-i][n-1-j] = matrix[j][n-1-i];  
12:          matrix[j][n-1-i] = tmp;  
13:        }  
14:      }  
15:    }  
16:  }  

There is a similar problem. It's tricky to solve it use the above solution. Found a really nice solution online.

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

[

 [ 1, 2, 3 ],

 [ 4, 5, 6 ],

 [ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

Refer to the original solution from http://ideone.com/bt8A5O

1:  public class Solution {  
2:    public List<Integer> spiralOrder(int[][] matrix) {  
3:      List<Integer> res = new LinkedList<Integer> ();  
4:      int m = matrix.length;  
5:      if(m == 0)  
6:        return res;  
7:      int n = matrix[0].length;  
8:      int left = 0;  
9:      int right = n-1;  
10:      int top = 0;  
11:      int bottom = m-1;  
12:      while(true) {  
13:        for(int i = left; i <= right; i++)  
14:          res.add(matrix[top][i]);  
15:        top++;  
16:        if(top>bottom || right<left)  
17:          break;  
18:        for(int i = top; i <= bottom; i++)  
19:          res.add(matrix[i][right]);  
20:        right--;  
21:        if(top>bottom || right<left)  
22:          break;  
23:        for(int i = right; i >= left; i--)  
24:          res.add(matrix[bottom][i]);  
25:        bottom--;  
26:        if(top>bottom || right<left)  
27:          break;  
28:        for(int i = bottom; i >= top; i--)  
29:          res.add(matrix[i][left]);  
30:        left++;  
31:        if(top>bottom || right<left)  
32:          break;  
33:      }  
34:      return res;  
35:    }  
36:  }  

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

This is a very interesting problem. 

1. Sort the array in descending order.

2. Scan the array from the biggest element. At each position, there are two values.

    n - Number of elements scanned so far

    k - The value of the last scanned element

n starts from 1 and k starts from the largest value. So in the beginning, k should always be greater than n. We can try to take the p value now, which equals Math.min(n, k). Since the p actually takes the value of n, which is smaller, we have to check the following element's value. If its value is greater than p, this p is invalid. 

3. While the scan keeps going, we might hit a point where n==k. That means we have n elements, there values are all >= k. For the remaining elements, their values are smaller than k. So p=n at this moment is the answer we are looking for.

4. Sometimes, if there is no point where n==k, we might be in this situation. At n', array value is k'. Math.min(n', k')=n' and the value of the next element k >= n'. So we need to keep going. For the next element, there are n elements in total, the value at n is k. Math.min(n, k)=k. Because we already know k >= n'. Here we know k <= n'+1. k can have only two possible values, n' or n1+1. So we can safely say there are k elements with values >= k. For the remaining element, their value <= k.

To summarize, starting from the biggest element, I'm looking for a point where n==k. If this position doesn't exist, then the transition point between k and k' is what I'm looking for.

 public class Solution {  
   public int hIndex(int[] citations) {  
     Arrays.sort(citations);  
     for(int i = citations.length-1; i >= 0; i--) {  
       int n = citations.length-i;  
       int k = citations[i];  
       int h = Math.min(n, k);  
       if(i==0 || citations[i-1]<h)  
         return h;  
     }  
     return 0;  
   }  
 }  

Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Naive solution is remove the right-most letters of string one by one and check whether the remaining part is palindrome. It exceeds time limit. The fancy solution is to use KMP.

1:  public class Solution {  
2:    public String shortestPalindrome(String s) {  
3:      String ss = s + "#" + new StringBuilder(s).reverse().toString();  
4:      int[] pie = new int[ss.length()];  
5:      int k = 0;  
6:      pie[0] = 0;  
7:      for(int i = 1; i < ss.length(); i++) {  
8:        while(k>0 && ss.charAt(k) != ss.charAt(i))  
9:          k = pie[k-1];  
10:        if(ss.charAt(k) == ss.charAt(i))  
11:          k++;  
12:        pie[i] = k;  
13:      }  
14:      return (new StringBuilder(s.substring(pie[ss.length()-1])).reverse().toString()+s);  
15:    }  
16:  }  

Implement strStr() using KMP

I'm reading "Introduction to Algorithms" to review the KMP algorithm. I feel the most important concept in the algorithm is k=pi[k]. It's very tricky to understand. The key to understand this is to remember for the matched part between target string and pattern string, checking target string is the same as checking pattern string. When constructing pi[], pattern string is both target string and pattern string. So apply the above rule again. Some notes per my understanding.

Code for strstr, which is also a leetcode question.

1:    public int strStr(String haystack, String needle) {  
2:      int l = needle.length();  
3:      if(l == 0)  
4:        return 0;  
5:      int[] pie = new int[l];  
6:      pie[0] = 0;  
7:      int k = 0;  
8:      for(int q = 1; q < l; q++) {  
9:        while(k>0 && needle.charAt(k)!=needle.charAt(q))  
10:          k = pie[k-1];  
11:        if(needle.charAt(k) == needle.charAt(q))  
12:          k++;  
13:        pie[q] = k;  
14:      }  
15:      int i = 0;  
16:      int j = 0;  
17:      while(i < haystack.length()) {  
18:        while(j>0 && needle.charAt(j)!=haystack.charAt(i))  
19:          j = pie[j-1];  
20:        if(needle.charAt(j) == haystack.charAt(i))  
21:          j++;  
22:        if(j == needle.length())  
23:          return i-j+1;  
24:        i++;  
25:      }  
26:      return -1;  
27:    }  

The Skyline Problem

The Skyline Problem

When I first started working on the problem, my idea is to insert and merge new intervals into the result list while loop through buildings. For the result list, I only need to grab the last two elements and compare with the new interval and do all the merging and insertion stuff. The solution can only pass part of the test cases. The reason is the new segment might have a start time which is earlier than the last two points. It's not enough to only compare it against the last two elements of the result list.

My solution fails in the above cases. When calculating the skyline of 1, 2 and 3, 3's starting point is before p3 and p4. The correct result after inserting 3 is create a new p3 and remove the original p3 and p4. It tells me that for each new interval, I need to go through all the existing points in result list, find the correct position to insert the new interval and than possibly modify many subsequent points in the result list.

I started my search of correct answer and this one looks very interesting. https://leetcode.com/discuss/37630/my-c-code-using-one-priority-queue-812-ms

Copy the explanation from the link above here,

"The idea is to do line sweep and just process the buildings only at the start and end points. The key is to use a priority queue to save all the buildings that are still "alive". The queue is sorted by its height and end time (the larger height first and if equal height, the one with a bigger end time first). For each iteration, we first find the current process time, which is either the next new building start time or the end time of the top entry of the live queue. If the new building start time is larger than the top one end time, then process the one in the queue first (pop them until it is empty or find the first one that ends after the new building); otherwise, if the new building starts before the top one ends, then process the new building (just put them in the queue). After processing, output it to the resulting vector if the height changes."

The explanation is very useful, but you may need to read it a couple of times before it makes sense to you. The fundamental principle is that at any time, the last element in result list is the starting point of the last segment. This point extends until the top point of the priority queue.

Try the code with the example below is the best way to understand the algorithm.

1:  public class Solution {  
2:    public class Pos {  
3:      int h;  
4:      int x;  
5:      public Pos(int hh, int xx) {  
6:        h = hh;  
7:        x = xx;  
8:      }  
9:    }  
10:    public List<int[]> getSkyline(int[][] buildings) {  
11:      LinkedList<int[]> res = new LinkedList<int[]> ();  
12:      if(buildings.length == 0)  
13:        return res;  
14:      PriorityQueue<Pos> queue = new PriorityQueue<Pos> (1, new Comparator<Pos>() {  
15:        @Override  
16:        public int compare(Pos p1, Pos p2) {  
17:          if(p1.h != p2.h)  
18:            return p2.h-p1.h;  
19:          else  
20:            return p1.x-p2.x;  
21:        }  
22:      });  
23:      int curr = 0;  
24:      int currX = 0;  
25:      int currH = 0;  
26:      while(curr<buildings.length || !queue.isEmpty()) {  
27:        //when buildings[curr] overlaps with segments already inserted  
28:        if(queue.isEmpty() || (curr<buildings.length && buildings[curr][0] <= queue.peek().x)) {  
29:          currX = buildings[curr][0];  
30:          //Insert the end point of this segment and the following segments' end point having the same start point into the queue  
31:          while(curr<buildings.length && buildings[curr][0]==currX) {  
32:            queue.add(new Pos(buildings[curr][2], buildings[curr][1]));  
33:            curr++;  
34:          }  
35:        }  
36:        //buildings[curr] has no overlap with already inserted segments  
37:        //Finish all the inserted segments before dealing with buildings[curr]  
38:        else {  
39:          currX = queue.peek().x;  
40:          //For end points which terminate earlier than currX and not has high as currX, they will be invisible in the skyline  
41:          //So we should directly pop them away  
42:          while(!queue.isEmpty() && queue.peek().x <= currX)  
43:            queue.poll();  
44:        }  
45:        //If queue is empty, it's the last point. The height should be zero  
46:        currH = queue.isEmpty() ? 0 : queue.peek().h;  
47:        //If the newly inserted point has the same height as the last element of result list, there is no need to insert it. Because the last element of result list will extend until the top of priority list, which must have a larger end point  
48:        if(res.isEmpty() || res.getLast()[1]!=currH) {  
49:          res.add(new int[]{currX, currH});  
50:        }  
51:      }  
52:      return res;  
53:    }  
54:  }