amyue.xing
BAN USERHi, should the decision part be that complex? In my opinion,
if(arr[mid] < k), the only case k is not in the right side is that right is an increasing order, but k is bigger than arr[right]. Otherwise, we can search in the right side. The same for arr[mid]>k.
Correct me if I am wrong.
Hi, Steve, will you bother to reply more about what you were thinking and what the interviewer responded to your thought? Thanks a lot.
 amyue.xing November 15, 2012A quick question before my interview with Twitter, I have seen some questions from Twitter on CareerCup, and most of them are focused on design. So is Twitter mostly focusing on finding design guys. BTW, I will interview for software engineer for new graduate.
 amyue.xing November 15, 2012Hi, can a push_back work here? I do not think so. Consider the sequence: 3, 1, 4, 1. When you pop the top 1, you will have no idea whether there will be another 1 inside the stack. Thus I suggest when stack.push(num), if(num<=minStack.peek()), minStack.push(num).
Correct me if I am wrong.
I think there are several faster ways to test prime.
1) you can start testing n/2, n/3, and then test n/(6*k+1);
2) you can apply Fermat's little theorem;
Hi, I do not really get counting sort, can you do me a favor to explain this?
 amyue.xing November 15, 2012we can simply run BFS and count how many times we do enqueue. This will take O(V). The same as DFS.
 amyue.xing November 15, 2012This should depend on what you would like to permute: either to permute based on number, or permute based on char.
I have provided 2 versions of code.
public class Phonebook {
static final char[][] keyPad = {
{}, {}, { 'A', 'B', 'C' }, { 'D', 'E', 'F' }, { 'G', 'H', 'I' }, { 'J', 'K', 'L' },
{ 'M', 'N', 'O' }, { 'P', 'Q', 'R', 'S' }, { 'T', 'U', 'V' }, { 'W', 'X', 'Y', 'Z' }
};
static final char[][] used = {
{}, {}, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 },
{ 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }
};
static StringBuilder strb = new StringBuilder();
static void permute(int[] input, int len){
if(strb.length() == len){
// print out since we are done with all numbers
System.out.println(strb);
}
for(int k: input){
if(used[k].length < 1  used[k][0] == 1)continue;
// print the chars belonging to this k
for(char c: keyPad[k]){
strb.append(c);
}
if(used[k].length > 1)
used[k][0] = 1;
permute(input, len);
used[k][0] = 0;
strb.setLength(strb.length()  keyPad[k].length);
}
}
static void permute_chars(int[] input, int len){
if(strb.length() == len){
//print out since we are done with all chars
System.out.println(strb);
}
for(int k : input){
for(int j = 0; j < keyPad[k].length; j++){
if(used[k][j] == 1) continue;
strb.append(keyPad[k][j]);
used[k][j] = 1;
permute_chars(input, len);
strb.setLength(strb.length()1);
used[k][j] = 0;
}
}
}
public static void main(String[] args){
int[] input = new int[]{1,2,3};
int sum = 0;
for(int k: input){
sum += keyPad[k].length;
}
//Phonebook.permute_chars(input, sum);
Phonebook.permute(input, sum);
}
}

amyue.xing
November 14, 2012 I changed my idea, since this question is very simple, for each node, the shortest path either comes from its left node or its upper node, thus I changed the d matrix. The following is my code:
// d for memorize
// m, M1, N1
int _ssp(int [][]m, int **d, int x, int y)
{
if(d[x][y]) return d[x][y];
int min = INT_MAX,
left = ssp(m, x1, y),
up = ssp(m, x, y1);
if(left < up){
min = left;
}else {
min = up;
}
d[x][y] = min
return min;
}
int ssp(int [][]m, int w, int h){
int **d = (int **)malloc(sizeof(int)*w*h);
int i = 0;
for(i = 0; i < w; i++){
d[0][i] = m[0][i];
}
for(i = 0; i < h; i++){
d[i][0] = m[i][0];
}
_ssp(m, d, w1, h1);
}
Here we need d for memorization, or we have to caculate for multiple times. Once we have run over the code, it's easy to populate some code to generate the path.
 amyue.xing November 14, 2012why not use BellmanFord's singlesource algorithm.
d[v][i] is the shortest path from v to matrix[0][0] using i edges.
d[v][i] = min(d[x][i1] + len(v,x)).
Hi, I didn't get it. "this can do 4 billion strings in 512MB memory (ideal case)" can you explain this much more in detail?
 amyue.xing November 15, 2012