Re: [algogeeks] Amazon Onsite
can any one give me anexample which takes worst case of this problem On Mon, Mar 26, 2012 at 1:56 PM, Arpit Sood wrote: > @ankur +1 > correct algo, can be done in just one pass. > > On Mon, Oct 24, 2011 at 11:03 PM, Ankur Garg wrote: > >> I think this can be solved like this . >> Start from the first petrol pump i.e first point in the circle . Now if >> the petrol finishes befor reaching the second petrol pump that means we >> chose the incorrect point . So , choose second petrol pump now. If u reach >> third, fill ur tanker and move to 4th . Now if before 4th we again run out >> of petrol that means our choice was incorrect . Start from 4th and so on .. >> If u reach the starting point again this is the choice we need to make >> ..and thats the answer . Programatically , it can be thought of Kadane Algo >> ..(seems to me ..not sure of algo) but I think this way we just make at >> most 2 pass (in case the petrol pump of choice is just before the first >> point ) . >> >> Please comment in case you think its right/wrong >> >> Regards >> Ankur >> >> >> On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel < >> ravindra.it...@gmail.com> wrote: >> >>> @Nitin, excellent algo. >>> >>> >> if S < 0 && j = i-1 return 0 // I believe this mean there is no >>> solution, you might want to return -1. >>> >>> >>> Thanks, >>> - Ravindra >>> >>> >>> >>> On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg >>> wrote: >>> Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i<=n) S += Pj - Dj; if S >= 0 && j = i-1 return i if S < 0 && j = i-1 return 0 else if S >= 0 j++ mod n; else if S < 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket wrote: > Suppose there is a circle. You have five points on that circle. Each > point corresponds to a petrol pump. You are given two sets of data. > > 1. The amount of petrol that petrol pump will give. > 2. Distance from that petrol pump to the next petrol pump. > > > (Assume for 1 lit Petrol the truck will go 1 km) > > Now calculate the first point from where a truck will be able to > complete the circle. > (The truck will stop at each petrol pump and it has infinite > capacity). > Give o(n) solution. You may use o(n) extra space. > > -- > 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. > > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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. >> > > > > -- > Regards, > Arpit Sood > > -- > 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 Onsite
@ankur +1 correct algo, can be done in just one pass. On Mon, Oct 24, 2011 at 11:03 PM, Ankur Garg wrote: > I think this can be solved like this . > Start from the first petrol pump i.e first point in the circle . Now if > the petrol finishes befor reaching the second petrol pump that means we > chose the incorrect point . So , choose second petrol pump now. If u reach > third, fill ur tanker and move to 4th . Now if before 4th we again run out > of petrol that means our choice was incorrect . Start from 4th and so on .. > If u reach the starting point again this is the choice we need to make > ..and thats the answer . Programatically , it can be thought of Kadane Algo > ..(seems to me ..not sure of algo) but I think this way we just make at > most 2 pass (in case the petrol pump of choice is just before the first > point ) . > > Please comment in case you think its right/wrong > > Regards > Ankur > > > On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel > wrote: > >> @Nitin, excellent algo. >> >> >> if S < 0 && j = i-1 return 0 // I believe this mean there is no >> solution, you might want to return -1. >> >> >> Thanks, >> - Ravindra >> >> >> >> On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg wrote: >> >>> Lets say the Amount of petrol is Pi and distance to next petrol pump is >>> Di for ith petrol pump. >>> >>> start from i=1, j=1 S =0 >>> while (i<=n) >>> S += Pj - Dj; >>> if S >= 0 && j = i-1 return i >>> if S < 0 && j = i-1 return 0 >>> else if S >= 0 j++ mod n; >>> else if S < 0 j ++ mod n, i = j , S = 0; >>> >>> return 0 >>> >>> >>> >>> it will traverse atmost twice, and hence O(n). no extra space required. >>> >>> >>> On Mon, Oct 24, 2011 at 4:06 AM, Aniket wrote: >>> Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) extra space. -- 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. >>> >>> >>> -- >>> Nitin Garg >>> >>> "Personality can open doors, but only Character can keep them open" >>> >>> -- >>> 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. > -- Regards, Arpit Sood -- 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 Onsite
Sorry there is some correction p[] : array of petrol d[]: array of distance int FirstPetrolPump(int p[],int d[],int n) { int c=0,ThisPetrol=0,FirstPump=0,i; for(i=0;ihttp://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Onsite
@ankur : I also think u r right @everyone : Plz check if my code is right p[] : array of petrol d[]: array of distance int FirstPetrolPump(int p[],int d[],int n) { int c=0,ThisPetrol=0,FirstPump=0,i; for(i=0;ihttp://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Onsite Chennai SDE
Aren't there multiple words that can be returned from the dictionary after various operations? eg: input string: CODE If we go on walking the trie for the dictionary, we'll get results C, CO, COD, CODA, CODE. So multiple edit distance operations can be done to each of the instances shown above to give various results.. At which point shall we assume that ok, THIS is the word I want ? On Tue, Nov 15, 2011 at 12:44 AM, aniket chatterjee wrote: > @Rajeev: The above algorithm assumes a source string and a destination > string. But here you are provided only the source string. And you will have > to edit it (minimally) such that the resulting string matches a word in the > dictionary. > > Need slight modification. Looking for the modification. (Interviewer told. > The same answer was given). > > > On Mon, Nov 14, 2011 at 4:59 AM, rajeev bharshetty > wrote: > >> Levensteins algorithm >> >> On 14 Nov 2011 18:19, "aniket chatterjee" wrote: >> > >> > yeah, that is normal bryteforce. Any better idea? >> > >> > On 11/14/11, Ankur Garg wrote: >> > > We can use a trie here .. Create a trie with all words of dictionary . >> > > >> > > Now delete the last character of the word and check if such a word is >> a >> > > valid word . If not see if adding a new character can make it a valid >> word >> > > . If not delete the next character and repeat the process again . >> > > >> > > This is what I can think of here. Any other solutions/guesses ? >> > > >> > > >> > > >> > > On Mon, Nov 14, 2011 at 12:43 PM, Aniket wrote: >> > > >> > >> You are given a word and a dictionary. Now propose an algorithm edit >> > >> the word (insert / delete characters) minimally to get a word that >> > >> also exists in the dictionary. Cost of insertion and deletion is >> same. >> > >> Write pseudocode for it. >> > >> >> > >> Seems like minimum edit distance problem but some modification is >> > >> needed. >> > >> >> > >> -- >> > >> 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. > -- Anup Ghatage -- 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 Onsite Chennai SDE
@Rajeev: The above algorithm assumes a source string and a destination string. But here you are provided only the source string. And you will have to edit it (minimally) such that the resulting string matches a word in the dictionary. Need slight modification. Looking for the modification. (Interviewer told. The same answer was given). On Mon, Nov 14, 2011 at 4:59 AM, rajeev bharshetty wrote: > Levensteins algorithm > > On 14 Nov 2011 18:19, "aniket chatterjee" wrote: > > > > yeah, that is normal bryteforce. Any better idea? > > > > On 11/14/11, Ankur Garg wrote: > > > We can use a trie here .. Create a trie with all words of dictionary . > > > > > > Now delete the last character of the word and check if such a word is a > > > valid word . If not see if adding a new character can make it a valid > word > > > . If not delete the next character and repeat the process again . > > > > > > This is what I can think of here. Any other solutions/guesses ? > > > > > > > > > > > > On Mon, Nov 14, 2011 at 12:43 PM, Aniket wrote: > > > > > >> You are given a word and a dictionary. Now propose an algorithm edit > > >> the word (insert / delete characters) minimally to get a word that > > >> also exists in the dictionary. Cost of insertion and deletion is same. > > >> Write pseudocode for it. > > >> > > >> Seems like minimum edit distance problem but some modification is > > >> needed. > > >> > > >> -- > > >> 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] Amazon Onsite Chennai SDE
Levensteins algorithm On 14 Nov 2011 18:19, "aniket chatterjee" wrote: > > yeah, that is normal bryteforce. Any better idea? > > On 11/14/11, Ankur Garg wrote: > > We can use a trie here .. Create a trie with all words of dictionary . > > > > Now delete the last character of the word and check if such a word is a > > valid word . If not see if adding a new character can make it a valid word > > . If not delete the next character and repeat the process again . > > > > This is what I can think of here. Any other solutions/guesses ? > > > > > > > > On Mon, Nov 14, 2011 at 12:43 PM, Aniket wrote: > > > >> You are given a word and a dictionary. Now propose an algorithm edit > >> the word (insert / delete characters) minimally to get a word that > >> also exists in the dictionary. Cost of insertion and deletion is same. > >> Write pseudocode for it. > >> > >> Seems like minimum edit distance problem but some modification is > >> needed. > >> > >> -- > >> 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 Onsite Chennai SDE
yeah, that is normal bryteforce. Any better idea? On 11/14/11, Ankur Garg wrote: > We can use a trie here .. Create a trie with all words of dictionary . > > Now delete the last character of the word and check if such a word is a > valid word . If not see if adding a new character can make it a valid word > . If not delete the next character and repeat the process again . > > This is what I can think of here. Any other solutions/guesses ? > > > > On Mon, Nov 14, 2011 at 12:43 PM, Aniket wrote: > >> You are given a word and a dictionary. Now propose an algorithm edit >> the word (insert / delete characters) minimally to get a word that >> also exists in the dictionary. Cost of insertion and deletion is same. >> Write pseudocode for it. >> >> Seems like minimum edit distance problem but some modification is >> needed. >> >> -- >> 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 Onsite Chennai SDE
We can use a trie here .. Create a trie with all words of dictionary . Now delete the last character of the word and check if such a word is a valid word . If not see if adding a new character can make it a valid word . If not delete the next character and repeat the process again . This is what I can think of here. Any other solutions/guesses ? On Mon, Nov 14, 2011 at 12:43 PM, Aniket wrote: > You are given a word and a dictionary. Now propose an algorithm edit > the word (insert / delete characters) minimally to get a word that > also exists in the dictionary. Cost of insertion and deletion is same. > Write pseudocode for it. > > Seems like minimum edit distance problem but some modification is > needed. > > -- > 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] Amazon Onsite Chennai SDE
You are given a word and a dictionary. Now propose an algorithm edit the word (insert / delete characters) minimally to get a word that also exists in the dictionary. Cost of insertion and deletion is same. Write pseudocode for it. Seems like minimum edit distance problem but some modification is needed. -- 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 Onsite
#include int main(){ //int pet[5]={10,1,19,19,1}; int pet[5]={10,1,18,20,1}; int point[5] = {10,20,30,40,50}; int tmp[5],index=0; int i; tmp[0]=pet[0]; for(i=1;i<5;i++){ tmp[i]= pet[i]+tmp[i-1]; printf("%d, %d\n",tmp[i],point[i]); if(tmp[i]https://groups.google.com/d/msg/algogeeks/-/7XY9shwXpyUJ. 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 Onsite
I think this can be solved like this . Start from the first petrol pump i.e first point in the circle . Now if the petrol finishes befor reaching the second petrol pump that means we chose the incorrect point . So , choose second petrol pump now. If u reach third, fill ur tanker and move to 4th . Now if before 4th we again run out of petrol that means our choice was incorrect . Start from 4th and so on .. If u reach the starting point again this is the choice we need to make ..and thats the answer . Programatically , it can be thought of Kadane Algo ..(seems to me ..not sure of algo) but I think this way we just make at most 2 pass (in case the petrol pump of choice is just before the first point ) . Please comment in case you think its right/wrong Regards Ankur On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel wrote: > @Nitin, excellent algo. > > >> if S < 0 && j = i-1 return 0 // I believe this mean there is no > solution, you might want to return -1. > > > Thanks, > - Ravindra > > > > On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg wrote: > >> Lets say the Amount of petrol is Pi and distance to next petrol pump is Di >> for ith petrol pump. >> >> start from i=1, j=1 S =0 >> while (i<=n) >> S += Pj - Dj; >> if S >= 0 && j = i-1 return i >> if S < 0 && j = i-1 return 0 >> else if S >= 0 j++ mod n; >> else if S < 0 j ++ mod n, i = j , S = 0; >> >> return 0 >> >> >> >> it will traverse atmost twice, and hence O(n). no extra space required. >> >> >> On Mon, Oct 24, 2011 at 4:06 AM, Aniket wrote: >> >>> Suppose there is a circle. You have five points on that circle. Each >>> point corresponds to a petrol pump. You are given two sets of data. >>> >>> 1. The amount of petrol that petrol pump will give. >>> 2. Distance from that petrol pump to the next petrol pump. >>> >>> >>> (Assume for 1 lit Petrol the truck will go 1 km) >>> >>> Now calculate the first point from where a truck will be able to >>> complete the circle. >>> (The truck will stop at each petrol pump and it has infinite >>> capacity). >>> Give o(n) solution. You may use o(n) extra space. >>> >>> -- >>> 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. >>> >>> >> >> >> -- >> Nitin Garg >> >> "Personality can open doors, but only Character can keep them open" >> >> -- >> 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 Onsite
@Nitin, excellent algo. >> if S < 0 && j = i-1 return 0 // I believe this mean there is no solution, you might want to return -1. Thanks, - Ravindra On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg wrote: > Lets say the Amount of petrol is Pi and distance to next petrol pump is Di > for ith petrol pump. > > start from i=1, j=1 S =0 > while (i<=n) > S += Pj - Dj; > if S >= 0 && j = i-1 return i > if S < 0 && j = i-1 return 0 > else if S >= 0 j++ mod n; > else if S < 0 j ++ mod n, i = j , S = 0; > > return 0 > > > > it will traverse atmost twice, and hence O(n). no extra space required. > > > On Mon, Oct 24, 2011 at 4:06 AM, Aniket wrote: > >> Suppose there is a circle. You have five points on that circle. Each >> point corresponds to a petrol pump. You are given two sets of data. >> >> 1. The amount of petrol that petrol pump will give. >> 2. Distance from that petrol pump to the next petrol pump. >> >> >> (Assume for 1 lit Petrol the truck will go 1 km) >> >> Now calculate the first point from where a truck will be able to >> complete the circle. >> (The truck will stop at each petrol pump and it has infinite >> capacity). >> Give o(n) solution. You may use o(n) extra space. >> >> -- >> 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. >> >> > > > -- > Nitin Garg > > "Personality can open doors, but only Character can keep them open" > > -- > 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 Onsite
Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i<=n) S += Pj - Dj; if S >= 0 && j = i-1 return i if S < 0 && j = i-1 return 0 else if S >= 0 j++ mod n; else if S < 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket wrote: > Suppose there is a circle. You have five points on that circle. Each > point corresponds to a petrol pump. You are given two sets of data. > > 1. The amount of petrol that petrol pump will give. > 2. Distance from that petrol pump to the next petrol pump. > > (Assume for 1 lit Petrol the truck will go 1 km) > > Now calculate the first point from where a truck will be able to > complete the circle. > (The truck will stop at each petrol pump and it has infinite > capacity). > Give o(n) solution. You may use o(n) extra space. > > -- > 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. > > -- Nitin Garg "Personality can open doors, but only Character can keep them open" -- 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 Onsite
I will choose the point where amount of fuel is maximum choose the shortest path from two direction (clockwise or anticlockwise).. With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Oct 24, 2011 at 4:36 PM, Aniket wrote: > Suppose there is a circle. You have five points on that circle. Each > point corresponds to a petrol pump. You are given two sets of data. > > 1. The amount of petrol that petrol pump will give. > 2. Distance from that petrol pump tp the next petrol pump. > > (Assume for 1 lit Petrol the truck will go 1 km) > > Now calculate the first point from where a truck will be able to > complete the circle. > (The truck will stop at each petrol pump and it has infinite > capacity). > Give o(n) solution. You may use o(n) extra space. > > -- > 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] Amazon Onsite
Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump tp the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) extra space. -- 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.