Simulate a 7-die with a 5-die

Isn't it an everyday situation that we find ourself with seven people and there's only a 5-sided die lying around :(. Well here's something you can do to alleviate the frustration:

Actually this is another interview question ;)

Q. How do you use a 5-sided die to get uniformly random outcomes between 1 and 7?

There could be many solutions to this, here's one:

1. Throw the die seven times and record the outcomes.

2. Then add the seven numbers.

3. Divide that number in step 2 by 7 and the remainder is your random outcome in [1,7]

(Working on the explanation)

Find Duplication in a List of Positive Integers in O(n)

This was a tech interview question, how would you find if there is duplication in an unordered list of positive integers in the range of [0,n-1] where n is the size of the list.

The bad news is that you can't use extra memory or the extra memory you use should be constant. And you have to do it in the order on O(n). So here's a solution I came up with (later on, that is)

For example here is a list
a=[1,5,2,6,7,4,3,0,5]
a=[-1,-5,-2,-6,-7,-4,-3,-0,5]

Imagine this list tells a routh in a graph on n nodes. So a[0]=1 tells you to goto node 1, then a[1]=5 tells you to goto node 5, and so on. You basically start traversing the list/(imaginary graph) and mark every visited node by negating the element in it. For example when a[0] told you to goto node 5, make a[5] = -1*a[5] (a[5]=4, so a[5] will now have -4).

To actually tell if there is duplication you check if a no. you're trying to negate is already negative, and if so, that means you've already visited the node (in the graph sense) and that there is duplication in the list. So in the above case, when the last element 5 (which is the duplicate) tries to negate a[5], it will be flagged as duplicate.

Even though the interviewer had asked me to only restrict it to determining if there was duplication and not all the elements which were duplicated, this way we can do both.

Python code:

import random

import math

a = range(10)

random.shuffle(a)

# duplicate some random entries

for i in range(50):

a[random.randint(0,len(a)-1)] = a[random.randint(0,len(a)-1)]

# increment each element in a by one, so as to make negation possible for 0

a = [1+x for x in a]

i=0

duplication=False

while i

if a[int(math.fabs(a[i])-1)] > 0:

a[int(math.fabs(a[i]))-1] *= -1

elif a[int(math.fabs(a[i])-1)] <>

duplication=True

break

i+=1

print duplication