@Dk..i dint frame the question buddy...:P
I found it over here....
http://geeksforgeeks.org/forum/topic/google-interview-question-for-software-engineerdeveloper-about-algorithms-75
On Mon, Jul 11, 2011 at 3:14 PM, DK <divyekap...@gmail.com> wrote:
> @Sunny: Thanks for this counterexample. The O(N) algorithm currently seems
> unfeasible to me.
> @Piyush: Are you sure an O(N) algo exists?
>
> Here's an O(N log N) algo (without the N^2 memory requirements of Sunny's
> algo as it doesn't generate duplicates)
>
> For arrays
> A = a1 a2 ... an
> B = b1 b2 .... bn
>
> Maintain a max priority_queue ordered by Val(a,b). (Use a BST for this).
> Insert (an, bn).
>
> Repeat N Times {
> Pop off and output the max value from the priority queue. Let that be
> (ai, bj) // O(log N)
> if(i == j) {
> Insert (ai-1, bj), (ai, bj-1), (ai-1, bj-1) in the priority queue. //
> O(log n)
> } else if(i < j) {
> Insert (ai-1, bj) in the priority queue. // O(log n)
> } else {
> Insert (ai, bj-1) in the priority queue. // O(log n)
> }
> }
>
> Time complexity: O(N log N)
> Space complexity: O(N) ??
>
> --
> DK
>
> http://twitter.com/divyekapoor
> http://www.divye.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/-/XCjyFaTFD-UJ.
>
> 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.
>
--
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=100000655377926 *
--
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.
