## oxygen

BAN USERInterested in recursive programs, algorithms, information security, compression and computer graphics.

- » Resume

- 0of 0 votes

AnswersGiven two dices labeled 1 to 6. Take 1 dice and relabel it such that the sum of the two dice's is between 1 and 12. This sum occurs with equal probability. How will you relabel it ?

- oxygen| Report Duplicate | Flag | PURGE

Expedia Software Engineer / Developer Brain Teasers

p & p^2+8 are primes, if p not equal to 2.

p*(p^2 + 8) is not prime as it is factored into prime numbers......(p^3+p*8)

To make it prime, we need to convert p*8 into something not divisble by p,

We take 2 in this case. So, it makes (p^3+2^4) a prime....this cannot be factored furthur.

Can someone comment on the solution ?

i think with 3 additional similar size arrays, it might be possible to construct B.

array B1: Walk A, calculate B1[i] = a[i-1] * a[i+1] (should be O(n))

array B2: Walk A calculate B2[i] = B2[i-1] * a[i] (should be O(n))

array B3: Walk A calculate B3[n-i] = B3[n-i+1] * a[i] (should be O(n))

B[i] = B1[i] * B2[i-2] * B3[i+2]

basically, idea would be to exclude the number itself so construct B1 by doing that.

then keep multiplications from [0-(i-2)] and [i+2 to n] in B2 and B3. this shall leave the

item at i behind.

Note:- Solution given by a Friend of mine

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

Open Chat in New Window

Dear Anand,

- oxygen September 10, 2007Two observations:

1. Try solving for this example: B = 1 2, A = 1 3 2 3 2 2 2 1 2, with your solution.

when i = 0

for B[0] = 1, we get index 0 in sorted order, i.e. ANS[0] = 0

when i = 1

for B[1] = 2, we get index 2 in sorted order, i.e. ANS[1] = 2

Even if we tried doing insertion sort on ANS, we would end up with ANS[0] = 0, ANS[1] = 2

window l = 0, k = 2

Observe ! There is a better 'smaller' window 1 2 in the end.

So, why did you miss it ?

2. You are trying to sort within a loop. In that case, the time complexity should be geater than O(n^2), depending on the sorting algorithm.

This can be brought down to O(n^2) by using count sort, but how do you implement the same ?