CareerCup

You can sort all of them as float numbers.

There is Rope data structure which works with large string and supports basic operations with logarithmic complexity.

You can use Newton's iterative method
Ai+1 = 0.5 * (Ai + X/Ai); where i - number of iteration

yes, you right, it is usual knapsack problem.

Can you write your solution?

@eugene.yarovoi... you wrong.
logic will look like this, every 3rd number divisible by 3, and we know it is not p nor p + 2, so it can be only p + 1, p + 4, p + 7, ...

n > 10 means that this question works only for number greater then 10, so your sample isn't correct.

I can say that even (p + 1) satisfies these conditions.
Just imagine if we have numbers (p-2), (p-1), p, p + 1, p + 2, ..., p + 7
1) Number is divisible by 6 if it divisible by 2 and 3.

We know that each second number is divisible by 2, so it should be (p-1), (p+1), (p + 3), ..., (p + 7), because p and p + 2 are prime and (n > 10)
The same logic for 3

Numbers can't be unique, because we have only 4b unique integers.
Unless the interviewer says that number has type long :)

yes, you are right, I'll think about it.

How do you think, Is there faster solution?

Write in-order trasversals of both trees, and then check is tree1's trasversal contains tree2 trasversal as subsequence?

Can you give some examples, I can't understand the problem?

Your solution is incorrect. You do not take into account this fact
MCMXLIV = 1000 + (1000 − 100) + (50 − 10) + (5 − 1) = 1944

" This would have it be RND(50) % (30 - 1) + 1, which obviously is just RND(50) % 30"
It's not true, because RND(50) % (30 - 1) + 1 lies in range [1:29], but RND(50) % 30 lies in range[0:29]

"The number being generated should have no association to the size of the list."
Why not?

"as mentioned earlier this would return values 1 to 30 as desired."
We can't just take random number from 1 to 30, because, for example, L can contain value 30 and it will be wrong answer.

I have realized some things
1) We can't generate random number from 1 to N, if N isn't divisible by INT_MAX, because it's impossible to allocate all the numbers [1-INT_MAX] in [1-N]
2) If N is divisible by INT_MAX, we can use my previous method

About 3rd step:
suppose L = { 2, 3, 6 }, N = 7
Create auxiliary array A = { 1, 4, 5, 7 } - all correct numbers. (N - K) = 4, 1-index based.
Now we will generate not random number(in the first meaning) but random index from 1 to (N - K), and probability all of them will be equal and answer will be A[random_index].
How to solve it without auxiliary array?

1 2 3 4 5 6 7 - index
1 0 0 1 1 0 1 - is it correct?
Can you find i-th correct element in this array? It'll be my solution

About1st step:
Seems you are right, I'll think how to generate random number from 1 to (n - k).

Cool problem :)
My solution with linear complexity O(k):
1) C = RND() % (n - k) + 1 // generate random number from 1 to (n - k)
2) RES = C
2) go through each element of L, and if it smaller or equal to C, then increment RES

WTF? is it magic?
The simplest solution is write all correct numbers to array and generate random index.
I do the same thing, but I do not use array.
Seems like there is faster solution, but it is the most obvious.

"a a a a a b c b c b c b c" - this issue possible to solve by stack
1. put current char to the stack
2. if stack size > 2 and if [top - 2, top - 1, top] forms valid sequence, just remove them from the stack
3. repeate from 1

This algorithm will be useful when there is one set of points and a lot of queries and the resulting complexity will be O(Q logN) where Q is number of queries, N is number of points.

It's not exactly true, because before you start to answer queries, you should build k-d tree, and it takes O(N log(N)) time, and after that each query will take O(logN) time.

If points given in random order, you can't solve this problem faster than O(N), because you should look at each point at least once, so you have to go through all the points and check distance between it and A

100% ;)
I didn't say that we should use flagging.

There is misunderstanding with operation delete(), because its prototype has not index variable, so if we can delete only from the end of an array we can use lazy deletion, else we should shift all elements placed next to the current.

You can review java.util.ArrayList or std::vector realization
@Carol Smith.
Your solution is very similar to standard, but usually size of an array will increase by two.

1) convert string to reverse polish notation by Shunting-yard algorithm
2) evaluate expression in RPN(it's easy)

@Carol - Ok! For each vertex of trie we'll have a mask, that means which of the input strings were included in the current vertex.
Then you should find the smallest path from the root vertex with mask=0, to any vertex with mask= 2^n - 1. Each transition along an edge will add a char to the result string. This path we can find by simple bfs.

<REMOVED>

<REMOVED>

<REMOVED>

<REMOVED>

I think that standart Aho-Corasick algorithm will solve your problem.

<REMOVED>

<REMOVED>

<REMOVED>

You can't use bin search here.

In this problam we can use the ternary search algorithm, because our function is unimodal
This is my simple python sol.

def solve(left, right, arr):
    '''Finds max element in an array'''

    if right - left <= 2:
        t = arr[left:right + 1]
        return left + t.index(max(t))

    # devide arr to three segments [left, m1], [m1, m2], [m2, right]
    m1 = (2 * left + right) / 3
    m2 = (left + 2 * right) / 3

    # values in arr forms unimodal function, so
    # we can assume that if arr[m1] <= arr[m2]
    # our max lies in [m1, right]
    if arr[m1] <= arr[m2]:
        return solve(m1, right, arr)
    else:
        return solve(left, m2, arr)

if __name__ == '__main__':
    arr = [10, 12, 16, 17, 24, 27, 8, 6, 5, 4, 2]
    print solve(0, len(arr), arr) + 1

Sorry for my bad English )

Point lies inside the triangle if sign of cross products (APB), (BPC), (CPA) are equals, or there is c.p. that equal 0, in other case point lies outside the triangle.

Your time complexity will be O(n * n) in the worse case.