Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: Phone Interview
Sorry for typo.....correct version
public void printPairs(int[] array, int sum) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
map.put(array[i], i);
}
for (int i = 0; i < array.length; i++) {
int other = sum - array[i];
if (other != array[i] && map.containsKey(other)) {
System.out.println("(" + array[i] + "," + other + ")");
}
}
}
- Sort the array first using quick sort
- then you can use the following logic
public static void sum(int []array,int sum){
int start = 0,end=array.length-1;
while(start<end){
if(array[start]+array[end]==sum)
{
System.out.println(array[start]+ ", "+array[end]);
start++;
end--;
}
else if(array[start]+array[end] > sum){
end--;
}
else if(array[start]+array[end] < sum){
start++;
}
}
}
1. Sort the array.
2. Take two pointers and traversing the array from both sides and check if sum of pair of elements is equal to required sum.
3. If sum of array elements is less than required value than move front point by one step.
4. else move back pointer one step.
If at any place value matches then print the two.
public static void main(String[] args) {
int arr[] = {2,5,3,8,1,0,3,5,7,2, 4};
int num = 5;
for(int i=0; i<arr.length-1; i++){
for(int j=i+1; j<arr.length; j++){
if(arr[i]+arr[j] == num){
System.out.println("{"+arr[i]+", "+arr[j]+"} ");
break;
}
}
}
}
Time Complexity - O(n)
public void printPairs(int[] array, int sum) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < array.length; i++) {
map.put(array[i], i);
}
for (int i = 0; i < array.length; i++) {
int other = sum - array[i];
if (other != array[i] && map.containsKey(other)) {
System.out.println("(" + array[i] + "," + other + ")");
}
}
}
package comdefault;
public class Stringarray {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int count=5;
int a[]={1,2,3,4,5};
int len=(a.length)-1;
System.out.println("length"+len);
for(int i=0;i<=len;i++)
{
for(int j=len;j>=0;--j )
{
if (count==( a[i]+ a[j]))
{
System.out.println("Test"+a[i]+"," +a[j] );
}
}
}
}
}
void fun1 (int* a, int num, int length)
{
int len= 0, temp=0;
for (int i=0; i<length;i++)
{
for (int j=0; j< length; j++)
{
temp= a[i]+a[j];
if (temp == num)
{
cout << "{\t" << a[i] << "," << a[j] << "\t}\n";
}
}
}
}
int main()
{
int array[]= {1, 4, 0, 2, 3, 6, 5, 7, 9};
int len=sizeof(array)/ sizeof(array[0]);
int result=6;
fun1(array,result, len);
}
I have solved the code using Perl.
my @arr = qw(0 1 2 3);
my $start =0;
my $end = scalar(@arr)-1;
my $sum = 3;
foreach(@arr){
if($arr[$start] + $arr[$end] == $sum){
print("\n".$arr[$start].",".$arr[$end]."\n");
$start++;
$end--;
}elsif($arr[$start] + $arr[$end] > $sum){
$end--;
}else{
$start++;
}
}
Here is the very simple implementation for this problem
import java.util.*;
public class SumOfNumArr{
public static void main(String []args){
int[] arr = {1,0,2,3};
int num = 3;
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length;j++){
if(arr[i]+arr[j]==num)
System.out.println(arr[i] +", " + arr[j]);
}
}
}
}
/*
* write a program takes array input{1,0,2,3} and num =3.and provides output {1,2}{0,3}{2,1}{3,0} sum equals the num.
*
*/
public static void printPairs(int arr[], int sum){
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
temp= arr[i]+arr[j];
if(temp==sum){
System.out.println("["+arr[i]+"," +arr[j]+"],");
}
}
}
}
int[] sumEquals = {0,1,2,3};
int[] result= {};
int n=3;
for (int a= 0; a<sumEquals.length;a++){
for (int b= 0; b<sumEquals.length;b++){
//System.out.println("numbers - "+ sumEquals[a]+"---"+sumEquals[b]);
if (sumEquals[a]+sumEquals[b]==n){
System.out.print("{"+ sumEquals[a]+","+sumEquals[b]+"}");
}
}
}
int[] sumEquals = {0,1,2,3};
int[] result= {};
int n=3;
for (int a= 0; a<sumEquals.length;a++){
for (int b= 0; b<sumEquals.length;b++){
//System.out.println("numbers - "+ sumEquals[a]+"---"+sumEquals[b]);
if (sumEquals[a]+sumEquals[b]==n){
System.out.print("{"+ sumEquals[a]+","+sumEquals[b]+"}");
}
}
}
*********************
int[] sumEquals = {0,1,2,3};
int[] result= {};
int n=3;
for (int a= 0; a<sumEquals.length;a++){
for (int b= 0; b<sumEquals.length;b++){
//System.out.println("numbers - "+ sumEquals[a]+"---"+sumEquals[b]);
if (sumEquals[a]+sumEquals[b]==n){
System.out.print("{"+ sumEquals[a]+","+sumEquals[b]+"}");
}
}
}
**************************
Approach1:
public static ArrayList<String> findPairs(int arr[], int sum) {
int len = arr.length;
ArrayList<String> arrOfPairs = new ArrayList<String>();
for (int i = 0; i <= len - 1; i++) {
for (int j = 1; j <= len - 1; j++) {
if (sum == arr[i] + arr[j]) {
arrOfPairs.add(String.valueOf(arr[i] + "," + arr[j]));
}
}
}
return arrOfPairs;
}
Approach2:
public static ArrayList<String> findPairsAgain(int arr[], int sum) {
int len = arr.length;
int j = len - 1;
ArrayList<String> arrOfPairs = new ArrayList<String>();
for (int i = 0; i <= len - 1; i++) {
if (arr[i] + arr[j] == sum) {
arrOfPairs.add(String.valueOf(arr[i] + "," + arr[j]));
} else if (arr[i] + arr[j] < sum) {
i++;
} else if (arr[i] + arr[j] > sum) {
j--;
}
}
return arrOfPairs;
}
So many questions:
- Andy October 08, 20131)What are the restrictions on the values in the input arrray? Is there duplicates allowed?
2)Restrictions on num?
2)Output only pairs of numbers that add up to sum, or subsets?