• Post Reply Bookmark Topic Watch Topic
  • New Topic

finding all pairs in an array  RSS feed

 
Philip Freeman
Ranch Hand
Posts: 31
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I have solved the problem already with 2 different approaches.
1. Sorting the array and comparing current element with current element + 1 and then incrementing my position in the array
2. Without sorting, I used two for loops, when a pair is found I remove the pair from the array

Now, I have had a third idea also. Explanation: find pair, once pair found remember the index of the second pair element in a seperate array. Use that array to filter out indexes that already formed pairs.
The code for this attempt is bellow. Does anyone see what I overlooked/where I made a mistake?

Correct output for the input below should be 30, mine is 27


[Moderator edit: broke up long line in code block]
 
Junilu Lacar
Sheriff
Posts: 11481
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are making things way too difficult for yourself.  Why not use smaller input data sets that are targeted to certain conditions instead of using a humungous data set that covers all possible scenarios?  When something goes wrong, it's easier to figure out which targeted data set causes your code to fail than it is to figure out which particular scenario in the humungous one caused a problem.

For example, does your humungous data set cover the scenario where you have three repeats of the same number? What is the desired behavior for that scenario?  That is, if you had { 3, 2, 3, 3 }, do you have one pair of 3s and {2, 3} that are not paired up? Because the definition of "pair" limits inclusion to exactly TWO elements.

Other examples:
{2, 2, 1, 5} - see if code handles consecutive numbers at the start.
{1, 2, 2, 5} - see if code handles consecutive numbers in the middle
{1, 5, 2, 2} - ... in the end

{2, 1, 5, 2} - ... pairs that are separated
{2, 1, 2, 5} - ... one at start, one in middle
{1, 2, 5, 2} - ... one in middle, other at the end

... and so on.

If you have separate tests for each scenario you can think of, it's a lot easier to zero in on the problem in your code.
 
Junilu Lacar
Sheriff
Posts: 11481
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Philip Freeman wrote:Does anyone see what I overlooked/where I made a mistake?

If you follow the advice in my previous post, I bet there would be a better chance of someone, including yourself, figuring out what is wrong. As it is, the huge input data set doesn't make anything jump out at you except for its SIZE so you really have to weed through all that code to try to see what could be going wrong.

Also, the approach you take doesn't sound all that good anyway.

I would suggest that you use a Map<Integer, Integer> to create a histogram, then iterate over the map and see which keys have a corresponding value of 2. Those keys are going to be the numbers that are paired. If you want to handle more than one pair of the same number, then you'd see how many times you can divide each value by 2. That's how many pairs of that key you have. Any remainder will tell you if there's one that doesn't have a pair.
 
Carey Brown
Saloon Keeper
Posts: 3314
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What about
{2,4,2,2,5}
That is an array with more than 2 of a kind? Would that be 3 pairs? Or no pairs?

Ah, missed the part where it said "SockMerchant". So then {2,2,4,2,2,5} would be two pairs of socks.
 
Liutauras Vilda
Sheriff
Posts: 4917
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:If you have separate tests for each scenario

@OP
It seems like too much information to persist in the head in one go, what needs to be satified, what was satisfied, what's failed and so on.

Do you have JUnit testing framework? (this is what Junilu basically telling you here, I think..) That is a actually a very good time to start using it. First, you can't solve this exercise without having answers what the outcome supposed to be in one or another numbers sequence. Once you know those answers, you could write separate tests to cover each of them. Check here, also look on some media sites for video, it isn't that difficult to get to start.

The thing is, that you don't need to write good code now, you need to know what is the goal here and write simple and short test methods to describe the goal. Then those test cases would be your "policeman" who'd tell you if you can go through the green traffic light towards next idea or still need to do some work before you can.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!