straniu, eu vad inca oameni ce editeaza. s-ar putea sa fie prea multi care editeaza pt google docs . mai studiez. edit: pare sa mearga

interni tech, ar fi misto sa stim de oameni din hedge funds/investment banks

Poti sa adaugi in tabel orice locatie. E editabil. Nu ma intereseaza asa mult internshipurile din Romania, si vroiam o delimitare, dar e oarecum arbitrara. Atat doar ca e un semnal calitativ, pentru ca firma trebuie sa plateasca pentru un bilet de avion. Era mai greu sa zic silicon valley + londra + zurich + asia .

http://www.infoarena.ro/blog/interni-2014

no, this doesn't yield a uniform random point. read the previous comments to see why.

Good question. Probability is pretty tricky to get right. The algorithm you mention doesn't work.
Try running it 1000 times and see how frequent are the 7 results.

I've implemented the algorithm you mention and the algorithm described in the previous comments in python. Here's how they compare:

Cod:

import random

def rand5():
    return random.randint(1, 5)

def badfunction():
  f = [0] * 8
  for i in xrange(0, 1000):
      f[rand5() + rand5() % 3] += 1
  print 'badfunction'
  print f


def rand0_24():
    return (rand5() - 1) * 5 + rand5() - 1

def rand7():
    r = rand0_24()
    while r >= 21:
        r = rand0_24()
    return r % 7 + 1

def goodfunction():
  f = [0] * 8
  for i in xrange(0, 1000):
      f[rand7()] += 1
  print 'goodfunction'
  print f

badfunction()
goodfunction()

the results are
badfunction
[0, 46, 108, 199, 195, 206, 165, 81]
goodfunction
[0, 144, 162, 142, 140, 131, 149, 132]

So you can see the function you mentioned returns 1 much less frequently than it returns 3.

Having a good random generator is important. Here's an example where not caring about the random function went wrong http://www.cigital.com/papers/download/developer_gambling.php

Good job guys! I think we went through all the problems.

@Darius
4) Good job. This is called the "Reservoir Sampling" algorithm.

There's a interesting weighted version of the problem where the algorithm gets more complex.

5) I think this is ok, but the Knuth shuffle algorithm mentioned above is O(n).

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[ i]

5) This works, it takes O(n log k) time and O(k) space. There's another solution in O(n) time and O(k) space. (you can also improve this one to take O(n) time and O(k) space)

Yes this works, the algorithm is called Fisher–Yates shuffle or Knuth shuffle.

It works. John von Neumann came up with the same solution.

Cool, plenty of comments. I'll go through them one by one.

@ Dan-Alexandru
2. 5^6 % 7 = 1 so one of the 7 results is sightly more frequent than the others.

3. using this method a point has 1/2 probability of being in the 1/2 r radius circle. this circle has 1/4th of the area of the entire circle. so the points are not evenly distributed.

4. this works! one caveat is that as n grows you start needing big number operations and the algorithm starts being somewhat slow.

@ vali_MIT
7. good job. this works.

@ Dan-Alexandru
1. you don't know p.

5. yes

6. average time

7. formula. you can see vali's solution.

@ Aurelian
6. Yes. This works.

I would do it slightly different:  the probability of seeing a new after already having i toys is (n - i) / n. The expected number of steps for an event that happens with probability p to happen is 1/p. So the expected number of steps for seeing a new toy after already seeing i toys is n/(n-i). Thus the total number of steps is
n / n + n / (n - 1) + ... + n/(n-i) + ... + n / 1 = n Hn

8. This works as well. How I would solve it:
the probability of line 4 being executed at step i is 1/i (the probability of the maximum number in a sequence of i numbers being in the last position of the sequence is 1/i).
so the expected number of times step 4 is executed is 1/1 + 1/2 + ... + 1/n = Hn.

@ Mihai Ciucu
2. good job. the key insight is that you have to ignore a few numbers to get uniform results. (now the algorithm is non deterministic but has a short expected execution time)

3. yup. using a random number between 0 and r*r then doing sqrt gives us a good distribution.


To sum up we don't have a good solution for 1. We don't have an efficient solution for 4. We don't have any solution for 5.

0 or 1 each appear with 1/2 probability

http://www.infoarena.ro/blog/probability-shortlist

spoiler alert (selectati textul pentru rezolvare):

se pot asocia elementelor x chei cu valoarea [x / k], dupaia folosim un hash table si rezolvam in O(n):
daca exista mai multe valori cu aceeasi cheie problema e rezolvata,
daca nu putem verifica pt fiecare i cheile [x/k] + 1 si [x/k] - 1. (evident, acestea vor contine cel mult un element)

Zi enuntul problemei pe care o vrei tu in O(n). Ca pot vedea mai multe interpretari.

Daca D = N atunci problema se reduce la distanta minima intre doua elemente ale sirului. Problema asta nu se poate rezolva mai rapid de O(N log N), deci faci ceva presupunere gresita Vlad.

haha, neat. good job. looks reasonable to me.

@Radu yes, good point, binary searching on the logarithm works. Also it converges faster, especially on large numbers. In fact it takes 64 steps since now at each step you find a bit of the answer. But it's a bit of a cheat since I mentioned using only +,-,*,/

I think your only question left unanswered is the one about the behavior for really small numbers and really large numbers. I see that the code returns reasonable results for c = 1e+305 and c = 1e-305 and the results are equal to those of pow(c, 1.0/3).

As you can see Tomek already pointed out that for large numbers my number of iterations is bad and you need about 1100 steps instead of 120. Will add a paragraph about that tomorrow. It's 2am here . I think python doesn't have floats it uses doubles.

http://www.infoarena.ro/blog/your-bisection-search-is-wrong

I can do it in k log n queries, where k is the average size of a minimal subset and n is the size of S. I don't think one can solve it faster than k queries.

yes, thanks

http://www.infoarena.ro/blog/binary-search-shortlist