## Cerberuz

BAN USEROk, i somehow missed that its subset sum problem which can be solved using dynamic programming.

```
array is a[ 1.. n ]
set dp[ target+10001 ] => all initialized to false
dp[i] = true iff array has a subset whose sum is i
dp[0] = true
for i = 1 to n:
for j = target-a[i] to 0 ( decrement ):
if dp[j] == true:
dp[ j+a[i] ] = true
if dp[target] == true:
return true
return false
```

This won't work if target < 0 but by using the dp range [ target+10001 to 2*target+10000 ], we can change it to work for that case also.

Time Complexity : O(target*n)

Space Complexity : O(target)

Oh sorry,

f(n) = 2*f(n-1) + 2*f(n-2)

Then also we don't need f(0) to solve as base matrix can be multiplied with appropriate [f(n),f(n-1)] to get [f(n+1,f(n)]. So we can use f(n) = 3 and f(n-1) = 1 where n = 2. Use kth power of base to get f(2+k-1) i.e. f(k+1) or we can say f(n+1)

There are more than 3.2*10^12 prime numbers in that range and it won't be possible to do that without using advance multithreaded-distributed computing. So, I doubt whether this is the exact question asked.

Miller-Rabin, AKS and fermat tests are useful for single prime number tests but for generating primes over a range usually sieve( segmented ) of erasthotenes or sieve of atkins is used.

This won't work. You are considering distance from a point to other k-1 points only for minimization rather you should minimize sum of pairwise distance.

e.g. When we find closest triplet of points then it means we have to find a triangle from set of points which has minimum perimeter i.e. we minimize AB+BC+CA not AB+BC.

In that case, you just know the fact that suffix tree takes O(n) time for construction. You don't know the approach. It's better to simply tell the fact and make it clear to the interviewer that you don't know the exact approach. He might then give you a hint or move on to next question. This is just my own opinion, others may not agree with it.

- Cerberuz January 06, 2013Yes most of the time they ask you to code but only if you get near to the correct approach. Secondly, if you have no clue about the question asked then you should look for it, you should think and interact with the interviewer about your idea. Interviewer would always give you hints. Knowing nothing about a problem and solving it there itself prove that you are capable enough to solve unknown problems unlikely those who already know the solution beforehand.

- Cerberuz January 06, 2013Use a hash[] array to keep track of generated numbers ( or use hash-map )

```
hash[] --> order of size of given list, set all false
count = 0 --> no of different values generated
do{
r = min + rand()%( max-min+1 );
index = hash_func(r)
if( !hash[index] ) {
hash[index] = true
count++
}
} while( r is in list and count < list size );
if( count < list size ) return r;
else : no random no. possible
```

Complexity : O(n* [ complexity of random() ] * [ complexity of hash_func() ]*[ complexity of list search ] )

- Cerberuz January 05, 2013```
For each index k in C :
Find index alim in A such that A[alim] <= C[k]
Find index blim in B such that B[blim] <= C[k]
left = 0
right = blim
-------while left <= alim and right >= 0 :
if A[left] + B[right] == C[k] :
Remove C[k] and break
else if A[left] + B[right] < C[k] :
left++
else :
right--
```

Complexity( O( (sizeA + sizeB)*sizeC ) ~ O*(n^2) )

- Cerberuz December 29, 2012Use max_sum[N][N] array, initialize its last row by last row of A[][] then use the following recurrence from i = N-2 to 0 ( rows are numbered from 0 to N-1 )

`max_sum[i][j] = A[i][j] + MAX( max_sum[i+1][j-1], max_sum[i+1][j], max_sum[i+1][j+1] )`

You can use A[][] itself to perform the recurrence operation thus avoiding any extra memory. Answer is MAX( for all j in max_sum[0][j] )

- Cerberuz December 16, 2012Yes, i think we can switch sides because we need end result i.e O(1) push-pop-top operations + we know linear structure of stack.

If elements are positive then we can set A[i] as negative to indicate that there is a direction change at this position for stack Y. So we don't need any extra memory. Otherwise we have to use a separate boolean array for indicating direction changes for middle stack Y. ( u can think same reason for elements in range also )

P.S : i might have made some mistakes while writing pseudo-code but i hope idea is clear.

=> O(1) time complexity for push-pop

=> No shifting required

=> Efficient only if array elements are +ve or in a particular range, otherwise it requires extra O(n) memory [ which is ridiculous because if we already have some extra memory why would we want to do such thing in a single array :) ]

Suppose given array is A[n].

X: First stack starts from A[0] and grows towards right [ maintain only top pointer ]

Y: Second stack starts from A[n-1] and grows towards left.[ maintain only top pointer ]

Z: Third stack starts from A[n/2] and can grow on either side and we can switch the end depending upon availability of space [ maintain left and right pointer + boolean switch for setting direction change for push/pop for its each element + current_top ]

Stack X : Push p

```
if X.top+1 != Z.left :
A[++X.top] = p
else If Z.right+1 != Y.top:
A[++Z.right] = A[Z.left]
Z.left++
Z.right.direction_change = true
A[++X.top] = p
else
overflow
```

Stack X: Pop p

`Pop A[X.top--] with stack underflow check`

Push/Pop strategy for stack Y is same as stack X.

Stack Z: Push p

```
if current_top is right:
if Z.right+1 != Y.top:
A[++Z.right] = p
else if Z.left-1 != X.top
A[--Z.left] = p
Z.left.direction_change = true
current_top = left
else
overflow
else //current_top is left
if Z.left-1 != X.top:
A[--Z.left] = p
else if Z.right+1 != Y.top
A[++Z.right] = p
Z.right.direction_change = true
current_top = right
else
overflow
```

Stack Z : Pop p

```
//with stack underflow check
if current_top is right:
pop p
if Z.right.direction_switch = true
Z.right.direction_switch = false
currect_top = left
Z.right--
else //current_top is left
pop p
if Z.left.direction_switch = true
Z.left.direction_switch = false
currect_top = right
Z.left++
```

Idea for stack Z is we push on current_top if space is available, otherwise we push on other end

and set the newly pushed element's direction switch flag as true i.e we will use this direction switch

flag while pop operation. This sounds tricky but its better than shifting the middle stack elements.

Moreover if stack elements are all +ve or in some range then there is no need for using extra memory

for direction_switch as we can convert elements to corresponding negative value to denote the flag being set as true.

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

Open Chat in New Window

- Cerberuz February 06, 2013