nixfish
BAN USERIf sorting is allowed than we can get the result in O(nlogn) time. Sample java code
public static int find2(int[] a) {
int[] b = new int[a.length + 1];
System.arraycopy(a, 0, b, 0, a.length);
b[a.length] = Integer.MAX_VALUE;
Arrays.sort(b);
int count = 1;
int num = 0;
for (int i = 1; i < b.length; i++) {
if (b[i] > b[i - 1] + 1) {
if (count > 1) {
num++;
}
count = 1;
} else {
count++;
}
}
return num;
}
Java code
public static int sumLeaves(TreeNode r) {
if (r == null) {
return Integer.MIN_VALUE;
}
if (r.left == null && r.right == null) {
return r.data;
}
int sum = 0;
if (r.left != null) {
sum += sumLeaves(r.left);
}
if (r.right != null) {
sum += sumLeaves(r.right);
}
return sum;
}
This code sample seems to work.
public static String convert(int n) {
if (n < 0) {
return "";
}
int m = n % 26;
StringBuilder sb = new StringBuilder();
sb.append((char)('A' + m));
n = n/26;
while (n > 26) {
m = n % 26;
sb.insert(0, (char)('A' + m - 1));
n/=26;
}
if (n > 0) {
sb.insert(0, (char)('A' + n - 1));
}
return sb.toString();
}
- nixfish October 06, 2012The question required a O(n) algorithm so we can scan the input only constant times and it is reasonable to think to start the scan from the end. Here is sample code
public static String maxSuffix(String s) {
if (s == null || s.length() < 2) {
return s == null ? null : new String(s);
}
char[] a = s.toCharArray();
int[] M = new int[a.length];
M[a.length - 1] = a.length - 1;
for (int i = a.length - 2; i >= 0; i--) {
if (a[i] >= a[M[i + 1]]) {
M[i] = i;
} else {
M[i] = M[i + 1];
}
}
return s.substring(M[0], s.length());
}
Where M[i] means the beginning index of the max suffix for sub-string starting at position i, 0 <= i < s.length.
- nixfish October 05, 2012This is more like a design problem other than a coding problem. I guess the key points to cover is
1. web servers to handle URL shortening request and to handle URL access request
2. database to store the mapping from URL to tiny url
3. caching to reduce the response delay and the hit on database
4. capacity: how much traffic is supposed to be served on average, at peak?
5. scalability: how to survive huge amount of requests?
6. availability: how to survive any system failure: server crash, database crash, cache crash
7. security: how to handle malicious requests?
Seems a lot to discuss here
Abstract class can have have states (instance variable) while interface cannot have. Abstract class can have some method implemented while interface cannot have. Abstract class can have method overridden by only its subclasses while interface have can have its method implemented by all other classes that implements the interface. More?
- nixfish October 05, 2012The question did not say binary tree. So treat it as a generic tree where the number of children can vary. Here is sample java code
public static int count(TreeNode root) {
if (root == null) {
return 0;
}
if (root.getChildren().isEmpty()) {
return 1;
}
int num = 0;
boolean uniValue = true;
for (TreeNode sub : root.getChildren()) {
if (sub.getValue() != root.getValue()) {
uniValue = false;
}
num += count(sub);
}
if (!uniValue()) {
return num + 1;
} else {
return 1;
}
}
It takes O(n) time where n is the number of nodes on the tree since each node will be accessed only once.
- nixfish October 05, 2012
Are there any examples?
- nixfish November 15, 2012