37
One of the best ways to make a program faster is not to compute things that you don't have to. In this question you are asked to compute the number of permutations. But your implementation goes and constructs all the permutations themselves, only to throw them all away again. It would be better to count them directly, via some kind of a mathematical formula.
...
36
Before I get started I have to say: Thank you for coming here. Mess of Java For Loops is almost an understatement. Now, let's get working, shall we?
In the below answer I assume that sortedDictionary and anagram_words is both of type List<String>. I also assume that anagramCharacters is of type char[].
Code duplication
Start by identifying which ...
31
GroupValues
GroupValues doesn't seem to serve much of a purpose beyond what you get from Map; it adds no functionality beyond an unused field. In practice, all I think it is achieving is obscuring what is actually going on.
FieldGroup
That you are extending ArrayList, rather than composing with it, is a code smell. I find myself looking at ...
30
For one thing, the inconsistency with whitespace use and curly brace placing may demonstrate a lack of attention to detail. Before you attack the actual problem, make sure your code is written cleanly.
This:
for(int i=0;i<=rowIndex;i++)
should use some whitespace:
for (int i = 0; i <= rowIndex; i++)
You already do this in other places, and it ...
29
To convert an integer to a bit string with a particular number of digits, use string.format with the b format type. For example:
>>> ['{0:04b}'.format(i) for i in range(16)]
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111',
'1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']
But really it looks to me as though you don't ...
27
There are at least two optimizations you could make.
First of all, you are performing r multiplications and r divisions for each value of C(k,r) you compute for r < k/2.
You should only need at most one multiplication and one division
per value of C(k,r) that you compute, because at the time you want to
compute C(k,r) you have already computed and stored ...
24
Types are very important in C++.
You are being sloppy with your types.
long long sol; // big int object.
While you are putting it into an object that only holds int
vector<int> v; // Only takes int
v.push_back(sol); // push long long and thus truncate
20
I'm going to skip reviewing the OP's code, which has already been reviewed quite nicely by others. Instead I'm just going to show a much faster version and explain it.
What is the algorithm?
Basically the way the algorithm works is that a buffer is created that holds alphaLen^2 patterns, where alphaLen is the length of the alphabet. A pattern is one ...
20
1. Code review
The question says, "Write an algorithm that counts the number of ways" but the program does not only do this: it also builds a list of the combinations. This means that the program is limited to values of \$N\$ and \$K\$ that are small enough that the list of combinations fits in the storage space of the computer. Whereas a program that did ...
19
I am kind of curious why you separated the Int variable out of the for loop?
int i;
for(i = 1; i <= r; i++) {
ans *= n - r + i;
ans /= i;
}
I would think that you would only do this if you want the variable outside of the loop, but it is the variable makes the loop function, you don't want it's scope to be that public, ...
19
As an interviewer, I'd see a big red flag in the implementation. Calculating each coefficient from scratch results in a lot of unnecessary recalculations.
Use recurrence: you already know \$\binom{n}{r}\$, so \$\binom{n}{r+1}\$ is just one multiplication and one division away.
18
There are three reasonable responses here:
yes, your recursion code can be improved for performance.
yes, part of that improvement can come from sorting the data.
yes, there's a way to refactor the code to not use recursion, and it may even be faster.
Bearing that in mind, this answer becomes 'complicated'.
Basic performance improvements for current code:
...
16
The structure of the code makes it difficult to test. Suppose you had two different implementations, and wanted to test that they returned the same results? The code doesn't lend itself well to this situation.
My first attempt at speeding up the code was to use the answer to TopinFrassi's question on Mathematics.SE.
As the answer explains, the solution is ...
16
As @BenC mostly put a code dump, I'll explain ways that your code could have improved.
reverseIt
Programming this is just wrong in Python.
This is as there are two ways to do this.
>>> list(reversed([1, 2, 3]))
[3, 2, 1]
>>> [1, 2, 3][::-1]
[3, 2, 1]
As an alternate way to this you could just calculate the range backwards off the bat.
&...
15
In this program, bruteImpl is a tight loop. I wouldn't bother optimizing anything else, even if it would save some time, because most of time will be wasted running bruteImpl anyway. Running memset one time won't save your time, as it's ran... length times. However, with length set to 5, bruteImpl is called... 15264777 times. This is definitely something ...
15
Expectation Setting
Your algorithm is an incrementing index, which you then convert in to the radix of your charset.
Your charset is what, 95 characters?
So, there are the following possible permutations for passwords:
1 char -> 95
2 char -> 9025
3 char -> 857375
4 char -> 81450625
5 char -> 7737809375
6 char -> 735091890625
7 char ->...
15
Pairing combinations like this is a very common thing to do in any language. There's a very 'idiomatic' way to do this type of operation:
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
// do something with pair (i,j)
}
}
You will see, and recognize this pattern anywhere.
Because that pattern is so ...
15
1. Analysis
In the general case, the problem of finding the sample of words with the "most even" distribution of letters is NP-hard. Here I'm considering a general instance of this problem to be:
Given an alphabet \$ Σ \$, a set \$ W \$ of 4-letter words over that alphabet, and an integer \$ n ≤ \left|W\right| \$, find the subset \$ W^* ⊆ W \$ with size \...
15
Please take a look at itertools.product. It will simplify your code greatly.
def getCombos(digits, caps, numbers):
# Build set of choices appropriately based on caps and numbers
choices = list(range(33, 126))
for vals in itertools.product(choices, repeat=digits):
print ''.join(map(chr, vals))
getCombos(3, True, True)
15
I would say yes, use an array.
Arrays afford very good memory locality, which is good for cache performance. They essentially are the most basic and efficient hash map if the key is the index.
You only need one array with 256 elements: first count up the number of times each character appears in the first string, and then count down for the number of ...
14
I prefer your approach much better than a recursive approach, especially when larger lists are being processed.
Some notes:
I like the name powerSet as per @200_success
You do not need to check for combination.length !== 0 if you start with i=1
If you call the function permutations, then you should not call the list you build combinations, that is ...
14
This problem begs for recursion....
private static final void checkWord(char[] chars, char[]current, int len, List<String> results) {
if (len == chars.length) {
final String result = new String(current);
if (sortedDictionary.contains(result)) {
results.add(result);
}
} else {
// get the next ...
14
I would say that this is pretty much impeccable as a recursive solution.
In bruteSequential(), I would rename i to len for clarity. As a slightly hackish optimization, you could move the memset() call before the for-loop, since you know that the output string lengths will never decrease. You could then combine it with the malloc() for
char* buf = calloc(...
14
Focusing on optimizations:
in GroupValues:
@Override
public int hashCode() {
if (bufferedHash != 0) {
return this.bufferedHash;
}
int result = super.hashCode();
this.bufferedHash = result;
return result;
}
to
@Override
public int hashCode() {
if (bufferedHash == 0) {
this.bufferedHash = super.hashCode();
}
...
14
Style
In Java it is common practice to have class names to use PascalCase (a.k.a. UpperCamelCase). Also the name spaceship doesn't make sense to me and is confusing. Also, why is the instance called kling?
Readability
I prefer to prefix my formal parameters with a for argument, for example aInputArray. I believe it would help readability of your code.
...
14
You're looking for set(). The reason for your program being slow is:
you're calculating the permutation once: perm_repeated = permutations(string)
then you're looping through all the permutations (question: if you already have all the permutations in perm_repeated why are you doing again for p in permutations(string) instead of for p in perm_repeated?) and ...
14
1. Review
The sum \$s=0\$ can be reached in \$n=0\$ throws in exactly one way, but:
>>> get_sum_dp(0, 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "cr161002.py", line 32, in get_sum_dp
t[1][j] = 1
IndexError: list index out of range
The name get_sum_dp could be clearer (what does "dp" mean? ...
14
The tool you need here is itertools.product:
>>> import itertools
>>> keys, values = zip(*config_overrides.items())
>>> experiments = [dict(zip(keys, v)) for v in itertools.product(*values)]
>>> len(experiments)
3234
>>> experiments[1034]
{'nhidden': 4, 'nodetype': 'lstm', 'loss': 'msle', 'opt': 'nadam', 'actfunc'...
14
Comparing two maps is linear, so that's not a big problem.
I don't think you've made particularly good use of maps though. As I see it, you have two choices. You could use an unordered_multiset, or you could use a unordered_map<char, size_t>. In the latter case, you'd keep a count of each character in the string, and increment the count for each ...
14
Binomial coefficient \$\binom{n}{k}\$ is growing too fast (with \$n\$) to keep a list of all combinations in memory. I would suggest to use yield return instead.
The main improvement which can be done here - not to use Recursion at all.
Solution without recursion
static class Combinations
{
// Enumerate all possible m-size combinations of [0, 1, ..., ...
Only top voted, non community-wiki answers of a minimum length are eligible
