CodeBoyS
BAN USERBorn 2 Code
@Supersonglj
while( (currSum > reqSum) && (p3>p2) )
{
--p3;// do --p4 only if( (p2+1 == p3) && (currSum > reqSum))
}
why i think p3 should be decremented and not p4 is because:
the array is sorted initially, lets consider following array:
[.... 7,8,9]
currently if p4 points to 9 and
p3 points to 8;
the next biggest sum which is lesser than 8+9 would have to be 7+9 and never 7+8.
since 7 is definitely going to be considered next, we have to decide which number to remove either 8 or 9. since removal of a smaller numnber(in this case 8) would give us a number closer to the previous biggest sum, we choose to decreemtn p3 and not p4.
@Sriram:
ur soln will not work.
It will fail for the follwing input[{]}.
Every closing bracket should match the previous opening bracket.
*the soln is to use a stack
*and push every opening bracket into the stack,
*and every closing bracket should pop from the stack
*the closing bracket should make a pair with the popped value from stack
*at no time the stack should go negative.
*at end the stack should be empty.
if the sorted array with duplicates. i.e. 1 2 2 3 4 4 5 6 7 7 7 8 9 etc. is given.
we should atleast be given tat the elemts are ranging from 1 to n, wher all the numbers between 1 and n are present.. then we can do binary search, calculate wat number to expect in the middle, if that number is lesser than wat is expected, then the left half needs correction. based on this we can come up with some method to skip some numbers, which will make it less than O(n).
How come MS asked such a simple question??
Anyways for guys with doubts, I ran the program and confirmed it.
It prints 3 5 7 11 13.
i.e.from the left it prints
the sum of 1 digit, 3
the sum of 2 digits, 3+2=5
the sum of 3 digits, 5+2=7
the sum of 4 digits, 7+4=11
the sum of 5 digits, 11+2=13
in case of stack frames being too big, which happens if we try declaring too many automatic variables which exceeds the default stack size for the thread, stack overflow occurs. so for each thread we can keep track of total size of automatic variables allocated and check if its less than the stack size for the thread.
we can also make the variables static to avoid stack overflow.
Store the blocks in the form of a n-ary tree structure. ( i.e. every sub block of a block stored as a child).
1.Initially a block( say Block1) is locked.
2.Next when another block( say Block2) needs to be locked, find the common ancestor(say Block3) of Block1 and Block2.
3. If (Block3==Block1) or (Block3==Block2)
then dont grant lock to Block2.
else
grant lock to Block2.
I can think of one solution.
1. Run through the list and find the MAX. TC = O(n).
2. Create a vector with size MAX and initialize to 0 or something else. SC = O(MAX)
3. run through the original array and using value of each element in the array as the index for your vector , set the vectors value to 1. TC = O(n)
4.Now run through the Vector and store the elements back in the array who's values are set to 1. TC= O(MAX)
So total Time complexity is = 2O(n) + O(MAX) ~= O(n)
So total Space complexity is = O(MAX)
@SupersongLj:
- CodeBoyS August 29, 2011thanks for pointing it out.
then the algo will have to a bit more complex,
after reaching 1,2,4,32. we'll need to increase the sum.
since p2 and p3 are already next to each other we'll have to increment p3, which gives us the soln.
if 8 were replaced by 9, then we would end up in an infinite loop. we'll need some exit condition. may be something like p2 and p3 shouldn't be adjacent more than once. haven't thought it through, just a vague idea.