eboyGTK
BAN USERQuite similar to the question in the book "Cracking the coding interview". Just did a small change. but don't know whether it is O(n).
public static Node commonAncestor(Node root, Node p, Node q){
System.out.print(root.value + "->");
if (covers(root.left, p) && covers(root.left, q)){
return commonAncestor(root.left, p, q);
}
if (covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p, q);
}
return root;
}
private static boolean covers(Node root, Node p){
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}
“How will you test this function” is the key point of the question.
So before writing code, we need to consider the possible exceptions. Obviously, here the integer could be positive, negative or 0. So the code should deal with all those conditions. The way of right shifting repeatedly is not available for negative integers because they are represented by complement + 1. So we can use left shifting. The code is shown as follows
public static int count(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n&flag) != 0)
count++;
flag = flag<<1;
}
return count;
}
“How will you test this function” is the key point of the question.
So before writing code, we need to consider the possible exceptions. Obviously, here the integer could be positive, negative or 0. So the code should deal with all those conditions. The way of right shifting repeatedly is not available for negative integers because they are represented by complement + 1. So we can use left shifting. The code is shown as follows
public static int count(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((n&flag) != 0)
count++;
flag = flag<<1;
}
return count;
}
I think the key here is how to compare two double values. In java, can use BigDecimal but need to convert double to String first. My code is shown as follows:
public static Node closest(Node root, BigDecimal key){
if (root == null)
return null;
BigDecimal value = new BigDecimal(root.value+"");
int compare = key.compareTo(value);
if ( compare == 0){
return root;
}
else if (compare < 0){
if (root.left == null) return root;
else {
BigDecimal leftvalue = new BigDecimal(root.left.value + "");
if (key.compareTo(leftvalue) > 0){
if ((key.subtract(leftvalue)).compareTo(value.subtract(key)) <= 0)
return root.left;
else
return root;
}
else
return closest(root.left, key);
}
}
else if (compare > 0){
if (root.right == null) return root;
else{
BigDecimal rightvalue = new BigDecimal(root.right.value + "");
if (key.compareTo(rightvalue) < 0){
if ((key.subtract(value)).compareTo(rightvalue.subtract(key)) <= 0)
return root;
else
return root.right;
}
else
return closest(root.right, key);
}
}
return null;
}
public class AddTwoArrays
{
public static int[] add(int[] a, int[] b){
int len1 = a.length;
int len2 = b.length;
int len = (len1 > len2)?len1:len2;
len = len + 1;
int [] result = new int[len];
int i = len1-1, j = len2-1, k = len -1, carry = 0, rest = 0;
while (i >= 0 && j >= 0){
rest = a[i] + b[j] + carry;
carry = 0;
while (rest >= 10){
rest = rest % 10;
carry = carry + 1;
}
result[k] = rest;
k--;
j--;
i--;
}
while (i >= 0){
rest = a[i] + carry;
carry = rest / 10;
rest = rest % 10;
result[k] = rest;
k--;
i--;
}
while (j >=0 ){
rest = b[i] + carry;
carry = rest / 10;
rest = rest % 10;
result[k] = rest;
k--;
j--;
}
result[0] = carry; // set the first digit of result as the carry
return result;
}
public static void main(String[] args)
{
int[] a = {3,9,9};
int[] b = {6};
int[] c = add(a,b);
if (c[0] > 0)
System.out.print(c[0]);
for (int i = 1; i < c.length; i++) {
System.out.print(c[i]);
}
}
}
public class PatternInMatrix
{
static boolean used[][];
public static boolean findPattern(char[][] matrix, int nRow, int nCol, char[] pattern) {
used = new boolean[nRow][nCol];
for (int i = 0; i < nRow; i++)
for (int j = 0; j < nCol; j++)
{
used[i][j] = false;
}
for (int i = 0; i < nRow; i++)
for (int j = 0; j < nCol; j++)
{
if (matrix[i][j] == pattern[0])
if (search(matrix, nRow, nCol, i, j, pattern, 0))
return true;
}
return false;
}
private static boolean search(char[][] matrix, int nRow, int nCol, int row, int col, char[] pattern, int index) {
if (index == pattern.length - 1)
return true;
// check up
if (row-1 >= 0 && !used[row-1][col]) {
if (matrix[row-1][col] == pattern[index + 1]) {
used[row-1][col] = true;
if (search(matrix, nRow, nCol, row-1, col, pattern, index + 1)) {
return true;
}
used[row-1][col] = false;
}
}
// check down
if (row+1 < nRow && !used[row+1][col]) {
if (matrix[row+1][col] == pattern[index + 1]) {
used[row+1][col] = true;
if (search(matrix, nRow, nCol, row+1, col, pattern, index + 1)) {
return true;
}
used[row+1][col] = false;
}
}
// check left
if (col-1 >= 0 && !used[row][col-1]) {
if (matrix[row][col-1] == pattern[index+1]) {
used[row][col-1] = true;
if (search(matrix, nRow, nCol, row, col-1, pattern, index+1)) {
return true;
}
used[row][col-1] = false;
}
}
// check right
if (col+1 < nCol && !used[row][col+1]) {
if (matrix[row][col+1] == pattern[index+1]) {
used[row][col+1] = true;
if (search(matrix, nRow, nCol, row, col+1, pattern, index+1)) {
return true;
}
used[row][col+1] = false;
}
}
// check left up
if (row-1 >= 0 && col-1 >=0 &&!used[row-1][col-1]) {
if (matrix[row-1][col-1] == pattern[index+1]) {
used[row-1][col-1] = true;
if (search(matrix, nRow, nCol, row-1, col-1, pattern, index+1)) {
return true;
}
used[row-1][col-1] = false;
}
}
// check left down
if (row+1 < nRow && col-1 >= 0 && !used[row+1][col-1]) {
if (matrix[row+1][col-1] == pattern[index+1]) {
used[row+1][col-1] = true;
if (search(matrix, nRow, nCol, row+1, col-1, pattern, index+1)) {
return true;
}
used[row+1][col-1] = false;
}
}
// check right up
if (row-1 >= 0 && col+1 < nCol && !used[row-1][col+1]) {
if (matrix[row-1][col+1] == pattern[index+1]) {
used[row-1][col+1] = true;
if (search(matrix, nRow, nCol, row-1, col+1, pattern, index+1)) {
return true;
}
used[row-1][col+1] = false;
}
}
// check right down
if (row+1 < nRow && col+1 < nCol && !used[row+1][col+1]) {
if (matrix[row+1][col+1] == pattern[index+1]) {
used[row+1][col+1] = true;
if (search(matrix, nRow, nCol, row+1, col+1, pattern, index+1)) {
return true;
}
used[row+1][col+1] = false;
}
}
return false;
}
public static void main(String[] args)
{
char[][] m = {{'A','C','P','R','C'},
{'X','S','O','P','C'},
{'V','O','V','N','I'},
{'W','G','F','M','N'},
{'Q','A','T','I','T'}};
String pattern = "MICROSOFT";
System.out.println(findPattern(m, 5, 5, pattern.toCharArray()));
}
}
/* Method: use bit operation (Assume that we are using 32-bit integer)
* First 28 bits used for saving numbers (four-bit each) So at most it can hold seven digits
* from 0000000-9999999
* Last 4 bits used as the pointer
*/
class QueueUsingOneInteger{
int queue = 0;
public void enqueue(int x) {
if (((queue << 28) >> 28) >= 7) {
System.out.println("The queue is full!");
return;
}
else
{
int numOfElements = ((queue << 28) >> 28);
numOfElements++;
queue = ((queue >> 4) << 4) + x;
queue = (queue << 4) + numOfElements;
}
}
public boolean isEmpty() {
return (((queue << 28) >> 28) == 0);
}
public int size() {
return ((queue << 28) >> 28);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("The queue is empty!");
return -1;
}
else
{
int numOfElements = ((queue << 28) >> 28);
int mask = 15 << (numOfElements*4);
int result = (queue & mask) >> (numOfElements*4);
queue = (queue & (~mask)) - 1;
return result;
}
}
}
Quite similar to the question in the book "Cracking the coding interview". Just did a small change. but don't know whether it is O(n).
- eboyGTK May 18, 2012public static Node commonAncestor(Node root, Node p, Node q){
System.out.print(root.value + "->");
if (covers(root.left, p) && covers(root.left, q)){
return commonAncestor(root.left, p, q);
}
if (covers(root.right, p) && covers(root.right, q)){
return commonAncestor(root.right, p, q);
}
return root;
}
private static boolean covers(Node root, Node p){
if (root == null) return false;
if (root == p) return true;
return covers(root.left, p) || covers(root.right, p);
}