New answers tagged algorithm
0
Could you do it without extra space and in \$O(n)\$ runtime?
The implementation uses \$O(n)\$ extra space.
A different approach is possible without extra space,
by rearranging the content of the input array,
so that the values that appear ordered, and at the position where they would be if nothing was missing.
Going with the example [4,3,2,7,8,2,3,1], the ...
1
# Uses python3
I don't see much to argue against documenting this instead with a hashbang:
#!/usr/bin/python3
Sure, on Windows that path won't work, but on many other platforms it will.
n, m = [int(x) for x in input().split()]
...
print (fib(n))
It is generally considered best practice to use
if __name__ == "__main__":
...
as a guard around "...
3
Never indent as you have done. This make code very unreadable due to the long lines.
Map.values() creates an iteratable object. It does not require an array to be created and is \$O(1)\$ storage as it iterates over the already stored values
You have forced the map to be stored as an array. Array.from(map.values()) That means that it must be iterated and ...
2
You have created a good solution, just a few style points that can reduce code size.
Why null rather than false or even 0 in arr[x - 1] = null;
Why not use commas to remove need for return. Eg .reduce((arr, x) => {arr[x - 1] = null; return arr; } becomes .reduce((arr, x) => (arr[x - 1] = null, arr))
To create an array of indexes you could have used ...
1
Your solution looks rather map-happy.
It is important to remember for this task that counting higher than 2 of any encountered is needless processing.
Also, doing a complete sweep of the input string may be ill-advised if the input string is of considerable length.
Due to not being as well across .js like others here are, I'll post a humble for loop.
...
1
Code organisation
Le's write your function in such a way that it is easier to test. First step is to provide m as a parameter. Also, we can take this chance to write a proper docstring for the function. We get something like:
def fib(n, m):
"""Compute Fibonnaci(n) % m."""
a = [0, 1]
if (n <=1):
ret = n
else:
for i in ...
3
Objects should be making the code easier to read. The Object you name position provides no behavioral benefit and serves only to bloat the code.
You should be using good old for loops for this rather than the hacky way you use the array iteration function forEach
Use function declarations function islandPerimeter(grid). Do not use function expressions var ...
4
Sorry, I am giving no code (I am on a phone and I don't know Python), but be aware that if m^2 is way lower than n, you could use the fact that your function gets periodical with a period maximally m^2 (as both a[-1] and a[-2] can gain m different values).
You could test in your for loop if/when you reached your period (if a[-2]==0 and a[-1]==1) and if so, ...
3
The 99th percentile is due to the linear nature of your approach. The goal of this exercise is to figure out a logarithmic one.
I don't want to spell out the algorithm entirely. Just a hint to get you started. Take a middle element of nums1. Find its lower bound in nums2; call it i2. In the sorted array the selected element would be at the position nums1....
1
This problem fits as a temporal problem that requires you to find overlaps between date ranges. SQL is optimized for such problems. But I'm sure it can be done without too much performance loss in managed code.
Should your algorithm take each year as its base unit or just take
into account the relevant date time ranges?
I would favour the latter (...
5
Since you're asking about readability, let's take a look at that.
Your functions and variables could be named better. Especially parts like this:
static final void digitsPlus(Digit sourceDigits,
Digit targetDigits,
int radix) {
Digit sourceDigit = sourceDigits;
Digit targetDigit = ...
2
How well/bad is this code written?
A good first timer implementation.
Is the code abstract enough?
Mostly. It does make unnecessary assumptions about range. It assumes int math does not overflow.
To make more abstract, code could use typedef int TVS_int; to ease future type changes.
How can you solve such challenges more quickly?
Take advantage ...
3
I'd just use string manipulation on this, with a simple conditional for the edge cases.
var reverse = n => {
const s = parseInt([..."" + n].reverse().join(""));
return s >= 2 ** 31 ? 0 : Math.sign(n) * s;
};
The approach is to stringify the number, arrayify the string, reverse it, re-join the array into a string and finally parse the reversed ...
4
I don't know what you mean by declarative in this case. All these functions are pure (except the console.log), but the implementations of the functions are all imperative (which is fine of course)
When adding to a set, you don't need to check if the key exists first. Just add it.
Splitting the string into an array of chars isn't necessary. You can use string ...
2
Do not map to array
I appreciate that streaming strings is a little messy. However, there is no need to create an array; instead we can just transform the stream. I would remove the arrays and change getFrequencyMap to take a String.
Use Map::getOrDefault to simplify countError
In particular, if you do aMap.getOrDefault(ch, 0) then the Math.abs case ...
3
Looking at your code for style
#include <stdio.h>
#include <string.h>
// array of strings for testing
These strings should be char const * unless you really want them to be altered
char *strs[] = {
You have the 'aperiodic comment twice here, which confuses me somewhat. If this is a section of aperiodic strings, why do you need the 2nd ...
3
Instead of looking for cool new features of Java i would strongly suggest that you concentrate on the basics of Java: Objects:
Think in Objects:
So far you have identified these Objects: Map, a Cell and an Island - so make some Objects of that type.
Map map = new Map(int[][] src);
Island island = map.extractIsland();
int diameter = island.getPerimater();
...
1
Storing properties of grid, which is a method parameter, into instance fields m and n, is bad practise. Now the reader has to wonder why their scope is exposed outside the method. M and n should stay in the same scope (they should be method variables).
M and n are bad names for width and height. There's nothing wrong with width and height and these would ...
1
Your implementation, to me at least, doesn't seem correct. You need to remove adjacent duplicates, but looking at your last example, the sequence acaaabbacdddd completely removes the b and d characters from the slice. You're also using an awful lot of code to do a simple thing. What I'd do is quite simply this:
Iterate over the slice from index 0 to the ...
2
As the comment says on the less-obfuscated version on Rosetta Code, their implementation is based on the Extended Euclidean Algorithm. Your implementation works by brute force to test every element in the field, so of course it's going to be slow.
6
The question states that the input is a number 32 signed int so checking for undefined or null is a waste of time.
The solution is a little long. Some of it due to not being familiar with some old school short cuts.
To get the sign of a number use Math.sign
-JavaScript numbers are doubles but when you use bitwise operations on them they are converted to ...
2
Good attempt, but unfortunately the nested loop brings the time complexity to O(n2). Keep in mind that .find performs a linear search on the vector, inspecting up to the entire array to find an element. We can arrive at a O(n) solution by exploiting the fact that no more than 2 swaps can be performed by any given element, which is a red flag in the problem ...
1
Overview
Terrible C++ but OK C.
Modern C++ has a completely different style when used to what you have written here. Though perfectly legal C++ this is not what you would expect to see and this makes it harder to maintain and implement.
Improvements
You tightly bind your interface to a specific implementation (an Array of Arrays of distance). You should ...
1
The answer by ggorlen covers most of the points and the alternative that was presented is very efficient, well sort of. In terms of complexity it is less complex and that shows when you compare your function.
If we use your algorithm and clean up some of the nasty bits, we get.
function longestSubstr(str) {
var res = 0, tmp = [];
for (const char ...
2
Style
Nice usage of arrow functions and spread operators. You can extend this to the function name as well:
const lengthOfLongestSubstring = s => { ... };
The code switches between two and four spaces within a block and between blocks. Choose one and stick with it throughout the entire program (the auto-formatter built into Stack Exchange does the job ...
3
Wow that is a lot of code to add two numbers.
Potential bug
The function ListNode has one argument yet in the function addTwoNumbers you call it with two arguments. However it does not manifest as a bug as you add the link in the lines following the node creation.
This also results in you creating twice as many nodes as needed.
E.G the second node is ...
3
There are few ways to simplify the code. First, to deal with rollover you don't need to convert a number to string and back.
if (k > 9) {
rollover = 1;
k -= 10;
}
looks more natural.
Second, the isFirst logic is rather convoluted. A standard technique is to initialize the resulting list with the dummy head, and not worry about ...
2
I think you're over-complicating the problem -- you need to think of a different approach.
Here's an algorithm: consider the first digit in the linked list. Add it to the "running total." If there's another number in the list, multiply it by 10*(number count) and add it to the running total. Keep going until you run out of new numbers.
Think of it this ...
5
Advice 1: l_moves
The name l_moves is ain't good at all. Consider numberOfMoves.
Since it is only read, make it a constant. Even better, it is customary in Java to name the constants with capital case. For this particular case, I suggest you rename l_moves
private static final int NUMBER_OF_MOVES = 4;
Advice 2: class SlidingPuzzle
I suggest you rename it ...
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 ...
2
Opportunities missed
You have essentially the same algorithm in both examples. When I first looked at the solutions the sort at the start was a worry. The logic is sound, to work from the smallest word as there will be no more characters to test then is contained in that word.
However you have the sort AoT and the result is you set first to be the longest ...
3
The <iostream> header is not used.
min_distance can theoretically return an uninitialized value if all elements of visited_set are nonzero. This shouldn't happen here, but initializing min_index = 0 would remove a potential problem and compiler warning.
display assumes that node 0 is the start node, but that value is passed in to dijkstra. It ...
1
How can I make [the code presented] better
Give Test First a try.
Document your source code, in the source code: what is the goal of "any" given piece? ("The This function returns the higest number comments" are a step in the right direction. (Your IDE doesn't check spelling?))
Be consistent. (In addition to a double blank,) There is an irritating ...
-1
I just saw my error now
function lowestAndHighest(arr) {
this.lowest = arr[0];//corrected
this.highest = arr[0];//corrected
//This function returns the lowest number
this.lowestNum = () => {
arr.forEach(elem => {
if(this.lowest > elem) {
return this.lowest = elem;
}
});...
5
At the end of their answer, @AJNeufeld has the right idea to improve the algorithm even further (in pure Python). You want to minimize the amount of numbers you have to mark off as being composite for every new prime you find. In order to do this, you can actually start at current_prime * current_prime, since you should already have marked up all smaller ...
5
AlexV has made some great points. I’ll try not to duplicate them.
while numbers[current_prime] <= sqrt_limit:
This seems like odd code. numbers[x] == x is true, or numbers[x] == -1 is true. You should save the indirect lookup in the numbers array, and just loop:
while current_prime <= sqrt_limit:
You take great pains to explain in a comment that ...
4
Big \$O\$
Time complexity is a ratio of some input metric (e.g. the number of character in the string) to the number of instructions required to complete the function.
In this case the metric \$n\$ is the string length. The first loop that uses String.match must for each character check all characters to find a count. That means at least \$n * n\$ steps ...
8
Four* letters to rule them all
The Sieve of Eratosthenes is an algorithm which heavily relies on loops. Unfortunately, Python's convenient scripty nature comes at a cost: it's not terribly fast when it comes to loops, so it's best to avoid them.
However, this is not always possible, or one, like me in this case, is not so much into algorithms to transform ...
1
Some points
Put magic numbers in constants to give them meaning.
Variables that do not change should be defined as constants
Use appropriate Array functions rather than iterating over the array.
Math.round only takes one argument. I do not know why you pass 2 as a second argument. If I guess you want to round to 2 decimal places. To do that you can use ...
2
Avoid magic numbers. That's 0.3048 and 0.82. When another developer comes in and looks at the code, they won't know what those numbers are. Put them in variables that are named accordingly.
You converted height into meters, which implies that height isn't in meters. What unit does it come in? Is it some other metric unit or is it another unit? You didn't ...
3
bug
You don't reset the offset when there is a mismatch, so "123 easy as b(" also returns True. Just add:
else:
offset = 0
optional parameter offset
The caller of the function should not care about the offset if he wants to check whether a combination is part of the string. I would change the method signature to def find_mutated_string2(...
2
There is one fairly obvious optimization that should cut your time in roughly half. Pascal's Triangle is symmetric. Take advantage of that with whatever algorithm you are using. Roughly speaking (without checking my end-conditions so do that):
for (j=1;j<i/2;j++)
{
value = matrix[i-1][j-1] + matrix[i-1][j];
matrix[i][j] = matrix[i][i-j] = value;
if ...
3
Your code looks quite good already. However there are a few details to improve:
1) There is Array.includes which will abstract away the for loop, making the code more concise.
2) You use bmiTotal and BMI, although both mean the same.
const countriesWithLowerBIP = ["Chad", "Sierra Leone", "Mali", "Gambia", "Uganda", "Ghana", "Senegal", "Somalia", "Ivory ...
3
One array solution
The following algorithm is an improvement on the two array system stated bellow it. Basically, we only need the context of the old previous value (as well as the next value, which goes unmodified), so we copy this value. From there we can set the new end to 1 then start over. This cuts down on the memory overhead. I think you'll see ...
0
I have two comments:
regarding DRYness: this is how I would do it: I see that rotation involves assigning values to 8 cells in the 3d array. I would have rotate() calculate the source and target indices of the rotation based on args. then the actual assignment can be performed in one place. now, when you put all index-calculations in one place, you start ...
2
Check each unique sub string once
I agree with the existing answer, however there is a faster way to solve the problem, there is also an early exit possible that many of the challenges will test for.
The early exit can be found by finding out if there are any two characters that are the same. If not then there are no anagrams that are longer than 1 ...
1
You can often replace switch statements with lookup functions. For example
function returnsHome(moves) {
var v = 0, h = 0;
const dirs = {
U() {v++},
D() {v--},
L() {h--},
R() {h++}
};
for (const move of moves) { dirs[move]() }
return !(h || v);
}
// or
function returnsHome(moves) {
var v = 0, h =...
3
Your code does indeed run forever. Regrettably you don't describe the method you're using, so I will have to get that from your code.
You start by getting all possible substring, of all possible sizes, out of the given input string and you store those substrings, its letters and position in an array.
You do a full matrix comparison of each array entry. You ...
2
It could be made more functional by avoiding the mutation of acc. The effects are contained within judgeCircle so it's not a big deal, but it feels like if you're going to mutate the accumulator, you might as well just use an imperative loop.
I also preferred to be explicit about the final check. I find the intent of !h && !v isn't quite as clear as ...
Top 50 recent answers are included
