[algogeeks] Re: Amazon interview Question (Array yet again!)
ya exactly..dp solution is working...
On Sep 5, 7:28 am, Gene wrote:
> I just figured out you are running the first (incorrect) greedy
> algorithm I tried. Please try the DP. It works fine.
>
> On Sep 3, 2:18 pm, Discover wrote:
>
> > @gene: nice solution..
>
> > but it's not working for a[]={20,22,13,11};
>
> > ur code will give soln : 24
> > but ans should be: 22 {11,11,11,11}
>
> > pls correct me if i m wrong
>
> > On Aug 28, 8:26 am, jagadish wrote:
>
> > > @Gene: Thanks alot! :-) your solution works like charm!
>
> > > On Aug 28, 7:09 am, Gene wrote:
>
> > > > This is a nice problem. It looks like a trivial matroid, so a greedy
> > > > algorithm will work fine. The obvious greedy algorithm is to work
> > > > left-to-right and incorporate elements into the sorted order one-by-
> > > > one. In each case, you have 2 choices. The first is to decrement
> > > > elements to the left by the amount needed to restore non-decreasing
> > > > order. The second is to delete the new element. The cost of each is
> > > > easy to calculate. Pick the choice with least cost and continue.
> > > > This algorithm is O(n^2). There may be a faster way to do it, but I
> > > > can't see one.
>
> > > > #include
>
> > > > int make_nondecreasing(int *a, int n)
> > > > {
> > > > int i, j, dec, dec_cost, total_cost;
>
> > > > total_cost = 0;
> > > > for (i = 0; i < n - 1; i++) {
>
> > > > // If we find a decrease...
> > > > if (a[i] > a[i + 1]) {
>
> > > > // Find cost of decrementing all to the left.
> > > > dec_cost = dec = a[i] - a[i + 1];
> > > > for (j = i - 1; j >= 0; j--) {
>
> > > > // Find decrement that would be needed.
> > > > dec += a[j] - a[j + 1];
>
> > > > // If no decement, we're done.
> > > > if (dec <= 0)
> > > > break;
>
> > > > // Count cost of decrement.
> > > > dec_cost += dec;
> > > > }
>
> > > > // Compare decrement cost with deletion cost.
> > > > if (dec_cost < a[i + 1]) {
>
> > > > // Decrement is cheaper. Do it.
> > > > for (j = i; j >= 0; j--) {
> > > > if (a[j] > a[i + 1])
> > > > a[j] = a[i + 1];
> > > > }
> > > > total_cost += dec_cost;
> > > > }
> > > > else {
>
> > > > // Deletion is cheaper. Do it.
> > > > total_cost += a[i + 1];
> > > > for (j = i + 1; j < n - 1; j++)
> > > > a[j] = a[j + 1];
> > > > --n;
> > > > }
> > > > }
> > > > }
> > > > return total_cost;
>
> > > > }
>
> > > > int main(void)
> > > > {
> > > > int a[] = { 14, 15, 16, 13, 11, 18 };
> > > > //int a[] = { 4, 3, 5, 6};
> > > > //int a[] = { 10, 3, 11, 12 };
> > > > int cost = make_nondecreasing(a, sizeof a / sizeof a[0]);
> > > > printf("cost=%d\n", cost);
> > > > return 0;
>
> > > > }
>
> > > > On Aug 27, 12:15 pm, jagadish wrote:
>
> > > > > You are given an array of positive integers. Convert it to a sorted
> > > > > array with minimum cost. Only valid operation are
> > > > > 1) Decrement -> cost = 1
> > > > > 2) Delete an element completely from the array -> cost = value of
> > > > > element
>
> > > > > For example:
> > > > > 4,3,5,6, -> cost 1
> > > > > 10,3,11,12 -> cost 3
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Simple reVerse
@shravan : but strrev() is using a while loop...
On Sep 4, 12:26 pm, Shravan wrote:
> int reverse(int x)
> {
> char a[20];
> int r;
> sprintf(a,"%d",x);
> strrev(a);
> r=atoi(a);
>
> return r;
>
> }
>
> On Sep 4, 12:01 am, albert theboss wrote:
>
>
>
> > if input is 12345
> > then the output should be 54321
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon interview Question (Array yet again!)
nice explanation gene :)
On Sep 2, 8:35 am, Gene wrote:
> Okay. First, you can make the DP more efficient than the one I gave
> earlier. You don't need to scan the whole previous column when
> calculating costs of decrementing. Rather there are only two
> possibilities.
>
> I will add that rahul patil's solution looks correct, but it's
> exponential time. DP is better for this problem.
>
> Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
> sequence with the last element being no more than m. And we always
> draw m from the set V of values in a.
>
> So here is the new DP:
>
> C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
> C(n, m) = min (
> a[n] + C(n - 1, m), // delete
> (a[n] <= m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
> )
>
> In case you don't follow, the "//delete" line is saying that we
> already know the cost of making everything up to element n-1 non-
> decreasing and no more than m. This, by recursive assumption, is just
> C(n-1,m). The additional cost of deleting a[n] is a[n].
>
> The "//decrement" line is similar, but there are 2 cases. If a[n] is
> more than m, we must decrement it. The cost here consists of making
> everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
> Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
>
> In the other case, a[n] is m or less. So there's no need to
> decrement, but we must get the elements a[1..n-1] to be no more than
> a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
>
> Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
> least cost here is obtained by decrementing the 5 to 1 (cost 4) and
> deleting the final 1 (cost 1) for a total cost of 5.
>
> So let's try the algorithm. (You must view this with a fixed font.)
>
> Table of C(n, m) values:
> m = 1 3 5
> n = 1 : 4 2 0
> n = 2 : 4 3* 1*
> n = 3 : 4 4 2*
> n = 4 : 4 4 3*
> n = 5 : 6m 4 4
> n = 6 : 6 5* 5*
>
> Here * means C resulted from decrementing and "m" means that a
> decrement was based on the value of m rather than a[n].
>
> We take the answer from C(6,5) = 5.
>
> Implementing this is a little tricky because m values are drawn from
> V. You could use a hash table for the m-axis. But it's more
> efficient to store V in an array and convert all the values of m in
> the DP into indices of V. Because all the indices lie in [ 1 .. |
> V| ], we can use simple arrays rather than hash tables to represent
> the rows of the table C.
>
> We only need 2 rows at a time, so O(|V|) storage does the job.
>
> For C, we also need to convert all the indices to origin 0.
>
> So here's the final O(n^2) code. I think this is a correct
> implementation. If anyone has an example that breaks it, I'd like to
> see.
>
> #include
>
> #define NMAX 1
>
> int cost(int *a, int N)
> {
> int i, j, max, Nv;
> int V[NMAX], A[NMAX], B[NMAX];
> int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
>
> // Compute set V with no duplicates.
> // Remember where max element is.
> Nv = max = 0;
> for (i = 0; i < N; i++) {
> for (j = 0; j < Nv; j++)
> if (a[i] == V[j])
> break;
> if (j == Nv) {
> V[Nv++] = a[i];
> if (V[j] > V[max])
> max = j;
> }
> a[i] = j; // Convert a to indices.
> }
> // Fill in first row of C.
> for (i = 0; i < Nv; i++)
> Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0;
>
> // Fill in the rest of the rows of C.
> for (i = 1; i < N; i++) {
> for (j = 0; j < Nv; j++) {
> int del = Cm[j] + V[a[i]];
> int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
> Cn[j] = (del < dec) ? del : dec;
> }
> // Swap row buffers so current becomes previous.
> int *tmp = Cn; Cn = Cm; Cm = tmp;
> }
> return Cm[max];
>
> }
>
> int main(void)
> {
> static int a[] = { 5, 1, 1, 1, 3, 1 };
> printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0]));
> return 0;
>
> }
>
> On Aug 30, 9:19 pm, vikash jain wrote:
>
>
>
> > @gene ..if u just give an example herethat will make things more
> > clear...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon interview Question (Array yet again!)
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should be: 22 {11,11,11,11}
pls correct me if i m wrong
On Aug 28, 8:26 am, jagadish wrote:
> @Gene: Thanks alot! :-) your solution works like charm!
>
> On Aug 28, 7:09 am, Gene wrote:
>
>
>
> > This is a nice problem. It looks like a trivial matroid, so a greedy
> > algorithm will work fine. The obvious greedy algorithm is to work
> > left-to-right and incorporate elements into the sorted order one-by-
> > one. In each case, you have 2 choices. The first is to decrement
> > elements to the left by the amount needed to restore non-decreasing
> > order. The second is to delete the new element. The cost of each is
> > easy to calculate. Pick the choice with least cost and continue.
> > This algorithm is O(n^2). There may be a faster way to do it, but I
> > can't see one.
>
> > #include
>
> > int make_nondecreasing(int *a, int n)
> > {
> > int i, j, dec, dec_cost, total_cost;
>
> > total_cost = 0;
> > for (i = 0; i < n - 1; i++) {
>
> > // If we find a decrease...
> > if (a[i] > a[i + 1]) {
>
> > // Find cost of decrementing all to the left.
> > dec_cost = dec = a[i] - a[i + 1];
> > for (j = i - 1; j >= 0; j--) {
>
> > // Find decrement that would be needed.
> > dec += a[j] - a[j + 1];
>
> > // If no decement, we're done.
> > if (dec <= 0)
> > break;
>
> > // Count cost of decrement.
> > dec_cost += dec;
> > }
>
> > // Compare decrement cost with deletion cost.
> > if (dec_cost < a[i + 1]) {
>
> > // Decrement is cheaper. Do it.
> > for (j = i; j >= 0; j--) {
> > if (a[j] > a[i + 1])
> > a[j] = a[i + 1];
> > }
> > total_cost += dec_cost;
> > }
> > else {
>
> > // Deletion is cheaper. Do it.
> > total_cost += a[i + 1];
> > for (j = i + 1; j < n - 1; j++)
> > a[j] = a[j + 1];
> > --n;
> > }
> > }
> > }
> > return total_cost;
>
> > }
>
> > int main(void)
> > {
> > int a[] = { 14, 15, 16, 13, 11, 18 };
> > //int a[] = { 4, 3, 5, 6};
> > //int a[] = { 10, 3, 11, 12 };
> > int cost = make_nondecreasing(a, sizeof a / sizeof a[0]);
> > printf("cost=%d\n", cost);
> > return 0;
>
> > }
>
> > On Aug 27, 12:15 pm, jagadish wrote:
>
> > > You are given an array of positive integers. Convert it to a sorted
> > > array with minimum cost. Only valid operation are
> > > 1) Decrement -> cost = 1
> > > 2) Delete an element completely from the array -> cost = value of
> > > element
>
> > > For example:
> > > 4,3,5,6, -> cost 1
> > > 10,3,11,12 -> cost 3
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Take 5 digit number and find 2 power that number.............
But how the number(in decimal form) will be displayedif ques demands so. On Sep 2, 1:49 pm, saurabh singh wrote: > Suppose the number of shifts be x. > Also let the integer be represented by 16 bits on that machine. > Now take int n= (int)(x/16 + 0.5), to take the upper cap on result :) . > SO having 2^x will be same as doing 2<<(x-1) so essentially if we represent > the resultant number in a linked list of nodes, where each node can store an > integer, then the bit position at 2+x-1=x+1 will be set as 1 and this > (x+1)th nit will fall in (x+1)/16th node in linked list also in that node > (x+1)%16 will give the position of bit to be set. > > On Thu, Sep 2, 2010 at 1:32 PM, ashish agarwal > > > > > > wrote: > > I think it will be 1< > > On Wed, Sep 1, 2010 at 10:53 PM, Yan Wang wrote: > > >> Maybe you misunderstand the question. > >> The question is how to compute 2^X where 0 <= X <= 9? > >> How? > > >> On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj wrote: > >> > a 5 digit number is of order 10^5 which is << 10^16 of which int in C > >> > is of size. > >> > Just multiply both numbers. > > >> > On Sep 2, 10:39 am, prasad rao wrote: > >> >> Program that takes a 5 digit number and calculates 2 power that number > >> and > >> >> prints it and should not use the Big-integer and Exponential > >> Function's. > > >> > -- > >> > You received this message because you are subscribed to the Google > >> Groups "Algorithm Geeks" group. > >> > To post to this group, send email to algoge...@googlegroups.com. > >> > To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com >> .com> > >> . > >> > For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algoge...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com >> .com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Thanks & Regards, > Saurabh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
