[algogeeks] Interview Question - Probability

[algo bard]

You are given n white balls in the beginning. Each day you pick up a ball
randomly, color it red and put it back. If it is already colored, you
simply put it back. This operation is performed for 'd' days. What is the
probability that after d days you will have greater than 'k' balls colored?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] DE Shaw written test

[algo bard]

The problem boils down to this:

http://www.geeksforgeeks.org/archives/6463

On Tue, Aug 7, 2012 at 1:59 PM, manish patel wrote:

> This is maximum sub-array problem. Nice explaination is given in CLRS -
> "Introduction to algorithms " Pg 68, ch-4 3rd edition
>
>
> On Tue, Aug 7, 2012 at 11:00 AM, Navin Gupta wrote:
>
>> @ashgoel :- Thanx for pointing it out, my earlier approach doesn't work.
>> Please check if this works.
>> We can apply this:-
>>  For every  element, find the highest element to the right of it.
>> For e.g:
>> I/P:- 35   4015   35   10 20
>> Highest to Right:-  40   3535   20   20-
>>
>> Now at every point, we will find the difference of both and  keep track
>> of the buy and sell dates.
>> This can be done in linear time without any space.
>>
>> void getDates(  int price[]  ) {
>> int maxSel l, maxBuy , maxGain= INT_MIN;
>> int Sell,Buy,curGain;
>> Sell = n;
>> for(int i=n-1;i>=0;i--)
>> {
>> curGain = price[Sell] - price[i];
>> if(curGain > maxGain){  // buying today gives more gain
>> that previous gain found, update the maxgain and buy,sell dates
>> maxGain = curGain;
>> maxBuy = i;// today
>> maxSell = Sell;
>> }
>> if( price[i]  >  price[Sell] ) // here selldate
>> is updated
>> Sell =  i ;
>>
>> }
>> }
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/BrQFNo1PKTIJ.
>>
>> To post to this group, send email to algogeeks@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.
>>
>
>
>
> --
> With Regards
>
> Manish Patel
> BTech Final year
> Computer Science And Engineering
> National Institute of Technology -Allahabad
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] merging

[algo bard]

http://geeksforgeeks.org/forum/topic/amazon-banglore-online-written-2

Read the solution given by asm. Pretty neat.

On Mon, Aug 6, 2012 at 1:05 AM, adarsh kumar  wrote:

> Cos, if they are stored as a vector of strings like a1, b1, etc. then u
> can use insertion sort like technique.
> Insert bi and ci between ai and a(i+1), for i=1,2,3n.
> This can be done simply by modifyin insertion  sort code. Pl let me know
> in case of any flaw! cos it seems to be so simple this way.
>
> On Mon, Aug 6, 2012 at 1:02 AM, adarsh kumar  wrote:
>
>> vector*
>>
>>
>> On Mon, Aug 6, 2012 at 1:02 AM, adarsh kumar  wrote:
>>
>>>
>>> Can you care to explain as to how exactly the elements are stored? Is it
>>> a vactor of strings??
>>>
>>> On Mon, Aug 6, 2012 at 12:32 AM, Navin Kumar 
>>> wrote:
>>>
 Actually i wanted to do it inplace. Using extra space it is much
 easier problem.


 On Mon, Aug 6, 2012 at 12:27 AM, payal gupta wrote:

> int merge(int arr[],int n)
> {
> int l=0;
> int j=(n/3);
> int k=2*(n/3);
> int *a=(int*)malloc(sizeof(int)*n);
> for(int i=0;i {
> a[l++]=arr[i];
> a[l++]=arr[j++];
> a[l++]=arr[k++];
> }
> for(int i=0;i arr[i]=a[i];
> free(a);
> }
> cud be dun be dun recursively also to minimize d space complexity...
>
>
>
>
>
> On Sat, Aug 4, 2012 at 8:20 AM, Navin Kumar 
> wrote:
>
>> In given array of elements like 
>> [a1,a2,a3,..an,b1,b2,b3,..bn,c**1,c2,c3,...cn]
>> .Write an efficient program to merge them like
>> [a1,b1,c1,a2,b2,c2,...an,bn,cn**].
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/gVCyxQV1IhAJ.
>> To post to this group, send email to algogeeks@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.
>>
>
>  --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@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.

>>>
>>>
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] [Amazon]

[algo bard]

@Shobhit: Can you give me a few hints on implementing a BS on the 2D?
@neelpulse: That's what I said. A 2D array *might* be a probable candidate.
In your example, the first 2d satisfies the criteria...so we check it --
Not found -- Reject -- Move on to next probable candidate.

On Sat, Jul 21, 2012 at 5:14 PM, neelpulse(Jadavpur University) <
neelpu...@gmail.com> wrote:

> May be I am missing a few details. But Consider this 3D array:
> {
>{
>   {1,2},
>   {7,8} // First 2D array
> },
> {
>{3,4},
>{9,10}
>  }
> }
> If you search for 3 then your search in first step will give first 2D
> which actually does not contain 3. As per my interpretation of the problem,
> my array is holding the preconditions.
>
> On Friday, 20 July 2012 16:25:49 UTC+5:30, algo bard wrote:
>>
>> Compare the element with the first([0][0]) and the last
>> element([n-1][n-1]) of each 2D array to pin down the 2D array it *might* be
>> present in.
>> After that you can follow this approach :  http://www.geeksforgeeks.org/*
>> *archives/11337 <http://www.geeksforgeeks.org/archives/11337>
>>
>> If it's not present in that 2D, move on and search for the next target 2D.
>>
>> The Probable 2D target set will be given by :
>> arr[i][0][0]<=element<=arr[i][**n-1][n-1].
>> Reject the 2Ds which don't follow this condition.
>>
>> TC: O(n^2)
>>
>> Though, I think an O(n) approach must exist for this problem.
>>
>> On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal > > wrote:
>>
>>> How will you search an element in sorted 3D Array ?  ( Sorted in all the
>>> 3 directions )
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>> googlegroups.com .
>>> For more options, visit this group at http://groups.google.com/**
>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>
>>
>>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/UKYO8gE0s08J.
>
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Directi Written Q 2012

[algo bard]

#include
#define RANGE_START 0
#define RANGE_END 100

int main()
{
int i,n,ctr=0;

for( i=RANGE_START ; i<=RANGE_END ; i++)
{
n = i;
while(n)  // Using Brian Kernighan's Algorithm to count the number
of set bits in a number.
{
n= n&n-1;
ctr++;
}

}

printf("%d ",ctr);
}

TC = No. of set bits in the given range of numbers.


On Tue, Jul 24, 2012 at 7:56 PM, Lomash Goyal wrote:

> // count number of 1's upto n.cpp : Defines the entry point for the
> console application.
> //
>
> #include "stdafx.h"
> #include
> #include
>  //the following functions will count number of bits in the number
> int countbits(int n)
> {
>int count=0;
>while(n)
>   {
> n/=2;
> count++;
>   }
> return count;
> }
>
>
> int countnumberof1(int number)
> {
> if(number==0)
>  return 0;
> if(number==1)
> return 1;
>  if(number==2)
> return 2;
> if(number==3)
>  return 4;
>  if(number>3)
>  {
> int bits=countbits(number);
> if(number==pow(2.0,bits)-1)
>  {
> return pow(2.0,bits-1)+2*countnumberof1(pow(2.0,bits-1)-1);
> }
>  else return
> pow(2.0,bits-2)+2*countnumberof1(pow(2.0,bits-2)-1)+countnumberof1(number-(pow(2.0,bits-1)))+number-(pow(2.0,bits-1))+1;
> }
> }
> int _tmain(int argc, _TCHAR* argv[])
> {
> printf("%d",countnumberof1(10));
> getch();
>  return 0;
> }
>
>
> On Tue, Jul 24, 2012 at 3:09 PM, ruru  wrote:
>
>> find no. of 1's in binary format of numbers from 1 to 100. like for
>> 1 to 10 answer is 17
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>>
>
>
> --
> Regards
>
> Lomash Goyal
>
> *
> *
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] [Amazon]

[algo bard]

Compare the element with the first([0][0]) and the last element([n-1][n-1])
of each 2D array to pin down the 2D array it *might* be present in.
After that you can follow this approach :
http://www.geeksforgeeks.org/archives/11337

If it's not present in that 2D, move on and search for the next target 2D.

The Probable 2D target set will be given by :
arr[i][0][0]<=element<=arr[i][n-1][n-1].
Reject the 2Ds which don't follow this condition.

TC: O(n^2)

Though, I think an O(n) approach must exist for this problem.

On Fri, Jul 20, 2012 at 11:24 AM, Sakshi Agrawal wrote:

> How will you search an element in sorted 3D Array ?  ( Sorted in all the 3
> directions )
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Programming Problem

[algo bard]

Can't we simply hash all the characters in an array and then print the
occurrence of each character in lexicographically decreasing order? This
way, it'll have all unique characters, will be the longest possible string
and will be derivable from s.

int hash[26] = {0};
hash all inputs using :-hash[input_char - 'a']

 for i=25 to 0
   if(hash[i])
   print i+'a';

TC: O(n)

Any improvements/ suggestions/ corrections?


On Fri, Jul 20, 2012 at 3:30 PM, ashish jain wrote:

> @piyus khanna---
> while forming a BST with aaab and removing duplicates if a charcter occur
> once ..
> so for aaab
> first make a node for 'a'.
> and ignore next two a's as they are already on the BST. next is 'b'.
> make 'b' as root and 'a' on the right side..
> and use inorder parsing to get 'ba' as the unique beautiful string.
>
>
>
> On Fri, Jul 20, 2012 at 12:22 PM, piyush khanna <
> piyush_khanna2...@yahoo.com> wrote:
>
>> @ashish jain :then what for aaab..
>>
>>   --
>> *From:* ashish jain 
>> *To:* algogeeks@googlegroups.com
>> *Sent:* Thursday, July 19, 2012 9:48 PM
>> *Subject:* Re: [algogeeks] Programming Problem
>>
>> if from the string s.. a binary search tree (with higher value alphabets
>> on the left side of the root and lower value alphabets on the right side of
>> root) is formed removing the repeated characters during the formation of he
>> BST and then applying inorder technique to get the string s2.
>>  String S2 will give the most beautifull unique string producible from s.
>>
>> ^^ Correct me if wrong!!
>>
>> On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb wrote:
>>
>> String s is called *unique* if all the characters of s are different.
>>
>> String s2 is *producible* from string s1, if we can remove some
>> characters of s1 to obtain s2.
>>
>> String s1 is *more beautiful* than string s2 if length of s1 is more
>> than length of s2 or they have equal length and s1 is lexicographically
>> greater than s2.
>>
>> Given a string s you have to find the *most beautiful unique* string
>> that is producible from s.
>>
>> *Input:*
>>
>> First line of input comes a string s having no more than 1,000,000(10^6)
>> characters. all the characters of s are lowercase english letters.
>>
>> *Output:*
>>
>> Print the most beautiful unique string that is producable from s
>>
>> *Sample Input:*
>>
>> babab
>>
>> *Sample Output:*
>>
>> ba
>>
>> *Explanation*
>>
>> In the above test case all unique strings that are producible from s are
>> "ab" and "ba" and "ba" is more beautiful than "ab".
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>>
>>   --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Amazon Interview Question

[algo bard]

No it's not O(n). Coz you're scanning the array and in case you do not find
a solution, you're jumping back to the start of the loop. That's equivalent
to a nested loop. And I think in the worst case...it'll turn out to be an
O(n^2) solution. Please correct me if I'm wrong.

On Fri, Jul 13, 2012 at 8:29 PM, jatin  wrote:

>  as long as we are using goto with proper comments to ensure that it won't
> decrease the readability we can use them and ther's no harm in it!
> Secondly the worst case for my algo is o(n) .?..correct me if i am wrong
>
> On Friday, 13 July 2012 18:12:41 UTC+5:30, adarsh kumar wrote:
>
>> Ya I didn't see that part, sorry. And in general, using goto is not
>> advisable.
>> Plus this will exceed O(n) in the worst case, as we may keep visiting the
>> goto again and again. Not sure of its exact time complexity.
>> --
>> From: vindhya chhabra
>> Sent: 13-07-2012 17:46
>> To: algogeeks@googlegroups.com
>> Subject: Re: [algogeeks] Re: Amazon Interview Question
>>
>> @adarsh
>> But i think jatin has asked to check for the number( we achieved in step
>> 1) occuring thrice or not..and in this check 27 will rule out.but i doubt
>> the algo given by Jatin runs in O(n) time. please comment.
>>
>> On Fri, Jul 13, 2012 at 5:17 PM, adarsh kumar  wrote:
>>
>>> @jatin:
>>> Your first method may be proved wrong.
>>>
>>> Here is a counter test case:
>>>
>>> Suppose the array is:
>>>
>>> 27 729 19683 2 3 3 27 3 81 729
>>>
>>> Here, 81 occurs once, 19683 occurs once, 2 occurs once,729 occurs twice,
>>> 27 occurs twice, and 3 occurs thrice.
>>>
>>> You are supposed to return 3
>>> But as per your method, the product will be computed as
>>> 729*19683*2*3*3*27*3*81*729=**product(say)
>>>
>>> Upon traversing the second time, it will return 27, as
>>> product%(27*27*27) is equal to zero!
>>>
>>> regards.
>>>
>>>
>>>
>>> On Fri, Jul 13, 2012 at 1:29 PM, @jatin  wrote:
>>>
>>>> Or we can make a BST from array list in o(n)
>>>> then traverse it inorder-o(logn)
>>>>
>>>> but this solution requires o(logn) space though.
>>>>
>>>> On Friday, 13 July 2012 13:16:50 UTC+5:30, jatin sethi wrote:
>>>>
>>>>>
>>>>> 1)Find product of the array and store it in say prod  o(n) and
>>>>> o(1)
>>>>> 2)now traverse the array and check if
>>>>>
>>>>> static int i;
>>>>> tag:
>>>>> while(i>>>> if( prod %(ar[i]*arr[i]*arr[i] ) ==0)
>>>>> break;
>>>>> //this may be the required element
>>>>> //e-o-while
>>>>>
>>>>> //now check is this is the element that is occuring three times
>>>>> o(n)
>>>>> if(number is not the required one then)
>>>>> goto tag;
>>>>>
>>>>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>>>>>
>>>>>> Given an array of integers where some numbers repeat once, some
>>>>>> numbers repeat twice and only one number repeats thrice, how do you find
>>>>>> the number that gets repeated 3 times?
>>>>>>
>>>>>> Does this problem have an O(n) time and O(1) space solution?
>>>>>> No hashmaps please!
>>>>>>
>>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To view this discussion on the web visit https://groups.google.com/d/**
>>>> msg/algogeeks/-/lmzhJ-GSdigJ<https://groups.google.com/d/msg/algogeeks/-/lmzhJ-GSdigJ>.
>>>>
>>>>
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>>> googlegroups.com .
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send em

[algogeeks] Amazon Interview Question

[algo bard]

Given an array of integers where some numbers repeat once, some numbers
repeat twice and only one number repeats thrice, how do you find the number
that gets repeated 3 times?

Does this problem have an O(n) time and O(1) space solution?
No hashmaps please!

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Directi question

[algo bard]

int no_of_steps[arr_length] = {MAX};

if ( (arr_length==0) || (arr[0] == 0) )   //if there are no elements or
the very first element is 0 -> we can't jump anywhere
return MAX;

no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.

for (int i=1; i= (i - j) )//if it is possible for us to jump from
jth element to ith element.
  {
 if( no_of_steps[i] > no_of_steps[j] + 1)// if no. of steps to
reach the ith element recorded till now is greater than the no of
 {   //
steps reqd to reach jth element + 1, then replace.

 no_of_steps[i] > no_of_steps[j] + 1;
 }
  }
}

}

cout< wrote:

> There is a greedy solution discussion about this approach. I don't have a
> formal proof for this.
> Any counter example will be helpful.
>
> at every place 'k' .. do the following.
>
> --> find max ( a[k+i]+i )  where 1 <= i <= a[i]
>
> for the given example:
> A = {4 0 0 3 6 5 4 7 1 0 1 2}
>
> initially a 4, the loop will be.
>   0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
> now at 6. (since, you can't reach end.)
> 5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, ==> 10 is max. jump to 7.
> make another step. (but you can reach the end.) so jump to last.
>
> this is greedy approach.. and a linear time soultion.
>
>
> On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
>>
>> Given an array A and the elements stored in an array denotes how much
>> jump an element can make from that array position. For example there is an
>> array A = {4 0 0 3 6 5 4 7 1 0 1 2}
>>
>> Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
>> are stuck if you end up at 0.
>> You have to output the minimum number of jumps that can be made from
>> starting position to end position of an array.
>>
>> --
>>
>>
>> Akshat Sapra
>> Under Graduation(B.Tech)
>> IIIT-Allahabad(Amethi Campus)
>> *--*
>> sapraaks...@gmail.com
>> akshatsapr...@gmail.com
>> rit20009008@ iiita.ac.in
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
>
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Directi question

[algo bard]

^  cout<< no_of_steps[arr_length -1];

On Mon, Jul 9, 2012 at 8:44 PM, algo bard  wrote:

> int no_of_steps[arr_length] = {MAX};
>
> if ( (arr_length==0) || (arr[0] == 0) )   //if there are no elements
> or the very first element is 0 -> we can't jump anywhere
> return MAX;
>
> no_of_steps[0] = 0; //no jumps required to jump from element 0 to itself.
>
> for (int i=1; i {
>no_of_steps [i] = MAX;
>
>for(int j=0; j to jump to.
>{
>   if( arr[j] >= (i - j) )//if it is possible for us to jump from
> jth element to ith element.
>   {
>  if( no_of_steps[i] > no_of_steps[j] + 1)// if no. of steps to
> reach the ith element recorded till now is greater than the no of
>  {   //
> steps reqd to reach jth element + 1, then replace.
>
>  no_of_steps[i] > no_of_steps[j] + 1;
>  }
>   }
> }
>
> }
>
> cout<
>
> On Mon, Jul 9, 2012 at 8:32 PM, Mr.B  wrote:
>
>> There is a greedy solution discussion about this approach. I don't have a
>> formal proof for this.
>> Any counter example will be helpful.
>>
>> at every place 'k' .. do the following.
>>
>> --> find max ( a[k+i]+i )  where 1 <= i <= a[i]
>>
>> for the given example:
>> A = {4 0 0 3 6 5 4 7 1 0 1 2}
>>
>> initially a 4, the loop will be.
>>   0+1,0+2,3+3,6+4 -- 10 is max. jump to 6.
>> now at 6. (since, you can't reach end.)
>> 5+1, 4+2, 7+3, 1+4, 0+5, 1 + 6, ==> 10 is max. jump to 7.
>> make another step. (but you can reach the end.) so jump to last.
>>
>> this is greedy approach.. and a linear time soultion.
>>
>>
>> On Monday, 9 July 2012 09:32:08 UTC-4, Akshat wrote:
>>>
>>> Given an array A and the elements stored in an array denotes how much
>>> jump an element can make from that array position. For example there is an
>>> array A = {4 0 0 3 6 5 4 7 1 0 1 2}
>>>
>>> Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
>>> are stuck if you end up at 0.
>>> You have to output the minimum number of jumps that can be made from
>>> starting position to end position of an array.
>>>
>>> --
>>>
>>>
>>> Akshat Sapra
>>> Under Graduation(B.Tech)
>>> IIIT-Allahabad(Amethi Campus)
>>> *--*
>>> sapraaks...@gmail.com
>>> akshatsapr...@gmail.com
>>> rit20009008@ iiita.ac.in
>>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/QRWxd8B2DzcJ.
>>
>> To post to this group, send email to algogeeks@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.
>>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Write a C program to reconstruct a BST from a given array of preorder traversal.

[algo bard]

^ Thank you! Mind discussing the algorithm please?

On Wed, Jul 4, 2012 at 7:06 PM, deepikaanand wrote:

> code :-
>
> http://ideone.com/O5yuo
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Interview question

[algo bard]

Urm. It's probably not the same. We could find the maximum element in the
array and use the trivial approach till we reach the max_element. After
that, all we need to do is to shift all the elements right of max_element
to the left by 1 and place max_element at the end. But again..this isn't
O(n). :-P Worst case: O(n^2).

On Sun, Mar 25, 2012 at 10:44 PM, algo bard  wrote:

> http://www.geeksforgeeks.org/archives/8405
>
> ^ Similar Question.
>
> On Mar 25, 4:49 pm, atul anand  wrote:
> > wont work for all cases...ignore
> > i will post the algoonce i fix it
> > On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
> >
> >
> >
> >
> >
> >
> >
> > > @atul : it would be better for all to understand if you write the algo
> > > instead of writing the code..
> > > --
> >
> > > Amol Sharma
> > > Third Year Student
> > > Computer Science and Engineering
> > > MNNIT Allahabad
> > >  <http://gplus.to/amolsharma99> <http://twitter.com/amolsharma99><
> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
> http://www.simplyamol.blogspot.com/>
> >
> > > On Sun, Mar 25, 2012 at 4:51 PM, atul anand  >wrote:
> >
> > >> @shady : yes i guess this is what question says:-
> > >> so acc to this below algo work , i didnt execute it but i guess it
> will
> > >> work
> >
> > >> void nextSmaller(int arr[],int n)
> > >> {
> > >> s1 s;
> > >> int i,next,ele;
> >
> > >> s.top=-1;
> > >> push(&s,0);
> >
> > >> for(i=1;i > >> {
> > >> next=arr[i];
> > >>  if(isEmpty(&s))
> > >> {
> > >>   ele=pop(&s);
> > >>   while(arr[ele] > next)
> > >>   {
> > >>  swap(arr,ele,i);
> > >>   next=arr[ele];
> > >> if(isEmpty(&s)==0)
> > >> {
> > >> break;
> > >>  }
> > >>   ele=pop(&s);
> > >>   }
> > >>   if(ele > next)
> > >>   {
> > >> push(&s,ele);
> > >>   }
> >
> > >> }
> >
> > >> push(&s,i);
> > >>  }
> >
> > >> }
> >
> > >> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
> >
> > >>> @gene
> > >>> i think for  3 4 2 you need to start from left most element, and then
> > >>> make substitutions one by one.
> > >>> so it will be
> > >>> 3 4 2
> > >>> 2 4 3
> > >>> 2 3 4
> >
> > >>> @all i googled a bit, and found that O(n) solution is possible for
> it,
> > >>> any idea ?
> >
> > >>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan <
> kartik.sac...@gmail.com>wrote:
> >
> > >>>> +1 @saurabh...:P
> >
> > >>>> --
> > >>>> You received this message because you are subscribed to the Google
> > >>>> Groups "Algorithm Geeks" group.
> > >>>> To post to this group, send email to algogeeks@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.
> >
> > >>>  --
> > >>> You received this message because you are subscribed to the Google
> > >>> Groups "Algorithm Geeks" group.
> > >>> To post to this group, send email to algogeeks@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.
> >
> > >>  --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@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.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@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.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Re: [algogeeks] Re: Interview question

[algo bard]

http://www.geeksforgeeks.org/archives/8405

^ Similar question.

On Sun, Mar 25, 2012 at 5:19 PM, atul anand  wrote:

> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
>
>> @atul : it would be better for all to understand if you write the algo
>> instead of writing the code..
>> --
>>
>>
>> Amol Sharma
>> Third Year Student
>> Computer Science and Engineering
>> MNNIT Allahabad
>>   
>> 
>>
>>
>>
>>
>>
>>
>> On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>>
>>> @shady : yes i guess this is what question says:-
>>> so acc to this below algo work , i didnt execute it but i guess it will
>>> work
>>>
>>> void nextSmaller(int arr[],int n)
>>> {
>>> s1 s;
>>> int i,next,ele;
>>>
>>> s.top=-1;
>>> push(&s,0);
>>>
>>> for(i=1;i>> {
>>> next=arr[i];
>>>  if(isEmpty(&s))
>>> {
>>>   ele=pop(&s);
>>>   while(arr[ele] > next)
>>>   {
>>>  swap(arr,ele,i);
>>>   next=arr[ele];
>>> if(isEmpty(&s)==0)
>>> {
>>> break;
>>>  }
>>>   ele=pop(&s);
>>>   }
>>>   if(ele > next)
>>>   {
>>> push(&s,ele);
>>>   }
>>>
>>> }
>>>
>>> push(&s,i);
>>>  }
>>>
>>> }
>>>
>>>
>>> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
>>>
 @gene
 i think for  3 4 2 you need to start from left most element, and then
 make substitutions one by one.
 so it will be
 3 4 2
 2 4 3
 2 3 4


 @all i googled a bit, and found that O(n) solution is possible for it,
 any idea ?

 On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan >>> > wrote:

> +1 @saurabh...:P
>
> --
> You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

  --
 You received this message because you are subscribed to the Google
 Groups "Algorithm Geeks" group.
 To post to this group, send email to algogeeks@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.

>>>
>>>  --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@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.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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: Interview question

[algo bard]

http://www.geeksforgeeks.org/archives/8405

^ Similar Question.

On Mar 25, 4:49 pm, atul anand  wrote:
> wont work for all cases...ignore
> i will post the algoonce i fix it
> On 25 Mar 2012 17:06, "Amol Sharma"  wrote:
>
>
>
>
>
>
>
> > @atul : it would be better for all to understand if you write the algo
> > instead of writing the code..
> > --
>
> > Amol Sharma
> > Third Year Student
> > Computer Science and Engineering
> > MNNIT Allahabad
> >   
> > 
>
> > On Sun, Mar 25, 2012 at 4:51 PM, atul anand wrote:
>
> >> @shady : yes i guess this is what question says:-
> >> so acc to this below algo work , i didnt execute it but i guess it will
> >> work
>
> >> void nextSmaller(int arr[],int n)
> >> {
> >> s1 s;
> >> int i,next,ele;
>
> >> s.top=-1;
> >> push(&s,0);
>
> >> for(i=1;i >> {
> >> next=arr[i];
> >>  if(isEmpty(&s))
> >> {
> >>       ele=pop(&s);
> >>       while(arr[ele] > next)
> >>       {
> >>  swap(arr,ele,i);
> >>                   next=arr[ele];
> >> if(isEmpty(&s)==0)
> >> {
> >> break;
> >>  }
> >>   ele=pop(&s);
> >>       }
> >>       if(ele > next)
> >>       {
> >> push(&s,ele);
> >>       }
>
> >> }
>
> >> push(&s,i);
> >>  }
>
> >> }
>
> >> On Sun, Mar 25, 2012 at 4:36 PM, shady  wrote:
>
> >>> @gene
> >>> i think for  3 4 2 you need to start from left most element, and then
> >>> make substitutions one by one.
> >>> so it will be
> >>> 3 4 2
> >>> 2 4 3
> >>> 2 3 4
>
> >>> @all i googled a bit, and found that O(n) solution is possible for it,
> >>> any idea ?
>
> >>> On Sun, Mar 25, 2012 at 1:59 PM, Kartik Sachan 
> >>> wrote:
>
>  +1 @saurabh...:P
>
>  --
>  You received this message because you are subscribed to the Google
>  Groups "Algorithm Geeks" group.
>  To post to this group, send email to algogeeks@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.
>
> >>>  --
> >>> You received this message because you are subscribed to the Google
> >>> Groups "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@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.
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@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.
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.