New answers tagged algorithm
0
One solution to (user1118321) would be to use a height_stack that keeps track of the height of the nodes in the node_stack, similar to what the answer above suggests.
for (auto it = top->children.begin(); it < top->children.end(); it++) {
node_stack.push(*it);
height_stack.push(current_height+1);
}
Note: You might have to be ...
4
Your solution is alright and I got it accepted as-is. Just had to choose "PyPy3" instead of "CPython3".
Anyway...
I'd use accumulate and a helper function to reduce code duplication and make the interesting code clearer:
from itertools import accumulate
def input_ints():
return map(int, input().split())
def solve():
_, q = ...
5
To add on to @hjpotter92's answer:
If you're not using i in for i in range(q), replace it with _, i.e. for _ in range(q) to indicate that you are not using the variable.
It turns out the actual bottleneck is the many calls to print() in a for loop. If you tweak your code so it instead builds a string of all the answers to the queries in memory and prints it ...
2
Here is my take on the problem, a function which accepts any string length and only allocates exactly enough memory:
//#include <malloc/_malloc.h>
#include <stdlib.h> // malloc, free
#include <assert.h> // assert
#include <stdio.h> // printf, fprintf
/**
* "Defangs" a string by replacing all `.` with `[.]`.
*
* @param ...
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&...
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 ...
5
List vs Python array vs NumPy array
To my surprise, my solution using Reinderien's suggestion to use a Python array was fastest in my benchmark in 64-bit Python (and not bad in 32-bit Python). Here I look into that.
Why was I surprised? Because I had always considered array to be rather pointless, like a "NumPy without operations". Sure, it ...
6
You are already using the optimal solution algorithm for the problem. A few things, which might speed-up the computations (.split should not be the limiting factor in most likeliness)
Variable naming
Use names which match the problem description, so that it becomes easier to follow your code. So, instead of x, y it'd be a, b. Also, in python, it is a good ...
2
If you instrument your code with some strategically place print statements, you will see that there is some repeated computations going on. In the second test case when processing the clause X2 v ~X3, the set {'X1', 'X2'} gets added to mySets twice. When processing the clause X3 v ~X1, the set {'X3', 'X1', 'X2'} gets added to mySets three times.
For large ...
3
Here's a suggested implementation that changes basically nothing about your algorithm, but
has proper indentation
uses a little bit of type hinting
uses set literals and generators
uses _ for "unused" variables
adds a parse_clause() because the clause code is repeated
uses a StringIO, for these purposes, to effectively mock away stdin and use the ...
2
Given that your array is a simple list of uniform type, you might see some small benefit in switching to https://docs.python.org/3.8/library/array.html , which is built specifically for this kind of thing. It's a compromise that uses built-ins without needing to install Numpy.
4
You could use itertools.accumulate to shorten your second part a lot and make it faster:
def arrayManipulation(n, queries):
nums = [0] * (n + 1)
for a, b, k in queries:
nums[a - 1] += k
nums[b] -= k
return max(accumulate(nums))
Can be used on Marc's version as well. Benchmarks with various solutions on three worst case inputs:
...
7
Nice implementation, it's already very efficient. Few suggestions:
Expand the variables in the for-loop from for q in queries to for a, b, k in queries. Given the problem description it's easier to read.
A better name for the variable current can be running_sum.
Avoid calling a variable max, since it's a built-in function in Python. An alternative name can ...
3
I don't know of any way to optimize this; I suspect you've cracked the way it was intended to be implemented. The following are just general recommendations.
Using black to format the code will make it closer to idiomatic style, with no manual work.
After formatting I would recommend running flake8 to find remaining non-idiomatic code. For example, function ...
3
Others have made good points, but I'll add in a stylistic quibble.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
is a heck of a one-liner. The ternary operator is fun but speaking as someone who has ...
3
I agree with everything in Martin York's answer. Just one thing: you can avoid having two unordered_maps if you don't create a purely random URL, but instead create one by hashing the original URL. This way, you will always create the same tiny URL for the same long URL, so you don't need encoded_url anymore. Of course, you would still need to handle ...
4
You are doing the lookup twice.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
I know that it is O(1) for the lookup. But there is a real constant inside that. Avoid it if you can.
Use find(). Then if it is there you can simply use it.
...
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 ...
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]
...
3
Some minor stuff:
This if:
if simulated[i] == q[i]:
continue
is redundant and can be removed, due to the predicate on your while. The while would execute zero times and have the same effect as if you continued.
The while itself:
while(simulated[i] != q[i]):
should drop the outer parens.
The range here:
for i in range(0, len(simulated)):
...
4
How long is a long long?
It depends on the CPU architecture and the operating system how long a long long really is. It might help to be more specific, and specify that a Fraction is a fraction of 64-bit integers, and then use int64_t. Also, instead of writing long long, consider creating a type alias:
using Integer = long long;
And use that everywhere. ...
6
Some things to consider:
Fundamental types do not have move constructors, so num(std::move(_num)) is just the equivalent of num(_num)
If you're not doing template code, move definitions out of header files. This can cause naming conflicts if multiple files include Fraction.h
Having a ++ and -- operator for a Fraction doesn't make sense. What does it mean ...
6
Drat. My super pretty NumPy solution which is probably efficient doesn't get accepted because HackerRank apparently doesn't support NumPy here. Oh well, here it is anyway, maybe interesting/amusing for someone.
import sys
import numpy as np
a = np.loadtxt(sys.stdin, dtype=np.int8)
h = a[0:4, 0:4] + a[0:4, 1:5] + a[0:4, 2:6] + \
a[1:5, ...
1
List literals
expressions = []
expressions.append(str(args.expression))
should just be
expressions = [str(args.expression)]
Pathlib
This:
if not os.path.exists(output_dir):
os.makedirs(output_dir)
should use the shiny new pathlib equivalent:
Path(output_dir).mkdir(exist_ok=True)
The same module can be used for
if not os.path.exists(...
1
I think I would change the Fraction::simplify, personally. I would maybe let it be a static class method that took a Fraction object and returned it's reduced representation without modifying the original object.
There are times when it might be useful to calculate a proportion without clobbering the original object, such as when calculating the Binomial ...
1
Congratulations on the correct use of the C++11 condition variables! As mentioned by vnp, there will be no difference functionally or performance wise in this specific case, as there is only ever one thread waiting while the other notifies. Some possible improvements though:
Unnecessary return statements
You don't need a return statement at the end of a void ...
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 ...
3
You can specify required arguments in argparse rather than handling them yourself. You can also specify defaults, for example for output_dir.
os.makedirs takes exist_ok=True to indicate that it should only create the directory if it doesn't exist yet.
The extensions argument to the SourceWalker constructor probably shouldn't be hardcoded.
Use with open(...
3
If I understand your description, you're only looking for comments but you are searching through the full code base every time. Since comments are normally a small part of the code (less than 10%?) I suggest doing a pre-process step first where you simply extract all the comments and then do the actual search on those.
By "extract" I mean save the ...
4
Using list comprehension, make a list of the numbers occurring more than once
i for i in a if a.count(i) > 1
Return the first match or -1 if no match was found
next((i for i in a if a.count(i) > 1), -1)
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 ...
7
Note that all the elements are positive, and the values are not greater than the length.
There is a very clever method to find the solution in these cases.
The idea is to mark the values by turning a[value] negative.
If a duplicate exists, it will encounter a[duplicate] as negative.
Here's the implementation:
for i in a:
if a[abs(i) - 1] > 0:
...
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 &...
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 ...
3
Trailing return types
Your use of trailing return types looks very inconsistent. Looking at the Google C++ Style Guide, it seems that they recommend using them if leading return types are "impractical or much less readable". That is of course a matter of taste then, but I would recommend being as consistent as possible: first, use the same type of ...
3
I think this is a theme for your code: const, where you've put it, has no benefit; and it's missing from other places that it should be there. Every single function in MyCircularDeque should drop the const out front, because those return values are scalar so marking them const has literally no effect. insertLast(const int value) has slightly more effect but ...
5
Using the same type for the deque contents and the sizes/indices (k, count, head, tail) feels wrong. At least, k and count should be std::vector::size_type.
Since you are backing up the deque with std::vector, making head and tail the std::vector::iterator looks more idiomatic.
k is not the most descriptive name. Consider capacity.
I am not sure that std::...
4
You can call stream.reserve(k) in the constructor to improve the efficiency of the vector because you know that you will only have k elements, so .reserve() will pre-allocate the memory.
Prefer using std::size_t over int
int k would be std::size_t k
You haven't declared a copy constructor nor a copy assignment operator. This can cause issues if you wanted to ...
0
Looks good!
I would say maybe the following styles would be just a bit more readable, easier to follow.
We can also alter l1 and l2 with more descriptive variable names.
Line Counting Fallacy:
Sometimes, Line/character countings are helpful for command line languages/scripts (awk, grep, sed, regex, etc.) or maybe Code Golfing, is not a JavaScript ...
5
If you can use c++17 you can use the stl filesystem, this header contains faculties for performing operations on paths and files and would make your code simpler, for example the delimiter can be handled with the std::filesystem::path class.
According to the documentation of std::filesystem::path a path can be normalized by following this algorithm:
If the ...
0
I think there is plenty of room for improvement. Whenever I write code I try to focus on 3 things in this order:
Does the code correctly perform its purpose?
If another developer reads this code in 6 months, will they
understand it?
Does the code perform optimally?
I think you fall short of (2). The thing that slaps me in the face is why is a List used ...
3
String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";
s is ...
1
Avoid converting data structures to string unnecessarily
Just store tuples of values in indegrees instead of strings:
if i == a:
indegrees[i].append((i, b))
indegrees[i].append((b, i))
Iterate over the keys in indegrees directly
In this piece of code:
for i in range(n):
for j in range(n):
if f'{i}-{j}' or f'{j}-{i}' in indegrees[i]:
...
4
The best way would be to change data structure. Instead of using a List<Int> you can use a Map<Int, Int>. If you want to have a List<Int> in the beginning, that's ok, you just need to convert it to a Map<Int, Int> and compare the maps.
Using the nice Kotlin methods in the stdlib, we can make the code into this:
fun <T> ...
6
Don't use system() for trivial tasks
Calling system() means starting a new shell process, which in turn has to parse the command and execute it. The clear command is not a built-in for Bash, so the shell in turn will start a new process to execute /usr/bin/clear. And it's just a program, it's not magic; clear itself is also written in C. And all it ...
6
General Observations
Welcome to code review, nice first question. I would leave the licensing information out since stack exchange uses the Creative Commons Attribution-ShareAlike license.
The comment block at the top is rather helpful otherwise. FYI, this compiles fine on Windows 10 in Visual Studio 2019 Professional, but doesn't link (usleep() is undefined)...
1
I don't think the generator should inherit from the solver. Rather, any methods that they both need could be moved into a third class that either 1) they both inherit from or 2) they both include as a member.
I would try to do #2.
2
Here's a rewrite incorporating everything said before, as well as an idea I got from Timsort: Instead of moving both halves out for the merge, only move one half out. I chose the left half. This saves space, saves the move costs, and also eliminates the need at the end to move remaining right values, as they're already where they belong. Also, I show the ...
4
Performance
For the moment, let's look at only one small part:
void sort(vector<int> &vec, int left, int right, int originalsize)
{
int insertion = right - left;
if(insertion <= 8) //if righ-left is less than or equal to 8
{
insertionSort(vec, originalsize); // call insertion sort
}
if(left < right)
{
int center =...
4
Algorithmic complexity is not a good indicator of real-world performance
When you have to choose between an \$\mathcal{O}(N^2)\$ or \$\mathcal{O}(N^{1.58})\$ algorithm, you would think that the latter is faster, however that is only true for sufficiently large values of \$N\$. In practice, unless you have more than a thousand digits to multiply, the simple \$...
Top 50 recent answers are included
