FAB postion

System

If the Floating Action Button (FAB) seems to be at the wrong position on the screen, check the version number of the Android supporting library. There is a bug in version 24.2.0 and above and we need to revert to a lower SDK and support library version. Check out this post.

DialogFragment

System

When using getContext to get the fragment’s context, if the IDE tells you that the getContext call requires API version 23 and current minimum is set to 15, make sure that the import for DialogFragment is import android.support.v4.app.DialogFragment instead of import android.app.DialogFragment. The same applies to Fragment too.

Reset android studio

System

On Mac, do the following

Then restart android studio, re-install any plug-ins.

Java PriorityQueue

Algorithms

Java PriorityQueue does not store the whole sequence in-order. So if we try to print it using System.out.println(Q), the output will usually not be in-order. But every time we do a poll() on a priority queue, it will give the smallest number in the current sequence.

Matrix transformation (2)

Algorithms

A second type of matrix transformation problem involves swapping matrix elements in different ways. One example is matrix transpose, which merely involves swapping element A[i][j] with element A[j][i]. A much more interesting example involves matrix rotation, e.g., the “rotate image” problem, which asks us to rotate a matrix by 90 degrees (clockwise or counterclockwise). This rotation problem can be solved through layer-level traversal. But different from the “layer rotation” problem discussed in “matrix transformation (1)“, the relative positions of elements at different layers are fixed in the “rotate image” problem. The following solution is from CTCI v6 page 203. The trick is to introduce 3 additional variables: “first” (start of a row or column), “last” (end of a row or column), and “offset” (index relative to the start).

Matrix transformation (1)

Algorithms

This type of problems are quite different from those discussed in “changing matrix elements” in the sense that the traversal can no longer be implemented using a simple nested loop that goes through row index and column index in order. One example is the “matrix layer rotation” problem, in which each layer of the matrix is rotated counterclockwise by a certain amount, which is different for different layers. In my solution in the following, I first traverse the matrix layer by layer from outside towards center and store the elements in each layer into a separate list. After this re-arrangement of the matrix elements, the elements in a rotated layer can be accessed through indexing as discussed in “querying the rotated array“. I then reconstruct the rotated matrix using the layers with the rotated index. During all those operations, it is important to fix a reference point and I used the upper-left corner, row = 0 and column = 0, as the reference.

A closely related problem is the “spiral matrix” problem, in which we need to traverse the matrix in spiral order. For this problem, it is important to check for corner cases (matrix that is very elongated along horizontal or vertical direction). My solution is the following.

There is also a problem that asks us to reconstruct a matrix from its spiral order traversal (the “spiral matrix II” problem). My solution is the following.

Re-arranging characters

Algorithms

Some of the problems ask us to rearrange a sequence of characters into different forms, e.g., a matrix, and then traverse the rearranged characters in different ways. One example is the “encryption” problem. The logic of the code can often be simplified significantly if we use a special character, e.g., “$”, to fill all the elements after the end of the original character array. My solution is in the following.

Java primitive explicit casts

Algorithms

When multiplying two very big integers together, say “c = a * b”, the result can overflow. If we just make “c” a long integer, the result of the right-hand-side will be implicitly cast from integer to long during the assignment. But that does not prevent the overflow! If “a * b” (the RHS) overflows, the number implicitly cast to long and assigned to “c” is the overflown integer (a negative integer), not the correct answer. So to prevent the RHS from overflow, we need to explicit cast at least one of the numbers on the RHS to long, i.e., “long c = (long)a * b”, in which “b” will be implicitly cast into a long integer and the result of the RHS will be a long before assigned to “c”. One example is the “modified Kaprekar numbers” problem and my code is following.

Convert numbers/words to words/numbers

Algorithms

Some of the problems ask us to convert numbers to English words or phrases, for example, the “time in words” problem, which asks us to convert a time specified using numbers to words. For this type of problems, a HashMap that binds the numbers to their corresponding words can be quite handy. My solution is int the following.

Another related problem is to convert numbers to other types of text representations, such as the “integer to Roman” and the opposite conversion “Roman to integer“. The opposite conversion (from Roman to integer) is simpler. Again, a HashMap is used to map Roman characters to their corresponding integers (the mapping can be found on wiki) in my following solution. The only issue is that some of the Roman numerals are two-character long and both characters also exist in the HashMap as independent keys, so I check for the existence of a 2-character key before checking for the existence of a 1-character key.

Mapping integers to Roman numerals is more complicated. In addition to the HashMap that binds single-character Roman numerals to corresponding integers, we also need a separate simplification map that binds 2-character Roman numerals to corresponding sequences of 1-character Roman numerals. After we map the integer to a sequence of single-character Roman numerals, we apply a simplification process that maps subarrays of single-character Roman numerals to corresponding 2-character Roman numerals. In order to iteration through all the keys in the HashMap in a specific order (decreasing order in my following code), I used a separate array to store the keys in descending order. The following is my code.

Java BigInteger

Algorithms

Java provides a data structure for storing very large integers that cannot fit into the 64-bit long type. It is called “BigInteger”. One example is the factorial calculation (e.g., the “extra long factorials” problem), which can overflow 64-bit long very quickly. My solution using BigInteger is the following.