Karthik
BAN USERO(n) solution with O(n) memory:
Input array: A of length n
1. Find min value of the input, lets call it X. O(n)
2. if X!=Integer.MIN then output=Integer.MIN (corner case)
3. Create a boolean array of length n with default value FALSE. Lets call it P.
4. The idea is to check if the input array contains numbers from X to X+(n-1) using n sized boolean array. Then output is any element that is missing from the range X to X+(n-1) and if none are missing then the output is X+n, unless X+n=Integer.MAX in which case the input array contains all possible integers from Integer.MIN to Integer.MAX.
for(i = 0 to n-1) {
j=A[i]-X
if(j<n) then P[j]=TRUE
}
for(i=0 to n-1) {
if P[i]==FALSE then output is Integer.MIN+i
}
if i==n && n!=(Integer.MAX+1-Integer.MIN) then output is Integer.MIN+n
else "no output"// corner case of input array containing all integers
--- O(n)
e.g
Input A = {1,-1,Integer.MIN,2,3,5}
X = Integer.MIN
P = {TRUE,FALSE,FALSE,FALSE,FALSE,FALSE}
Output = Integer.MIN+1
O(n^2 (log n )+m) solution, m-#outputs:
1. Generate all possible pairs ( 2 value combinations) from the array values. Sum the values of the pair and subtract it from the target sum x , in this case 4. Lets call it as T. - O(n^2)
The idea is, a pair when joined with another pair whose sum is T will form a 4 value array whose sum is 4. Since we are generating all possible pairs from the original array, a cross join will provide all the possible 4 value array. But doing a naive cross join and filter for sum 4 will incur O(n^4) runtime. But here we will join pairs only when their sum is 4, making it O(m) runtime.
2. Bucket the pairs according to their sum. E.g. <1,2> and <4,-1> paris will go in to bucket(3). -- O(n^2)
3. For each bucket (if not already joined with another bucket) get the bucket whose value is 4 - current bucket sum. E.g. Join bucket(5) and bucket(-1). In order to find the right bucket for joining, the buckets have to be sorted by their number. We can also use hash table here. -- O(n^2 log n)
4. In each joined bucket, generate all possible 4 value array from the pairs and output it - O(M)
E.g.
Input: {1,2,3,5,0,-2} , x=4 i.e. a+b+c+d=4
All possible pairs:
{<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,0>,<1,-2>
<2,2>,<2,3>,<2,4>,<2,5>,<2,0>,<2,-2>,
<3,3>,<3,4>,<3,5>,<3,0>,<3,-2>,
<4,4>,<4,5>,<4,0>,<4,-2>,
<5,5>,<5,0>,<5,-2>,
<0,0>,<0,-2>,
<-2,-2>}
Bucket(-4)
<-2,-2>
Bucket(-2)
<0,-2>
Bucket(-1)
<1,-2>
Bucket(0)
<2,-2>,<0,0>
Bucket(1)
<1,0>,<3,-2>
Bucket(2)
<1,1>,<2,0>,<4,-2>
Bucket(3)
<1,2>,<3,0>,<5,-2>
Bucket(4)
<1,3>,<2,2>,<4,0>
Bucket(5)
<1,4>,<2,3>,<5,0>
Bucket(6)
<1,5>,<2,4>,<3,3>
Bucket(7)
<2,5>,<3,4>
Bucket(8)
<3,5>,<4,4>
Bucket(9)
<4,5>
Bucket(10)
<5,5>
Buckets {-4 and 8}, {-2 and 6}, {-1 and 5}, {0 and 4}, {1 and 3}, {2 and 2}
Output of corresponding buckets:
<-2,-2,3,5>,<-2,-2,4,4>
<0,-2,1,5>,<0,-2,2,4>,<0,-2,3,3>,
<1,-2,1,4>,<1,-2,2,3>,<1,-2,5,0>,
<2,-2,1,3>,<2,-2,2,2>,<2,-2,4,0>,<0,0,1,3>,<0,0,2,2>,<0,0,4,0>
<1,0,1,2>,<1,0,3,0>,<1,0,5,-2>,<3,-2,1,2>,<3,-2,3,0>,<3,-2,5,-2>
<1,1,1,1>,<1,1,2,0>,<1,1,4,-2>,<2,0,1,1>,<2,0,2,0>,<2,0,4,-2>,<4,-2,1,1>,<4,-2,2,0>,<4,-2,4,-2>
O(n^2) solution:
Sort the string using bubble sort and go through the array deleting the character that is same as the previous character in the sorted string. Deleting, in place, a character at position "i" can be achieved by moving right in the string and finding a character that is not the same character being deleted and moving it to the ith place and repeating the process.
O(n) solution:
Use boolean array of length equal to the size of the character set -- O(1) memory
For every character in the string, set the corresponding index in the boolean array to true. -- O(n)
Traverse the given string and delete the character if the boolean value for it is FALSE else set the boolean value to FALSE and move on to next character. This process will preserve the order of characters in the string as we de-dupe it.
O(1) solution:
Not possible as we have to look at each character of the given string before we can conclude it is a duplicate one.
Given: w={w1, w2, .... wN}
output: n with probability of (wn/sum(w))
Create a non zero weight array, W, with another array containing their corresponding index+1, K.
for example: w={11,22,13,0,2}
create 2 arrays W={11,22,13,2} and K={1,2,3,5} --- O(N)
Generate a cumulative array of weights, Wc = {Wc1, Wc2, ... WcN} where Wci=Wc(i-1)+Wi for i=2...N and WC1= W1 --- O(N)
For every input call generate a random number, r.
let R=floor(r*WcN), so that R will be distributed randomly between 0 and WcN-1, remember WcN = sum(w)
I can think of two ways to solve this, one in O(log N) time and another in O(1) time but needs O(sum of w, i.e.WcN) memory.
O(log N) solution:
Do a binary search on Wc to find i such that Wc(i-1)<=R<Wci, assume Wc-1=-1
Then output K[i]
O(1) solution:
Precompute output for full range of R (0 ... WcN-1) and store in an array of length WcN. You can look up an array after computing R for each input in O(1)
p=0
for i from 0 to W.length-1
for j=1 to W[i]
O[p]=K[i]
p++
end
end
E.g.
input: w={3,1,2,0,2}
W={3,1,2,2}
K={1,2,3,5}
Wc={3,4,6,8}
R={0,1,2,3,4,5,6,7}
O={1,1,1,2,3,3,5,5} (precomputed output)
one index for src and another for dst. Since we are not querying for a specific edge we dont need index on src and dst together.
- Karthik April 15, 2013