# Help me solve a puzzle on datastructures

Ranch Hand
Posts: 109
Hi ranchers,

Recently in a interview I was asked to solve a puzzle and I gave my solutions. Wanted to know if there is any better approach.

Puzzle:

1. I have 200 numbers ranging from from 1 to 50. more than one number can be found i.e 1 can be repeated 4 times etc. Now the puzzle is to print the number of times the combination of the numbers which adds to 50. for example 1+49 make one combination and should print only once. similarly the other combination's like 2+48 etc.. each pair makes one entry. How would be the approach.

Solution which i suggested.

first create a and pass the list of numbers to the constructor. The result will be a sorted set without duplicates. Then have a business logic method to compare two numbers and check their sum and print it.

Is there any better solution than this?

2. How to implement a object pool using java. with datastructures?
Solution which I gave was to use a Object pool using commons pool.

But he was wanting it in plain java. whether to use Arrays, ArrayList, LinkedList, HashMap....

How to implement in java. I think A ques would solve..

Suhas Bilaye
Ranch Hand
Posts: 80

Well I think I would have taken similar approach with a little change in the solution.
After getting the numbers in tree set I will get the first number in the tree set and subtract it from 50 then search whether the set contains the remainder. Remove these 2 numbers out of the set and print it. This way it will be faster.

You might surely get other solutions as well. This would be my way of going about it.

Regards,
Suhas

Janeice DelVecchio
Saloon Keeper
Posts: 1809
12
I would have several questions to begin with.

1. Is each number only duplicated a maximum of 4 times? Do you need to keep track of how many times each number is duplicated?

2. If 1 and 49 show up 4 times each, do you need to keep track of the number of sums too?

I guess I would make one array and one map. The array[200] to keep track of the integers and the amount of times they show up, the map to keep track of the "sum matches"

I've heard things about object pooling in Java increasing performance, but I've read some articles that are very contradictory. The "Object Pool Pattern" is related to the Singleton, which is a subject of... well.... let's say I'm even scared to mention the term around here.

I would be scared that this is a trick question, but I'm not exactly an expert. I'm curious what some of the more experienced ranchers think.....

Maneesh Godbole
Saloon Keeper
Posts: 11060
13
Not a beginner question. Moving to a more suitable forum.

Ranch Hand
Posts: 109
No not necessary that the number can be duplicated 4 times. it can be duplicated 1.. n times. also one combinaton such as 1-49 has to be printed only once.

Janeice DelVecchio
Saloon Keeper
Posts: 1809
12
I think I would use an arraylist and one map.

arraylist to hold all values until a sum match came up, map to hold the sum pair...

I think my algorithm might go like this:

2. search for 50 - value in the arraylist
3. if it's there, add both to the map, discard both used numbers
4. if it's not, add the new number to the arraylist
5. Loop back until all values read
6. output SortedMap

Of course, now that I think about it, this assumes that (1+49) is different than (49+1).

hmph.... I'm sure there's a better way.

David Newton
Author
Rancher
Posts: 12617
You can't just eliminate duplicate numbers--for example, if the number 1 appears 4 times in the original list, 46 + 1 + 1 + 1 + 1 equals 50 and would be a valid answer. What you want to eliminate is "1+46+1+1+1" and so on. You need to eliminate the permutations of a set of numbers, not the duplicate numbers themselves.

Misha van Tol
Ranch Hand
Posts: 56
1. I have 200 numbers ranging from from 1 to 50. more than one number can be found i.e 1 can be repeated 4 times etc.

I would say it's inevitable for numbers to occur more than once

I think the objective of the puzzle is to print only the pairs (1+49, 2+48...) right?
And the numbers are from 1 to (but not including) 50.

If so:

If you're not allowed to sort the array fist it's going to be somewhat more difficult.

David Newton
Author
Rancher
Posts: 12617
Misha van Tol wrote:I think the objective of the puzzle is to print only the pairs (1+49, 2+48...) right?

Not according to the original problem statement, which says nothing about any limit on how many numbers to print for each sum.

Ranch Hand
Posts: 109
Hi ranchers,

Sorry for not mentioning the problem domain correctly. Its the sum og only two numbers like 2+48, 3+47 etc. each pair make one combination.

Here is what my approach:

1. first put all the 200 elements in a treeset.
2. take the subset of numbers till 50 as there is no way that the number more than 50 because there is no matching number to add it to make it 50.

3. compare each number starting from 1 and sutract it by 50. for example 50-1 = 49. Now search for 49 in the set. If present print it once.

4. You do this process till 25 elements because by the time you have reached the 25th element you have completed one side of comparing. The other side will be mirror image and need not be tested. for eg: 20+30 = 50, so no need to check again from 30.

Is this fine. Also there may be even better approach.

Regards,

Mike Simmons
Ranch Hand
Posts: 3090
14
David Newton wrote:
Misha van Tol wrote:I think the objective of the puzzle is to print only the pairs (1+49, 2+48...) right?

Not according to the original problem statement, which says nothing about any limit on how many numbers to print for each sum.

The original statement did say "each pair makes one entry." Which is too bad, as the remaining problem is much less interesting.

Personally, I'd use a boolean array rather than a TreeSet. Otherwise my approach would be basically the same as what Pradeep outlined. Step 3 should say if both numbers are present in the input, print the combination.

Ranch Hand
Posts: 109
Personally, I'd use a boolean array rather than a TreeSet.

What is the advantage of a boolean array over a Treeset and what is the advantage of this approach. Can you please throw some more light on this.

Regards,

Mike Simmons
Ranch Hand
Posts: 3090
14
It should be considerably faster, and slightly simpler. Memory usage, eh, it could be higher or lower, I don't know. (Depends how many unique values there really are.) I don't suppose it matters too much, most of the time. Different optimizations are possible depending on what you need to optimize (if anything). If memory is really important, a BitSet will be much smaller - but 50 booleans is nothing, even if each boolean ends up taking 32 or 64 bits.

Reiner Herman
Greenhorn
Posts: 19
Hallo,

your algorithm for the problem seems to have time complexity O(N*logN) if the number of integres is N. For your specific small input the complexity is of course not important but for the general problem it is probably nice to look for something faster. I think you should be able to get down to O(N) using bucket sort and doing the checking of existence of pairs summing to 50 in a more efficeint way (When the integers are sorted look at the sum of the smallest and largest integers. Too small --> Look at sum of next smallest and greatest. Too big ---> look at sum of smallest and second largest . Equal --> output pair and move look at second smallest and second largest . ...

Ryan McGuire
Ranch Hand
Posts: 1068
4
Reiner Herman wrote:Hallo,

your algorithm for the problem seems to have time complexity O(N*logN) if the number of integres is N. For your specific small input the complexity is of course not important but for the general problem it is probably nice to look for something faster. I think you should be able to get down to O(N) using bucket sort and doing the checking of existence of pairs summing to 50 in a more efficeint way (When the integers are sorted look at the sum of the smallest and largest integers. Too small --> Look at sum of next smallest and greatest. Too big ---> look at sum of smallest and second largest . Equal --> output pair and move look at second smallest and second largest . ...

IF the "numbers" are integers, then just use an array to keep track of how many time each number is in the input. That way you can print out the number of two-input pairs that add up to 50. e.g. if the input included [2, 2, 48, 48, 48] you could pair those up in 2*3=6 different ways to add up to 50. The exception to this is 25. If you have [25, 25, 25, 25] in the input, you could pair them up in (4 * (4-1))/2 = 6 ways.

If you don't care how many [2, 48] pairs there are (which is how I think the original problem is worded), then you could just use an array of booleans. ...or continue to use the array of ints and just set arr[i]=1 instead of arr[i]++. ...or use ints, keep the arr[i]++ but then just report "2 + 48 are in the input."

BUT... you have to be careful at i=25. You have to make sure arr[25] > 1. You can't just rely arr[i]>0 and arr[50-i]>0; otherwise you might report a false positive for "25+25".

Mike Simmons
Ranch Hand
Posts: 3090
14
It seems we still have some different interpretations of the problem. I see this in the original problem statement:
for example 1+49 make one combination and should print only once.

I interpret the "only once" to mean only once, even if either 1 or 49 appear multiple times in the input. Otherwise, why say "only once" at all? Under this interpretation, duplicates in the input are merely distractions to be eliminated. That's why Pradeep is using a TreeMap, and I am using a boolean array. If we do need to count duplicates in the input as separate entities to be considered, then that leads to slightly more complex solutions such as Ryan describes. I don't know which interpretation is more accurate; it seems like a fairly dull problem either way.

Mike Simmons
Ranch Hand
Posts: 3090
14
Reiner Herman wrote:your algorithm for the problem seems to have time complexity O(N*logN) if the number of integres is N.

Were you responding to Pradeep or me? Pradeep would get O(N*log N) because he's using the TreeSet. I would get O(N) using a boolean[] or BitSet. Or a HashSet, for that matter.

Ranch Hand
Posts: 109
for example 1+49 make one combination and should print only once.

Yes it means that if I have the number 23 being repeated 5 times because the data structure is having 200 elements. Hence there will be duplicates and one pair for ex: (24+26) should be printed only once. the next time you see 24 or 26 it should not be printed. Hence i used a Treeset to eliminate all the duplicates.

Ranch Hand
Posts: 109
Mike Simmons wrote:
Personally, I'd use a boolean array rather than a TreeSet.

Can you please explain ow would you use a Boolean array to execute this problem domain.

Ryan McGuire
Ranch Hand
Posts: 1068
4
Mike Simmons wrote:It seems we still have some different interpretations of the problem. I see this in the original problem statement:
for example 1+49 make one combination and should print only once.

I interpret the "only once" to mean only once, even if either 1 or 49 appear multiple times in the input. Otherwise, why say "only once" at all? Under this interpretation, duplicates in the input are merely distractions to be eliminated. That's why Pradeep is using a TreeMap, and I am using a boolean array. If we do need to count duplicates in the input as separate entities to be considered, then that leads to slightly more complex solutions such as Ryan describes. I don't know which interpretation is more accurate; it seems like a fairly dull problem either way.

Yeah, why use a TreeSet or other complicated data structure if there are at most only 50 different input numbers?

I agree that the origianl question only asks for whether 1+49 should be printed, not how many time 1+49 could be made. I was just trying to ad a little pizzazz to the problem.

However, I'm sure a boolean array works. How can you tell the difference between zero, one and two occurences of 25 in the input?

Ranch Hand
Posts: 109
Ryan McGuire wrote:
However, I'm sure a boolean array works. ..

Can you please explain me how would I make use of a boolean array to solve this..

fundoo anshu
Greenhorn
Posts: 7
Hey Ryan,
I doubt you are getting complexity as O(N). May be in this case you have already assume that thr are only 25 combinations possible and you are gonna hardcode it out. in that case. yes, you will have O(N) but I don't think you should hardcode it out. Correct me in case I got you wrong.

What I will do is, simply sort the available list......N * Log(N).

start two pointers from either side of the sorted list. One where the least Number is, another where the highest number is. whenever the sum of the ints at two points come less than 50, move the least Number Pointer. whenever the the sum of the ints at two points come more than 50, move the highest Number pointer. Whenever it comes 50, check whether this combination is already registered. If not, then register it and move both the pointers. ....... Complexity N.

total complexity N*Log(N).

Mike Simmons
Ranch Hand
Posts: 3090
14
Ryan McGuire wrote:However, I'm sure a boolean array works. How can you tell the difference between zero, one and two occurences of 25 in the input?

Did you mean you're not sure a boolean array works? Well, you need at least 24 bits if information to handle the numbers of 1-24, and then two more bits to handle 25 (since we need to know if it occurs more than once). So a boolean array of size 26 could be used, with a little custom logic. Or a boolean[25] or boolean[24] with one additional variable on the side.

Pradeep wrote:Can you please explain ow would you use a Boolean array to execute this problem domain.

Here's one possible implementation:

fundoo anshu
Greenhorn
Posts: 7
Regarding the Object Pool -
I believe you wanna implement a fixed size reusable Object Pool. In that case you must use an array.
If you want to use not-reusable growing object pool. Go for link list.

Challenge will be to make it safely accessbile to multiple threads.

Mike Simmons
Ranch Hand
Posts: 3090
14
fundoo anshu wrote:I doubt you are getting complexity as O(N). May be in this case you have already assume that thr are only 25 combinations possible and you are gonna hardcode it out. in that case. yes, you will have O(N) but I don't think you should hardcode it out. Correct me in case I got you wrong.

I'm not Ryan, but I think your comment applies to me just as well, so I'll answer. There are only 25 combinations possible for the given problem. It's not an assumption; it's fact. We don't have to "hard code" each one if they can be put in a loop. Perhaps you object to seeing the number 25 be "hard coded" - well, it would be trivial in my code to replace 25 with something like inputNums.size() / 2 or whatever. Maybe a little more work to make sure it works correctly for both even and odd lengths. Not difficult, though.

fundoo anshu
Greenhorn
Posts: 7
Mike, yup I saw that in the code. I interpreted it in a different way, however code was simple to understand. I agree it is probably the most optimized solution for such problems.

Ranch Hand
Posts: 109
fundoo anshu wrote:Regarding the Object Pool -
I believe you wanna implement a fixed size reusable Object Pool. In that case you must use an array.
If you want to use not-reusable growing object pool. Go for link list.

If we want to implement a fixed size reusable Object Pool and go with an array how to return an object from the array when requested. every time we request for an object from the pool we give out the next element in the array and when the last object is given out upon the next request what should be done? I mean how do you know that the previous object has been returned back to the pool? also we need to synchronize the object when retrieved from the pool.

fundoo anshu
Greenhorn
Posts: 7
Look Object pooling is usually done for the objects which are expensive to create, but frequently used. Each such object will require to have a method ,say dissociate(), which should be invoked when the client is done with the object. whenever dissociate is called, it Object Manager will tell Object Manager that this object is not in use any more. To register the unused objects we can keep a bitMap.

If we can keep the Objects Immutable, a lot of effort can be saved for thread safety. The effort will only go to make few processes atomic....

like - checkUnused and Assign.

Ranch Hand
Posts: 109
Yes i agree that making the object immutable will resolve the multi threaded related issues. We need to have an array to hold the objects. A ObjectManager to register and unregister the object in the array. Upon the disassociate method call from the client the Objectmanager should put it back at the end of the array. Upon requesting an object from the Object pool the Objectmanager should pull the first object from the array and then shift the index of all the elements to make it contiguous.

But why a bitmap and what is it?

fundoo anshu
Greenhorn
Posts: 7
The Manager should know which are the Objects in use and which are not. This information would exist in the bitMap. whose size is equal to the size of the pool and the size of maximum number of Objects in the Object pool.

Ranch Hand
Posts: 109

fundoo anshu
Greenhorn
Posts: 7
bitMap is nothing but a boolean array..... you just have bits 0,1 at bitMap[x] to tell you whether the object at x location is occupied or not. It is used to optimize the search a little bit. however here its implications are trivial. For more information read for bitmap indexing in oracle database.

Maneesh Godbole
Saloon Keeper
Posts: 11060
13
fundoo anshu wrote:

Rakesh Bagaria
Greenhorn
Posts: 14
import java.util.*;

class AL
{
static int count;
public static void main(String args[])
{
Vector <Integer> al=new Vector<Integer>();
int i,j,l=0,k=0;

System.out.println(al.size());
Enumeration it=al.elements();
while(it.hasMoreElements())
{
i=(Integer)it.nextElement();
l=al.indexOf(i);
j=10-i;
System.out.println("i="+i+" j="+j);
if (al.contains(j))
{
k=al.indexOf(j);
if(k>l)
{
al.remove(k);
count++;
}

}

}

System.out.println(al.size());
System.out.println(count);

//System.out.println(al);

}
}

i just started learning java above program is for finding number of pairs whose sum is 10. similar concept can be apply for 1 to 50 . any suggetion for me .

David Newton
Author
Rancher
Posts: 12617
@Rakesh: Arrays.asList()

Ryan McGuire
Ranch Hand
Posts: 1068
4
Mike Simmons wrote:
Ryan McGuire wrote:However, I'm sure a boolean array works. How can you tell the difference between zero, one and two occurences of 25 in the input?

Did you mean you're not sure a boolean array works?

Exactly. Just typing too fast.

Here's one possible implementation:

I think you need to make bits[] go up to bits[50]... bits[49] at the very least. In both of the loops, the subscript for bits could go over 25.

Mike Simmons
Ranch Hand
Posts: 3090
14
Yes, true. I wrote that out too quickly - had the special case of 25 on my mind. Also, several of my comments are off. E.g. my comment about inputNums.sze() should refer to bits.length. These were left as an exercise for the reader. ;)