Amazon Interview Question SDE1s
Team: Software Developer, Infrastructure Planning, Analysis and Optimization
Country: United States
Interview Type: Phone Interview
void FindIntsWithSum(unsigned int[] array, unsigned int sum)
{
if(0 == array.length)
return;
Dictionary<unsigned int, unsigned int> myDict = new Dict();
for(int index = 0; index < array.length; ++index)
{
if(myDict.contains(sum - array[index]))
{
Console.WriteLine("{0} & (1}", array[index], myDict.key(sum - array[index]));
return;
}
else
{
myDict.add(array[index]);
}
}
Console.WriteLine("This array does not contain values that sum upto: {0}", sum);
return;
}
// Test cases
// Empty array
Single element array
Large array -- Blow the memory
Small array
Arrays with lot of duplicates
Array without sum of the integer ...
Array with multiple combination...
Performance, Memory: (Large and small array)
Simple tests: Small arrays with sum present : Basic P1
Check for buffer overflow
I've checked and slightly corrected your code. Now it works fine.
static void FindIntsWithSum( int[] array, int sum)
{
if(0 == array.Length)
return;
Dictionary<int, int> myDict = new Dictionary<int, int>();
for(int index = 0; index < array.Length; ++index)
{
if(myDict.ContainsValue(sum - array[index]))
{
Console.WriteLine("{0} & {1}", array[index], myDict.FirstOrDefault(x => x.Value == sum - array[index]).Value);
return;
}
else
{
myDict.Add(index, array[index]);
}
}
Console.WriteLine("This array does not contain values that sum upto: {0}", sum);
return;
}
@Pradeep. Code was not working completely I added a line in that code.
int a[]={12,3,5,4,8,7,2,6,5,89,78,4,5,68,58,4,8,8,5};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int diff;
for(int i=0;i<a.length;i++)
{
if(a[i]<=10)
{
diff=10-a[i];
if(map.containsKey(diff))
{
System.out.println(a[i]+" "+diff+"= 10");
if(!map.containsKey(a[i])){
map.put(a[i],i);
}
}
else
{
map.put(a[i], i);
}
}
}
Here are a couple of ways I would do it:
class SumOfTwoNumbers {
public static void main(String... args) {
int[] largearr = {5,9,1,100,5000,0};
for (int i : largearr) {
for (int j : largearr) {
if ((i+j) == 10) {
System.out.println(i + " " + j);
}
}
}
}
}
and
class SumOfTwoNumbers2 {
public static void main(String... args) {
int[] largearr = {5,9,1,100,5000,0};
Set<Integer> allInts = new HashSet<Integer>();
for (int i : largearr) {
allInts.add(i);
}
for (int i : largearr) {
int diff = 10-i;
if (allInts.contains(diff)) {
System.out.println(i + " " + diff);
}
}
}
}
import java.util.HashMap;
import java.util.Map;
public class QuicklyFindingSumOFTwoNumber {
public static void main(String[] args) {
Map<Integer ,Integer> valueMap = new HashMap<Integer ,Integer>();
int a[] = { 0,10,2,3,4,5,6,7,8,9,0,123,34};
for(int i=0;i<a.length;i++){
if(a[i]<=10){
int temp = 10-a[i];
if(valueMap.containsKey(temp)){
System.out.println("positions :("+valueMap.get(temp) +" " + i +")" + temp +" " + a[i]);
System.exit(0);
}
valueMap.put(a[i], i);
}
}
}
}
C++ implementation with O(n) time complexity and O(1) space complexity.
# include <iostream>
void findSum (unsigned int *arr, int len) {
int index[] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
for (int i = 0; i < len; ++i) {
if (arr[i] <= 10) {
if (index[10 - arr[i]] == -1) {
index[arr[i]] = i;
}
else {
std::cout << "Indexs are " << index[10 - arr[i]] << " " << i << "\n";
return;
}
}
}
std::cout << "No two numbers with sum 10\n";
}
int main () {
unsigned int arr1[] = {0, 2, 5, 4, 3, 8};
unsigned int arr2[] = {1, 2, 1, 9, 8, 2};
unsigned int arr3[] = {3, 0, 13, 10, 3, 1};
unsigned int arr4[] = {3, 4, 5, 0, 5, 1};
unsigned int arr5[] = {9, 4, 3, 3, 4, 3};
unsigned int arr6[] = {11, 32, 45, 12, 24, 93};
unsigned int arr7[] = {3, 2, 13, 10, 3, 1};
findSum (arr1, 6);
findSum (arr2, 6);
findSum (arr3, 6);
findSum (arr4, 6);
findSum (arr5, 6);
findSum (arr6, 6);
findSum (arr7, 7);
return 0;
}
/**
*
*/
package h;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author vaio
*
*/
public class twoNoWhosSumis10 {
/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int n,i,j,sum,k,l,r,s;
System.out.println("how large you want to make the array of unsigned int");
n=Integer.parseInt(br.readLine());
int arr[]=new int [n];
int dupli[]=new int [n];
for(i=0;i<n;i++)
{
System.out.println("Enter your value into the postion no "+(i+1)+" in the array");
j=Integer.parseInt(br.readLine());
if(j<0){
System.out.println("Did you forget that we are dealing with array of unsigned int!!! Re-enter ");
j=0;
i--;
}else{
arr[i]=j;
}
}
k=-1;l=-1;
r=0;s=1;
int flag1=0;int flag2=0,q;
dupli[0]=-1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
if(i!=j){
sum=arr[i]+arr[j];
if(sum==10 && k!=arr[i] && l!=arr[j] && k!=arr[j] && l!=arr[i]){
k=arr[i]; l=arr[j];
for(q=0;q<s;q++){
if(dupli[q]==k){
flag1=1;
break;}
else
flag1=0;
}
for(q=0;q<s;q++){
if(dupli[q]==l){
flag2=1;
break;}
else
flag2=0;
}
if(flag1==0 && flag2==0){
dupli[r]=k;
dupli[s]=l;
r+=2; s+=2;
System.out.println("The two number whose sum is 10 are "+k+" and "+l);
}
}
else{
continue;
}
}
}
}
}
}
If required sum is less than number of bits in long,we can use bit operations to provide the solution.(given numbers are unsigned int's)
c++ code:
#include<iostream>
using namespace std;
int main()
{
long check=0;
int A[100],n;
cout<<"enter number of elements in array\n";
cin>>n;
cout<<"enter elements\n";
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<n;i++)
{
int num=10-A[i];
int check_tmp=1;
if(num>=0)
{
// checking 10-current_num already exists in list or not
check_tmp=check_tmp<<num;
if((check & check_tmp) >0)
{ cout<<"first pair is"<<num<<"\t"<<A[i]<<endl;
return 0;
}
//if 10-current_num doesn't exist then we'll make the bit in current num's position to 1
check_tmp=1;
check_tmp=check_tmp<<A[i];
check=(check | check_tmp);
}
}
return 0;
}
small correction on comment in code
// If (10-current_num) doesn't exist in already parsed array elements, then we'll make the bit in (current num+1) position to 1.
Note:we are using (current num+1)position instead of current num position because if current num is 0 then we are making check's right most bit as 1 to handle (0,10) case.
Pros:
time complexity -worst case O(n)
space complexicity: O(1) (we are using only 2 variables)
bit operations are faster
public class Check {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = { 3, 10, 12, 5, 8, 2, 0, 7 };
boolean flag = false;
if (a.length == 0) {
System.out.println("Empty array");
} else {
int i = 0, j = 0;
while (i < a.length) {
while (j < a.length) {
int x = a[i] + a[j];
if (x == 10) {
System.out.println(a[i] + " " + a[j]);
flag = true;
break;
} else {
j++;
}
}
i++;
j = i;
}
if (flag == false)
System.out.println("No combo");
}
}
}
is above program fine in interview w.r.t time complexity
class FindTwoWithGivenSum{
public static void main(String... a){
int[] arr = {5,4,6,1,11,8};
int number = 10;
// Sorted !!
for(int i=arr.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
for(int i: arr){
System.out.print(i);
}
// Find closest smallest element for a given no.
int indexClosest = 0;
for(;indexClosest<arr.length;indexClosest++){
if(number<arr[indexClosest]){
indexClosest--;
break;
}
}
if(indexClosest == arr.length){
indexClosest--;
}
System.out.println("\n closest Index:"+indexClosest);
boolean solutionFound = false;
if(indexClosest>=0){
int startIndex = 0;
int endIndex = indexClosest;
while(startIndex<endIndex && !solutionFound){
if(arr[startIndex]+arr[endIndex] ==number){
System.out.println(arr[startIndex]+","+arr[endIndex]);
solutionFound=true;
}
else if(arr[startIndex]+arr[endIndex] > number){
endIndex--;
}
else{
startIndex++;
}
}
}
if(!solutionFound){
System.out.println("No such combination of numbers found in given array!!");
}
}
}
1) sort the given array in ascending order till the max value of 10.it means now the array contains only elements from 0 -10
2) then loop thru the array from beginning till middle of the array(outer loop)
fetch the first element
then subtract from 10 get the reminder
3) loop thru the array from end till middle(inner loop)
search for the reminder from the end of the array till middle.
if found break else conitinue step 3
repeat step 2
Done in O(n) complexity with O(n) memory:
public static int[] getSum(int[] arr, in sumTo){
if(arr == null || sumTo < 1){
return null;
}
HashSet<Integer> cache = new HashSet<Integer>();
for(int i : arr){
int otherSum = sumTo - i;
if(cache.contains(otherSum)){
return new int[]{i, otherSum};
}
}
return null;
}
(edit: fixed logical bug)
O(n)
- Alfredo November 26, 2014We go across the array (which is large and maybe distributed) and capture the index of all numbers below 10 (from 0 to 10). The rest are discarded.
When we find a number below 10, we look for its partner (2 to 8, 3 to 7, 0 to 10) and check whether we have a registered index, if not we append the index we have in a dictionary identified by the original number and continue examining the array.
When two partners are found we print their indexes in screen.
In a distributed system, we could send to a centralized computer or broadcast everytime we find numbers below 10, or after certain amount of time depending on P(X<10).
indexes={0:[], 1: [], 2:[] ... 10:[]}
L=[1,7,8,10,34,3....]
for i in range(len(L)):
if L[i] < 11:
if len(indexes[10-L[i]]) >0:
print indexes[10-L[i]], i
else:
indexes[L[i]].append(i)