## Vladislav Kudelin

BAN USERI think the problem is "o(1) space complexity", so

int[] availableChars = new int[256];

above (etc.) doesn't quite solve it (stricktly speaking);

- maybe that's the catch? (YAISAQ).

- Fascinating thread!..:-).

Implementing rand7 (with bits manipulation or else) from 5 uniformly distributed numbers as they are is I think impossible.

Why? Basically, we deal with given probabilities:

... 1/5, 2/5, 2/5.

Solving this to get uniform 1/7 out of the above fractions: be my guest.

So,

"reject sampling" (as somebody above has called it) seems to be the only easy choice.

Here is how I did it:

a) from rand5(), take 4 and reject the 5th; get rand4();

b) from rand4(), build rand2() and rand8();

c) from rand8(), again take 7 and reject the 8th.

Here is the implementation:

def rand5():

...return random.randrange(5) # this is the only "real" random

def rand4():

...while(1):

......n = rand5()

......if n < 4:

.........return n

def rand2():

...return rand4() <2

def rand8():

...n4 = rand4()

...if rand2():

......n4 += 4

...return n4

def rand_5_7():

...while(1):

......n = rand8()

......if n < 7:

.........return n

A few takes (each one calls it 100000 times and stores the results):

:~> ./rand_5_7.py 100000

0: 14424; 1: 14114; 2: 14207; 3: 14517; 4: 14241; 5: 14250; 6: 14247;

:~> ./rand_5_7.py 100000

0: 14383; 1: 14195; 2: 14140; 3: 14265; 4: 14226; 5: 14389; 6: 14402;

:~> ./rand_5_7.py 100000

0: 14281; 1: 14195; 2: 14156; 3: 14287; 4: 14245; 5: 14531; 6: 14305;

:~>

Looks like random to me:-)...

The fefinition of the "union of rectangles" is accurate in the 1st post:

this is the smallest rectangle which includes both our rectangles within it.

Given:

R1: (x1,y1),(x2,y2);

R2: (x3,y3),(x4,y4);

No assumptions about their orientations and coordinate system is needed (i.e. x1>x2 or vise versa), still we have:

left: min(x1,x2,x3,x4);

right: max(x1,x2,x3,x4);

top: min(y1,y2,y3,y4);

bottom: max(y1,y2,y3,y4).

Union: (left,bottom), (right, top)

.

Thanks!

// To me, it was not clear that the [name] is a link... I am too old for CSS...:-).

Rep**tracyremly**, Anesthesiologist at NessI am Tracy, working as an Anesthesiologist handles surgical patients and their pain relief during procedures.Rather than my job ...

Rep**HelanZelda**, Consultant at AdventHelanZelda from Atlanta, GA, United States. I have a passion for exploring/sharing new ideas and experiences throughout the interdisciplinary ...

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

Open Chat in New Window

It is a trick question. First of all, one must realize that solutions like "produce all anagrams..." / search for each in string2 are damn slow, even if we use Boyer-More / Robin Karp and all good stuff. So just forget about this path. Instead, there is a linear solution.

Notice that if any contiguous part of s2 contains contains all characters from s1 and in the same amount, it is an anagram of s1 by definition.

So here is the algo:

This is algo O(N) (as dictionary operations are O(1))

Python implementation:

- Vladislav Kudelin October 07, 2017