loveCoding
BAN USERIf you cant explain the logic, There is no point putting your answer here.... downvoted for no explanation
- loveCoding July 06, 2012I think they meant O(n).... You can do first pass of array to store all positives and -ves in two tem arrays and now do a second pass to copy these into original first +ves and than -ves
Time O(n)
Space O(n)
What is the question? Please elaborate
- loveCoding July 04, 2012This is completely wrong
- loveCoding July 03, 2012Static synchronize will lock on class i.e if this method is executing none of the other intances will be able to execute any synchronized method.
- loveCoding July 03, 20128 races. 6 races to find the first place and after that for next i.e. Second we need one more and so on
First take 5 sets of 5 horses. Notice the position of each group horces. Now take top five horses say A1,B1,C1,D1,E1... now with one race we can know the top horse lets say its B1, Now choose B2 and have a race between A1,B2,C1,D1,E1..... now we need another race to know the second position. Similarily we can find the third one in 1 more race Sp total races are 6(to determine 1st place) + 1(to determine 2nd) + 1(to determine (3rd), So total of 8 races
I dont see any oop in the above code
- loveCoding July 02, 2012Say all tokens are allocated and now token no. 1002 is freed, how will you reallocate this token?
- loveCoding July 01, 2012downvoter care to explain?
- loveCoding June 27, 2012No we cannot.
- loveCoding June 27, 2012There can be maximum of [N/2] matches per day.(here N/2 is int devision i.e 3/2 is 1 and 5/2 is 2)
Total number of matches possible are N*(N-1)/2. Since this is uniform distribution we can always choose max of N/2 matches each day. Below is the code (for clarity run the below code)
static void scheduleMatches(int N){
if(N<=1)
return;
int totalMatches = N*(N-1)/2;
int MAX_MATCHES_IN_DAY = N/2;
int days = 0;
int[] a = new int[N-1];
for(int i=0;i<N-1;i++)
a[i] = i+1;
while(totalMatches!=0){
int j=0;
int num = MAX_MATCHES_IN_DAY;
System.out.print("\n Day " + (days+1) + " Matches :");
while(num!=0){
// Check if team j has played all the matches
if(a[j]<N){
int matchnumber = N*(N-1)/2 - totalMatches +1;
System.out.print("Match " + matchnumber +": " + "Team " + (j+1) + " Vs Team " + (a[j]+1) + " ");
a[j++] += 1;
totalMatches--;
num--;
}else
j++;
}
days++;
}
System.out.println("\n Total Number of Days is " + days);
}
Look at the code now
- loveCoding June 23, 2012Hey eugene.yarovoi.. please look at the implementation... you misunderstood my reply
- loveCoding June 23, 2012The solution is as follows
1. Create one method RevBiased which will return opposite
2. now create one function goodrandom() -> call biased and revbiased if they are equal return that value if not call goodRandom recusively.Probability of both 1 or both 0 is P(1-P) hence probabilty of 0 and 1 is 0.5.
{
int goodRandom(){
int i = biasedRandom();
int j = RevbiasedRandon()
if(i == j)//Probability of both 1 or both 0 is same i.e. is P(1-P)
return i;
return goodRandom()
}
int RevBiasedRandom(){
int i = BiasedRandom();
if(i==0)
return 1;
else
return 0;
}
This is NOT correct. That way we will have a string like " edcba" which is NOT correct as "cba" is NOT subsequence of "abc"
- loveCoding June 22, 2012Lets say bangalore population of that particular area is 5 lakhs (I am not sure though-- dont tell this to interviewer :-)) ,.. Now lets say there are 5% auto drivers --- so its total of 1/4 lakhs and our of those 50% are travelling so its totral of 1/8 lakhs i.e. 12,500.....
- loveCoding June 14, 20121000^3 small cubes if you need solid
1000^3 - 998^3 if you need hollow
1. Your toothpaste will come in 4 flavors and you can choose flavor by pressing a button.
2. It will be connected to internet and ordered automatically from a grocery store when finished and will be configurable if you want to say order 1st day of a month
3. Many more tell me if you want more?????
Why you need buf[100] in your solution?
- loveCoding June 13, 2012IT WORKS PLEASE TEST IT YOURSELF
- loveCoding June 13, 2012it can be done in O(log n)
- loveCoding June 13, 2012it can be done in O(logn)
- loveCoding June 13, 2012Look at my solution
- loveCoding June 13, 2012public static void printAllCombinations(int N) {
printAllCombinations(N, "");
}
public static void printAllCombinations(int N, String prev) {
if (N == 1) {
System.out.println(prev + " " + N);
return;
}
if (N == 0) {
System.out.println(prev);
return;
}
boolean rep = false;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < prev.length(); j++) {
char c = prev.charAt(j);
if (c != ' ' && i > c - '0')
rep = true;
;
}
if (rep == false)
printAllCombinations(N - i, prev + " " + i);
}
}
are you OK? why you need all this?
- loveCoding June 13, 2012We have to parse the data at least once, so no choice. The whole point of pre-processing is to reduce lookup time and thats what we achieved.
I am sure that was the answer interviewer would be expecting. Thats why he specifically mentioned "he could call the function every second with input 11:05:20, 11:05:21,11:05:22, 11:05:23..........14:30:30".
Let me give a completely different strategy... Assuming N is very large million or billion
Assume time is between 00:00:00 and 23:59:59
Since we want to optimize the lookup time , we need to preprocess data.
below is the strategy to have constant time for lookup...
1. initialize an array with 86400 elements and all elemets are 0
2. Now for every element b/w starttime and end time, increment the array by 1, for e.g for 00:00:00(Start) and 00:00:59(End) array index 0 to 59 are all incremented by 1.
3. Do this for all entries.
4. Now to look at the people present in office just refer to array index (CONSTANT TIME)
Do a BFS... At every point print first and last Node. Except last where you will priont the whole Queue. Although order will be little different then you mentioned but even that is easy to format by maintaining the list of border nodes instead of printing right away.
Time complexity o(n) space complexity is O(log n)
answer is b
- loveCoding April 05, 2012@code756 it takes care of that with condition
if(open>close) at top of the method
calculate Sum of all page num. now subtract from n(n+1)/2... answer is missing page num
- loveCoding March 06, 2012Thanks. You are right!!!!!!!
- loveCoding March 06, 2012Design simple stack with one variable called min to track variable. I am supposing we dont need deletemin functionality
- loveCoding March 05, 2012We can achieve this in NlogN. here is the approach
1. Start with the middlle column and look for any zeros
2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.
Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0
Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes
We can achieve this in NlogN. here is the approach
1. Start with the middlle column and look for any zeros
2. If we find zeros it means we have to look in the left half
3. If no zeros found it means we have to look on the right half
4. Now do step 1,2 and 3 untill we have only one or two columns left.
Here is the example
1--1--0--0--0
1--0--0--0--0
1--1--1--0--0
0--0--0--0--0
Now for step 1 start with 3rd column, We found zero Now take the left half i.e matrix col(1,2,3)
again we will have a look at middle column i.e. row-2 we found zero again, so now we move to left again i.e. col(1,2)
Now we can check row 1 if we found zero i.e. row with max zeros, If not look at row 2 and find zero and that is the row with max zeroes
static void printParenthesis(int n){
printParenthesis("",n,n);
}
static void printParenthesis(String s,int open,int close){
if(open>close)
return;
if(open == 0 && close == 0){
System.out.println(s);
return;
}
if(open < 0 || close<0)
return;
printParenthesis(s + '{',open-1,close);
printParenthesis(s + '}',open,close-1);
}
Go Through the array and count number of zeros(say it countZeros). Now go through again and set it to zero till index countZeros-1. remaining array should be 1.
TC O(n)
space complexity : constant
Can you tell me what get_any_number exactly is?
More specifically does it delete the number from DS
BitVector wont work as we need to delete number and if there are two identical numbers added and one deleted.
So we need to use int array.
Use int array of 1000, where index0-represents 1 and index-999 represnts 1000.
Add just increase the array value by 1
Delete just decrease the array value by 1
Search just check if array[number-1] >0
Get any number is similar to search
static void printConsecutive(String str){
if(str==null || str.length()<=1)
return;
str = str.toLowerCase();
StringBuffer temp = new StringBuffer();
for(int i =0;i<str.length();i++){
if((temp.length()==0) || ((temp.length()>0) && (str.charAt(i) - temp.charAt(temp.length()-1) == 1)))
temp.append(str.charAt(i));
else{
if(temp.length()>1){
System.out.println(temp);
}
temp.delete(0, temp.length());
temp.append(str.charAt(i));
}
}
if(temp.length()>1){
System.out.println(temp);
}
}
@bdeesh what is that?
- loveCoding February 01, 2012We can do it by bit logic (E,g, a=4 b=10)
1. Calculate difference b-a (for given e.g. 6)
2. Now calculate ceil(log(b-a+1)(Base 2)) i.e. no of bits required to represent all numbers b/w a and b
3. now call random(0,1) for each bit. (for given example range will be b/w 000 - 111)
4. do step 3 till the number(say num) is less than or equal to 110 i.e. we need only 7 levels since b-a is 6.
5. return num+a.
We can do it in O(n) and constant space
1. for every element calculate index = Math.abs(a[i]) -1
2. check the value at index
a. if it is +ve, multiply by -1 i,.e make it -ve.
a. if it is -ve return (index+1) i.e. the value thats repeated.
What is the question? What we have to do?
- loveCoding January 30, 2012I am assuming two trees are same if all the nodes are same with same left/right childs.
Now start with root of both.
Compare roots IF equal, compare left and right and do this recursively.
boolean isSame(Node root1, Node root2){
if( (root1==null && root2!=null) || (root2==null && root1!=null))
return false;
if(root1 == null && root2 == null)
return true;
if(root1.data == root2.data)
return(isSame(root1.left,root2.left) && isSame( root1.right,root.right));
return false;
}
I think the question said we need to store polynomial after the sum.
Initial polynomial can be given as string /array of objects etc.
This is very open ended
We can make hash of polynomials where index is used as key.
In that case for addition, we just need to update hash which can be done in constant time.
We can build two strings one with every first letter of the String(strFirst) and second with every last letter of the String(strLast).
Now check if strFirst is a rotation of strLast.
If true chain is possible else NOT.
How did you get "r^2=2*(r+1)" Explain
- loveCoding July 06, 2012