# Tag Info

33

From a pure Python standpoint, a list is already a stack if you narrow its methods down to only pop and append. l.append(x) will put x at the end of the list, and l.pop() will remove the last element of the list and return it. So generally speaking, when you need a stack in Python, you'll just make a list and use append and pop. The same goes for queues, ...

21

You wrote very clear and readable code: the variable names express the purpose you use const and let instead of the old var you encapsulated all the interesting code in a function, which makes it easy to copy and reuse the code You chose to use as few temporary memory as possible (4 local variables, no arrays or other objects), at the cost of needing more ...

21

This is purely stylistic, but I'd add some spacing around the loops. I'm also not a fan of multiple declarations on the same line, so I'd separate out the maxLeft and maxRight declarations. Lastly, the parameter should arguably be called heights. height suggests that it's a single number representing a height, whereas it's actually multiple height values. ...

21

Usability I have a remark about defining recursive functions. You don't want consumers of your API to think about the intermediate variables and their initial value. The consumer does not care you are using recursion internally. Make your recursive function private. private static int maxPlayer1(int[] a, int currSum, int sum, int start, int len) And ...

19

A triangle has, by definition, three sides. I find it therefore weird to take a single sides argument, which could be of any size. This opens you up to obscure bugs, such as these ones, which are not covered in your tests: >>> is_triangle([1,2,3,4]) True # ? >>> is_triangle([1, 1]) True # ??? >>> is_triangle([float('nan')]) ...

18

Putting this through the built-in profiler reveals some hot spots. Perhaps surprisingly: ReverseBits. It's not the biggest thing in the list, but it is significant while it shouldn't be. You could use one of the many alternate ways to implement ReverseBits, or the sequence of bit-reversed indexes (which does not require reversing all the indexes), or the ...

17

About naming: intI and intK: don't include the type in the variable name, it is obvious from the context and intellisense and as a loop index a plain i and k are more understandable. A first simple optimization is that you can avoid the check if intK has reached the end: a.Length - 1 == intK ? Instead you can just iterate up to a.Length - 1 and then ...

17

Use a better container The main issue is that std::vector<int> is a bad container for storing a set of ASCII characters. Every vector allocates on the heap, and an empty vector is likely 24 bytes in size. So this is huge waste. Why not use a container designed to hold a series of ASCII characters, like... std::string! Do you need to store all ...

16

I guess your code is slow because of the two loops and its O(n^2) complexity. You can actually solve it with only one loop by rotating the index with % (modulo). This would even allow you to rotate the array in both directions; public static IEnumerable<T> Shift<T>(this T[] source, int count) { for (int i = 0; i < source.Length; i++) {...

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

Following @Martin R's comment, I'll make my comment above a solution: printf already supports what you're trying to achieve with your if-then-else jungle: #include <stdio.h> int main() { int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { int N; scanf("%d", &N); int hours = N / 60; int ...

15

Your solution is far too complicated. It's also inefficient, because it uses functions .lastIndexOf() and .includes(), both of which analyze the entire str looking for target, whereas an optimal solution should look only starting at a known position at the end of str. Here are two simple solutions: function confirmEnding(str, target) { return str....

15

You're right, it can be turned into one line using comprehension syntax which would be your best option of you're looking for a slightly more efficient code. isdecimal() is better to use in this case than isnumeric() because the isnumeric() accepts types like ½ and ¼ and n² which might produce some side effects you don't want if you're using this function ...

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

If it is known that a majority element exists, then the efficient algorithm to use is the Boyer-Moore majority vote algorithm, which requires only O(1) space.

14

Reviewing complexity So far only one answer has addressed the complexity issue, and is a considerable improvement over your solution. As the existing answers have addressed code style I will stick to the complexity as there is a less complex solution. Looking both ways!? Your solution is looking in both direction to find the next peak and thus calculate ...

14

I am only looking for some feedback on my coding style. Formatting is good. I hope it is auto formatted. Respect the presentation width Rather than oblige a horizontal scroll bar, auto format to a narrower width to avoid that. Avoid dogma "to ONLY USE ONE return statement in functions and NOT to use things like break, continue or go-to." --> This is a ...

14

Convergence testing if pi == piold: break This is not usually done, because float equality has a lot of gotchas. In this case it's possible due to the numbers being Decimal, but if you need to move away from Decimal you're going to encounter issues. Usually, convergence is measured as the absolute error decreasing below a chosen epsilon, a ...

14

On the whole the code is good, but I would look for three improvements: Information-hiding: I would change self.stack to self._stack to indicate to readers of the code that this is an implementation detail that should not be accessed directly. Reasons: Mutating self.stack directly, for example self.stack.insert(2, 42) could break the expectations a client ...

13

Not all counting problems require enumerating the items being counted. If you were asked to count how many sheep there are in total if there are $n$ trucks with $k$ sheep each, you could write something like: total_sheep = 0 for truck in range(n): for sheep in range(k): total_sheep += 1 Or you could cut to the chase and compute it as: ...

13

What you are approximating is $$\pi =\sum_{m=1}^{\infty}\frac{(-1)^{s(m)}}{m},$$ where $s(m)$ counts the number of appearances of primes of the form $4k+1$ in the prime decomposition of $m$, compare How can we prove $\pi =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}-\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\cdots\,$? on Mathematics Stack Exchange. The ...

13

EDIT: Thanks to @benrg pointing out a bug of the previous algorithm. I have revised the algorithm and moved it to the second part since the explanation is long. While the other answer focuses more on coding style, this answer will focus more on performance. Implementation Improvements I will show some ways to improve the performance of the code in the ...

13

The code is clean. My major concern with how it looks is that your naming doesn't follow PEP8. Names should be snake_case, not camelCase. So isEmpty should be is_empty. With how it works, I'd work on giving it consistent behavior with other collections. Right now, you have a sizeStack method for returning the size. This should really be __len__ instead: ...

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

Time complexity Your time complexity is linear but you can save a few traversals over the string and lower the constant factor as you improve readability. Checking whether a string is a palindrome can be done in one pass with two pointers at each end of the string (plus some conditionals for your special characters), but this gains speed at the expense of ...

11

Review Testing (I haven't rigorously tested it). Well you should write some test to ensure validity of the function. So even after changes you can be sure it will still work. doctest is a pretty nice module to use, and is a nice extension of your docstring Naming Variables should have descriptive names! lst1, lst2 if it wasn't for that docstring I ...

11

In-place sort Your selection_sort is an in-place sort, so there's no need to return the same list you were given. In fact, returning the list is confusing, because it somewhat implies that you would be returning something different from what you were given. You can just drop the return, here and in similar functions. Failure modes if sublist_increment // ...

10

Bug There is a case that requires NFA instead of simple DFA to recognize string (of course it is possible to convert NFA to DFA): eval("aaab", "a*ab"); Gives false, even though the string matches the regex. Disallowing same character after * fixes the problem too. Style why-is-using-namespace-std-considered-bad-practice. Pass by const reference for ...

10

The minheap approach seems correct. The problem is in the answers. It may grow quite large (up to $10^9$). All the reallocations due to its growth are very costly. However you don't need it at all. You only care about the time of the most recent alarm. Just one value: while k: v = heapq.heappop(times) heapq.heappush(times, v + x) ...

10

Preface This is great code. Your solution is more than $10^{42}$ times nicer than the given solutions on the linked page that promote crap like #include <bits/stdc++.h>. You are already much better than them in this regard. The algorithm Making use of the STL, your algorithm can be simplified like this: std::vector<long long> subsetSums(...

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