Pergunta de entrevista da empresa Booking.com
Given an array, find there are 3 numbers have
when we add them the value will equals a specified sum
Example:
{1,4,6,10,20,21}
Sum=32, Result:true (1+10+21)
Sum=65, Result:false
Respostas da entrevista
Used 3 for loops, asked on complexity. Said O(n*n*n), should have thrown other solution with 2 loops to make it O(n*n).
Its a 3 sum problem that you can achieve using in O(n^2) as a+b+c = 32; so in O(n^2) you can calculate a+b-32 and store it in HashSet and get value in O(n) . So the final complexity would be in O(n^2)
Can be reduced to O(n*n) if we sort the array first and then use two loops.
Here is the logic how I have achieved-
1. First sorted the array using QuickSort( complexity O(nlogn)
2. In outer loop pick one element and and for other two go to inner loop.
3. In inner loop point first element and last element
4. Check the sum of there if its less than the provided number increase the lower counter else decrese the higher counter.
Here is pseudocode -
private static void printNumbers(int[] arr, int x) {
int last = arr.length - 1;
quickSort(arr, 0, last);
for (int i = 0; i arr[j] + arr[k]) j++;
else k--;
}
}
}
import java.util.HashMap;
import java.util.Map;
public class BookingGlassDoor {
public static void main(String[] args) {
int result = 6;
int[] arr = {1,4,5,10,20,21};
if(solution(result, arr))
System.out.println("hello");
}
private static boolean solution(int result, int[] arr) {
Map map = new HashMap();
int num = 0;
for (int i = 0; i 0 & isInRestOfMap(map, num, i, j))
return true;
}
}
return false;
}
private static boolean isInRestOfMap(Map map, int num, int i, int j) {
int index;
if(map.containsKey(num)){
index = map.get(num);
if(index != i && index != j)
return true;
}
return false;
}
}