3

I had an interview and was asked a question that I'd like to understand the solution.

The Question

Create a recursive function that returns the number of possible combinations of arrays of a given length that could be made from an array of non-repeating consecutive integers.

f(array, length) = Combinations

Example 1

  • array = [0,1,2,3]
  • length = 2
  • Combinations = 10 (all combinations: [0,0] [0,1] [0,2] [0,3] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3])
  • Note that [0,0] is allowed but [1,0] is not because [0,1] is defined

Example 2

  • array = [0,1]
  • length = 3
  • Combinations = 4 (all combinations: [0,0,0] [0,0,1] [0,1,1] [1,1,1])

One "hint" was offered. The interviewer said the array itself shouldn't matter; the length was all that was needed.

Improve this question
12
  • 3
    Do you not understand the question or the solution? Do you know how recursion works? The point of questions like this is not to get "the right answer" but to think about how you would solve a problem. IF you don;t understand recursion, then the solution won't make sense to you either. Commented Aug 3, 2017 at 14:01
  • @DStanley - I do actually understand recursion, although it added to the complexity. What I had the most trouble understanding was how you would use recursion to accomplish the desired result. My gut instinct was to use a series of really ugly loops. It just completely stumped me. Commented Aug 3, 2017 at 14:06
  • 1
    There's nothing in your question that explains why [2,1] and [1,0,0] aren't valid combinations. Commented Aug 3, 2017 at 14:15
  • 1
    @MattTimmermans If [1,0] is not allowed because [0,1] is defined then I guess [2,1] isn't because [1,2] is defined, same with [1,0,0] and [0,1,0] as [0,0,1] is defined. Commented Aug 3, 2017 at 14:18
  • 3
    Also nothing to say why [0,2] is not a solution because the criternion of "non-consecutive" applies to the input array only Commented Aug 3, 2017 at 14:32

2 Answers 2

Reset to default
4

This algorithm can be expressed recursively because the solution can be expressed in terms of solutions for smaller inputs. "Smaller" here has two meanings:

  • A subset of the array; specifically the sub-array after the current element index

  • Solutions for smaller length; these can be added together to give the solution for length + 1

Stopping conditions:

  • When the array size A = 1 - only one combination can be generated

  • When the length L = 1 - number of combinations = number of elements in array

The fully recursive procedure is a surprisingly simple one-liner: 

return [recursive call to rest of array, same length] + 
       [recursive call to same array, length - 1]

This is called dynamic programming.

Code:

int F(int A, int L)
{
    if (A <= 1) return 1;
    if (L <= 1) return A;
    return F(A - 1, L) + F(A, L - 1);
}

Tests:

  • F(4, 2) = 10
  • F(2, 3) = 4
  • F(3, 5) = 21 (trace it with pen-and-paper to see for yourself)

EDIT: I've given an elegant and simple solution, but I perhaps haven't explained it as well as @RoryDaulton. Consider giving his answer credit too.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks so much! This makes sense but even seeing it written out I can barely wrap my head around it. It will be fun to dig deeper into this stuff. Blowing a phone screen and not having the problem explained was killing me.
2

You do not give a target language and you do not say just how much help you want. So I'll give the overall idea of an algorithm that should be simple to code if you know recursion in a certain language. Ask if you want more code in Python, my current preferred language.

You know you need to do recursion, and you have two things you could recurse on: the length of the given array or the length of the desired arrays. Let's recurse on the second, and let's say the given array is [0, 1, ..., n-1] since you know that the actual contents are irrelevant.

If the desired length r is 1 you know there are only n desired arrays, namely [0], [1], ..., [n-1]. So there is the base case for your recursion.

If you have a "combination" of length r-1, how can that be expanded to length r and keep the requirements? Look at the last element in the array of length r-1--let's call it k. The next element cannot be less than that, so all the possible arrays extended to length r are the r-1 array appended with k', 'k+1, ..., n-1. Those are n-k arrays of length r.

Is it clear how to code that? Note that you do not need to keep all the arrays of length r-1, you only need the count of how many arrays there are that end with the element 0 or 1 or ... n-1. That makes it convenient to code--not much memory is needed. In fact, things can be reduced further--I'll leave that to you.

Note that the interviewer probably did not want the code, he wanted your thought-process leading to the code to see the way you think. This is one way to think the problem through.

Improve this answer

1 Comment

Thanks Rory, this is very helpful. I appreciate the time you took to break down the thought process.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.