## Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Try this out...

``````int start=0, end=0;

for(i=0; i<arrary.lenght; i++)
{
for(j=i+1; i<arrary.lenght; j++)

{
if (a[i]+a[j] = number)
{
if (a[i] > a[j])
{
if (a[j] - a[i]) > (end -start)
{
start = a[i]
end = a[j]
}
}
Else
{
if (a[i] - a[j]) > (end -start)
{
start = a[j]
end = a[i]
}
}

}
}

}

CWL("Pair is {{0}, {1}}" , start, end) ;``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````def Find(List, sum):
l = len(List)
for d in range(1,l):
for i in range(l-d):
if(List[i]+List[i+d]==sum):
print List[i],List[i+d]
return``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static Tuple<int, int> FindPair(int[] int_array, int num)
{
int first = -1, second = -1;
int pair_diff = int_array.Count() + 1;
for (int i = 0; i < int_array.Count(); i++)
{
for (int j = i + 1; j < int_array.Count(); j++)
{
if ((int_array[i] + int_array[j]) == num)
{
if ((j - i) < pair_diff)
{
first = int_array[i];
second = int_array[j];

pair_diff = j - i;
}
}
}
}

Tuple<int, int> pair = Tuple.Create(first, second);

return pair;

}``````

Comment hidden because of low score. Click to expand.
0

You solution have problem, in Best case scenario, also run all possible combination. Because you have just try to find all solutions. Best way to go greedy approach and just check distance 1 options first and if find any combination with distance 1 than stop further process and print answer. If not than go for distance 2 options. This way, your complexity will be low in best case scenario and worst case, it will run all pairs.

My Solution:

``````public static void FindPair(int[] input, int num)
{
int distance = 1;
bool isFound = false;
// Check all options with distance 1 and go further
for (distance = 1; distance < input.Length; distance++)
{
for (int i = 0; i < input.Length; i++)
{
if (i + distance < input.Length)
{
if (input[i] + input[i + distance] == 10)
{
isFound = true;
Console.WriteLine(string.Format("({0},{1})", input[i], input[i + distance]));
break;
}
}
}
if (isFound)
break;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a hashtable to store the index of each element. As we iterate through the array, check if the target (10 - current element) is already in the hashtable. If so, we get the value (target's position) and store this pair as the potential result if its distance is shorter than the existing pair (if any). Note that we want to overwrite any existing value with the newer index.

``````class ClosestPair {

static int[] closestPair(int[] arr, int n) {
int[] closest = new int[] {0, Integer.MAX_VALUE};
HashMap<Integer, Integer> seen = new HashMap<Integer, Integer>();
for(int i=0; i<arr.length; i++) {
int target = n - arr[i];
if(seen.containsKey(target)) {
int pos = seen.get(target);
if(i-pos < closest[1]-closest[0]) {
closest[1] = i;
closest[0] = pos;
}
}
seen.put(arr[i], i);
}
return closest;
}

public static void main(String[] args) {
int[] arr = new int[args.length];
for(int i=0; i<args.length; i++) {
arr[i] = Integer.parseInt(args[i]);
}
int[] pair = closestPair(arr, 10);
if(pair[1] == Integer.MAX_VALUE)
System.out.println("No such pair");
else System.out.println("" + arr[pair[0]] + " " + arr[pair[1]]);
}
}``````

Comment hidden because of low score. Click to expand.
0

Same idea in Python. Feels much cleaner.

``````def closest_pair(arr, n):
closest = None
seen = dict()
for index, value in enumerate(arr):
target = n - value
if target in seen:
pos = seen[target]
if(closest == None or index-pos < closest[1]-closest[0]):
closest = (pos, index)
seen[value] = index;
return None if closest == None else (arr[closest[0]], arr[closest[1]])

print closest_pair([1, 7, 5, 3, 9], 10)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do O(n^2) with iterating two loops or O(n) with a hash

O(n^2)
public static Pair<int, int> ClosestPair(int[] input, int num) {
if(input.length < 2) return null;

int firstIndex = -1, secondIndex = - 1, closest_distance = Integer.MAX_VALUE;
for(int i = 0; i < input.length - 1; i++) {
for(int j = i+1; j < input.length; j++) {
int distance = j-i;
if(input[i] + input[j] == num && distance < closest_distance) {
firstIndex = i;
secondIndex = j;
closest_distance = distance;
}
}
}

if(firstIndex == -1 || secondIndex == -1)
return null;

return new Pair(input[firstIndex], input[secondIndex]);
}

O(n)
public static Pair<int, int> ClosestPair(int[] input, int num) {
if(input.length < 2) return null;

//Key is an integer in input. Its value is its index
HashMap<Integer, Integer> inputIndexMap = new HashMap<Integer, Integer>();

int firstIndex = -1, secondIndex = -1, closest_distance = Integer.MAX_VALUE;

for(int i = 0; i < input.length; i++) {
int correspondingIndex = inputIndexMap.get(num - input[i]);
if(correspondingIndex != null && i - correspondingIndex < closest_distance) {
firstIndex = i;
secondIndex = correspondingIndex;
closestDistance = i - correspondingIndex;
}

//We only put after the check because perhaps duplicate values is
//our solution so we don't want to overwrite too soon.
//ex. input[i] == input[j] and input[i] + input[j] == num
HashMap.put(input[i], i);
}

if(firstIndex == -1 || secondIndex == -1)
return null;

return new Pair(input[firstIndex], input[secondIndex]);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The key thing is the 'CLOSEST' pair consideration which I've taken to mean the pair with a sum that is numerically closest to the desired value. A hash table does not make it so easy to find the closest pair since it looks for exact values. Arcane Java constructs could possibly be used like NavigableMap constructs, but those will take more space to fully compute.

If you sort the array ( O(n log n) ), then you should be able to iterate through with runners from the front and the back in (O(n) ). Therefore, you should be able to solve with O(n log n) with no extra space.

``````public static int[] getClosestSumPair(int[] arr, int k){
if(arr == null){
throw new NullPointerException();
}
if(arr.length < 2){
throw new IllegalArgumentException();
}

//sort the array
Arrays.sort(arr);

int lo = 0;
int hi = arr.length -1;
int[] best = new int[]{arr[lo], arr[hi]};
int actualSum = best[lo] + best[hi];
int actualSumDistance = Math.abs(k - actualSum );
int bestSumDist = actualSumDistance;
while(lo < hi - 1){
if(actualSum > k){
hi--;
}
else if(actualSum < k){
lo++;
}
else{
return best;
}
actualSum = arr[lo] + arr[hi];
actualSumDistance = Math.abs(k -actualSum);
if(actualSumDistance < bestSumDist){
best[0] = arr[lo];
best[hi] = arr[hi];
bestSumDist= actualSumDistance ;
}
}
return best;
}

//tests
public static void test_getClosestSumPair_null(){
boolean foundException = false;
try{
getClosestSumPair(null, 0);
}
catch(Exception e){
foundException = e instanceof NullPointerException;
}

assert(foundException);
}

public static void test_getClosestSumPair_1elmt(){
boolean foundException = false;
try{
getClosestSumPair(new int[]{ 1 }, 0){
}
catch(Exception e){
foundException = e instanceof IllegalArgumentException;
}

assert(foundException);
}

public static void test_getClosestSumPair_exact(){
int[] pair = getClosestSumPair(new int[]{1, 7, 5, 3, 9}, 10);
assert(pair != null);
assert(pair[0] = 1);
assert(pair[1] = 9);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a different solution than my first. This one interprets 'closest' to mean the pair with the closest proximity within the array. It operates in worst case O(n^2) but it's actual performance is significantly faster in most cases with O(n) memory using a HashMap:

``````public static int[] getClosestSumPair(int[] arr, int k){
//map the val to positions within the array for all values
HashMap<Integer, Collection<Integer>> valToIndexMap = new HashMap<Integer, Collection<Integer>>();
for(int i = 0; i < arr.length; i++){
int val = arr[i];
Collection<Integer> col : valToIndexMap.get(val);
if(col == null){
col = new ArrayList<Integer>();
valToIndexMap.put(val, col);
}
}

//now construct viable pairs
int bestDist = Integer.MAX_VALUE;
int[] bestPair = null;
for(int i1 = 0; i1 < arr.length; i1++){
int val1 = arr[i1];
//find what the other value needs to be for k = val1 + val2
int val2 = k - val1;
Collection<Integer> col : valToIndexMap.get(val1);
//if the other value exists, then check it
if(col != null){
//for every location at which this value exists in the array
for(Integer i2: col){
//don't consider cases where the same value might be used twice
if(i1 == i2){
continue;
}
//if the distance between these two indices is the new best, capture it
int dist = Math.abs(i1 - i2);
if(dist < bestDist){
bestDist = dist;
bestPair = new int[]{val1, val2};
}
}
}
}
return bestPair;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//Objective C solution
int sumToBeFound = 10;
NSArray *numbersArrayGiven = @[@(1),@(7),@(5),@(3),@(9)];
NSMutableDictionary *finalPair = [NSMutableDictionary new];
[numbersArrayGiven enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
for (NSUInteger k = idx+1; k<numbersArrayGiven.count; k++) {
if ([obj integerValue]+[numbersArrayGiven[k] integerValue] == sumToBeFound) {
NSMutableArray *pairOfNumbers = [NSMutableArray new];
finalPair[@(k-idx)] = pairOfNumbers;
}
}
}];
NSInteger leastDistance = sumToBeFound;
for (int i = 0; i<finalPair.allKeys.count; i++) {
if ([finalPair.allKeys[i] integerValue]<leastDistance) {
leastDistance = [finalPair.allKeys[i] integerValue];
}
}
NSArray *leastArray = finalPair[@(leastDistance)];
NSLog(@"leastArray :%@",leastArray.description);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public String findClosestPair(int[] numArray,int number){
int minDiff=-1;
boolean pairFlag=false;
String closestPossiblePair="";
for(int i=0;i<numArray.length-1;i++){
for(int j=i+1;j<numArray.length;j++){
if(numArray[i]+numArray[j]==number){
pairFlag=true;
int k=numArray[i]-numArray[j];
if(k < 0){k=-(k);}
if(k<minDiff||minDiff==-1){
minDiff=k;
closestPossiblePair=numArray[i]+","+numArray[j];
}

}
}
}
if(pairFlag==false){closestPossiblePair="no pairs are there";}
return closestPossiblePair;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution O(nlogn)

``````void findClosestPair() {
int N = 50;
int arr[] = {4,4,22,6,32,8,2,12};

list<int>::iterator it;
list<int>::reverse_iterator rit;
list<int> l (arr, arr + sizeof(arr)/sizeof(int));
l.sort();
it = l.begin();
rit = l.rbegin();
unsigned int diff = abs(*it + *rit - N);
int l1,l2;
for(;it!=l.end(),rit!=l.rend();) {
cout << "Iteration: " << *it << " " << *rit << " Diff: " << diff << endl;
if(*it>=*rit) {
cout << "Result: " << l1 << " " << l2 << endl;
return;
}

unsigned int d;
if(*it+*rit == N) {
cout << "Result: " << *it  << " " << *rit << endl;
return;
} else if (*it+*rit < N) {
d= abs(*rit + *it - N);
if(d>diff) {
cout << "Result: " << l1 << " " << l2 << endl;
return;
}
l1=*it;
l2=*rit;
it++;
} else {
d = abs(*rit + *it - N);
if(d>diff) {
cout << "Result: " << l1 << " " << l2 << endl;
return;
}
l1=*it;
l2=*rit;
rit++;
}
diff = d;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution is clean and simple.

``````public static int[] solve(int[] array, int size, int num) throws Exception {
for (int distance = 1; distance < size; distance++) {
for (int j = 0; j < size - distance; j++) {
if (array[j] + array[j + distance] == num) {
int[] pair = {array[j], array[j + distance]};
return pair;
}
}
}
throw new Exception("No pairs have that sum.");
}``````

Comment hidden because of low score. Click to expand.
0

``if (array[j] + array[j + distance] == num)``

You might want to check the question again. We are trying to find closest sum here. Exact sum is great but if you cannot find exact sum pair, return the closest sum pair.

Comment hidden because of low score. Click to expand.
0

Thanks for the feedback. How do you know that from the question? If that was what the question intended, wouldn't it have specified?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.