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);
}
}
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, M-1, N-1
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, x-1, y),
up = ssp(m, x, y-1);
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, w-1, h-1);
}
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 Bellman-Ford's single-source algorithm.
d[v][i] is the shortest path from v to matrix[0][0] using i edges.
d[v][i] = min(d[x][i-1] + 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