jiex.cs
BAN USER
Comments (6)
Followers (1)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
public class Digits {
private int MAX;
private int[] digits;
private void print() {
for (int i = 0; i < digits.length; i++)
System.out.print(digits[i]);
System.out.println();
}
private void generate(int index) {
if (index == MAX)
print();
else {
if (digits[0] == 4 && index == MAX  1) {
digits[index] = 4;
generate(index + 1);
} else {
for (int i = 0; i < 10; i++) {
if (index == 0  digits[index  1] != i) {
digits[index] = i;
generate(index + 1);
}
}
}
}
}
public void printDigits(int max) {
this.MAX = max;
this.digits = new int[MAX];
generate(0);
}
public static void main(String[] args) {
new Digits().printDigits(4);
}
}

jiex.cs
December 26, 2011 Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
it is as simple as continuously applying a procedure of merging two adjacent sorted lists.
For example,
1,2,3,12,11,2,10,6
Round 1. Merge 1,2,3,12 and 11,2, merge 10 and 6, the result is 1,2,2,3,11,12, 6,10
Round 2. Merge 1,2,2,3,11,12 and 6,10' the result is 1,2,2,3,6,10,11,12
It's O(log m) where m is the number of sorted sublists, note m <=n ( number of elements in the lists)
Using two pointers,pointing two positions in the two sorted sublist, the merge can be done in place, so space is O(1)
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
Repcamillerharry, Data Engineer at Student
Hi, I am Camille from Easton USA. Currently, I am working as Staff assistant at Northern Star company. A managed ...
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
1. First sort the array A
 jiex.cs January 23, 20122. Then solve this problem using DP as follows:
Let f(i, j) denote, maximum difference if you select i numbers from the array, starting from index j and element at index j must be selected.
f(i, j) = max { min( f(i1, m), A[m]A[j] ) }, m=j+1 to n1, if i<=nj
f(i, j) = Infinity, if i >nj
the goal is to solve f(1, k), (note: it is always safe to include 1st element in the k numbers), complexity is O(n^2)