• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Hackerrank Sales by Match problem - I'm getting answer but can't return it (my1st recursion attempt)

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm trying to complete the Hackerrank Sales by Match problem:
www [dot] hackerrank [dot] com/challenges/sock-merchant/problem?isFullScreen=true

My method is meant to just look for duplicates, remove them, then call itself to look for another duplicate. If there are no duplicates, then it just returns the number of times it found a duplicate.

I added a bunch of sysout lines to help debug, and according to the debug output, I am successfully getting the count variable to correctly identify the number of duplicates. Here are my problems:

1. Why do I need the return statement at the end? And how is my code even reaching it? When the if statement is true, it reaches a return statement. When the if statement is false, the method just calls itself again. So that last return statement at the end should never be reached, but somehow it is being reached and returning a 1.
2. See my debug output below the code. Why is my for loop continuing to run even after the if statement is true (and therefore my method reaches a return statement and should stop)?
-----if it makes a difference, when I run it against the other test case, the method actually stops when there are no more duplicates, but still returns a 1 instead of the actual count (as if it's reaching the return statement at the end of the code somehow).



The debug output is as follows:

 
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't see why you've turned this into a recursive problem or why you need to remove elements from ar. Once you sort it you can just start at the beginning and if the current value matches the previous value you have a pair, and so on.
 
Chaz Winter
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:I don't see why you've turned this into a recursive problem


Because I wanted to
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
On line 42 you don't do anything with the newCount that is being returned.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The return at line 28 only unwinds the recursive calls one level and you eventually get back to a call you made on line 32, which, after the loops are exhausted will end up at the return at the very end.
 
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You do not need that double for-loop. In matchCheck, the list is sorted, so you can simply do:
 
Chaz Winter
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:On line 42 you don't do anything with the newCount that is being returned.



That's what I thought as well, but if I change that line to -1 is what ends up on stdout. I reach my return statement on line 28 (debug prints the line right before it), and then the for loop runs again for some reason after the return, and the return on 42 is what gets passed.
 
Chaz Winter
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:The return at line 28 only unwinds the recursive calls one level and you eventually get back to a call you made on line 32, which, after the loops are exhausted will end up at the return at the very end.



Okay, so if I'm understanding you correctly, if I make a recursive call, the return statement doesn't get returned to the method that originally called it, but rather gets returned to the previous method call (ie the one that called itself)? So after my matchCheck method calls itself three times, it finally returns an int, but instead of returning it to the original sockMerchant method that called matchCheck, the int gets returned to the 3rd matchCheck that was called?

And so what happens is the very first matchCheck call, which incremented newCount by 1, is the one that actually returns the int, which is why my code gets 1 on stdout instead of 3. Correct?

This is why I wanted to use recursion - I can't learn the details of recursion without trying to use it on something.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you've got the gist of it now.

You can try
 
Chaz Winter
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:I think you've got the gist of it now.

You can try



As a test, I placed that line directly above the return statement at the very end of the code, and sure enough, I can now see (via the debug output) the newCount go from 3, stay 3, then go to 2, and then 1, as the methods "unwind."

I'm not entirely sure how I could use the existing recursion to actually solve the problem, but I'm glad to actually learn something new in the process.



EDIT: Sorry, that's the output from the other test case...which now that I'm looking at it, it actually doesn't keep testing values like the first test case. It actually hits "true" every time, unlike the first test case, which hits false for some reason before exhausting all checks and using the return statement at the end of the code.
 
Chaz Winter
Greenhorn
Posts: 10
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you for helping me understand recursion. Now that I get it, I decided to avoid it for this particular problem (though it was fun debugging and seeing how it actually works).

I ended up solving it like this:



I'm sure more experienced coders could solve it even more simply, but that's what I came up with.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I like your solution. Small and readable.

This is what I came up with which has the advantage of only making two passes through the data, once for sorting, and once for counting.

 
Piet Souris
Bartender
Posts: 5465
212
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Indeed, nice and very readable. Here are two other ways that are O(n):
 
Chaz Winter
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:Indeed, nice and very readable. Here are two other ways that are O(n):


HashMaps are the other thing I've heard over and over, but never used and don't quite understand. Gonna have to look it up on YouTube and find some problems to solve with it.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A quick benchmark.
Output: seconds for 100,000 iterations
Chaz: 12.606
Carey: 0.173
Piet1: 1.318
Piet2: 1.37
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Carey,

yes, I could have expected a performance test!

One remark though: in your Carey-test you create a list ar, that gets sorted. That means that from try 2, the argument-array is already sorted, and that saves a lot of time. I adjusted the test in two ways: one where each list is created in the method itself, and two where I create a general list, and in your method I take a copy and sort that. That gives quite a difference.

But the way to the outcome is much more interesting than the corresponding performance. and OP has quite a few solutions now. Hope he likes it.
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmmm, I didn't take into account that once the array had be sorted that subsequent calls to sort ran extremely fast. Writing benchmarks is tricky. So here's a more realistic outcome and mine didn't fare so well this time.
Output: seconds per 100,000 iterations
Chaz: 10.5
Carey: 8.358
Piet1: 1.454
Piet2: 1.856
 
Carey Brown
Saloon Keeper
Posts: 10687
85
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows ChatGPT
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Interesting observation... On line 4 I replaced "int" with "Integer" so it might not do auto-unboxing and it did shave a few nano-seconds off the time.

 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It sure is tricky. When determining the files in the methods themselves, I used for each of the methods

but for your method, I also sorted the list with .sorted(), but it differed also between

and
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic