## amit

There are some procedures to generate pythogorean triples if one side is given. Time complexity is o(size of input number). If one is known and other 2 are generated then , Time complexity becomes o(size of input number) + 2 * o(log number of inputs) /*For searching in array*/

- amit September 02, 2013Make an array (Like the one we use in heap sort). ith node has its children at 2i and 2i+1

Fill the array value with Node Data. if no child then fill with (-1) . { O(n) }

Then for every node u know the parent using simple math . j/2 and (j-1)/2. { Every node O(height) operations}

So O(n) + O(nLogn) ==> O(nLogn)

If u r smart u wont need the array and do the simple math in the matrix itself.

But point is it cannot be lower than O(nLogn)

Even if the sequence were specific to a user from the table we can generate

User 1 : 1 -> 2 -> 4 -> 1 -> 6

User 2 : 1 -> 2 -> 4

.

.

During the generation of this data itself we can find the frequency of the sequences.

All pages can be mapped to unique numbers :) as there are only 8 pages.

Steps :

1. Inorder traversal of BST gives array elements in sorted order O(N)

2. When traversing BST to find the sorted order find the largest element that is lower than K. (Operation doesn't take time done as a part of step 1)

3. Problem reduces to a modification of the maximum sub-array problem

This seems a little weird question :) , assume all the elements are non-negative integers. Then the largest sum should include as many elements as possible. Therefore the length of the edges of the matrix should be (m-1)x(n-1), this implies that there are only 5 matrices possible :) . why DP ?

- amit November 25, 2012**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Catalan number

- amit September 02, 2013