Useful Links

This blog is just used as reference and put some useful links together for future convenience. Will update this blog from time to time.

How to Install Oracle Java JDK on Ubuntu Linux

Introduction to SVN

How to Install Android on Ubuntu Linux With Eclipse Ide

Install Third Party Apps on Android

For 3rd-party apps that are not in Google Play, one can install them by manually downloading the .apk files to SD card and then installing with package installer.

Just a simple note here. By default, 3rd-party apps are not allowed on Android and users have to change the settings. I am using a Android 4.1.1 (Jelly Bean) and here is the setting change.

1. Go to Main Menu
2. Select "Settings"
3. In "Personal" section, select "Security"
4. In "Device administration" section, check "Unknown sources"

Shuffle an Array

Question:
Given an input array, shuffle it and output a randomized sequence.

Analysis:
The array can actually be of any type, not necessary integer or number. One special example is to shuffle a deck of cards. That happens to be of integer type.

Variations:
There may be different variations of this similar problem. I hope to summarize all the cases here and would like to go through each with some implementation.

1. Randomize an array of n elements
2. Randomly select m elements out of an array of n elements
3. Randomly select m elements out of a stream of n elements (n is known before hand)
4. Randomly select m elements out of a stream of elements (not sure how many elements there are until stopping reading)

This blog talks about Case 1. The code is not hard but there are some tricks. It's better to select from the end of array and that will help control the number of elements remained. Also, the code will be cleaner.


The mathematical proof would be trickier and it's good to have some combinatorics. The probability of any output sequence will be \[\frac{1}{n!}\]

Decide if a Binary Tree is Binary Search Tree

Question:
Given a binary tree, validate if it's a binary search tree.

Analysis:
The elements in a BST are sorted if traversed in-order. This is a very important feature BST and based on the definition, the problem can be solved by in-order traversal.

The class definition of tree node:

Based on the analysis above, we can have the implementation below.

Many people may think we can simply check "left.value < parent.value < right.value" for each node. That being said, we can have an implementation like this:

However, this is not correct. Simply checking the parent and children relationship is not sufficient. Here is a counter-example.

      5
     /  \
    /    \
   3    7
  / \    / \
2  6  4  9

This is a top-down approach although it's not correct. If adding more constraints on the value for each node, there is a working solution for this. Here is the implementation:

Find Next Character in Sorted String

Question:
Given a sorted array of unique elements R, that are letters of English alphabet and an input character x. The elements in R are sorted with the least element appearing first. Find the minimum r in R such that r > x. If there is no r > x, find the first element of the array (wrap around).

Example:
R = ['c', 'f', 'j', 'p', 'v']
if x equals:
'a' => return 'c'
'c' => return 'f'
'k' => return 'p'
'z' => return 'c' (wrap around case)

Is Input String a Valid Number?

Question:
Given an input string, check if it is in a valid number format.

Analysis:
Valid number format can be either positive or negative, can be integer or float number.

Solution 1:
Directly call Java library method and if the string is not in a valid format, it will throw out an exception. Return false if catching an exception.

Solution 2:
Make a regular expression and call the string library method to see if the input matches the pattern.

Solution 3:
Start from no library method available. Compare and make decision based on the characters in the input.