CareerCup

> the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found

@Yev, What is the start value of max surpasser in above step?

Copying an answer from SO:

Solution 1

I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.

Initialize an empty binary search tree and then iterate in reverse order through the array.

Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)

The max number of successors is given by the largest count observed.

Your algorithm will only work if we have find just 2 numbers in the array whose summation= given number? There may be a subset of >2 numbers whose summation= given number.

Googler, just wanted to point out that your code expects a sorted string.

Googler, amazing code. How do you ensure lexicographic order?

dude, can you elaborate. almost sounded like greek

I think "abc"

Would your solution work for:

Array 1 = [1,1]
Array 2 = [2,2]

If I understood your solution correctly, final answer would be 0 but the arrays do not have any common elements.

@Rashmi, Your solution won't work for this input:

Array 1 = [1,2,3]
Array 2 = [1,1,1]

@ yingsun1228, Your solution wont work with duplicate elements. Here is one example where your solution will report "IDENTICAL ARRAYS"

Array 1 = [1,2,3]
Array 2 = [1,1,1]

Can you explain the meaning of :

A
B
Mat
expectation

You are correct, Rayden, eugene. My mistake.

Simplest possible answer. Amazing Travis.

The question is more interesting and of practical use if the ordering of letters is important.

How exactly are you building your graph? What are the weights on the edges? How did it go from O(vlogv) to O(v)?

Can you explain with an example. Suppose I have a board with a ladder from 2 to 100, then answer should be 2 i.e. 1->2->100. But if I understood your solution, the answer would be 1+3+5+...99

You will print each path twice. When you reach a leaf, you will print the path twice - once for each of its null child

This is influenced by Venkatesh's solution - just a slightly different way to do it.

PreOrder: a b c d f g e
PostOrder: c f g d b e a

We first get the root. a is the root, (As for preorder, it starts with the root/ for post order it is the last.)

Then we locate the element immediate to root's right in pre order. i.e b

We take that b and locate in post-order. So cfgdb is left subtree and e is right subtree.

Now problem is reduced to:

Left subtree of root:
PostOrder:cfgdb
PreOrder:bcdfg(whatever is the length of PostOrder string above, we take that many chars in original PreOrder string. In this case 5)

Right subtree of root
preOrder: e (whatever is left after removing root and PreOrder substring from previous step)
PostOrder:e (whatever is left after removing root and PostOrder substring from previous step)

Repeat till the tree is constructed.

@ jiangok2006,

Your statement is right. However, it is possible to do if all non-leaves are distinct. See Venkatesh's algorithm above.

Keep two variables to store the 'max till the boundary' and 'max before the boundary'. Iterate over the elements of the array one by one and keep updating the variables. This is similar to the O(n) maximum subarray problem.

static int getMaxSubSeqNonAdjacent(int[] array) {
        int sumTillBoundary   = array[1];
        int sumBeforeBoundary = array[0];

        for (int i = 2; i < array.length; i++){
            int sumBeforeBoundary2 = sumBeforeBoundary;
            
            sumBeforeBoundary = Math.max(sumTillBoundary, sumBeforeBoundary);
            sumTillBoundary   = Math.max(sumBeforeBoundary2 + array[i], array[i]); 
        }
        
        return Math.max(sumTillBoundary, sumBeforeBoundary);
    }

Can you explain "max sum". An example would help.

@sp!de?,

>increament the index for this array from which least number is taken

If I understand your algorithm, you will need to store n indexes. So, it is not using O(1) space.

@sp!de?,

>increament the index for this array from which least number is taken

If I understand your algorithm, you will need to store n indexes. So, it is not using O(1) space.

Avinash, You are doing 2 traversals at the same code. Amazing idea.

@eugene.yarovoi, I had some concerns regarding quickselect.

The file may not have fixed size records. How would you implement iterating thru the file? It may not be trivial. There may be multiple integers on one line and each line may have different number of integers. Even if we have one integer per line, finding the next number would require some parsing (like find the bytes between the next 2 newlines)

@sourav.hitk, those 4 elements are not a valid subarray of given array (its elements are not contiguous)

Hi don, could you explain the "tournament tree with help of input and output buffers" a bit more. Maybe a link would be helpful.

Notice that we can't use extra space. How much space will your n-way merge use?

Pick the min of every array till there are no elements in any of the arrays and append the min to the output array. Uses 2-3 temp variables.

Complexity = O(n*m) where m is the total number of elements in the array.

yes DP = Dynamic programming

@OptimumsPrime,
[-4,9] is not a solution as it is not maximal - it is a subset of a larger solution [-4 9 10]

You have to look at all pairs (not just adjacent pairs) in the subarray.

-4 9 10 4 is not a solution as -4 + 4 < k = 4

Interesting use of min-heap. Could you explain your solution a bit in english - it is easier to follow than code.

Where is the heap in your code? Oh, I see, you are using priority_queue as heap. Interesting

Also, why are you multiplying items with -1?

You are only printing one solution. There may be multiple subarrays. See the question - it has an example

Because not all pairs in

9 10 4 -3 8 9

add to > k

e.g. 4 + -3 = 1 which is less than k = 4

Yes. Updated the question

This was asked at Palantir but I can't choose Palantir as a company name in careercup.

Epic_coder, could you explain approach 2 a bit more.

Very smart and simple solution, Manan. Unlike other solutions, there are no multiplies or other arithmetic that you are using. So, there is no chance of overflow.

Thanks Aparna.

In this solution, we are not keeping the ordering of elements. The nth element can be moved in the middle of the array. So, it becomes the ith element. Ideally, if we remove the ith element, then i+1 th element should become the ith element.

@als365, Could you you explain your solution a bit more. We also have to think about how to choose a random element when our key is hashed to a location that has multiple values chained there.

My previous comment is wrong. Found an example where both conditions are true but tree is not symmetric.

10
   /  \
  5   10
 /    /
10   5

I think we need to enhance your logic with

depth of left subtree == depth of right subtree &&
preorder traversal should be a palindrome

This won't work. Here is an example:

10
   /
  5
 /
10

Look at careercup.com/question?id=14722757

We can also run Dijkstras algorithm. Seems simpler than doing 2 BFS

Amazing idea. But I think this clause is not correct

else if(n1!=null || n2!=null)

It would make the initial call thru isMirrorImage(root,root) return right away. It won't go into any recursion.

This line doesn't look correct to me:

cur.right = buildTreePreorder(cur.left.index + 1);

It should be:

cur.right = buildTreePreorder(cur.index + number of nodes in the left subtree + 1);

I agree. Here are 3 trees with the same preorder traversal:

N
   /
  N
 / \
L   L

N
   / \
  N   L
 /
L

N
   / \
  N   L
   \
    L

Since, there can only be 26 characters, we can use a O(n) sort. So, complexity will change to

n + m+ nlogm

nitin, good solution but how do we prove that your solution will produce smallest sequence?