New answers tagged algorithm
1
I really don't recommend trying to write anything that is more complicated than necessary during an interview, especially if it's on a whiteboard. Interviews are stressful enough for you; introducing more opportunities for errors is not a good idea. As for the interviewer, their likely thoughts are that your code lacks elegance and is hard to verify.
In ...
-1
The code should work fine once the issues mentioned by @alexwlchan are fixed, I added those changes and code looks like this:
def peakfinder(arr):
if len(arr) == 0: # If list is 0, there is no peak.
return None
if len(arr) == 1: # If list has been reduced to 1 element, it's a peak.
return arr[0]
if len(arr) == 2:
if arr[...
2
depth
From the snippets posted here I have a feeling that you didn't really know where to place the depth information. You're passing it as a parameter to the makePlyImpl method but then never use it. Instead you're checking state.getDepth() but that's only set before calling the method, and I don't see it updating the depth on all it's children.
As I ...
4
"""DocStrings"""
+1 for adding a doc string to the wordBreak() method, but -1 for not having any content in it.
PEP-008
Your code diverges from the PEP-008 guidelines in several areas:
Use snake_case for functions and variables, not mixedCase.
Use a single space around operators (elif i > len(s):), not 2 spaces, and then no spaces.
Add a blank line ...
0
This task can be accomplished using a regular expression.
As an example, for the input wordDict = ["apple", "pen"], one can build a regular expression r"(apple|pen)+", and then match it against the entire input string "applepenapple" (use re.fullmatch, not re.match). The underlying algorithm for regular expression matching is based on a finite automata and ...
10
On the logic, you should notice that the next state of the i'th house becomes
state[i - 1] ^ state[i + 1]
(some care at the boundaries to be exercised). Upon the closer inspection you may also notice that if you represent the state of the entire block as an integer composed of bits from each house, then
state = (state << 1) ^ (state >> 1)
is ...
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 ...
5
Enumerate
Instead of writing range(len()), consider using enumerate. It provides the index and the value associated with that index. It's useful in your case because, instead of having to write in_states[i], you can write value instead. This will save you from having to index the list again with in_states[i].
Docstrings
You should provide a docstring at ...
2
Alternatives
There are other alternatives (spoiler alert) with around the same time complexity, that adhere to the specification of in-place removal.
Review
This is in \$O(n)\$.
I'm not sure it is. The outer iteration while (node = node.next) is \$O(n)\$.
while (node = node.next)
h[node.data] += 1
if h[node.data] > 1
previous_node = ...
5
General remarks
This
using namespace std;
is considered bad practice, see for example Why is “using namespace std” considered bad practice? on Stack Overflow.
Consistent indenting and spacing increases the legibility of the code.
Use curly braces for if/else blocks even if they consist only of a single statement.
Enable all compiler warnings and fix ...
4
Adding to the other reviews, here are a few more points.
Outside-class Functions vs. Methods
Here is a long discussion about function and methods. In general, if a function operates only on instances of a class (including its subclasses), it should be a method of that class. In your program, most of the functionality of the three functions decToBase, ...
3
def decToBase(n: int, b: int) -> list:
def baseToDec(n: list, b: int) -> int:
These names reflect a common misconception. int is not inherently decimal. If any named base were appropriate, it would be bin for binary. But it's far more sensible to think of int as being int: either call them int to base and base to int or, IMO better, base compose and ...
9
Combine division and modulus
Use https://docs.python.org/3/library/functions.html#divmod
rather than this:
digits.append(int(n % b))
n //= b
Replace loop with sum
This
res = 0
for index, i in enumerate(reversed(n)):
res += int(i) * b ** index
return res
is a good candidate for conversion to a generator, i.e.
return sum(int(i) * b**index ...
3
Overall your implementation is fine, I would just suggest a few things:
Naming - move_rings and helper are not very descriptive. Give them better names, and give them good docstrings (I like NumpyDoc, but personal preference is fine)
move_rings shouldn't both do calculations and print to stdout. Instead, move_rings should return the information, and the ...
6
Review
This review may sound a bit harsh, but bad habits are hard to break so I point them out.
Use constants for variables that do not change.
Don't create single use variables if they do not improve readability.
Don't test for equality / inequality when the statement expression evaluates to a boolean. eg if(str.includes(target) === true){ is the same as ...
2
The solution makes sense, but like @dfhwze said, there are too many variables.
As a future maintainer, I skim your solution and wonder what subtractLengths is, because it's ambiguous unless you move your eyes up to read more code to get the context. It doesn't read very smoothly.
I would re-arrange it a bit to read more like this:
str.lastIndexOf(target) +...
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....
8
Review
You have a bit too many variables to my taste, but that's not much of a problem.
let lengthOfString = str.length; // is a variable that useful here?
I would use const instead of let because the variables are only set once.
The if-statements could be written with much less overhead.
First,
str.includes(target) === true
could be written as
str....
2
A few more points:
The precision of the decimal context is set at the top-level of the code, while the result of computation is rounded within the two methods. That is not good because in this case the methods actually have no knowledge about how the precision is adjusted based on user input. These two operations should be handled on the same level: either ...
13
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 ...
1
Without even doing anything clever regarding the algorithm, this:
new_count = count + sum(stones[start:start + k])
merged_count = sum(stones[start:start + k])
can be cleaned up as
merged_count = sum(stones[start:start + k])
new_count = merged_count + count
7
The algorithm provided by the OP presumes that the array is important and preserves the original array. In addition, the displayed algorithm seeks an "instantaneous answer", as if the routine may be interrogated at any point to get that answer at the point in time.
All that is important here is the output - a single number. Any other information used to ...
2
Unnecessary else after return
In the body of an if, if you end up returning something in that body, an else is not required. A return will exit the body of the function, so the code in the else won't be run. So, you can simply move the code in the else to the outside, after the if. This may have been confusing, but take a look at the updated code to see ...
1
As mentioned in the comments, you can check the Manacher's algorithm. Here's the link for python code of the algorithm: https://zkf85.github.io/2019/03/26/leetcode-005-longest-palindrome#approach-5-manachers-algorithm-on
This is the solution mentioned on the above link in python:
class Solution5:
def longestPalindrome(self, s: str) -> str:
N = len(s)...
5
Better complexity can be achieved using a heap. The input array can be organized into a min-heap in \$O(n)\$ time with negative integers dropped. Then the smallest number can be popped one by one until the target number is found. The complexity of this algorithm is \$O(n + klogn)\$ where \$k\$ is the insertion index of the target number among the sorted ...
8
I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere).
As was mentioned in the comments, for your purpose, there is no significant difference in performance between ...
1
Maybe the code is time efficient because you are lucky. Maybe the code is time efficient because you have good intuitions. This review is about moving toward luck playing less of a role in the performance of your code and/or reaching good intuitive conclusions by a more formal path.
Top Down
The code seems to be written bottom up from loops rather than top ...
3
Type hints
Presumably all of the argument to calculate_distance, as well as the return value, are float. You should indicate so with PEP484 type hints.
List literal unpacking
row = [" "] * 40
row[0] = "#"
row[-1] = "#"
can be
row = ['#', *[' ']*38, '#']
Magic numbers
Assign 40 to something like GRID_SIZE. Rather than 38, write GRID_SIZE - ...
2
Docstrings
You should include a docstring at the beginning of every function, class, and module you write. This will allow documentation to determine what your code is supposed to do.7
Variable Naming
Here is a list of variables/parameters that I would change. This increases readability, and makes the variables easier to understand.
input_str -> ...
2
Precision
1 <= M <= N <= 1,000,000,000 implies a need for 30 bit of precision. (log21,000,000,000 --> 29.897...)
float usually has 24 bits of precision (23 explicitly encoded, 1 implied).
Code as below can readily lose precision when converting from int to float for values of N > 224.
float halfPrice = N;
float sum = halfPrice;
double ...
3
Your approach is working too hard. The inner loop does K iterations (with could be as large as 1,000,000,000), and most of them are redundant: as soon as halfPrice goes beyond M it will stay beyond M for the rest of the loop. Notice that in the worst case (N = 1,000,000,000, and M = 1) you'll need just 30 iteration to reach M. So, something along the lines ...
3
Formatting
This may be a copy and paste error, but generally int main() will start in the first column like the #include does. Other the rest of the indentation needs to be based on that. This was correctly done in your earlier question.
#include <stdio.h>
int main()
{
int T;
scanf("%d", &T);
...
}
Functions
You may not have run ...
10
If your code is checked by an automated process, you will probably fail all test cases because your code prints a #, which was not asked for. You should better remove it. Just print "Case %d" instead of "Case #%d".
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 ...
2
Review
Since you are building the array yourself, as opposed to you get a source array from a consumer of your method, I don't think you should create a new array, but rather just adapt the source array. This way, you could avoid slice and concat altogether.
The number of rotations is an integer. However, reading the description behind the link tells use it'...
2
The linearity of your approach is due to the fact that your longest could never be longer than the size of the alphabet (otherwise it'd have a duplicate for sure). It means that your code runs at \$O(N * A)\$, where \$N\$ is a length of the string, and \$A\$ is a size of alphabet. Since the latter is a constant, you may safely take it out of the big-O, ...
2
List objects are iterables. A for loop implicitly calls iter() on the list, but you can do it yourself, too.
nums_iter = iter(nums)
num0 = next(nums_iter)
for num in nums_iter:
# ...
The list is not copied, and the for loop will begin with the second item, as required.
However, this is far less clear than for num in nums[1:]:
Much clearer is to ...
2
for num in nums[1:] is the prefered way to iterate over a partition of an array; if you are worried about performance, it actually is faster, because accessing by index is more expensive in python than copying then iterating values (you can play with snippets of timeit to verify that claim, but I'm fairly sure of that - accessing by index in python involves ...
4
Other developer-oriented issues such as variable namings, documenting, commenting, and such are not really a concern here since it's just for practicing algorithm and data structures, and have to follow the tutorial as much as possible.
I feel this is a bad idea, this is as it promotes detrimental core habits.
Myself and a friend used to play a purely ...
1
Note: your code doesn't currently compile for at least two reasons: you are not telling the compiler cout and endl live in the std namespace, and you can't declare your arrays start and end because n is not known at compile-time (instead, you'd have to use dynamic memory allocations).
In any case, your code smells like your background might be in C (but ...
1
use a recursive function
I guess avoiding the stack-juggling (because of the recursivity of fromRPN) and the unnecessary creation of String objects (with StringJoiner) should make it fast enough.
fromRPN( new ArrayList<String>( Arrays.asList( "1 3 + 2 4 5 - +".split( " " ) ) ) ); // ((1+3)/(2+(4-5)))
public String fromRPN( ArrayList<String> ...
3
"""
Module Docstring
This is a simple object-oriented implementation of merging two Single Linked Lists with some associated methods,
such as bubble sorting, create list, and such.
"""
The line Module Docstring is probably a placeholder which you're meant to remove, but it's good to see that the methods are documented.
def create_list(self):
...
1
edges: [
['0', '4'],
['1', '2'],
['1', '3'],
['1', '4'],
['2', '3'],
['3', '4'],
['3', '3'],
['0', '1'],
['1', '2'],
['2', '0'],
]
is not an adjacency list representation. That would be
edges: {
'0': ['1', '4'],
'1': ['2', '2', '3', '4'],
'2': ['0', '3'],
'3': ['4', '3'],
'4': []
}
vertices is ...
2
Strictly speaking, the list of vertices is not neccessary because the adjacency list already contains all (connected) vertices and disconnected ones can be represented as [x, null]. If you prefer to keep vertices, you'll have to synchronize them with edges:
in removeVertex you not only remove the vertex but also all edges connected to it
in addEdge you add ...
5
I don't like this:
do
{
printf("Card number: ");
scanf("%lld", &no);
}
while(no<10);
That blank line makes it look like the while (); is a separate (possibly infinite) loop. I recommend writing the while keyword straight after the closing brace, like this:
do {
printf("Card number: ");
} while (scanf("%lld", &no) != 1);
(I've ...
3
d_16 = no%10;
d_15 = ((no%100)/10)*2;
d_14 = (no%1000)/100;
d_13 = ((no%10000)/1000)*2;
d_12 = (no%100000)/10000;
d_11 = ((no%1000000)/100000)*2;
d_10 = (no%10000000)/1000000;
d_9 = ((no%100000000)/10000000)*2;
d_8 = (no%1000000000)/100000000;
d_7 = ((no%10000000000)/1000000000)*2;
d_6 = (no%100000000000)/10000000000;
d_5 = ((no%1000000000000)/100000000000)*...
2
Docstrings
You should have a docstring at the beginning of every module, class, and method you write. This will allow documentation to identify what your code is supposed to do. You're on the right track, having comments above the classes and methods. Now, just move those comments inside these classes and methods at the very beginning, inside triple quote ...
2
Lets move above JavaScript 101
To OP, I first must address the quality of some parts of some of the given answers that concern me.
I am continually shocked at the misunderstanding of JavaScript here in Code Review, Sorry if I rub some the wrong way but please, we are professionals and our answers should reflect that fact.
Issues
The naming critique is ...
3
Even after using reserve, as suggested by @L.F. and @AJNeufeld, there was no considerable speedup and it was still timing out. So I decided to use dynamically allocated arrays instead. I also removed using namespace std, and instead only imported those std functions which are required in the program.
#include <iostream>
#include <vector>
#...
1
This bit of your code that is trying to vectorize text into count vector
doc2_words = word_processor(document2)
doc1_word_freq = {i: doc1_words.count(i)
for i in doc1_words} # the doc1 vector
doc2_word_freq = {i: doc2_words.count(i)
for i in doc2_words} # the doc2 vector
can be replaced by scikit-learn's CountVectorizer
...
Top 50 recent answers are included
