aka[1]
BAN USER- 3of 7 votes
Answersgiven an input array of integers where each integer represent the maximum amount of jump a frog can take.Frog has to reach the end of the array in minimum number of jumps.
- aka[1] in United States
Example:[1 5 4 6 9 3 0 0 1 3] answer is 3 for this.
[2 8 3 6 9 3 0 0 1 3] answer is 2 for this.
Any DP solution for this?| Report Duplicate | Flag | PURGE
Amazon Applications Developer Algorithm
Recursive solution makes sense along with backtracking. So basically pick the character from a pool of largest character. Put it at 0th index and then recurse. In the recursion check the previous character and see if the previous character is same if same then pull the any different character and put in the current index. Recurse for the next state and do the same. Base cases is when you don't have any characters or when you have lot of same characters or same characters size is more than half the length of the string.
- aka[1] October 10, 2015Same concept as LCS(longest common sub sequence):
#include <stdio.h>
int max = -1;
int maximum(int a, int b)
{
return a>b?a:b;
}
int foo(char *target, char *a[10], int i, int j, int size, int cost)
{
if (i >= size) {
if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
return foo(target, a, i+1, 0, size, 0);
}
printf("%s\n", a[i]);
return 0;
}
if (j >= strlen(a[i])) {
if (cost+abs(strlen(a[i])-strlen(target)) > 1) {
return foo(target, a, i+1, 0, size, 0);
}
printf("%s\n", a[i]);
return 0;
}
if (a[i][j] == target[j]) {
return foo(target, a, i, j+1, size, cost);
} else {
return foo(target, a, i, j+1, size, cost + 1);
}
}
int main(void) {
char *s = {"banana"};
char *a[10] = {"bana", "apple", "sanana", "banaba", "bonanza", "banamf"};
printf("%d\n", foo(s, a, 0, 0, 5, 0));
return 0;
}
Let p[steps] be the minimum penalty to reach "steps", same goes for q[steps] which runs in parallel.
So we can write recursive solution as:
p[steps] = min(p[steps-1]+p1, q[steps -1]+q1)
where p1 is the penalty for moving 1 step from previous step to current step.
and q1 is the penalty for moving 1 step across from previous step to current step.
We can write similarly for q[steps].
In the end, to reach the top we have to probably go to some common step:
minimum penalty = min(p[steps-1]+p1, q[steps-1]+q2)
where q2 is the penalty for moving in 'q' staircase from previous to current step.
sort the input set according to finish time in monotonically non-decreasing order.
Basically it is greedy algorithm where we are making sure that finishing time of
the set should be the least so that we can get the maximum non-overlapping intervals.
You can read more on this in "Introduction-Algorithms-Edition-Thomas-Cormen"
Take the finishing time of first set and compare that with rest of the set. If any other set is compatible i.e. starting time is more than finishing time
of first set then add to result. Now make the compatible set as current set and do the same.
's' is array of starting time and 'f' finishing time
func(s, f)
{
n = s.length
A = a1
k = 1
for (m =2 to n) {
if (s[m] >= f[k]) {
A = A union { a[m] }
k = m
}
}
return A
}
he wanted to see if you can imagine character array as block of integers or not ?
As you know how to count number of set bits in a integer you just have to pair 4 integers together out of character array and apply the same old question "how to count number of set bits in a integer"
basically recurrence relation should be written with a possible explanation but @anonymous doesn't get it.
recurrence relation:
let f(n) be the least number of square which sum up to the given number "x".
f(n) = min(f(n), f(n-p)+1) where p can go up to max of sqrt(n).
so f(3) = min(f(3), f(3-1)+1)
f(3) = min(f(3), f(2) + 1)
where f(2) is 2
so f(3) = 3
we can calculate the value of any other 'n' with this recurrence relation.
same logic in c though:
#include <stdio.h>
int a[100];
int i=0;
void foo(int size, int i)
{
if (size < 0)
return;
if (size == 0) {
int j;
for (j=0;j<i;j++)
printf("%d", a[j]);
printf("\n");
return;
}
a[i] = 1;
foo(size - 1, i+1);
a[i] = 2;
foo(size - 2, i+1);
}
int main(void) {
foo(4, 0);
return 0;
}
generic solution for any number with infinite supply:
int foo(int *a, int sum,int size)
{
int i;
if (sum == 0)
return 1;
if (sum < 0)
return 0;
for (i=0;i<size;i++)
if (foo(a, sum-a[i], size))
return 1;
return 0;
}
int main()
{
int i;
int a[] = {7, 8};
printf("%d\n", foo(a, 18, SIZE(a)));
printf("%d\n", foo(a, 19, SIZE(a)));
printf("%d\n", foo(a, 20, SIZE(a)));
printf("%d\n", foo(a, 21, SIZE(a)));
printf("%d\n", foo(a, 22, SIZE(a)));
return 0;
}
do you need the sum to be propagated to the right? I think sum should be propagated to the parent of the left node i.e. sum of both left and right subnodes.
eg:
before:
5
2 6
1 3
after:
11
3 6
1 3
As you can see the parent of 2 should get the entire sum of the left and right subnodes not 3 in the "before" bst.
Most probably he means in the increasing sequence as below:
between 100 and 145:
112, 113, 114, 115, 116, 117, 118, 119, 123, 124, 125, 126, 127, 128
basically individual digits of a number in the increasing order but this is just a guess. However people interested can solve this :)
Think of this as a graph problem.
example: -1, 5, -2, 0
1. Make a graph with nodes equal to number of elements in the array.
2. Connect the edges in this way: -1 can connect to -2 and 0 so there will be a outgoing two outgoing edges to -2 and 0.
Same goes with other nodes i.e. 5 node will be connected to 0 using only one outgoing edge.
3. Once you have the graph ready then nodes values will be equal edge weights.
4. for_each_node {
target = 0 (end of array element)
start = current_node
longest_path = max(longest_path, find_longest_path(graph))
}
return longest_path
We can use BFS to get the solution as below:
[1 5 4 6 9 3 0 0 1 3]
We need to make a Directed acyclic graph for this array and then all we need to do is to find out the minimum number of hops till we reach the destination which is 3 in this case.
Anyway if someone can post a DP solution with clear explanation that would be great.
Sorry it won't work. Please try your logic for the string "abc". You also need to maintain dictionary of "seen" elements. BFS is what you are looking for.
- aka[1] January 23, 2016