## V.Krestyannikov

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

- V.Krestyannikov May 06, 2012You 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.

- V.Krestyannikov January 30, 2012Can you write your solution?

- V.Krestyannikov January 22, 2012@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.

- V.Krestyannikov January 18, 2012I 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.

- V.Krestyannikov January 14, 2012How do you think, Is there faster solution?

- V.Krestyannikov January 14, 2012Write in-order trasversals of both trees, and then check is tree1's trasversal contains tree2 trasversal as subsequence?

- V.Krestyannikov January 14, 2012Can you give some examples, I can't understand the problem?

- V.Krestyannikov January 14, 2012Your 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.

- V.Krestyannikov January 05, 2012It'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.

- V.Krestyannikov January 05, 2012If 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

- V.Krestyannikov January 05, 2012100% ;)

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.

- V.Krestyannikov January 05, 2012You 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>

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012I think that standart Aho-Corasick algorithm will solve your problem.

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012<REMOVED>

- V.Krestyannikov January 03, 2012You can't use bin search here.

- V.Krestyannikov October 03, 2011In 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 )

- V.Krestyannikov October 02, 2011Point 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.

- V.Krestyannikov June 10, 2011Your time complexity will be O(n * n) in the worse case.

- V.Krestyannikov June 10, 2011

Rep**ewasam940**, Backend Developer at Absolute Softech LtdI am a 29-year-old Investment Advisor from New York. I help people make the right investment decision. I met many ...

Rep**amandaben422**, Graphics Programmer at Abs india pvt. ltd.Hi, I am a webmaster from the USA. I think social networks have the power to connect two different people ...

Rep**thubmorfin**, Android Engineer at ABC TECH SUPPORTI am currently working as a safety-focused Service Technician from Red Bank. I execute routine maintenance work while advising clients ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

You can sort all of them as float numbers.

- V.Krestyannikov July 27, 2012