Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Jul 1, 2011
Given an unsorted array of integers, find first two numbers in the array that equal a given sum.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (6)
1 of 2 people found this helpful
Jul 6, 2011
Sort the array. O(nlogn)
take two pointer at head( index 0 ) and tail (index array.length-1)
while (head <tail){
s= array[head]+array[tail]
if(s<sum)
head++
else if(s>sum)
tail--
else
print head and tail
}
take two pointer at head( index 0 ) and tail (index array.length-1)
while (head <tail){
s= array[head]+array[tail]
if(s<sum)
head++
else if(s>sum)
tail--
else
print head and tail
}
Helpful Answer?
Yes |
No
Inappropriate?
8 of 9 people found this helpful
Jul 6, 2011
The question is ill-posed. What does 'the first two numbers" mean? Suppose that the numbers at indices 1 and 100 add up to the given sum, as well as the numbers at indices 2 and 5, as well as those at indices 3 and 4. Which one of these three pairs constitute "the first two numbers"?
Finding a valid pair can be done in linear time with hashing: (1) hash al the numbers, together with their index in the array, into a hashmap (2) for every insertion of a number n, do a lookup of (sum - n) to check if that value is in the hashmap too. If so, you have found your pair.
Finding a valid pair can be done in linear time with hashing: (1) hash al the numbers, together with their index in the array, into a hashmap (2) for every insertion of a number n, do a lookup of (sum - n) to check if that value is in the hashmap too. If so, you have found your pair.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 3 people found this helpful
Jul 14, 2011
Here you go, an excuse for me to play a bit with Ruby and an excuse for you to learn it:
def find2sum(array,desired_sum)
the_hash=Hash.new
i=0
array.each do |elt|
complement = desired_sum-elt
lookup = the_hash[complement]
if (lookup == nil)
the_hash[elt]=i
else
#puts "soln found, complement=#{complement} at index=#{lookup}, with #{elt} at #{i}"
return [lookup,i]
end
i=i+1
end
#puts "soln not found!"
return[-1,-1]
end
puts find2sum([39,5,15,3,7,9,16,30,23],30)
def find2sum(array,desired_sum)
the_hash=Hash.new
i=0
array.each do |elt|
complement = desired_sum-elt
lookup = the_hash[complement]
if (lookup == nil)
the_hash[elt]=i
else
#puts "soln found, complement=#{complement} at index=#{lookup}, with #{elt} at #{i}"
return [lookup,i]
end
i=i+1
end
#puts "soln not found!"
return[-1,-1]
end
puts find2sum([39,5,15,3,7,9,16,30,23],30)
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Aug 3, 2011
Ok im on a tablet so i ll keep it short.
make an array up to sum/2.
Scan thru the list.
If u find int represented by array or its counter part, mark the the space.
Eg 2+5 equals 7
if 2 or 5 comes along put that in 2.
Now do that until u bump into 5 or other number before. U know?
its easy just think bout it.
make an array up to sum/2.
Scan thru the list.
If u find int represented by array or its counter part, mark the the space.
Eg 2+5 equals 7
if 2 or 5 comes along put that in 2.
Now do that until u bump into 5 or other number before. U know?
its easy just think bout it.
Helpful Answer?
Yes |
No
Inappropriate?
Jan 29, 2012
Sort the array. go with two pointers one from the begining and one from the end, each time comparing the sum and moving the pointers accordingly. the complexity is o(nlogn) which is the sort.
package com.google.interview2;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindSum {
public static int[] findSum(ArrayList<Integer> array, int sum){
Collections.sort(array);
int i=0, j=array.size()-1;
while (i<j){
if ((array.get(i) + array.get(j)) == sum){
int[] indexes = {array.get(i),array.get(j)};
return indexes;
}
else if (array.get(i)+array.get(j) > sum){
--j;
}
else {
++i;
}
}
return null;
}
public static void main(String[] args) {
List<Integer> arr = new ArrayList<Integer>();
arr.add(7); arr.add(-9); arr.add(1); arr.add(0); arr.add(79);
int[] res = findSum((ArrayList<Integer>) arr,7);
if (res != null){
System.out.println("found "+res[0]+"+"+res[1]);
}
else{
System.out.println("not found");
}
res = findSum((ArrayList<Integer>) arr, 76);
if (res != null){
System.out.println("found "+res[0]+"+"+res[1]);
}
else{
System.out.println("not found");
}
}
}
package com.google.interview2;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class FindSum {
public static int[] findSum(ArrayList<Integer> array, int sum){
Collections.sort(array);
int i=0, j=array.size()-1;
while (i<j){
if ((array.get(i) + array.get(j)) == sum){
int[] indexes = {array.get(i),array.get(j)};
return indexes;
}
else if (array.get(i)+array.get(j) > sum){
--j;
}
else {
++i;
}
}
return null;
}
public static void main(String[] args) {
List<Integer> arr = new ArrayList<Integer>();
arr.add(7); arr.add(-9); arr.add(1); arr.add(0); arr.add(79);
int[] res = findSum((ArrayList<Integer>) arr,7);
if (res != null){
System.out.println("found "+res[0]+"+"+res[1]);
}
else{
System.out.println("not found");
}
res = findSum((ArrayList<Integer>) arr, 76);
if (res != null){
System.out.println("found "+res[0]+"+"+res[1]);
}
else{
System.out.println("not found");
}
}
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
2 of 2 people found this helpful
by Interview Candidate:
Build a binary tree out of the array, do a traversal of the tree, and use the fact SUM = A + B, where A is the node you are currently visiting. Do a binary search of B. Was asked to come up with a O(N) solution.