1. Calculate how many times 10 can by divisible by a number?
- Gave an O(n) Solution:
public int count(int n){
if(n == 0){
return 1;
}
int count = 0;
while(n % 10 == 0){
count++;
n /= 10;
}
return count;
}
2. How can you do better than linear?
- Was a lot more difficult for me, but finally got an O(log n) Solution
public int binarySearch(int val, int start, int end){
if(start > end){
return -1;
}
int mid = (start + end) / 2;
if(val % 10^(length - i) == 0 && ((val / 10^(length - i)) % 10) != 0){
return (length - i);
}
else{
// if value is non 0, search right for value
// if value is 0, search left for value
if(val % 10^(length - i) != 0){
binarySearch(val, mid+1, end);
else{
binarySearch(val,start, mid-1);
}
}
}
3. Given 2 people, find if one is the ancestor of another? These are actual people so, there is a mother and father who are ancestors of their son, along with grandmothers and grandfathers. (Not a tree)
Given:
def isAncestor(me, anotherPerson):
class Person:
string id
string name
int gender
date dob
- What if the path up the tree is very long? It takes a long time to traverse up?
- Can store additional info in the Person class
