Re: [algogeeks] Re: Interview Question based on histogram
Navin , your reply is correct. On Sat, May 19, 2012 at 10:36 PM, Gene wrote: > The problem is not so clear, so you must make some assumptions to gat > an answer. Since we have water, we have to envision the histogram in > 3d. Then assume that the distance between histogram bars is 1 and bar > i has height H[i], 0<=i plane is at zero. Water is held in the "pockets" between bars. Then > the "pocket" between H[i] and H[i+1] holds min(H[i],H[i+1]). To get > the total, just sum these for 0 <= i < N-1 . > > On May 17, 1:57 am, Nikhil Agarwal wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you > > can pour water on top of your histogram. Describe an algorithm that > > computes the amount of water that remains trapped among the columns of > the > > graph. Clearly on the edges the water would fall off. Use the language or > > the pseudocode you prefer. > > > > -- > > Thanks & Regards > > Nikhil Agarwal > > B.Tech. in Computer Science & Engineering > > National Institute Of Technology, > Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// > beta.freshersworld.com/communities/nitd > > -- > 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. > > -- Thanks & Regards Nikhil Agarwal B.Tech. in Computer Science & Engineering National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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 based on histogram
The problem is not so clear, so you must make some assumptions to gat an answer. Since we have water, we have to envision the histogram in 3d. Then assume that the distance between histogram bars is 1 and bar i has height H[i], 0<=i wrote: > Imagine that you have an histogram stored in an array. Now imagine that you > can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, > Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd -- 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 based on histogram
we need to find the amount of water stored on every bar of the histogram. For this, we need to find two values :- v1 :- the highest bar to the left - O(n) v2:- the highest bar to the right - O(n) amount of the water stored on the current bar is Res= ( minimum of the two values(v1,v2) - height of the bar ) (assuming the length & breadth of bar is unity) sum all the values of water store on individual bar Time complexity - O(n) Space Complexity - O(n) On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > On Thursday, 17 May 2012 11:27:44 UTC+5:30, Nik_nitdgp wrote: > > Imagine that you have an histogram stored in an array. Now imagine that > you can pour water on top of your histogram. Describe an algorithm that > computes the amount of water that remains trapped among the columns of the > graph. Clearly on the edges the water would fall off. Use the language or > the pseudocode you prefer. > > -- > Thanks & Regards > Nikhil Agarwal > B.Tech. in Computer Science & Engineering > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- 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/-/SRp0wWOK_kUJ. 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.
