LoocalVinci
BAN USERIncorrect! Think about {1, 1, 4}
- LoocalVinci September 04, 2012Common sense in the theory of external sorting problem.
- LoocalVinci September 03, 2012There is no tree in the very beginning. It takes O(nlgn) to construct trees.
- LoocalVinci September 02, 2012I'm not sure whether your code works. But, you got the point!
- LoocalVinci September 02, 2012It's easy to achieve O(n) by using Hash table. Travel the array from a1 to an, find whether there is sum-ai in Hash table. Then, put each element in Hash table if and only if it is not in hash table, unless the value is equal to sum/2.
- LoocalVinci September 01, 2012I need to explain here
F(N)=F(7N/8)+C, N=n^3
O(log(8/7)N) = O(3log(8/7)n) = O(log(8/7)n), better than O(n)
We come up with the same algo.
F(N) = F(7n/8)+C
Time complexity is O(log(8/7)n), definitely better than O(N)
Looks like your algo has nothing to do with BST
- LoocalVinci September 01, 2012I don't understand. Median could be found in O(n). Why O(nlgn)?
- LoocalVinci September 01, 2012“If there exists a cycle in a path from source to destination print Infinite path”
I don't get your point. If there is no cycle between source and destination, there must be only one path between them. Do you mean that we only consider the simple path?
You algorithm doesn't work. Because there is no absolute breadth. Only nodes in a tree has breath, because there is no cycles in a tree.
- LoocalVinci September 01, 2012answer should be 7, isn't it?
15
125
1325
1235
135
1345
12345
O(nlgn)
1. sorts all the sets O(lgn).
2. merge them by using min-heap O(lgn). It's easy to remove redundant numbers.
It depends on the requirement.
By using link list, we could have a O(1) checkout /O(n) checkin algorithm.
Hashtable could achieve O(n)checkout / O(1)checkin.
If we maintain a BST, we could have a O(lgn) algorithm for both checkin and checkout.
What if there are k exceptions?
- LoocalVinci August 31, 2012Amazing!
- LoocalVinci August 31, 2012{5}
{5,21}
{5,21}
{5,21,30}
{5,21,30,40}
Return value is 4. I think it works.
DP, O(N*S)
public int getMinCoins(int[] coins, int count)
{
int[] nums = new int[count+1];
for(int i=0; i<=count; i++)
nums[i] = -1;
nums[0] = 0;
for(int i=0; i<coins.length; i++)
{
int value = coins[i];
for(int j=count-value; j>0; j--)
{
if(nums[j]!=-1)
{
int n = nums[j]+1;
if(nums[j+value]==-1||n<nums[j+value])
{
nums[j+value] = n;
}
}
}
nums[value]=1;
}
return nums[count];
}
Firstly, your algo is a O(2^n).
Secondly, your program is not gonna work.
For example, there is a list (1, 5) (10, 21) (20, 39) (30, 35) (40,55)
Processing (1,5), we have M[1] = 5, saying a chain with length 1 are found. The last position is 4.
Processing (10,21), we have M[1] = 5, M[2] = 21, saying a chain with length 2 are found. The last position is 21.
Processing (20, 39), we have {5, 21, 39}
Processing (30, 35), we have {5, 21, 35} because 21<30<39, so this pair could be added to the chain with length 2. Then their is a new chain with length of 3. Because 35<39, we update M[3].
It is easy to prove that M is a increasing sequence. So whenever you get a new pair, you can use binary search to locate which chain you are going to update.
Could you explain your question a little bit?
- LoocalVinci August 30, 2012O(nlgn)
1. Sort all the pairs p_i (x_i,y_i) with respect to x_i. Takes O(nlgn)
2. Create an array M[1..n], M[i] represents that p_M[i] has a chain with length of i and has the smallest yi. Travel from p1 to pn and update M by using binary search. Takes O(nlgn)
Then if he moves k+1 steps, the probability will be
(dp[j-1][k][i-1]+dp[j+1][k][i-1]+dp[j][k-1][i-1]+dp[j][k+1][i-1])/4
dp[i][j][k] means the probability Bod will die if initial position is (x,y) and steps he moves is k.
- LoocalVinci August 30, 2012Maybe I'm wrong, but for me this is a basic External sorting problem. Usually, time complexity is O(mnlgm) by using min-heap. However, m is a predefined constant. So time complexity is exactly O(n), and space complexity is O(lgm) = O(1).
The trick thing is "You are provided m*n space in which you have to arrange all data in increasing order.". Is that supposed to mean we already have enough space to store the resulting array?
感谢国家!都准备面试amazon呢。
- LoocalVinci August 30, 2012Let me know if I'm wrong. I use DP algorithm like I said. Time complexity is O(m*n*N).
public class CareerCupAmazon {
public double calcAliveProbability(int N,int m,int n, int x, int y)
{
if(x>m-1||x<0||y>n-1||y<0)
return -1;
double[][][] dp = new double[m+2][n+2][N+1];
for(int j=0; j<m+2; j++)
{
for(int k=0; k<n+2; k++)
{
if(k==0 || k==n+1 || j==0 ||j==m+1)
{
dp[j][k][0] = 1;
}
else
dp[j][k][0] = 0;
}
}
for(int i=1; i<=N; i++)
{
for(int j=0; j<m+2; j++)
{
for(int k=0; k<n+2; k++)
{
if(k==0 || k==n+1 || j==0 ||j==m+1)
{
dp[j][k][i] = 1;
}
else
{
dp[j][k][i] = (dp[j-1][k][i-1]+dp[j+1][k][i-1]+dp[j][k-1][i-1]+dp[j][k+1][i-1])/4;
}
System.out.print(dp[j][k][i]+"\t");
}
System.out.println();
}
System.out.println();
System.out.println();
}
return 1-dp[x+1][y+1][N-1];
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CareerCupAmazon a = new CareerCupAmazon();
System.out.println("the probability that bob is alive is "+a.calcAliveProbability(10, 20, 20, 10, 2)*100+"%");
}
}
Intuitively, I'll choose DP algorithm for this kind of problems. Time complexity should be O(m*n*N).
- LoocalVinci August 30, 2012-0 might mean a real value approaching to zero from left, which is not an integer.
- LoocalVinci August 15, 2012generator(int[] a, int index, String prefix)
{
if (index == a.length)
{
System.out.print(prefix+",");
return;
}
for(int i=0; i<table[a[index]].length;i++)
{
generator(a, index+1, prefix + table[a[index]][i]);
}
}
c(sum,n) = c(sum,n-1)+c(sum-d[n],n)
- LoocalVinci August 10, 2012None of the solution above really works.
Think about this fake random number generator.
static n = 0;
void fakerand()
{
n++;
if(n%2==0)
return rand()*0.5;
else
return 1-(rand()*0.5);
}
We need to generate a really long sequence. And try to proof, as much as we can, that there is no pattern in this sequence.
boolean checkOneChild(int[] preorder)
{
for(int i=0; i<preorder.length-2; i++)
{
int a = preorder[i]-preorder[i+1];
int b = preorder[i]-preorder[preorder.length-1];
if(a*b<0)
return false;
if(a*b==0)
{
if(a+b<0)
return false;
}
}
}
BST reconstruct(int[] preorder, int s, int e)
{
if(s==e)
return null;
BST root = new BST(preorder[s]);
if(preorder[s]>preorder[s+1])
{
int r = s + 1;
for(; r<e; r++)
{
if(preorder[s]<preorder[r])
break;
}
root.leftchild = reconstruct(preorder, s, r);
root.leftchild = reconstruct(preorder, r, e);
}
else
{
root.rightchild = reconstruct(preorder, s+1, e);
}
return root;
}
class Hashtable
- LoocalVinci October 16, 2012{
private int size = 100000;
pair[] slot;
Lock[] write_lock;
int currentSize;
class pair
{
K key;
V value;
}
public Hashtable()
{
value = new V[size];
write_lock = new Lock[size];
currentSize = 0;
}
private int hashcode(K key, S preSlot){}
public V put(K key, V value)
{
int index= -1;
do
{
index = hashcode(K, index);
if(slot[index]==null)
{
write_lock[index].lock();
if(slot[index]==null)
{
slot[index] = new pair();
slot[index].key = key;
slot[index].value = value;
return null;
}
else if(slot[index].key==key)
{
V preValue = null;
preValue = slot[index].value;
slot[index].value = value;
return preValue;
}
write_lock[index].unlock();
}
else
{
if(slot[index].key==key)
{
V preValue = null;
preValue = slot[index].value;
slot[index].value = value;
return preValue;
}
}
}while(currentSize < size*0.5);
this.resize();
return put(key, value);
}
}