Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
@oOZz I have mentioned the same solution using HashMap below. Java Docs says, we should use Hashmap, it gives constant-time performance for get, put and containsKey, where it is O(n) in worst case. I also searched on Internet, they say Hashtable is obsolete, you should use Hashmap instead
@mayur The data structure is called hashtable, so I didn't mean java.util.Hashtable. In Java though, both java.util.Hashtable and java.util.HashMap have (amortized) constant time put, get, delete operations. The only difference between them is java.util.Hashtable is synchronized, but java.util.HashMap is not.
@oOZz thanks for explanation. But I think that's what I was trying to say. If you search online, it would say that Hashtable is synchronized, and HashMap is not. But if you look in docs, Hashtable is really old, obsolete, ConcurrentHashMap can overcome the synchronization issue here. Hashtable is threadsafe, that's only when you use it. I don't think anybody uses Hashtable anymore. I didn't know that either until last month, a company rejected me. So I searched online and found out that Hashtable were used only until Java v1.2
Thanks for explaining though. It was great for others.
Your solution wont work if the sum was say sum of 9 and the arrays are [4 5] and [4 3 2]. you are making the assumption that the the resultant sub array sizes are always 2, which need not be the case. The right solution is using dynamic programming
I don't understand your solution. What would be the key and what would be the value in the hashmap? You just say:
1. Put numbers in the hashtable (this in O(n))
The solution of subtracting each element in the array from the sum is correct but how you verify that the difference is in the input array escapes me. You should probably use a binary search tree.
Sort the array and start pointers from both ends of the array checking if the given pair add up to the given value.
0. If the current pair sum equals the value of the given number print the pair.
1. If the current pair sum exceeds the given number decrement the right pointer by 1
2. else increment the left pointer by 1
public static void main(String[] args) {
int[] a = new int[] { 1, 3, 10, 4, 5, 6, 7, 2, 6 };
Set<String> resultSet = new HashSet<String>();
int sum = 12;
if (a == null || a.length < 2) {
return;
}
int left = 0;
int right = a.length - 1;
java.util.Arrays.sort(a);
while (left < right) {
int i = a[left];
int j = a[right];
if (i + j == sum) {
resultSet.add(String.valueOf(i)+"-"+String.valueOf(j));
left++;
right--;
} else if (i + j > sum) {
right--;
} else {
left++;
}
}
System.out.println(resultSet);
}
You can solve it like:
a.First sort the array in non-decreasing order.Take two pointers left and right.Left point to the start and the right pointer points to the end of the array.
b.while(left<right)
b.check whether a[left]+a[right]<k.If yes then increment the left pointer by one.
c.check whether a[left]+a[right]>k.If yes decrement the right pointer by one.
d.If a[left]+a[right]==k.Return true
public class CheckSum {
/**
* @param args
*/
public static void main(String[] args) {
int a[]={4,5,1,3,2};int c[]=new int[2];int j=0;
for(int i=0;i<a.length;i++)
{j=1;
while(j<5)
{System.out.println("j"+j);
if(a[i]+a[j]==6)
{System.out.println("good"+"\n");
for(int t=0;t<2;t++)
{
//int b[]=new int[t];
c[0]=a[i];
//t--;
c[1]=a[j];
System.out.println(c[t]);
}
}
j++;
}
}
}
}
O(n) time & space, as simple/short as possible
public static List<Integer[]> compute(List<Integer> ints, int sum){
Set<Integer> intsNeeded = new HashSet<Integer>();
List<Integer[]> answer = new ArrayList<Integer[]>();
for(Integer num : ints){
if(intsNeeded.contains(num))
answer.add(new Integer[]{num, sum - num});
else
intsNeeded.add(sum-num);
}
return answer;
}
public static void main(String[] args) {
int[] testArray = { 4, 5, 1, 2, 3};
int length = testArray.length-1;
int sol;
int sağ;
for (sol = 0; sol < length; sol++) {
for (sağ = length; sağ >=0 ; sağ--) {
if(sol>=sağ)
{break;}
if ((testArray[sol] + testArray[sağ]) == 6) {
System.out.println(testArray[sol] + "," + testArray[sağ]);
}
}
}
}
}
public class Sum1
{
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
// EBAY.com
// Given an integer array, find pairs in an array which sum up to a given number.
// For example: Array{4,5,1,3,2} and required sum=6 then output should be [1,5] and [2,4].
int [] arr = {4,5, 1, 3, 2};
int sum = 6;
for(int i =0;i<arr.length;i++)
{
for (int j = i+1;j<arr.length;j++)
{
if ((arr[i] +arr[j])==sum)
{
System.out.println(arr[i]);
System.out.println(arr[j]);
System.out.println();
System.out.println();
}
}
}
}
}
int[] num={4,5,1,3,2,3};
int sum = 6;
int length=num.length;
HashSet<Integer> temp=new HashSet<Integer>();
for(int i=0;i<length;i++){
temp.add(num[i]);
}
for(int i=0;i<length;i++){
int tempSum=sum-num[i];
if(tempSum!=num[i]){
if(temp.contains(tempSum)){
System.out.println("numbers are: "+tempSum+", "+num[i]);
}
}else if(tempSum==num[i]){
int count =0;
for(int j=0;j<length;j++){
if(tempSum==num[j]){
count++;
}
}
if(count>=2){
System.out.println("numbers are: "+tempSum+", "+num[i]);
}
}
}
public class subSet
{
public Object a;
public int n;
public int[] x;
public boolean flag;
private int c;
public subSet(int[] a, int c)
{
this.a = a;
this.c = c;
this.n = a.length;
this.flag = false;
this.x = new int[n];
}
public boolean isPartial(int k)
{
int sum = 0;
for (int i = 0; i < k; i++)
sum += ((int[]) (a))[i] * x[i];
return sum <= c;
}
public boolean isComplete(int k)
{
int sum = 0;
if (k >= n)
{
for (int i = 0; i < n; i++)
sum += ((int[]) (a))[i] * x[i];
}
return sum == c;
}
public void printSolution(int k)
{
for (int i = 0; i < n; i++)
if (x[i] == 1)
System.out.print(((int[]) (a))[i] + " ");
System.out.println();
}
public static void backtrack(subSet p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}
private static void explore(subSet p, int k)
{
if (k >= p.n)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
for (int i = 0; i < 2; i++)
{
p.x[k] = i;
if (p.isPartial(k))
explore(p, k + 1);
}
}
public static void main(String args[])
{
int b[] = { 1, 2, 3, 4 };
subSet t = new subSet(b, 6);
t.backtrack(t);
}
}
public class subSet
{
public Object a;
public int n;
public int[] x;
public boolean flag;
private int c;
public subSet(int[] a, int c)
{
this.a = a;
this.c = c;
this.n = a.length;
this.flag = false;
this.x = new int[n];
}
public boolean isPartial(int k)
{
int sum = 0;
for (int i = 0; i < k; i++)
sum += ((int[]) (a))[i] * x[i];
return sum <= c;
}
public boolean isComplete(int k)
{
int sum = 0;
if (k >= n)
{
for (int i = 0; i < n; i++)
sum += ((int[]) (a))[i] * x[i];
}
return sum == c;
}
public void printSolution(int k)
{
for (int i = 0; i < n; i++)
if (x[i] == 1)
System.out.print(((int[]) (a))[i] + " ");
System.out.println();
}
public static void backtrack(subSet p)
{
explore(p, 0);
if (!p.flag)
System.out.println("no sulution!");
}
private static void explore(subSet p, int k)
{
if (k >= p.n)
{
if (p.isComplete(k))
{
p.flag = true;
p.printSolution(k);
}
return;
}
for (int i = 0; i < 2; i++)
{
p.x[k] = i;
if (p.isPartial(k))
explore(p, k + 1);
}
}
public static void main(String args[])
{
int b[] = { 1, 2, 3, 4 };
subSet t = new subSet(b, 6);
t.backtrack(t);
}
}
import java.io.*;
class ArrTest1{
public static void main(String args[])throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int s;
System.out.println("Enter the size for array");
s=Integer.parseInt(br.readLine());
System.out.println("Enter the sum numbers equals to");
int d=Integer.parseInt(br.readLine());
int a[]=new int[s];
System.out.println("Enter the"+s +"numbers for array");
for(int i=0;i<s;i++){
a[i]=Integer.parseInt(br.readLine());
}
boolean b=true;
for(int i=s-1;i>=0;i--){
for(int j=i-1;j>=0;j--){
if(i==j){}
else{
if(a[i]+a[j]==d){
System.out.println("["+a[i]+"+"+a[j]+"]");
b=false;
}
}
}
}
if(b){
System.out.println("No pair found");
}
}
}
O(nlog(n)) due to sorting...
public void findPairs(int[] array, int sum){
Arrays.sort(array);
int head = 0, tail=array.length - 1;
while(head<=tail){
if(array[head] + array[tail] == sum){
System.out.println(array[head] + "+" + array[tail]);
head++;
tail--;
}else if(array[head] + array[tail] > sum){
tail--;
}else if(array[head] + array[tail] < sum){
head++;
}
}
}
//This Works for negative values also
Integer arr[] = {1,2,3,5,6,7,8,9,4,3,3,5,-1,-2};
//Convert the Array to List
List<Integer> list = Arrays.asList(arr);
int sum = 6;
//Take a Map and put the values with their count of occurrence
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < list.size(); i++) {
if(null != map.get(list.get(i))) {
int value = map.get(list.get(i));
map.put(list.get(i), ++value);
}
else {
map.put(list.get(i), 1);
}
}
//Take a Iterator of the List
Iterator<Integer> it = list.iterator();
//Iterate the List
while (it.hasNext()) {
int val = it.next();
int remainVal = sum - val;
//Compare remain value of list with map
if(map.containsKey(remainVal) && map.get(val) < 2) {
System.out.println("Val1: "+val + "Val2: "+remainVal);
//Remove Values from the map so that no repetition is there
map.remove(remainVal);
map.remove(val);
}
if(map.containsKey(remainVal) && map.get(val) >= 2) {
System.out.println("Val11: "+val + "Val22: "+remainVal);
//Remove Values from the map so that no repetition is there
map.remove(remainVal);
map.remove(val);
}
}
#include <iostream>
using namespace std;
int main()
{
cout << "Hello World" << endl;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int n=10;
int N=10;
int k=0;
for(int i =0; i< n; i++)
{
for(int j= i; j<n; j++)
{
if(a[i] + a[j] ==N)
{
cout<<a[i]<<endl;
cout<<a[j]<<endl;
cout<< " End Of Pair"<<endl;
}
}
}
return 0;
}
This problem can be phrased mathematically as:
x + y = z
where z = input
x, y are pairs from the array.
This equation can be modified to y = z - x
So if we take the input and subtract every value in the array then this will give us the set of candidates. Then the solution is to find all values in the candidates that are in the array.
You can do that by constructing a binary tree and then searching it. So the complexity of this algorithm would be O(nlogn).
Time: O(n)
static void pairEqualToSum()
{
System.out.println("----------------------------------------------------------------\n");
int arr[]={4,5,1,3,2};
int sum=6;
Hashtable<Integer,Integer> h=new Hashtable();
for(int i=0;i<arr.length;i++)
h.put(arr[i],arr[i]);
System.out.println(h.toString());
int cur;
for(int i=0;i<arr.length;i++)
{
cur=arr[i];
if(h.containsKey(sum-cur) && cur!=h.get(sum-cur))
{
System.out.println(cur+" "+h.get(sum-cur));
h.remove(sum-cur);
h.remove(cur);
}
}
}
Here's one solution I could think of:
public class hashM {
public static void main(String[] args) {
HashMap<Integer, Integer> hMap = new HashMap<Integer, Integer>();
hMap.put(1, 1);
hMap.put(2, 3);
hMap.put(3, 10);
hMap.put(4, 4);
hMap.put(5, 5);
hMap.put(6, 6);
hMap.put(7, 7);
hMap.put(8, 2);
hMap.put(9, 6);
int sum = 12;
for(int i=1; i<hMap.size(); i++) {
int j=sum-hMap.get(i);
if (hMap.containsValue(j)) {
System.out.println("items: " + hMap.get(i) + "," + j);
}
j=0;
}
}
}
this will print the required output..
public static void main(String[] args) {
int[] testArray = { 4, 5, 1, 2, 3 };
int length = testArray.length;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (testArray[i] + testArray[j] == 6) {
System.out.println(testArray[i] + "," + testArray[j]);
}
}
}
}
@emalaj23
The above is not the most inefficient code. An even more inefficient way of solving this problem is to have all the n! permutations of the array and check if the sum of the first and last elements sum up to the given number. I am sure there can be even more inefficient ways that beat my method.
The solutions described here is O(n log n) due to sorting. There is an O(n) solution using a hashtable, therefore, this is an O(n) space solution:
- oOZz June 14, 20131. Put numbers in the hashtable (this in O(n))
2. Iterate the array and subtract each element from sum and check if the result is in the hashtable.
2.a. if it's in the hashtable, print the two numbers
2.b. if it's not then continue
There is a special case though, when the array contains duplicates. In that case, you will also need to save the count of the number and process accordingly. e.g., if the array is [2,3,5,10] and sum = 6, 6-3=3 and 3 is in the hashtable, so you need to check if the count of the 3 in the hashtable is >=2.