17.1 swap a number in place.(without temporary variables)
a = a ^ b;
b = a ^ b;
a = a ^ b;
17.3 Write a function which computes the number of trailing zeros in n factorial.
To count the number of zeros, we only need to count the pairs of multiples of 5 and 2. There will always be more multiples of 2 than 5 though, so, simply counting the number of multiples of 5 is sufficient.
public int count(int num){
int count = 0;
if(num < 0) return -1;
for(int i = 5; num /i > 0; i *= 5)
count += num / i;
return count;
}
17.4 Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.
public int flip(int bit){
return 1 ^ bit;
}
public int sign(int a){
return flip((a >> 31) & 0x1);
}
public int getMax(int a, int b){
int c = a - b;
int sa = sign(a); //if a >= 0 : 1 other : 0
int sb = sign(b); //if b >= 1 : 1 other : 0
int sc = sign(c); //depends on whether a - b overflows, like a = INT_MAX, b < 0
int use_sign_a = sa ^ sb;
int use_sign_c = flip(sa ^ sb);
int k = use_sign_a * sa + use_sign_c * sc;
int q = flip(k);
return a * k + b * q;
}
17.9 Design a method to find the frequency of occurrences of any given word in a book.
The first question that you should ask is if you will be doing this operation once or repeatedly.
Solution: Single Query
go through the book, word by word, count the number of times that words appears. O(n)
Solution: Repetitive Queries
do pre-processing on the book! create a hash table which maps from a word to its frequency.
Hashtable<String, Integer> setupDic(String[] book){
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
for(String word : book){
word = word.toLowerCase();
if(word.trim() != ""){
if(!table.containsKey(word)) table.put(word, 0);
table.put(word, table.get(word) + 1);
}
}
return table;
}
int getFrequency(Hashtable<String, Integer> table, String word){
if(table == null || word == null) return -1;
word = word.toLowerCase();
if(table.containsKey(word)) return table.get(word);
return 0;
}
17.11 Implement a method rand7() given rand5(). Given a method that generates a random number between 0 and 4, write a method that generates a random number between 0 and 6.
Nondeterministic Number of Calls
public int rand7(){
while(true){
int num = 5 * rand5() + rand5();
if(num < 21) return num % 7;
}
}