Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Very clean, correct solution. Checking A[i] < min is unnecessary because it's always true unless they're equal (since your array is sorted). Better to skip that if statement. Also no need to maintain a set. Try just:
i = A.length-1;
while ( (i>=1) && (A[i-1] + A[i] >= K) )
{
--i;
}
return A.subArrayStarting(i);
Hell, you could even do a binary search. Won't really matter because your algo is O(N logN) because of the sort. There's an O(N) algo.
O(n) algo ( without sorting )
1. max = maximum element seen still yet. Initialize with A[0]
1. start from second element of A.
2. stop if next visited element i.e A[i] + max is >= K.
3. Now we have got our first element in the set. i.e maximum of A[i] and max. Store the min of these two in the min. (min is min element in the set)
4. next check for all element whose when added with min then the result >= K. update the min and continue.
std::vector<int> numSet;
int i = 1;
int max = A[0];
int min = 0;
for (i = 1; i < n; ++i) {
if (max + A[i] < K) {
if (max < A[i]) max = A[i];
} else {
min = (max < A[i]? max: A[i]);
if (min == A[i])
numSet.push_back(max);
else
numSet.push_back(A[i]);
}
for (j=i+1; j <n; ++j) {
if (min+A[j] >= K) {
if (min < A[j]) {
numSet.push_back(A[j]);
} else {
numSet.push_back(min);
min = A[j];
}
}
}
numSet.push_back(min);
}
First we sort the array. Assume A is sorted.
Let B be a subset of A whose minimum element is b. Now every element x in B must be at least K-b.
So, here is the algorithm: for every element in A, see how many elements are at least K minus that element. Take the maximum over all.
This takes O(n logn) in total
I didn't get your solution. Could you please explain more elaborately, may be with some pseudo code ?
sort(A)
max = 0;
max_index = 0;
for (int i=0; i < A.size(); i++){
int x = {the minimum index such that} A[x] >= K-A[i]
if (n-x >= max){
max = n-x;
max_index = i;
}
}
for (int i=0; i < A.size(); i++)
if (A[i] >= A[max_index])
cout << A[i] << " ";
if the example in the question is what is required then here's an O(n) solution. all the elements >= k/2 should be in the result set.
This is almost correct. The only thing is that you might include one element < k/2 depending on the parameters of the set >= k/2
void printMaxSubsetWithAllPairSumMoreThanK(int[] a, int k) {
int minSubsetElement = Integer.MAX;
for (int i = 0; i < n; ++i) {
if (a[i] > (k >> 1)) {
System.out.println(a[i]);
if (minSubsetElement > a[i]) {
minSubsetElement = a[i];
}
}
}
for (int i = 0; i < n; ++i) {
if (minSubsetElement > a[i] && minSubsetElement + a[i] > k) {
System.out.println(a[i]);
break;
}
}
}
A refined solution of 'Anonymous' :)
It is O(n) solution and only requires 2 passes over the array. Would like to see if there are any cases breaking the code. Code follows:
int A[] = {1,2,3,4,10,5,6,7,8,9} ;
int array_length = sizeof (A)/sizeof(int) ;
int B[100], b_index = 0 ;
int max_elem = 0, max_index = 0, K = 14;
max_elem = get_max_value(max_index, A, array_length) ;
std::cout<<"Max Elem:"<<max_elem<<endl;
std::cout<<"Max Pos :"<<max_index<<endl;
B[b_index++] = max_elem ;
for (int index = array_length - 1; index >=0 ; --index)
{
if (index == max_index)
continue ;
if ((A[index] + max_elem) > K)
{
B[b_index++] = A[index] ;
if (A[index] < max_elem)
{
max_elem = A[index] ;
}
}
}
max_elem is the size of longest such set and B[] contains the set itself.
1, loop over array
if (element >= k/2){
store it in result array
}
2, find the smallest one in result array
3, loop over array
if(element + smallest one > k){
add element in result array
}
4, return result array
step 3 can be optimized cause the elements in result array can be skipped
This solution is almost correct except for a minor bug. We should not add all elements satisfying the if() condition of the third step, because then two elements added in this manner will have a sum less than k. Instead, if there are say 'm' number of elements satisfying the if() condition of the 3rd step, then we have 'm' different subsets with the same length satisfying the all pair sum criterion of the question. All of these should be displayed...
private static Set printMax(int[] a, int length, int k) {
int diff = k- a[0];
int i=1;
Set<Integer> result = new HashSet<Integer>();
result.add(a[0]);
while (i <length){
if (a[i] > diff){
result.add(a[i]);
int tempDiff = k-a[i];
if (tempDiff > diff){
diff = tempDiff;
}
}
i++;
}
return result;
}
- Anonymous November 14, 20111. sort the array A => 1,2,3,4,5,6,7,8,9 2. Include the max element in the set S i.e S = {9} and min = 9, i = 8 (index of max) 3. now for all i. If (A[i] + min >= K) then add A[i] into set S. if (A[i] < min) then min=A[i] --i