Amazon Interview Question
Software Engineer / DevelopersSorth array using quick sort. o(nlogn) complexity.
Now for each element a[i], find N-a[i] using binary search.O(log n)
I think you can get in O(nlog n) + o(logn) complexity.
u have written "Now for each element a[i], find N-a[i] using binary search.O(log n)"
if there are n elements , and u r doing it for each element,how can it be O(log n), it shud be O(nlogn)
so the correct complexity in worst case is O(nlogn) + O(nlogn) and
not O(nlogn) + O(logn) as has been mentioned.
Using hash table, I think it is possible to do in O(n).
Array : a[]
Sum required : value
1. Take each element, a[i], from the array. Apply hash function, h(a[i]), to it.
1.1. Now apply same hash function to h(value - a[i]). If there exists a value in that place then these two numbers are victim. Here, we need to check that index this hash functions yield is not out of array bounds.
1.2. make an entry in hash table for a[i].
Continue above steps.
1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution
1) Sort the array using Radix sort(O(n))
2) Have 2 pointers , one pointing to start and another pointing to the end of that array
3) sum up the numbers at the index pointed by the pointers, if the sum is greater then required sum, decrease the right pointer, else , increase the left pointer
4) repeat step 3 until u find the two numbers or until the pointers cross each other in which case there is no solution
Think: Dynamic Programming!
This is a good case for the Subset Sum algorithm. Where the value at c[k, u] (k is the index of the value we are using and, u, is the actual weight - the sum) is the actual capacity. This can be done with the max of {(k-1, u-value[k]) + value[k], (k-1, u)}.
If you want to limit it to only 2 values from the array then all you have to do is find the minimum of the recurrence I gave above.. and instead of adding value[k] you add a 1. If c[k, u] gives you 2, then there are 2 values in the aray that add up to u.
Given C, find A and B such that A + B = C.
Answer: choose A to be any number and let B = C - A.
If we can assume that the array is sorted then,
you can have 2 variabled one for first index, other for last index(end).
if sum of values at those index is less than the value needed, increment end index
if the sum is greater than, increment front index
if they are equal, u have found the one needed.
If front equals or crosses over back then its not present in the array.
Did you mean
"f sum of values at those index is less than the value needed, increment end index "
thats because the end index cannot be incremented
The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.
int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}
The two pointer solution works just fine.One needs to sort the array first and the length of the array needs to be specified.Here's the code.
int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
quicksort(arr,len);//Any other alorithm could also be //used
int *first=arr;
int *second=&arr[len-1];
while(first<second)
{
if( (*first + *second)==sum)
{
*num1=*first;*num2=*second;return 0;//success
}
else if ( (*first + *second)>sum)second--;
else {first++);
}
return -1; //Such numbers are not present in the array
}
For unsorted array this code should work:
int find2nums(int *arr,int *num1,int *num2,int sum,int len)
{
if(!arr) return -1; //failure
for (int i=0;i<len-1;i++)
for (int j=i+1;j<len;j++)
{
if (arr[i]+arr[j]==sum)
{
*num1=arr[i];*num2=arr[j];return 0;//success
}
}
return -1; //Such numbers are not present in the array
}
Use inplace sort that will take O(nlogn) time. And have two pointers at:
startindex = 0 and lastindex = last
find the sum if this sum > resultsum
lastindex = lastindex - 1
else if sum < resultsum
startindex = startindex + 1
else // the numbers found.
print element at startindex and lastindex.
do this for until we find the elements.
This will be done in O(n) so, O(nlogn) is the max time with minimal memory.
#define sum 100
#define HASHSIZE 256
int hash[256];
int main()
{
int a[] = {30,70,40,60,50,50};
int index = 0;
for(index=0;index<HASHSIZE;index++)
hash[index]=0;
index =0;
while(index<sizeof(a)/4){
hash[a[index]]=1;
index++;
}
index = 0;
while(index <sizeof(a)/4){
if(hash[(sum-a[index])]==1)
printf("%d and %d\n",a[index],sum-a[index]);
index++;
}
return(0);
}
Just a simple logic, for simplicity not including checks like if element is < sum or not, or if number is -ve etc etc.
1.) Use a bit vector of length = (given_sum)
2.) Scan the array, for each element read, mark the corresponding bit in the bit vector, for example number 5 will set 5th bit to 1 in the bit vector.
3.) Scan the array again, for each element say i check if (sum-i)th bit in the bit vector is SET (or 1. If yes this is the pair. In this way you can find all the pairs.
We can avoid 2nd iteration through the array as well, while scanning the array for the first time, include the checks to find the other paired number as well (whether or not it is set to 1)
1) iterate through the array -- put each value into a hashtable (the key is input[i], the value is the number of times that value has occurred)
2) iterate through the array again -- int myValue = sum-input[i]
3) if myValue == input[i], then make sure myValue occurs in the array more than just once. if it does, then that's a pair
4) if myValue != input[i], then if myValue occurs in the array 1 or more times, then that is a pair.
Using sorting,
Time complexity : o(nlogn)
import java.io.*;
import java.util.*;
public class Sum2
{
// Global variables
static int len=0,sum=0;
private static int array[] =new int[len]; // initialization of array length as 0
public static void main(String args[]) throws NumberFormatException, IOException
{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter length of array");
len =Integer.parseInt(br.readLine()); // take length of array from user
setArray(Arrays.copyOf(getArray(), getArray().length + len)); // reinitialize array to given length
System.out.println("Enter elements:"); // takes input
for(int i=0;i<len;i++)
getArray()[i]=Integer.parseInt(br.readLine());
System.out.println("Enter sum:");
sum =Integer.parseInt(br.readLine());
Sum2 s = new Sum2();
Quicksort q = new Quicksort();
q.sort(0,getArray().length-1); // perform sorting
s.find2sum(); // to find pair in A[] with sum as x
}
/***************************************************************************
* Method for finding pair in A[] with sum as x
***************************************************************************/
void find2sum()
{
System.out.println("Output pairs:");
int lo = 0;
int hi = array.length-1;
while (lo < hi)
{
if((array[lo] + array[hi]) == sum)
System.out.println("Pair with given sum "+sum+" is (" + array[lo]+", "+array[hi]+")");
if((array[lo] + array[hi]) < sum)
lo++;
else
hi--;
}
}
/***************************************************************************
* functions to access array
***************************************************************************/
public static int[] getArray() {
return array;
}
public static void setArray(int array[]) {
Sum2.array = array;
}
}
/***************************************************************************
* QuickSort Algorithm
***************************************************************************/
class Quicksort
{
static Quicksort q1= new Quicksort();
void sort(int low,int high) // Check whether an array is empty
{
if(high<=low)
return ;
int j=partition(low,high);
// recursive call to quickSort() method
sort(low,j-1);
sort(j+1,high);
}
int partition(int low,int high)
{
int i=low;
//System.out.println(s1.getArray()[low]);
int j=high+1;
int pivot=Sum2.getArray()[low];
while(true)
{
while(Sum2.getArray()[++i]<pivot) // find item on low to swap
if (i == high) break; // Boundary case
while(Sum2.getArray()[--j]>pivot) // find item on high to swap
if (j == low) break; // Boundary case
// check if pointers cross
if (i >= j) break;
q1.exchange(i,j);
}
exchange(low, j);
return j;
}
void exchange(int i,int j)
{
int temp=Sum2.getArray()[i];
Sum2.getArray()[i]=Sum2.getArray()[j];
Sum2.getArray()[j]=temp;
}
}
/***************************************************************************
OUTPUT:
Enter length of array
8
Enter elements:
55
181
45
69
-81
3145
31
801
Enter sum:
100
Output pairs:
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
Pair with given sum 100 is (45, 55)
***************************************************************************/
using hashing,
Time complexity : o(n)
import java.io.*;
import java.util.*;
public class Sum2Hash
{
public static void main(String args[]) throws NumberFormatException, IOException
{
Sum2Hash s=new Sum2Hash();
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter array length");
int len =Integer.parseInt(br.readLine());
int array[]=new int[len];
System.out.println("Enter Element");
for(int i=0;i<array.length;i++)
array[i]=Integer.parseInt(br.readLine());
System.out.println("Enter sum:");
int sum =Integer.parseInt(br.readLine());
s.findpairs(array, sum);
}
void findpairs(int array[],int sum)
{
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
for (int i=0; i<array.length; i++)
{
if(pairs.containsKey(array[i]))
System.out.println("Pair with given sum "+sum+" is ("+array[i] +", "+ pairs.get(array[i])+")");
else
pairs.put(sum-array[i], array[i]);
}
}
}
/***************************************************************************
OUTPUT:
Enter array length
8
Enter Element
55
181
45
69
-81
3145
31
801
Enter sum:
100
Pair with given sum 100 is (45, 55)
Pair with given sum 100 is (-81, 181)
Pair with given sum 100 is (31, 69)
***************************************************************************/
1. sort the array
2. kep one pointer at smallest and one at largest,
3. Use binary search to bring the largest pointer to either the x-a[0] or if that is not there just smaller one.
3. now increase left if smaller or decrease right if bigger(perhaps here too we should use binary search to increase or decrease)
This could be solved with Hash table.
- Sentha July 30, 20051. Parse through the entire Array. If the value is less than the sum, lets say , a then Has this value in to the hash table.
2. Traverse the entire array again, for element b[i], Lookup hash[a-b[i]] if it does exist then b[i] and the a-b[i] exist in the array and make the pair.
Can some one give it with O(n) run time and constant space instead of hash table?