• 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

List and sublist manipulation [foobar challenge]

 
Ranch Hand
Posts: 46
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I recently received this code challenge from google foobar while searching.

The question states:
Given the list l as [4, 3, 5, 7, 8] and the key t as 12, the function answer(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function answer(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15.

Here is my attempt but this will not work if the list is bigger in size (list can be up to 100 in size). Any suggestions or different approaches to take as im sure there are

 
Marshal
Posts: 79467
379
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you tried working out the problem on paper? You cannot usually solve such problems in code.
 
Sheriff
Posts: 17652
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
7 + 8 = 15

So I don't know if there are more constraints to the problem or if whoever wrote that problem missed that. Never mind, I missed the fact that there was as different list of numbers. Doh!
 
Kyle Jones
Ranch Hand
Posts: 46
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How can I use recursion to improve this?? Thanks

 
Junilu Lacar
Sheriff
Posts: 17652
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, first you have to boil the algorithm down and eliminate all but a few of those conditional statements (if-else).  You cannot extend or contract this program every time your input changes.  You have to generalize the idea so that your program works for all sizes of lists, whether it has 0 or 500 numbers in it.

Look for patterns in the code, like consistent changes from one part to the next. Then look for the most basic case. The basic case can usually be identified by a literal value instead of a relative value.  A literal value is something like 5 -- that's the actual number 5.  A relative value would be where N represents the value of 4, then the relative value of 5 is represented by the expression N + 1. That is, speaking relatively, the value 5 is one more than the value of 4.  In recursion, a case that where you can specify a literal value is usually the base or degenerate case where you can end recursion.  The relative cases are where you use relative values, in which case you need to continue the recursion and reduce the problem so that the next problem is closer to the base/degenerate case relative to the current case.
 
Marshal
Posts: 28263
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Kyle Jones wrote:How can I use recursion to improve this??



Is using recursion a requirement of the problem? Because I wouldn't start by trying to improve that code. I wouldn't have gone down that road in the first place. My algorithm is like this:

For each position in the array:
 Can I add up numbers starting at this position to add up to N?
 
reply
    Bookmark Topic Watch Topic
  • New Topic