# Tag Info

28

About using typedefs First, don't create aliases for standard types. Just write std::string instead of str. For someone reading your code, or perhaps you yourself reading your own code half a year later, whenever one reads str one wonders "is this a std::string or some other kind of string?" Furthermore, it is not good practice to introduce very ...

18

I'll propose an alternate implementation, because dictionaries are good at storing key-value pairs and you don't care about the value: def first_duplicate(given_list): seen = set() for value in given_list: if value in seen: return value seen.add(value) return -1 A set will buy you basically the same behaviour as the &...

16

Overall, I like this. To really nitpick, I don't really like the use of rules[::2]. [::2] conveys that we are picking out every even element of rules as if that was significant. But in this case, it is more like it just happens to be that the first and last rules are what we want to pick out and that happened to match up with choosing all even elements. I ...

15

While you don't want alternative solutions, you should take a look at the data in your specific usecase. As an example, for some randomly generated input (both lists of length ~600) on my machine (Python 3.6.9, GCC 8.3.0), your function takes In [18]: %timeit sorted_lists_intersection(a, b) 179 µs ± 1.19 µs per loop (mean ± std. dev. of 7 runs, 10000 loops ...

14

Benchmark and slightly improved versions of some solutions. Congratulations, in the worst case (a = list(range(1, 10**5 + 1))) your original solution is about 2-4.5 times faster than the solutions in the previous answers: 5.45 ms 5.46 ms 5.43 ms original 4.58 ms 4.57 ms 4.57 ms original_improved 25.10 ms 25.59 ms 25.27 ms hjpotter92 11.59 ms ...

13

Overall, it looks good to me. Just a couple observations. They aren't necessarily better or more pythonic, but you may see them in peoples code. Use whichever you find more readable: The first rule turns the digits to ints to compare them, but the ascii for the digits compares the same as the integer digits ('0' < '1' ... < '9'). So the int() isn'...

12

Watch your memory allocations and deallocations. In both cases, you've got defangIPaddr returning a const char * to heap-allocated memory, which needs to be freed by the caller... but it can't be freed, because free expects a non-const void* as its argument. Functions that return ownership-of-a-heap-allocation to the caller should (A) return char*, not const ...

11

Disclaimer I don't have a working C compiler on my work computer, nor do I have Xlib available to me (I'm also not familiar with it, at all). That being said, given that we know our image is a square, you can do this with a single loop. Use a simpler algorithm The basic idea is that we know each corner of our square, and then by stepping through the length ...

11

Perhaps, using a dictionary to keep account of already seen values? from collections import defaultdict def first_duplicate(given_list): seen = defaultdict(bool) for value in given_list: if seen[value]: return value seen[value] = True return -1 Function name should be lower_snake_case. defaultdict initialises with ...

11

Avoid mixing floating point and integer arithmetic As mentioned by greybeard, there is a potential problem here: const unsigned short n = log10(ULLONG_MAX); ULLONG_MAX is larger than can be exactly represented by a double. This means the result might not be what you expect. The same goes for pow(10, n). While you can compensate for it, it is better to find ...

10

isPrime() Complexity This function contains a simple loop that iterates up to Math.sqrt(number) times, so assuming Math.sqrt(...) can be computed in $O(1)$ time, the function has $O(\sqrt N)$ time complexity. Review This function is terribly inefficient. Math.sqrt(number) is computed $\lfloor \sqrt N \rfloor$ times, yet the value is a constant. ...

10

Algorithm Correctness Due to a small problem in GetBranchPrecedents this algorithm does not actually work. The case that all parents might already be present in the complete order. E.g. take the graph with the edges (C,A), (D,A), (E,A), (D,B), (E,B). In this case, A has the most prerequisites and will be treated first. This puts all nodes but B into the ...

10

if q in dic is pointless. You initialized dic so that it does have all queries. dic = dict.fromkeys(queries, 0) should be a bit faster. dic is not a particularly meaningful name, counter or ctr would be better. Creating results at the start of the function gives the false impression that it's needed there already. I'd create it right before the loop that ...

9

You should put your programming skills aside for a bit and think. Think mathematically, what it actually means. $$11^n = (10+1)^n$$ Lets say a=10, b=1 => $(a+b)^n$, this can be expanded using pascal triangle: 1 1 1 1 2 1 1 3 3 1 ... I suppose everybody knows how this continues... It then goes like this:  (a+b)^n = {n \choose 0} a^n b^0 + {n ...

9

Your function f should probably be a proper function, like all the others. There is no reason for it to be a lambda. def fuel(mass): return mass // 3 - 2 Instead of using recursion, you could use iteration in partial_sum: def total_fuel(mass): total_mass = 0 while True: mass = fuel(mass) if mass <= 0: break ...

9

The code seems to be too complicated. There are a few ways it can be optimized: if i1 == len1: return intersection and if i2 == len2: return intersection return statements can be expressed as yield so that the return for the entire array is not required; it returns constantly. However, this condition needs to be there otherwise it won't ...

9

The real performance issue here is fairly simple: good performance is obtained by not repeating steps. The big step that you are doing repeatedly is to figure out where the pixel goes in the output space. If we consider @Dannano's img[WIDTH * y + x] = 456; We wind up doing that currently for every point. Multiplication is hard (at least classically, and ...

9

In my opinion, the best way to improve this program is by using bitboards. Instead of using a table in two dimensions to represent the chess board, you use 12 numbers of 64 bits, each number representing a type of piece and each bit saying whether there's a piece or not on a square. You can then use bitwise operators to modify the chessboard. This method is ...

8

The implementation is wrong, and will return incorrect results once n exceeds 15. A double stores values using a 53 bit mantissa, allowing accurate representation of values with approximately 16 digits of precision. When $n \gt 16$, then $11^n \gt 10^{16}$, and the double value runs out of precision, and cannot represent the value precisely. This ...

8

If you treated your 2 inputs as iterables instead of simply lists, you could think in terms of for loops with direct access to elements instead of using __getitem__ all around. The second advantage being, obviously, that you can call the function using any iterable instead of only lists; so data that is in a file, for instance, can be processed with, e.g.: ...

8

using namespace std; Never do that; certainly not in a header - that inflicts the harm onto every source file that includes the header. Prefer to include your own headers before Standard Library headers. This can help expose unsatisfied dependencies of your library's headers. Prefer <cmath> to <math.h> (etc.), as this puts the standard ...

8

I believe you could reduce it to $O(n\log{n}+m\log{n}+n m)$ if you want. Sort the inputs, then iterate over the tests and for each one, do a two variable iteration over the inputs, where you start as close to the test value/2, and move one index in the increasing direction and the other in the decreasing direction depending on whether the sum is less ...

8

Specific suggestions: In many situations it would probably be useful to return sub rather than len(sub). This makes the code somewhat simpler and gives the caller more information. Depending on the context that may or may not be useful, but it simplifies the code, which makes it easier to focus on the core issue. The code iterates over all sub-lists, ...

8

Memory Your list implementation uses (depending on your architecture) 8 bytes per list element. >>> import sys >>> b = [False] * 100001 >>> sys.getsizeof(b) 800064 Note: This is just the memory of the list structure itself. In general, the contents of the list will use additional memory. In the "original" version, this ...

8

Any time you are using a dict, and you need to do something special the first time a key is used, take a look at collections.defaultdict(). from collections import defauldict def matchingStrings(strings, queries): results = [] counts = defaultdict(int) for s in strings: counts[s] += 1 results = [counts[q] for q in queries] ...

8

Consider using asprintf() Just like you are using strdup() to simplify making a copy of a string, consider using asprintf() to print a string without having to worry about allocating memory yourself. This will greatly simplify your code: char* defangIPaddr(const char* address) { char* defanged; int ip[4]; if (sscanf(address, "%d.%d.%d.%d&...

8

struct Node would benefit from its own constructor. As a side note, if you don't want to expose struct Node to the client (and trust me, you don't), better make it private to class LinkedList. tmp doesn't deserve to be a class member. It is strictly local to each method. DRY. push_back could and should be streamlined: struct Node * tmp = new Node(data); ...

8

General I found no "dumb mistakes associated with generic code". Good job. Still, there are some points which can be improved. (Aren't there always?) The first point is encapsulation. Letting nodes float around free, instead of keeping them in their dedicated container, or (rarely) evacuating them to a handle for re-insertion, is not recommended. ...

7

Your function code can be simplified to one line. from itertools import combinations from typing import List def array_sum(inputs: List[int], tests: List[int]) -> bool: """ Determines if any two integers in inputs add up to any integer in tests. :param List[int] inputs: Input data :param List[int] tests: Numbers to test against ...

7

I think it's a nice project. I would say that the main things for you to work on is getting further acquainted with Python's standard library and with standard practices, which is what most of my advice will be surrounding. Minor improvements For your alphabet, you could use ascii_lowercase from string, i.e.: from string import ascii_lowercase alphabet = ...

Only top voted, non community-wiki answers of a minimum length are eligible