zhangtemplar
BAN USER
Comments (5)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Use Python and cost is o(log2(n))
def square(x):
if x<0:
return square(x)
else:
return mul(x,x)
def mul(x, y):
if y==1:
return x
elif y==0:
return 0
else:
Return mul(x,y>>1)<<1+mul(x,y(y>>1)<<1)

zhangtemplar
May 01, 2016 Comment hidden because of low score. Click to expand.
0
of 0 vote
Can't we use Kmeans algorithm for this purpose?
 zhangtemplar February 17, 2014Comment hidden because of low score. Click to expand.
0
of 0 vote
I also think this is the dynamic programming problem.
/**
* we define the following function f(int []a, int k, Char [] f)
* where a is the set of players used
* k is the required # of followers
* f is list of current followers
* output is the # player used.
* f(a, k, f)=min_i {f(a U i, k, merge(f, arr[i]))}
*/
Comment hidden because of low score. Click to expand.
0
of 0 vote
/**
* Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
* The simple way has complexity O(n^3). However, we use the knowledge that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++. By doing this way, the complexity is O(n) or more exactly O(3n)
*/
public static void minDifference(int [] arr1, int []arr2, int []arr3)
{
if (arr1==null  arr1.length<1  arr2==null  arr2.length<1  arr3==null  arr3.length<1)
{
System.out.println("Illegal input");
return;
}
long min=Long.MAX_VALUE;
long tmp;
int i, ii, j, jj, k, kk;
i=0;
j=0;
k=0;
ii=0;
jj=0;
kk=0;
while(i<arr1.length && j<arr2.length && k<arr3.length)
{
// check the best until now
tmp=(long) Math.abs(arr1[i]arr2[j])+Math.abs(arr2[j]arr3[k])+Math.abs(arr1[i]arr3[k]);
if (min>tmp)
{
min=tmp;
ii=i;
jj=j;
kk=k;
}
// this is the best of possible
if (tmp<=0)
{
break;
}
// find next step
// we know that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++
if (i<arr1.length1 && arr1[i]<=arr2[j] && arr1[i]<=arr3[k])
{
i++;
}
else if (j<arr2.length1 && arr2[j]<=arr1[i] && arr2[j]<=arr3[k])
{
j++;
}
else if (k<arr3.length1 && arr3[k]<=arr1[i] && arr3[k]<=arr2[j])
{
k++;
}
else
{
// though it should never be reached
break;
}
}
System.out.println("The sum of the minimum differences is "+min+": a["+ii+"]="+arr1[ii]+", b["+jj+"]="+arr2[jj]+" and c["+kk+"]="+arr3[kk]);
}

zhangtemplar
August 12, 2013 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
How about dynamic programming:
 zhangtemplar May 03, 2016f[i] the number of sentence made from s[:i]
f[0]=1
f[i]=\sum_j{f[j]*(s[j:i] in dictionary)}
return f[1] as the result.
The cost would be o(n2)