If in a simple case you find that you're printing (visiting) the same element more than once, then its likely that you dont have a O(n) solution.
@jacosta66, if you're asking about what O(n) means (or the "O(...)" notation in general is), its basically a way to estimate what the upper bound of execution time a certain piece of code would take to complete.
An example of O(n) means that a function will complete in the worst case by parsing a given list a constant number of times. So with a list of 100 elements, we can expect the upper time complexity limit to be a multiple of the time it takes to process all 100 elements.
Conversely, O(n^2) means that for every element in the list, we have to parse the entire rest of the list elements. So for 100 elements, we can parse somewhere around 100^2 or 10000 elements total. That difference in time taken is what makes the 10 million element case impossible to solve within a reasonable timeframe.
While you do bring up a strange logic scenario, there are approaches to this problem that don't rely on length checking or bifurcation. I recommend trying out different approaches!
How about adding some print statements to debug exactly what elements and indices you're looking at for a simple case?
What language are you using? The test case you point out should have a sum value of 16, not 31.
Thanks for the feedback! While I may have certain feelings about dismissing a kata because an optimal solution common to a variety of problems can be solved by a common approach (binary searches here), the assertion message concern is quite valid.
I'll take this down and work on the messages, but if you have any recommendations here, I'd be more than willing to listen!
As far as making sure the kata is 'unique', there are variations of this problem that might push it beyond just the one-shot binary search.
I thought that I'd leave the scope of the kata to just the binary search with the graph, as there are common gotchas that are 'enough' to deal with for the common coder — so I thought leaving out those extra challenges would be best.
Whoops! Thanks for catching that case!
Your solution is O(n^2), because you have a for-in and an if-in statement with a list comprehension!
Because there are tests that involve 10 million elements, even if you had a computer that could iterate through 1 million elements a second, it would take over 13 thousand hours for the entire array to be parsed if there are no matches.
(10000000*(10000000-1)/2)/(1000000*3600) = 13888.8875
(3600 is the number of seconds in an hour)
Really the question you need to ask yourself is, "will recursion actually save me time/space for this problem?"
Recursion in most languages involves saving a set of details onto a call stack, then once we've gotten to the base case, popping them all off the stack one-by-one and applying any remaining logic.
A mental picture could be sending a package through mail, only for n number of addresses saying, "oh, this isn't your final destination. Here: go to this address instead." Eventually, the right address gets the package, but then simply scribbles a note on the box and ships it back to the last address that sent the box to it! This then daisy-chains its way back to the post office, before its done.
Recursion is a neat tool in programming, but often times its way more efficient to not go through the hoops of a postal service-esque solution if you know in advance what optimizations you can make space/process-wise to get your solution.
I was asked this question in my own interview for my current job 5 years ago. I liked it so much I decided to make Katas from the memorable ones.
Doing that would honestly increase the difficulty of the kata, simply because users would not only have to memoize the proper values that added up to the sum, but also the indices they were found in.
Consider that an "extra credit" problem ;)
Your answer is running in O(n^2) time! The outer for loop is the first "n", but your call to Array.indexOf() does another linear search through the array for a second "n" search, increasing the time by quite a lot!
I recommend searching online for some of the Kata tags for clues :)
I suggest making lists given the description comment about 10,000,000 length lists with both valid pairs in various locations, and ones without any valid pairs, just to ensure your algorithm can even parse through a list with that many elements without timing out first.
This comment is hidden because it contains spoiler information about the solution