New answers tagged programming-challenge
-2
========== Triangle =========
11
7 12
4 8 13
2 5 9 14
1 3 6 10 15
======================
Explanation
First column 1,2,4,7,... which can be formulate as (x(x-1)/2)+1
Second column 3,5,8,... which can be formulate as ((x+1)x/2)+2
Similarly 3rd column can be formulate as (x+2)(x+1)/2)+3
Final formula from 1, 2 and 3 is (((x+y-1)*(x+y-2))/2 + x)
So return ...
1
The accepted answer is great, but it's probably important to note that the suggested solution doesn't actually pass the actual test cases because the prompt specifies that order must be maintained.
So solution([1,2,4)] = 1 but solution([4,2,1]) = 0.
Regardless, here is my ELI5 of the accepted answer:
"""
First, we must recognize that any "...
2
Take a look at what translating
1241234113
results in when aligned slightly differently
One Billion
Two Hundred Forty One Million
Two Hundred Thirty Four Thousand
One Hundred Thirteen
you can see that there are several patterns here.
Every number can be chunked into groups of 3 digits like ...
4
Solve with math
This is a math problem. Let say we have a competition: [a, b, c] score [5, 2, 10], this means that the scoring is:
$$
\begin{array}{|l|r|r|r|}
& \textrm{a} & \textrm{b} & \textrm{c} & \textrm{res} \\
\hline
\textrm{a} & \text{NaN} & 3 & -5 & -2 \\
\textrm{b} & -3 & \text{NaN} & -8 & -11\\
\...
0
Edit: this is same algorithm as provided by Simon but different code.
.......
One option is to use Euler himself to solve Euler Project #1. Namely triangular numbers (Elements of Algebra, 427).
def triangular_number(num, max_num=999):
"""Return maximum triangular number of num in range max_num (inclusive).
Calculate number of ...
1
Make helper functions private
Member functions that are not part of the public API should be marked private.
You should know that by now :)
Use uint64_t instead of size_t
There is no guarantee that size_t is big enough for the calculations you are doing. While you might only need 32 bits to store the results, you need to do the calculations using 64 bit ...
1
inline std::string int2string(const int n) {
if (n >= one_billion) {
return int2string(n / one_billion) + " "+ BILLION + int2string(n % one_billion);
} else if (n >= one_million) {
return int2string(n / one_million) + " " + MILLION + int2string(n % one_million);
} else if (n >= one_thousand) {
...
4
Avoid globals. consecutivo is particularly confusing. It is too easy to miss the fact that it is reset to 0 at each iteration. Always prefer returning a value:
int suma_elementos(int elemento)
{
int proporcion = n;
int consecutivo = 0;
while (proporcion >= elemento)
{
proporcion--;
consecutivo++;
}
return ...
0
Timing of your algorithm
def f():
x = 0
for i in range(1000):
if i % 3 == 0 or i % 5 == 0:
x += i
return x
%timeit f()
152 µs ± 12.5 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Using Principle of Inclusion and Exclusion (PIE) gives you the answer faster.
%timeit (sum(range(3, 1000, 3)) + sum(range(5, 1000, ...
1
This is not a proper review. I just want to show an argument why passign the input by value is actually more useful then passing it by const reference, in this particular case.
Yes, it's true you should not modify the input for the caller, because he didnt ask you to do so.
But it is also true, that your implementation takes advantage of the ability to ...
2
Passing by reference or value
Currently,
std::vector<int> nums
forces callers to pass a copy of the entire vector by value. You could argue that this is actually useful, since your algorithm needs to mutate it (or a copy of it) in-place. My preference is usually to make this copy-step explicit instead:
Pass a const & reference, not a mutable copy
...
2
Make clone_tree() private
Make helper functions that are not part of the public API private.
Avoid unnecessary nesting of statements if possible
In allPossibleFBT() there's a lot of indentation. There's a risk of the code running off the right hand side of the screen, making it hard to read. Try to reduce nesting if possible (but only if it improves ...
0
Consider what you are doing here. You are generating a list of primes less than a number. You are generating this list in order of increasing size. One simple optimization is to seed the list with a few primes at the beginning. In particular, 2 and 3. Then you iterate to skip over all the even numbers. That cuts your checks in half.
Now, a second point ...
1
Function signatures
You've made the best out of a slightly silly situation. I think your function signatures, while abiding to the template, have improved since the last post of yours that I reviewed.
I'm not sure whether this will break LeetCode compatibility, but if you want to enforce that no one can instantiate this class, try making a private default ...
2
You forgot a std::
There's a string without std:: in front of it. I guess you secretly used using namespace std and/or #include <bits/stdc++.h> before submitting the result. The rest looks fine though.
Consider using const TreeNode * everywhere
I know the public API of the LeetCode problem explicitly takes non-const pointers to TreeNode, so you shouldn'...
3
In addition to what Reinderien said:
Move class Trie inside class StreamChecker
Your class Trie is not a generic class, but rather a specialized trie implementation specifically for StreamChecker. You can move it inside class StreamChecker, so that it is clear that they belong to each other, and so that class Trie does not pollute the global namespace:
class ...
1
You should measure the duration of each step in the algorithm to detect where the bottleneck(s) is/are. You can do that using console.time("id") paired with console.timeEnd("id"):
function findPrimes(count) {
console.time("prime generation");
storePrimes(count);
console.timeEnd("prime generation")
...
3
Template
You can't rename functions; but can you change their signature? i.e.
StreamChecker(vector<string>& words) {
would be better as
StreamChecker(const vector<string> &words) {
Similarly,
void insert(const std::string word) {
should be
void insert(const std::string &word) {
The same for search.
Also, the const in
bool query(...
1
Improvement in function isprime:
for(let i = 2; i <= number / 2; i++)
can be
for(let i = 2; i <= Math.round(Math.sqrt(number)) + 1 ; i++)
Otherwise, the best easy to understand approach(in accordance to my knowledge) is to use the Sieve of Eratosthenes. Your problem can be a subset of the following problem Sieve of Eratosthenes JavaScript ...
0
Quite often with HackerRank puzzles, there will be a check that your algorithm scales to large sizes. Here we are explicitly told that n may be up to 199 999.
You have managed to come up with a homebrew sort that appears to be efficient given the data constraints. However, you are calling it in the outer loop, so your algorithm appears to be O(n^2) overall.
...
5
As explained in another answer, the implementation of the standard library that you use internally passes the comparator by value. It would not have to do that, but you still would have passed it by value to sort, and it is best to avoid that copying altogether. Now, you do not need to change the structure of your program to avoid this.
First, now that you ...
5
The main issue is that the comparator object is passed by value. Not only from your application to std::sort(), but it's also passed by value internally in the implementation of std::sort(). This means that bag and indices get copied by value a lot. So you ideally want to generate those only once, and then have class compare store a pointer or reference to ...
2
Constant members
n and k can be constant, so long as
you remove them from being parameters to crackSafe
you add them as parameters to a constructor
the constructor uses inline initialization syntax, i.e. n(n)
Basically, your two member functions should - in their current form - be bare functions outside of a class, since the class member variables only ...
1
Appending to a string
For this:
std::to_string(row) + "#" + std::to_string(col) + "#" + std::to_string(k);
Check the list of overloads. One of them accepts a character, which you should prefer to using a string.
Const results
This:
inline const int get_distance(...
does not benefit from declaring the return value const. Integers are ...
2
The most expensive operation is the addToKey x that adds x to all keys in map, because substantially you have to create a new entry key, value + x in your hashmap and delete the old entry key, value. To avoid the need of caching the old entry while iterating over the map, you can distinguish two cases:
x > 0, then if you have iterate over a keyset ordered ...
0
The C++ key word inline is pretty much obsolete.1 2 Since at least C++03 inline is a recommendation to the compiler and nothing more. In the LeetCode environment it may help, but most C++ compilers are optimizing compilers and when code is compiled -O3 for maximum optimization the compiler decides what should and should not be inlined and ignores the keyword....
3
You can iterate once over text and short-circuit right away if any character is not unique.
import string
def is_isogram(text):
seen = set()
for char in text:
if (lower := char.lower()) in string.ascii_lowercase:
if lower in seen:
return False
else:
seen.add(lower)
return True
2
I have some suggestions for you.
Extract some of the logic to methods.
In your code, when the query is insert and get, you have two big blocks of code that are similar; you can extract to a method and reuse the method in both sections.
I suggest a method that returns a boolean based on the if condition, so you will be able to set the currValue and currKey ...
1
Your code is difficult to read, there are no comments to explain what the code is doing, or how it’s doing it.
Using typedefs would also add explanations to the purpose of the code.
More verbose variable names would also help, dp doesn’t mean anything.
To me it looks like you have ported the code without understanding what it is doing, which has its place, ...
2
ord()
Do not define constants like ASCII_LOWER_BOUND, use ord('a'). Easy to read, no uncertainty about the value.
character range/set
Do not use an integer range and ord(). It is error prone and hard to review.
if ord(char) in range(ASCII_LOWER_BOUND, ASCII_UPPER_BOUND + 1)
rewrites to
import string
if char in string.ascii_lowercase
No off by one, easy to ...
2
Some remarks
A_DECIMAL and it's use
A_DECIMAL = 65
# [...]
indices = {char: divmod((ord(char) - A_DECIMAL), WIDTH) for char in string.ascii_uppercase}
there is nothing wrong with
ord('A')
which you can use inline without defining a global (which it is not in the required Solution context).
You can even get rid of the ord math by enumerating.
indices = {...
1
Use C++ Container Classes
This code looks too much like C code and not enough like C++ Code.
In the modern day C++, the use of raw pointers such as uint32_t* accumulated = a; are frowned upon, and container classes such as std::array and iterators were developed to reduce the use of raw pointers.
The C style array b is never initialized, and the C style ...
3
Ensure you match the given API
Using size_t for sizes is a good thing to do, however the LeetCode problem specifies the API, and you should not change it. minimumDistance() should return int.
Use static constexpr for compile-time constants
Use static constexpr instead of const for the constants. This allows the compiler to make more optimizations, and they ...
3
Code Review
Your code is a little hard to read.
You should have a blank line after the solution body, to separate it from the mainline code.
This code is hard to describe, document, and debug:
l = map(int, input().split(' '))
print(solution(*l))
What is l? How many arguments are there? If the wrong number of arguments are given as input, the problem doesn'...
4
Use size_t for sizes
Although the LeetCode question specifies that the constructor takes an int capacity, using an int to hold a size is not appropriate for two reasons:
int might not be big enough to handle all possible sizes that fit into the available memory.
int is signed, and now you have to deal with potentially negative numbers.
Also note that the ...
1
I have some suggestions for you, good job on the code!
Always add the empty diamond operator, even if defined in the left-hand side
If you don’t add the diamond, Java will use the old raw types instead of the generic types; those are only kept for compatibility.
Here is a good explanation with more details: https://stackoverflow.com/a/4167148/12511456
Before
...
2
G. Sliepen wrote a rather comprehensive review, I'm going to expand on one point in their review, and add 2 others.
Avoid using namespace std and/or #include <bits/stdc++.h>
I see you forgot to add std:: to some standard library types, implying that you have using namespace std somewhere or are using the non-standard #include <bits/stdc++.h>.
...
4
Avoid unnecessary member variables
You added res and exponent as member variables. However, they are only used inside longestDupSubString() and functions called by it. You should just declare them inside longestDupSubString() instead, and pass them by reference to other functions if necessary. But see below for why these variables might not be necessary at ...
2
The class template provided provides the necessary public interface, anything else should be private rather than public. Therefore the variable int curr_shot_id and the variable std::unordered_map<int, std::vector<pair<int, int>>> id_map; should be declared after private:.
The variable curr_shot_id should be initialized by the constructor ...
3
Seems basically reasonable. Some English nits: You said "nominator and denominator," when the English terms are "numerator and denominator." You also seem to be using the word "evaluate(s)" as a noun (something like "precipitate" in chemistry), when I think the word you meant was more like "value(s)."
struct ...
2
Pass by const reference to prevent copying and modification:
int expressiveWords(std::string const& base_string, std::vector<string> const& words)
^^^^^^ ^^^^^^
bool is_stretchable(std::string const& base_string, std::string const& words)
^^...
1
In the following code, I tried two modifications.
I slightly modified the way tests are performed, in order to minimize them a little bit
I used iterators, like this :auto p_str = base_string.begin() + right;
with the idea to avoid a redirection here:
count_map[*p_str++]--;
instead of
count_map[base_string[right++]]--;
At the end, we cannot be sure how ...
9
Use built-ins
alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
This is a very verbose and error-prone way of getting all of the ASCII lowercase letters.
from string import ascii_lowercase as alpha
will give approximately the same result. It is a string, instead of a ...
3
I think the general algorithm is OK, but you have a lot of repetition in your code! Also avoid writing out the alphabet by hand when you could have Python generate it for you. Here is the code without repetition:
n = int(input('Enter a size: '))
alpha = [chr(ord('a') + i) for i in range(0, 26)]
for k in range(1 - n, n):
j = n - abs(k)
center = '-...
3
Correct me if I am wrong but I think your code in findprimes is checking every number to see if it is a factor and then checking every factor to see if it is prime.
Rather than doing this I suggest you want to find all the prime factors, and then making the list of all factors just comes from all the combinations of prime factors in two subsets.
When you ...
2
I would make a few suggestions, rather than just saving the input string it would be better, as you suggest, to save the output of the get_rows function in memory, so you don't have to recreate it every time.
Similarly when you want an individual row or column, it seems inefficient to gather all the rows, (and then all the columns) just to reject all but one ...
1
I have some suggestions.
Extract some of the logic to methods.
In your code, I see at least three sections of code that could be in methods. In my opinion, those extraction will help with the reading and make the code a bit shorter.
The validation of the parameters.
Before
if (string == null || target == null || string.length() == 0 || target.length() == 0 ...
1
First off I think your code can be adjusted:
Booleans to keep track of even or odd size of matrix and even or odd numbered rows allows you to use one set of loops and simply change which set of numbers are printed.
To test for odd or even I like (num & 1) if the result is 0 it's even, 1 it's odd. I think using modulus for this is inefficient.
Changing ...
3
I'm not sure if online courses even go into this, but this is the exact opposite of what good code should look like. Unless there is a dire performance requirement (which is rarer than you think) the aim is always to make your code as readable (clear/stupid/simple) as possible, so that:
Errors have fewer places to hide
It is easier to reason about what the ...
1
I'll comment on C style:
#define BUF_SIZE (1 << 10) // approx 2 KiB or 1024 chars
```n
This comment makes no sense. A `char` in C is, by definition, 1 byte. `1 << 10` bytes is exactly 1024 `char`s. I suppose I can understand if you're coming from Java where `char` is a UTF-16 code unit.
```c
char* next_token() {
char* buf = malloc(...
Top 50 recent answers are included
