New answers tagged algorithm
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 ...
6
The code is slow on larger arrays because of the nested for loops. The number of times the inner loop runs depends on the length of the array. The outer loop runs arr_len times and the inner loop runs arr_len/2 times on average. As a result the code in the loop runs arr_len**2 / 2. If the size of the array doubles, the amount of work the code does quadruples....
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, ...
0
// Both s_weights and s_values will have the same length.
private static int[] s_weights; // array holding the weights of the items.
private static int[] s_values; // array holding the values of the items.
private static Dictionary<(int, int), long> s_memo; // memoization dictionary.
// NOTE: I cannot use an array instead of a dictionary here, cause ...
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 ...
4
Seems like you already incorporated a few of the suggestions from back when this was on StackOverflow, e.g. changing the inner loop to max. However, you do so in a very inefficient way:
you create a slice of the list, O(n) time and space
you get the max of that slice, O(n) time
you get the index of that element, O(n) time
Instead, you can get the max of ...
1
Instead of storing the actual values in a tuple as the key in a dictionary for memoisation, multiplex them together into a single value and use that as the key. You will need to pick multiplex value that is an order of magnitude higher than the largest "numberOfItemsToConsider" you can expect. Or you could turn them into strings and concat for the ...
8
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 ...
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'...
2
To address your immediate concerns,
Using the return stack for storing your temporaries is a perfectly valid technique.
pick is always frown upon (as well as tuck, roll, and friends). It seems that the len parameter to bubblesort does not participate in computation - except the very beginning - and mostly just stays in the way. Consider
: bubblesort
...
2
Functions
For many reasons, you should attempt to move your global code into functions. Reasons include testability, meaningful stack traces, and de-cluttering the global namespace.
User input
This prompt:
input("Input set of integers for S : ")
is missing a description to the user that they should be entering a comma-delimited list.
This input:
...
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(...
2
For an interview, this is bad code. It is \$O(n \log n)\$. But it can be done in \$O(n)\$ time. Your code does not show your skills in that direction. Also, many interviewers (justifiably) will be unhappy for using streams. Streams may look cute but at scale like Gmail, they cause performance problems.
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 ...
2
Indentation
The standard indentation style in Ruby is two spaces, not four.
Single-quoted strings
If you don't use string interpolation, it is helpful if you use single quotes for your strings. That way, it is immediately obvious that no string interpolation is taking place.
Frozen string literals
Immutable data structures and purely functional code are ...
3
public int? Value { get; }
I really can't think of any situation where I would vant to store a null value in a search tree. But maybe I'm too narrow minded? What should the point be?
It is by the way impossible to set the value to null, because it is readonly and the only constructor takes not an int? but an int. So how would one could set a null value? And ...
4
You can tremendously reduce the memory requirements of this code by acknowledging that you can replace the lists you use by single values:
private static bool IsBinarySearchTree(Node root, int max, int min)
this allows you to successively tighten the bounds on subtrees without storing the values you traversed in a list:
public static bool IsBinarySearchTree(...
0
I think there is no need to create a new list for every recursive step.
The main logic is whenever the current node is left side of its parent then:
its (current node) left child value <= current node value
its (current node) right child value >= current node value and less than the value of the current node's parent
And the logic is exactly reverse ...
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
Constant parameters
parser::tokenize(string expr){
would be better off as
parser::tokenize(const string &expr) {
Similarly for pre_process_trig_and_constants, which should use an intermediate variable for the reassignment statements in that function.
Encapsulation
toks_and_ops res ={toks,ops};
Rather than structures that don't know how to initialize ...
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....
2
The code you have there may accomplish the task you have in mind for it, but it's not useful for a "real world" usecase.
That's because usually you'd want to be able to run an algorithm like this multiple times on the same graph, maybe even concurrently.
The problem that's posing itself here is that Node mixes two concerns: Representing the graph ...
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
Use standard array notation
When you are accessing array elements, the idiomatic way in C is to write foo[bar] instead of *(foo + bar). So instead of:
int next_number = *((i * rows + arr) + col);
Write:
int next_number = arr[i * rows + col];
It is both shorted, and now it is clear what part the array pointer is and what part the index is.
Avoid unnecessary ...
3
Algorithm
You do a nested loop which is completely without reason
for mult1 in range(100):
for mult2 in range(100):
# find all multiples of mult1 and mult2 that can be factored
# into all numbers in a, while ignoring zero.
if all(v == 0 for v in [(mult1 * mult2) % factor for factor in input_factors]) and (mult1 * mult2 != 0):
...
2
Instead of writing a nested for loop, directly write it as a list comprehension. In addition, you can start the second loop at the value of the outer variable in order to remove some double counting. This reduces the numbers to iterate over from 9801 to 4950, by a factor two, since you don't have both e.g. 2 * 6 and 6 * 2. However, some values still appear ...
6
Redundant calculations
You calculate mult1 * mult2 three times. Instead, do this once, assign it to a variable, and use that.
Since you want to never want to calculate when a value is 0, you can set the start of range to 1.
range(1, 101) # 1 -> 100, since (inclusive, exclusive)
Now you can remove that (product != 0) check.
Type hints
At first, it looks ...
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 ...
4
Symbolic Constants
It is good that you named these numeric constants, but they are constants so rather than declare them as variables, declare them as constants.
static void Main(string[] args)
{
const int n = 5; //nodes
const int m = 100; //size of square
const int mm = 999; //maximum cost
...
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
...
1
I have some suggestions to make the code cleaner, not faster.
Always try to pass the size of the maximum size to the Collection / Map when known
The ArrayList has a default size of 10 elements, if you have more elements, the list will have to resize its internal pool. By setting the size, you can prevent the resize and make your code faster.
//[...]
int ...
3
Compilation Error
The first problem is to solve the compiling error.
Just follow the interface:
public Node<Integer> mergeAscend(Node<Integer> a, Node<Integer> b)
Warnings and Code convention
You should add the type information to the store_next_a_node variable (and store_next_b_node). Additionally, in Java naming conversion, variable ...
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 ...
-1
Using while loops
s = "azcbobobegghakl"
c = s[0]
b = s[0]
n = 0
while n != len(s) -1:
if s[n] <= s[n+1]:
n+= 1
c += s[n:n+1]
if len(c) > len(b):
b = c
else:
n += 1
c = s[n]
print("Longest substring in alphabetical order is: " + b)
7
I don't think exposing the Node class is useful. It should probably be mostly an internal class within your class (or at least package/namespace)
Node could be using generics, so Node<T> instead of always having an int
At least some of your AddNode-methods could simply be called Add instead. Because they're actually adding a number, a list of numbers, ...
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 ...
0
All of the endpoints are redundant. If anyone can add anything else I'd still appreciate it.
#include <stdio.h>
void matrix_addition_partition(size_t n, size_t m, int A[m][m], int B[m][m], int C[n][n], size_t start, size_t end) {
for(size_t i = 0; i < m; ++i) {
for(size_t j = 0; j < m; ++j) {
C[i+start][j+end] = A[i][j] + ...
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 ...
0
As it happens, there is already an implementation of Karatsuba multiplication in the implementation of BigInteger. Of course that's integer multiplication instead of polynomial multiplication, but they're very similar, apart from how they handle carries. You can read the source here, look for multiplyKaratsuba. It's more of a high-level implementation, ...
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 ...
2
String traversal
At several places in your code you convert a string to an array of its characters in order to iterate over it:
let letters = Array(word)
for letter in letters {
// ...
}
These intermediate arrays are not needed. A Swift string is a collection of characters, so that you can iterate over it simply with
for letter in word {
// ...
}
...
Top 50 recent answers are included
