CareerCup

Catalan number

o(n) solution is already given :)

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*/

How is your code O(n^2)
For each element in A (executed n times) -> for each element in A say x (executed n times) -> if sum-x is present in H (May be log(n) if sorted)

Loop->Loop->Search

Check out my solution :

"github.com/amitgoswami/ALGO_TRIALS/blob/dev/CommonAlgoQuestions/SubsetSumEqualNos/src/SubsetSumEqual.java"

it is a link add https as prefix

Greedy / Knapsack 0/1 ?

Gud One

Make 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)

How is time O(n) ? did u consider the number of times u ran the for loop ?

Dynamic programming ?
Why not Graph theory ?

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.

Good one !

A sudoku block can contain numbers from 0 to 9 . Convert all the numbers into bit feilds enable numbers .
1 == 0x0000 0001
2 == 0x0000 0002
3 == 0x0000 0004
.
.
9 == 0x0000 0200

SUM == 0x0000 02FF == ( bit-wise OR every number)

Guarentees uniqueness + FAST !

How is Log(n) possible ? if we have to find the missing element , we have to visit all the elements at min. Search of one value in sorted unique element array is possible

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

U Dont need Dynamic programming then.
BIGGEST_DENOMINATION should be used maximum number of times

Good Logic . Liked the bit about the starting character. What is the complexity ? n == stringlength ?

I really doubt such an easy question was asked !

I feel that the purpose of the question is to reduce the number of multiplications. We have to store the intermediate results somewhere.

Nice soln !

I guess if post-order OR pre-order for BST is given, then tree can be constructed , but in-Order for BST is given we cannot construct tree. can someone please clarify ?

i am sort of new to DP. can you explain how dp has to be applied ?

Nice One Bro !

All the guys who claim this solution works , can confirm it works for this

1
                    /       \
                  2         3
                 / \         / \
                4   5   11  12

Only two loops can be used.

Please refer to this question , can it help ?
[Carrercup Link] + question?id=14946937

Isn't this exactly the merge step of the merge sort ?
Merge sort == O(log n) rows with each row taking O(N) time
So this problem should be O(n^2) only . Am I right ?

Looks neat !

Explain ?

Oops ! if KxK is taken then , k = min(m,n) still the number of matrices doesn't seem to be much to handle with DP:)

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 ?

AMEN to that - "Not to mention that it's an extremely shitty interview question"

Introduction to algorithms Cormen problem :)

Small Error in the line 13 (13th line of code)
if( (arr[mid] + 1)!=num) ==> if( (arr[mid + 1])!=num)
Let me know if it works !

I agree about dynamic programming.
There should be a matrix which hold the values of the sums of consecutive integers.
What is the meaning of first "sub array" ? how would you reduce the number of computations then ?