Is the Number A Power of Two?

Problem:
Given an integer number, decide if it's a power of 2. Return true if yes, otherwise return false.

Analysis:
Can the number be negative?
>> Should not be. Since a power of any number can only be positive. Hence, let me assume non-negative numbers only in this problem.

Solution 1:
Runs in constant time and makes use of bit operations.

Solution 2:
Shifts the bits and counts the number of 1's.

Solution 3:
Uses arithmetic operation only. This is similar to Solution 2. Division by 2 is equivalent to right shift by 1 bit. Check the modulo by 2 is equivalent to check the least significant bit of the integer.

Binary Tree Comparison

Problem:
Given two binary trees, compare if they are the same. If yes, return true, otherwise return false.

Analysis:
This is a very common programming interview question. Not that hard but it's very good to test the idea of recursion. Also, there are some edge cases one needs to consider.

Complexity:
Since it's a binary tree, should consider average case and worst case.
Balanced or unbalanced?

Solution:

Language Setting on Windows

Keep some notes about language setting on Windows. Just in case forget some time in the future.

After installing a English version Windows, to properly display foreign languages on the system, one may need to do following 2 steps:

1. Install the language from the system CD.
   Normally, Control Panel -> Regions and Languages -> ...
   After this step, one may be able to see characters in the languages you just installed, like on webpages.
2. Change language for non-Unicode programs.
   For some special programs, one may still see weird characters even after doing Step 1. This is because some programs were not coded in Unicode and in this case, changing the setting will help.

Note:

• System restart is required for the changes to be effective.
• One may notice some language changed even where you didn't expect (because of non-Unicode coding).

Lowest Common Ancestor in Binary Search Tree Given Two Values

Problem:
Given a Binary Search Tree (BST) and two values, find the lowest common ancestor.

Note:
Two values are given in this problem, instead of two nodes. But the idea should be similar. Here I am giving two options: one is to find the node first and then search by node, and the other is to directly search by value. However, these two are the same in nature: comparing by value and validating the nodes.

Assumption:
The values are distinct in the BST. If not, the problem will become complicated. Consider the BST with all equal values in nodes.

Complexity:
Average case? Worst case?
For BST, balanced or unbalanced? Need to take this into consideration.

Solution 1:
Find the nodes first and then search by node.


Solution 2:
Directly search by value and then validate the values.