Dinesh Pant
BAN USER- 0of 0 votes
AnswersGiven array of ball size we need to return the sum of shadow balls
- Dinesh Pant in India
For example
7 3 2 8 1
shadow ball of 7 ---> 3, 2, 1
shadow ball of 3 ---> 2, 1
shadow ball of 2 ---> 1
shadow ball of 8 ---> 1
Output ---> 3+2+1+1 --> 7
Complexity should be better than 0(n^2)| Report Duplicate | Flag | PURGE
Microsoft SDE-3 Algorithm - 1of 1 vote
AnswersThere are discounts on particular time period
- Dinesh Pant in India
suppost
Day1 - Day5 => 10%
Day2 - Day 8 => 5%
Day4 - Day6 => 20 %
find the period where maximum discounts is available.
For above example the period is Day4 - Day5 => 10+5+20
that means 35%
Provide the generalize solution. Period can be time also.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
Hey consider the same graph. Now 1 is connected to 2, 3, 4, 5. And 2 is connected to 3 and 5. Now if input is 1 then what will be the output. Are we considering the directed graph here?
- Dinesh Pant April 13, 2016Hey..this will break if left subtree has height 3 and right subtree has height 5 and the input node is depth 5 node. Your loop will never go to depth 5.
- Dinesh Pant December 14, 2015The worst case will be O(N) because you are not travelling only path. Suppose first time you chose the left node but the depth of the node is h-2 that means the if your input node is in height h then you should chose the right node first.The way you solve is using recursion. That will end up using O(N) in worst case.
- Dinesh Pant December 14, 2015This solution is not generic...days could be replaced by time or some decimal values..
- Dinesh Pant April 26, 2015Create a min heap of size N. Insert the number in them. Every time before inserting the number check whether it is greater than the min number from heap it is then replace it with current number and call heapify. Complexity : O(count of numbers) Storage O(N)
- Dinesh Pant April 26, 2015Its a copy of getting change of coins....can be solved using dynamic programming
public static int findNumber(int amount, int[] coins)
{
int[] result; // to store the result for all amounts
int[] mySol; // temporary store the results for an specific amount with all coins
result = new int[amount+1];
mySol = new int[coins.length];
result[0] = 0;
for(int j=1; j<=amount; j++) //This for loop will calculate for all amount till given amount
{
for(int k=0; k<coins.length; k++)
mySol[k] = -1; // store all coin values as -1
for(int k=0; k<coins.length; k++)
{
if(coins[k] <= j)
{
mySol[k] = result[j-coins[k]] + 1; // Store result with one specific one coin and value of pevious amount
}
}
result[j] = -1;
for(int k=0; k<coins.length; k++)
{
if(mySol[k] > 0)
{
if(result[j] == -1 || mySol[k] < result[j])
result[j] = mySol[k];
}
}
}
return result[amount];
}
Code is wrong..
Suppose we have following list
a -> b -> c -> d
After first while loop it will be
b-> null -> c-> d
Third time loop will not execute..
Sort the array in ascending order
Array.sort(inputArray);
Once sorted traverse the array for modifications and swap every two elements in the following logic
for(i=1; i<inputArray.length-2; i=i+2)
{
int temp = inputArray[i];
inputArray[i] = inputArray[i+1]
inputArray[i+1] = input Array[i]
}
This will result the array in required output. Please correct me if I am wrong.
I think we should not look for 0(n) scan...because for 0(n) we can store the elements in normal array and can get the element in just 0(n) time...We can do it in BST with logn complexity..
- Dinesh Pant September 26, 2013comparision can always be done...override the method and give normal trivial comparision criteria....
- Dinesh Pant September 20, 2013check the string length divide it by two then sum it up...if sum is same then append 12345 in starting...It should not be this much simple....please clarify the constraints in the problem...
- Dinesh Pant September 19, 2013First compare with the first element of n/2 row so we will be able to eliminate half matrix then compare first element of n/2 column. After these two operations we will get 1/4 th matrix...so using this way we will get the solution in O(log n) complexity. Please correct if i m wrong...
- Dinesh Pant September 13, 2013Every thread will get its own copy of string builder object and java works as pass by value ...so reference will not get changed....Please correct if i am wrong
- Dinesh Pant September 13, 2013This means u need to exclude the intersecting element of two diagonals
- Dinesh Pant September 13, 2013
I feel, example is wrong. x=233614 should return 23314.
- Dinesh Pant August 02, 2016