loveCoding
BAN USERWhat are you trying to ask actually?
- loveCoding August 30, 2012It assumes that each step is equally likely. Not each point
- loveCoding August 29, 2012look at the code... Carefully.. You will understand
- loveCoding August 29, 2012You just need to go though the string by char.
1 keep one String variable prev = 0 and sum = 0
2. Now go through string char by char say ch is the character
3. If ch is a digit -> prev = prev*10 + ch
4. if ch is NOT a digit or end of string -> sum = sum + prev AND set prev to 0
time complexity O(n) : 1 ITERATION
This can be solved in O(N).
1. Possible positions after N steps can be (-1,-1) to (m+1,n+1)
2. Now with (x,y) We can divide N steps in N+1 ways. For every division we can have max of 4 possiblities. 2 if division is equal or one of them is 0.
calcAliveProbability(int N,int m,int n, int x, inty){
int dead = 0;
int alive = 0;
for(int dx = 0;dx<=N;dx++){
int newx = x + dx;
int newy = y + (N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x + dx;
int newy = y - (N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x - dx;
int newy = y +(N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
int newx = x - dx;
int newy = y -(N - dx);
if(getState(newX,newY,m,n) == 0)
dead++;
if(getState(newX,newY,m,n) == 1)
alive++;
}
return (alive/(alive+dead));
}
int getState(int newX, int newY,int m,int n){
if(newX<-1 || newX > m+1 || newY<-1 || newY >n+1)
return -1;
if(newX==-1 && newY==-1)//Special case NOT possible
return -1;
if(newX==m+1 && newY==n+1)//Special case NOT possible
return -1;
if(newX==-1 || newX == m+1 || newY==-1 || newY==n+1)
return 0;
else
return 1;
}
Does NOT work for 1,2,3,4,4,4
- loveCoding August 19, 2012Basically we need to build the string using either "1" or "10".
We can do this with simple for loope
int total = 0;
//i is no. of"10" in the string
for(int i=0;i<=K/2;i++){
if(i%2!=0)
continue;
total += fact(k-i)/(fact(i)*fact(k-2i));
}
1. count no. of spaces in the sentence( say nos)
2. calculate diff = page width - sentence length - nos
3. calculate diff/nos. replace all spaces by this number of spaces.
4. calculate xtra = diff%nos. add one extra space to every space and dcrement xtra untill xtra is zero.
Sure I repeat
while(true){
Question is NOT clear
}
LOL
Question is NOT clear... I repeat NOT CLEAR
- loveCoding August 09, 2012@Cobra Answer for 1/97 should be 0.(010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567).
Answer for 127775 / 50000 should be definitely 2.5555
You got it right Sanjay
- loveCoding August 08, 2012Here is the algorithm divide(A,B)
1. if A>B , Just add A/B to the soFar String and call the divide(A%B,B)
2. if A<B A = A*10 and add "." to the soFar String if it does NOT already have it. Now if A is still less than B keep multiplying A by 10 while(A<B) for each multiplication now we need to append a "0" to soFar String
3. In step 2 we will add A in Hashtable and store the length of soFar, This is to make sure when we see this again in future we will stop the execution and return the Result.
I know Hard to explain in words so below is the Working/Tested Code
public static String divideIterative(int A, int B) {
StringBuffer soFar = new StringBuffer("");
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
if (A == 0)
return soFar.toString();
while (A != 0) {
if (A >= B) {
soFar.append(A / B);
A = A % B;
} else {
if (soFar.indexOf(".") == -1) {
if (soFar.length() > 0)
soFar.append(".");
else
soFar.append("0.");
}
if (map.containsKey(A)) {
int index = (Integer) map.get(A);
return soFar.substring(0, index) + "("
+ soFar.substring(index) + ")";
} else {
map.put(A, soFar.length());
}
A = A * 10;
while (A < B) {
A = A * 10;
soFar.append("0");
}
}
}
return soFar.toString();
}
The complexity can be 2*logn first to find the number then next binary search to find the first instance
- loveCoding August 06, 2012@amitmsingh Inorder traversal of that tree would be 2,3,3,4,5,5,8,8,8,10,10. Tell me if you cant calculate no of duplicates with this.
- loveCoding August 02, 2012Just do Inorder Traversal and count the Duplicates as Inorder will give you sorted order so you just need to compare currentValue with last value.
- loveCoding August 02, 2012I think the whole purpose here is to minimize the calls to multiplication function... and to know that we need DP.
For e.g say we need to find A^11... you solution will call Multiplication 5 times whereas the optimized way to solve this would be to call mult 4 times
This is dynamic programming where we need to find minimum steps to n.
- loveCoding July 27, 2012MIN HEAP. MIN HEAP.. MIN HEAP
- loveCoding July 23, 2012It can be done using Dynamic Programming, We will start with bottom right point and build it up.
- loveCoding July 23, 2012Not possible. If you find one You can earn billions.
- loveCoding July 23, 2012Is m given to be some value b/w 1 to 27?
- loveCoding July 23, 2012This is a pessimistic approach. First we need to see if this is really interrupting user and what about users who wants these features desperately. But I agree it is an open ended question so there is NO right or wrong answers for it.
- loveCoding July 22, 2012Log n is definitely not possible as you will have to go through the whole string at least once to know the character is unique.
- loveCoding July 21, 2012I would first try to find out why the problem is there.
Once I understand the problem, I would try to see if there is any feasible solution.
If there is an easy solution that can be done in a day or two, I would have my team fix it and release a new build after testing.
If there is a hard solution that may take month(s), I would try to figure out what feature caused this issue. If I can identify a particular feature, I would revert that feature and release a new build to customer and later on work on to fix that Issue.
Lastly I would ask developers to be more careful in coding so that these things wont happen again.
Worst case will always be O(n^2).... Unless some range is mentioned for input array.
- loveCoding July 19, 2012You are a PIG.
- loveCoding July 18, 2012@niteeshm I think you commented on wrong post
- loveCoding July 18, 2012Here is the simple way of doing this
1. Find out lengths of both lists(Say List A and List B). This can be done in O(n)
2. Say lengths are a and b where a>b Now for for the bigger list traverse the node to next for (a-b). That if a is 10 and b is 8, Go to next node for List A twice,
3. Now start comparing the nodes one by one, when they are equal it is the merge point
So overall complexity is O(n)
Going to parent will be expensive(Unless yiou modify a Tree to have parent pointer)..... We Should to use stack to first find out the path (i.e. without "." and "..") once we have the path we can follow Tree to go to the correct directory
- loveCoding July 18, 2012We can use min heap of size k. element at the leaf will be kth largest.
- loveCoding July 18, 2012Stop posting fake questions.
- loveCoding July 18, 2012Executer is kind of Theread Pool which keeps the number of thread in a process finite. It is very efficient as it controls process creating too many threads.
- loveCoding July 17, 2012There is no O(N) and constant space solution for this.
The best with constant space can be O(nlogn)
When you have public constructor.
- loveCoding July 17, 2012lol
- loveCoding July 13, 2012They completelely Different except the List word :)
- loveCoding July 13, 2012First you need to find a duplicate.
- loveCoding July 13, 20121) When ever you find a duplicate replace it with root element
2) Now delete the last node in heap and replace its value with root element(which is actually duplicate)
3) Now run heapify.
I am NOT sure why people are advertizing there videos on this WebSite.
- loveCoding July 12, 2012We can use Quick Sort, At every time we place a player such that who lost goes to left side and all who won, go to right side we can do it recursively.. Complexity O(nlogn).
Note we cannot use Merge Sort or any other Sort as in this situation is a1>a2 and a2>a3, it does NOT mean a1>a3.
I can only see exponential solution for this
below is explanation
1) For <i,j>, there are 4 possibilities <i-1,j>,<i+1,j>,<i,j-1>,<i,j+1>
2) Maintain a set for already traversed Pairs, If that alreadu exit dont explore that path
3) Now for each possiblity check if its word print the word and continue, If not word check if it is prefix, if thats true then continue else we ignore that path.
Sort it in nLogn and then it can be found in )(n). So the total is )(nlogn).... Can we do better?I dont think so
- loveCoding July 12, 2012It is just like a restricted Permutation. Below is the Code.
public static void printInterleavings(String s1,String s2){
printInterleavings(s1,s2,"");
}
public static void printInterleavings(String s1,String s2,String soFar){
if((s1==null||s1.length()==0) && (s2==null||s2.length() == 0))
return;
if(s1==null || s1.length()==0){
System.out.print(" " + soFar + s2 +" ");
return;
}
if(s2==null || s2.length()==0){
System.out.print(" " + soFar + s1 +" ");
return;
}
printInterleavings(s1.substring(1), s2, soFar + s1.charAt(0));
printInterleavings(s1, s2.substring(1), soFar + s2.charAt(0));
}
Where is the answer for this question
- loveCoding July 11, 2012Haha
- loveCoding July 10, 2012String type in Java is Immutable i.e. if you do any operation it creates a new string. So if dealing with large number of Strings using StringBuffer is a better alternative.
Storing :: We can store strings in a trie.
it will be (nlogn)
- loveCoding July 06, 2012No
- loveCoding July 06, 2012
Sorting would do it in O(nlogn + n) which is O(nlogn)
- loveCoding August 30, 2012