tryingtolearn
BAN USER@chrisk thanks for pointing out the problems with offset approach, I did not take into account at all, I would have to calculate carefully the sum, or consider mapping of ranges for dp as you suggested thanks again
- tryingtolearn September 08, 2017@chrisK, as always thanks for your detailed response :), I was also concerned about which subset to chose, the problem does not say minimization but being FB interview question it may be implied like you suggested. The only reason I sorted because, we don't have to consider elements greater than index i, for subset problem and you are right, it won't improve that much but it won't hurt either.
- tryingtolearn September 08, 2017@chrisk, I could be wrong or else some else has similar but robust logic above code snippets submitted, can you please let me know if you think this will work
1) find max negative number and offset with his value so that all numbers are positive or zero
2) Sort the numbers
2) iterate i from 1 to n-1
perform perfect sum problem with (0, i-1) with sum = nums[i] , using dp this costs O(n * sum) to calculate subsets, (If there are duplicate sums, I am not sure if first one or longest one to pick to mark as removed along with ith index, may be this decision may result in np complete like you said)
the numbers that remaining, count is the answer, it will take it O(n^2 * sum)?
@johanson1, thanks for pointing out what I missed (if cell neighboring has like wise state, my code has to check it is not captured as well which is recursive in nature), sorry for my incorrect answer, I will try out dp approach with some memorization to solve it, thinking about it see O(n^2), but may be I am wrong, I will try to work it out, thanks again
- tryingtolearn September 07, 2017@makarand beautiful answer, thanks for sharing
- tryingtolearn September 07, 2017Sorry if I misunderstood, the question, it seems fairly straight forward from description, here is some pseudo code
bool IsCaptured(int x, int y) {
if(x < 0 || y <0 || x >= state.GetLength(0) || y >= state.GetLength(1))
{
return false;
}
// or single cell
return true
var currentState = state[x,y];
if(x -1 >=0 && state[x-1, y] == currentState or empty){ return false;}
if(y -1 >=0 && state[x, y-1] == currentState or empty){ return false;}
if(x + 1 < state.GetLength(0) && state[x + 1, y] == currentState or empty){ return false;}
if(y + 1 < state.GetLength(1) && state[x, y + 1] == currentState or empty){ return false;}
}
May be some one has better idea, just thinking out loud,
This can be done using dynamic programming, set totalMinSteps to In32.maxValue
a) a knight has 8 directions to go from any position,
b) we try out 8 ways till we hit destination point,
c) once we get there we can totalMinSteps = k, at any point if we hit more than steps, we can simply to In32.MaxValue from the initial location to terminate the search
Space complexity is O( 8 * 8), where each location will have total number of steps to reach destination, Most locations will have Int32.MaxValue indicating that some path already found a minimum possible way to get to destination
@Chrisk thank you so much for the clarification , I also appreciate your clear explanations for questions on this site, most of the time, it helps me understand the posted question and understand an approach to solve the question. thanks again.
- tryingtolearn August 09, 2017I am confused, the question mentions the distances are given in random order, lets say
scenario 1) a-0, b-10, c-30
ab =10, ac = 30, bc =20,
scenario 2) a-0, b-20, c-30
ab =20, ac = 30, bc =10,
but 10, 20,30 are common in both scenarios, how can we find correct solution ? can some one help me understand this? thank you
I am not sure this optimal or not,
1) we can construct graph from list of routes
2) then use Dijkstra's algorithm when he hit end, we stop the algorithm as Dikstra's gives shortest distance from start to all vertices but we just need till end here,
May be there is much easier way than what I wrote here :)
@petrov4feedly, thanks for providing optimized version without memorization,a minor bug that I see,
for e,g -3, -2 , -1 int curr = box2 + boxes[i]; this needs to be changed to int curr = max(box2 + boxes[i], boxes[I]))? or else your solution gives out -2
@Chrisk, thank you for pointing out, my recursion is wrong. I apologize I wrote it without thinking though. I have a question in your solution
print(maxboxes([8,1,-1,2,2,10])) # should be 18, should not this be
20, { 8,2, 10} =20?
this dynamic programming problem
f(m) is max value at index m
f(m) = max{ f(m-1) +value(m), f(m-1)}
can we flip dijkstra's algorithm instead of calculating single source shortest path, we can find single source longest path using max heap instead of min heap?
- tryingtolearn March 08, 2017@BenC, if you have preorder of 5 4 2 1 3, both 1 and 3 are leaves, but only 3 gets printed in your algorithm?
- tryingtolearn February 28, 2017
@abouads I think if the only contains only parenthesis, it may not be possible to use stack as in worst case scenario half of the file is on stack, I am not sure if it is allowed
- tryingtolearn December 14, 2017