38
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 ...
32
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 ...
31
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 ...
28
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 ...
25
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
21
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 ...
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 ...
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:
...
17
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 ...
16
Your approach is an example of good R code. However, there is a base function that allows creating a cartesian product of strings, interaction. This function creates a factor, and the levels are equivalent to the cartesian product.
Furthermore, instead of paste(..., sep = "") you can use paste0(...).
If you use these functions, your code will be much ...
16
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 -> ...
16
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 ...
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.
&...
16
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'...
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
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();
}
...
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 ...
15
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, ..., ...
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
I'm going to throw my hat in the ring with the iterative version of Heap's method of generating permutations. It took me a while to get right, as my reference source has a typo in the algorithm -_-.
function swap(chars, i, j) {
var tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
function getAnagrams(input) {
var counter = [],
...
14
Your solution works fine, and it's fairly efficient. You're using loops and mutation, which are speedy, but also not terribly readable. This algorithm can be expressed more functionally in terms of recursion and mapping, which can make it somewhat more readable, though slightly less efficient.
function pairwise(list) {
if (list.length < 2) { return ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible