New answers tagged combinatorics
2
Performance Problems
Your current solution works decent for small cases, but there are a few problems when the problem starts to scale up, which causes the performance to drop. I will mention the two biggest I have found.
You construct all paths toward the goal, even the unviable ones, in full until you remove them. This causes an exponential amount of ...
3
I have a few suggestions for you:
You should get in the habit on wrapping all code that isn't in a function in a main guard, to ensure that that code only runs if that file is running, and to protect it from import mishaps
Running your code with pylint, a few warnings that popped up were:
Returns: All return statements should return something or none of ...
1
Possible Bugs
In main() there is an assignment from a fuction that returns long long (factorial) to an integer variable (fact). This may result in errors depending on the word size of int. One of the possibilities is a positive long long value can be converted to a negative integer. Since there is a comparison between the variable fact and another long long ...
3
verbose vs readable
Why choose?
Just encapsulate all the explicit code and error checkings into functions (if possible) or macros (only when functions can't do it), and have a clean high level function.
Safe usage of malloc()
Malloc is easily misused. Problems using malloc are the following:
sizeof(type) vs sizeof(*foo):
foo = malloc(sizeof(*foo) * ...
2
As others have pointed out, the code should be object oriented. It’s OK to start with procedural code as you have, but if you do, you should get in the habit of writing a quick test in your main entry point. Once you’ve written the first test, it can help you start seeing objects more clearly (and drive you to further unit tests.)
For example: an ...
7
3 good answers already, but there's more!
I don't like that you modify the array you are given. This sort of thing would need to be documented, and generally creates confusion for all. You don't need arrays as inputs, so you could take IEnumerables instead without any added cost, which makes the code easier to reuse and communicates to the consumer that you ...
8
The good thing first:
You divide and conquer the problem by creating some reasonable (and well named) methods. You could have gone all in by making methods for combining and final selection as well:
...
var combinedTotals = Combine(affordableKeyboards, affordableDrives);
return SelectMaxBuy(combinedTotals, budget);
}
But as shown below, dividing the ...
10
early pruning
This is very nice:
// delete any that are over our budget
Doing it before sorting can slightly speed the sorting operation.
I say slightly because "items over budget" is determined by the input,
and it will be some fraction f of an input item category,
so the savings is O(f * n * log n).
early discard
This is a bigger deal.
...
7
General Guidelines
You have coded everything in a single class Program. Take advantage of the fact C# is an object oriented language. Create at least one custom class that defines this problem.
Your current implementation is very strict and specific to 2 types of items. What if Monica needs to buy from n item types? It is up to you to decide the scope of ...
0
Why the last answer was pretty good, it had some unneeded steps there.
For the sake of one liners here my version:
>>>from itertools import product
>>>experiments = [dict(zip(config_overrides.keys(), value)) for value in product(*config_overrides.values())]
The main difference here is that there is no need to split the dict up earlier.
0
Requirements
It all depends on what you think is 'best'. The code that can be implemented in as little time as possible? The most efficient code? In terms of memory? CPU?
The solution below doesn't do any input checking, but instead is an approach that would be rather fast and very memory efficient
Return type
I prefer a solution that has an Iterator or ...
2
Managing memory requirements
Did you get the method signature from the interviewer? If not, it could use some improvement. Consider Joop Eggen's answer and the worst case scenario, where there are 2^63 different combinations. While his approach is likely the most efficient computationally, the method signature limits the operation to calculating everything ...
4
Usability
Your addCombinations(String input, int index, List<String> output) is harder to use than necessary. The user must:
create the storage for the result
pass in a mysterious 0 value
It would be better to add a "helper" function, to do these tasks for the user:
public static void main(String[] args) {
List<String> output = ...
1
Such a problem is also looking whether the interviewed has a nice logic filtering, simplifying things.
Now the problem actually only varies for the question marks. So:
void allCombinations(String pattern) {
if (!pattern.matches("[01\\?]+") {
throw new IllegalArgumentException("Invalid pattern: " + pattern);
}
int questionMarks = pattern....
2
For an interview setting, I think the code presented to be a very decent initial solution but for the lack of comments:
it is easy to read (and consequently should be easy to maintain).
It invites a question if there is any (semi-obvious) way to reduce machine resources used.
(AJNeufeld is entirely right about StringBuilder vs StringBuffer - leaving it ...
1
This can be solved dynamically and in O(N) time.
Define the list and reverse it.
Then simply add the previous element to the current item
Then print the reversed list
Having a nested for and while loop will slow the code down.
lst = [1,4,6,4]
lst = lst[::-1]
for index in range(len(lst)):
if index > 0: lst[index] += lst[index-1]
print(lst[::-1])
4
If your output is really what you desire, you are working way too hard for this.
In your original solution you work from the back, and sum all the needed elements in each step to generate the new sum. This is inefficient. Working from the back, you can reuse the sum from the previous step and just add the current element on top of it.
def ...
Top 50 recent answers are included
