New answers tagged algorithm
0
Algorithm
One optimization in terms of space complexity would be to store the names in a separate array and use a simpler data type for the permutations (e.g. integer - could be indexes of the array).
I also see this block within the compute method:
$i=0;
$total = 0;
$n = count($this->locations)-1;
foreach ($perms as $...
0
Since jwvh already has a great solution to your problem, I'll point out a few things in your original code.
One thing that immediately caught my eye was the use of Breaks.break(). This does not work the same as in Java. It throws a BreakControl exception that can stop your program if not caught by the breakable block encasing your while loop. Throwing and ...
-1
Consider 2 Pointers low and high are keep moving towards center direction ultimately x == value will be centered
int x = 10;
Integer[] intList = new Integer[] {9, 12, 3, 5, 14, 17, 10, 10};
int pointlow=0, pointhigh = intList.length-1;
Integer arr[] = new Integer[intList.length];
for(int i=0; i<= intList....
2
The signum function returns -1, 0, 1 if the argument is negative, zero, or positive.
int original_diff = signum(to-from);
When signum(to-current) is diferent, we know the relationship changed, regardless of which direction you were going.
if (original_diff == 0) return; //do nothing
for (int current= from; signum(to-current) != original_diff; current += ...
2
The only difference is the </> which swaps on multiplication by a negative factor:
x < y <=> -x > -y. An ugly use would be:
for (int i = from; signum(step)*i < signum(step)*to; i += step) {
for (int i = from; signum(i - to) == signum(step); i += step) {
for (int i = from; (i - to)*signum(step) < 0; i += step) {
for (...
4
I think the easiest way to solve this is to first calculate how many steps it takes to go from from to to, and then just build an array of that many elements. That also has the advantage that you can reserve the right amount of elements in the vector up front. You also have to make sure that step has the correct sign.
if (from <= to != step > 0)
...
0
This one might be faster reducing allocations amount.
Also some naming issues were fixed.
// avoid using fields where possible, it makes the code portable and reusable
public void MainAlgorithm(List<double[]> xs, List<double[]> ys)
{
//this line replaces GetSmallestArray method, Linq is fine here while xs.Count isn't a large number
double[...
0
If each list is sorted in descending order, I don't see why you need seen lists at all. Like the previous post https://math.stackexchange.com/questions/4122113/finding-the-top-sums-of-values-from-multiple-lists you will always move to the next highest term in the list that reduces the sum the least -- ie, argmin{k}(list_k[x+1]-list_k[x]). Just that instead ...
1
I am not sure if your post and my answer fits to code review because it is about algorithm design. But here is my proposal for a better algorithm. Use dynamic programming as my slow CAS does by multiplying from left to right.
(%i15) (x^9+x^8+x^7+x^6+x^5)*(x^15+x^13+x^11+x^9+x^2)*(x^16+x^13+x^12+x^11+x)*(x^17+x^12+x^4+x^2+x)*(x^19+x^9+x^8+x^7+1)*(x^21+x^17+x^...
0
I have written a new solution to the problem based on the same principles of the code in my question, but this time using a dictionary with keys equal to the seen sums and the indices as values. This is better because I don't need to sort anything, while in the other solution I need to sort every new list added, and also, I don't need to pop the max elements ...
0
Since this is asking for a new algorithm, I will try to provide some hints. Look at the output of
from itertools import permutations
sorted([a*1000 + x*100 + y*10 + z for a,x,y,z in permutations([1,2,3,4])])
Which digits are most likely to be different between consecutive members of this list?
Look at the elements that start with 4. Can you see a pattern in ...
1
It's not so much the implementation.
With problems like these (typical coding competition ones) it's always the same, that you have to find a clever algorithm instead of writing down as code a straightforward implementation of the problem description.
I haven't myself analyzed the problem, but I'd try to answer some questions:
Of all possible permutations, ...
2
Always True
In addition to forsvarir's answer, especially the "always True" aspect, I'd like to give an additional reason why to change that.
Your parkBigCar() method (and its siblings) is only legal to be called after isPlaceForBigCar() has been checked and returned true. You surely know that today and wrote all your calls appropriately, but if ...
3
using namespace std;
There are lot of good answers why you shouldn't use it. See here
Use std::pair<int, int>
Since your result struct is just acting as a container for two ints, consider using std::pair<int, int>
Don't hardcode values
Why do you want hardcode 16 as the array length? You can just pass it to the function as a parameter, or use ...
7
Questions (+ design review)
Could anyone do some little code review please?
The biggest issue I see with your current design is that you are using the “god object” anti-pattern. Your Sorter class:
Loads the data from a file.
Implements over a half-dozen sort algorithms.
Tests over a half-dozen sort algorithms.
Writes sorted data to a file (over a half-dozen ...
2
I have a few issues with the posted code. We'll start with the trivial.
Code posted on Code Review should be complete. You forgot to include the necessary import to make this compile.
val target = 0 - I find this somewhat redundant. If target isn't zero then you also need to change the name of the method. On the other hand, we're not supposed to bury "...
-1
Your solution also works with O(n ^ 2), except you need to cover few cases as mentioned in the comments above.
A small solution that could make things look neat:
Efficient O(n ^ 2) ThreeSum Solution In Scala
object Solution {
import scala.util.Sorting
import scala.collection.mutable
def threeSum(a: Array[Int]): List[List[Int]] = {
if(a.isEmpty) ...
1
Applied few minor optimisations to the code from the OP's answer. Also fixed naming issues (locals name starts from a lower-cased letter).
class Program
{
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < t; i++)
{
int n = ...
0
I was finally able to reduce it enough to return result for 1 million inputs in around 10 secs.
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine());
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < T; i++)
{
int N = Convert.ToInt32(Console....
0
Your bubble sort algorithm has way too many variables. You don't need to keep track of the right and left item. All you need to do is compare two values, and swap if one is bigger than the other.
def bubble_sort(nums):
length = len(nums)
for i in range(length - 1):
for j in range(0, length - i - 1):
if nums[j] > nums[j + 1]:
...
2
The difference averages to .2 microseconds per number checked.
To see if its the inner loop, try unrolling it in the second program:
...
for i in range(5, ceiling+1, 6):
# test only against factors less than the square root
# just use the sqrt of the bigger number to avoid another call to sqrt
root = math.sqrt(i + 2)
# tests 6k - 1
for j ...
1
In general flatten is intended to flat a tree, not a list, that is to collect all the non-null leaves of the tree in the same order as a classical traversal of the tree. See for instance the definition of flatten in the Racket Manual:
Flattens an arbitrary S-expression structure of pairs into a list. More precisely, v is treated as a binary tree where pairs ...
3
this.
There's a lot of this. references in your code. Typically in Java you only use this. where you need to in order to disambiguate variables. Consider removing them as they're only adding noise to your code.
always True
Your park methods all return boolean, even though they all always return true. If you want to maintain the same approach, consider ...
2
void pairs_sum_up_to_value(int arr[], int target)
What's the length of arr? You should make it work like an STL algorithm, so it takes two iterators, or a range of some kind.
There's no return value? Where does the result go??
I see you have a result vector inside the function, but it's not returned.
int p1 = 0;
int p2 = 15;
int flag = 2;
Despite your ...
3
This is a typical LeetCode problem. I would write an O(n) solution as follows:
#include <unordered_set>
#include <utility>
#include <vector>
template <typename T>
std::vector<std::pair<T, T>> twoSum(const std::vector<T>& arr, const T& target) {
std::unordered_set<T> seen;
std::vector<std::...
0
So, I started looking at it in a different way, filtering out all '() before flattening. Then I found
this answer by Óscar López, which is almost exactly what I needed.
Here's what finally worked:
;; Filter a (possibly nested) list returning a flattened version of the
;; list with only those elements that satisfy the predicate function.
(define (deep-filter ...
-3
Complexity: \$O(\log n)\$
It worked. It gave me correct answers for many testcases:
i/p:[1, 5, 4] ,0
o/p:1
i/p:[4, 1, 3, 5, 6] ,0
o/p:3
l=list(map(int,input().split()))
n=int(input())
p=n-1
q=n+1
while(p>=0 or q<len(l)):
if(p>=0 and l[p]>l[n]):
print(p)
break
elif(q<...
1
no naked new
See ⧺R.11 and a few other guidelines that mention "naked new".
bool* whether_itroduced = new bool[input_length + 1]{0};
Use a std::vector rather than a bare allocated array. (This also fixes the problem where you are not freeing it, as it becomes automatic).
On the other hand, vector<bool> is weird. It is optimized to be "...
2
There's some straightforward and common C++ problems immediately obvious:
using namespace std; - avoid that; it makes your code more fragile. It doesn't even make it shorter!
Streaming input without checking. If you use >>, it's essential to only use the value if it was actually written. For a simple program like this, it's easiest to just set std:...
2
I learned to use space for programming instead of tab, and we were told to do 3 spaces, how many space do you recommend 2, 3, 4, or X amount?
And how many space do you use when programming?
This is a style issue and best to follow your group's coding standard which apparently is 3. I use 2.
A good coding environment allows you to change the indent on the ...
1
No naked loops. Every loop represents an important algorithm, and as such deserves a name. For example, the loops in split_list really are
uint32_t list_length(struct Node *);
and
struct Node * advance(struct Node *, uint32_t);
split_list is a bit more complicated than necessary. The fact that front becomes current is known in advance. Do we really ...
3
In addition to JDługosz's excellent answer, I'd like to add these remarks:
Use switch-statements where appropriate
Replace chains of if-else-statements that check the value of an enum type variable with a switch-statement. This usually makes the code more readable, and also has the advantage that the compiler can warn you if you don't explicitly handle all ...
2
Structure seems pretty good, I'd mainly make the follwing changes:
Use underscores and more desciptive names for internal variables and functions
push and pop look like the would have stack-like behaviour, so I turned them into internal methods with more appropriate names.
inc would better be named and work like update from Counter, so I changed that and ...
3
As the Standard Library headers are independent of each other, it makes sense to include them in consistent order - alphabetical is a good choice.
The main() function here is very long - more than a screenful. That's usually a sign that it should be split into functions for the different responsibilities. In particular, the file reading seems worthy of its ...
5
General impression when starting to read your code is that it's good! You're using constexpr, defining your constructors nicely, etc.
includes
Generally, I'll list standard includes first, and project-local includes at the end of the list.
scope and namespaces
Your point header is defining tolerance as a global variable, which may have nothing to do with ...
2
Use const
In FindCompress and Union the parameters N, i and j could be passed as const as they are not changed in the functions.
Avoid using keywords as function names.
In C union is a keyword, even though the function name is currently in CamelCase I would still recommend against it.
Styling
Segment struct definition
typedef struct Segment Segment;
...
2
Your code looks very well written, following many C++ best practices. The only strange things I found is that you don't use auto inside for-statements, for example I would write for (auto &c: cards) instead of for (const Card &c: cards), and some missed opportunities for using std::make_unique. So I'll focus only on the performance aspect of your ...
1
if the following implementation is any better or worse?
Consider 0
GCD(a,b) is usually considered communicative: GCD(a,b) == GCD(b,a).
while ((a = a % b)) is OK when a==0, yet undefined when b==0.
No swap
Rather than spend time swapping, just add a little more code.
unsigned gcd_no_swap(unsigned a, unsigned b) {
while (a) {
b %= a;
if (b == 0) ...
-1
You can just create every possible triplets with nested loops and keep a record of those that satisfy the requirements.
I don't know Python, so I learned a bit of it to write this code, take it as an example and translate it to proper Python. I think that the main issue of the code is the usage of while loops. I am used to the C's for loops where you have ...
5
#include <stdlib.h>
This is not required - we use nothing declared by that header.
void swap_numbers(void *a, void *b)
{
int temp = *(int *)a;
Avoid void! We don't need to erase and reinstate type information like that:
static void swap_unsigned(unsigned *a, unsigned *b)
{
unsigned temp = *a;
*a = *b;
*b = temp;
}
If we'll need this for ...
6
Unnecessary function calls
My quick thought is that you are making an unnecessary function call.
unsigned temp;
while ((temp = a % b)) {
a = b;
b = temp;
}
The thing with the doubled parentheses is a hack to keep some compilers from warning you that you may be doing an unintentional assignment. It should make no functional difference.
This does ...
2
As always, the interface provided by LeetCode is atrocious. In order to make your code Rusty, I recommend writing your own interface first and then call it within the implementation of LeetCode's interface. Here's why.
The full interface of the search function, imposed by LeetCode, is
impl Solution {
pub fn search(nums: Vec<i32>, target: i32) -&...
1
Just a few points for now, I will extend my answer over the weekend:
I think you should think about the max size of your table anyway. I mean you can't have 4 billion nodes in there.
This is connected to the size. If you only have to resize your table maybe once or twice, it's probably not worth storing the hash value. It's a trade off between speed and ...
1
General points
Use const when a variable does not change.
Avoid using underscore in JavaScript names
Making names too long makes code hard to read, especial when the relevant part of the name is tiny. eg nIntersection, eIntersection, sIntersection, wIntersection when in busy lines the n,e,w,s can easily be overlooked.
The function getLineIntersection ...
1
The typical insertion sort is O(n) for already sorted input, and "almost O(n)" for "almost sorted" input. Which is somewhat common in real world data. Your way you don't have that, you're \$\Theta(n^2)\$. Someone not familiar with how lists work internally might think your code is O(n) for reverse-sorted input, but since del lst[i] takes ...
1
Unfortunately, it looks like your code won't work.
The last condition:
if(butt3 = HIGH){
will always be true.
This is a common mistake in C and C++, missing one = in a condition, turning it in to an assignment.
A useful trick to avoid this is always put the constant first, then the compiler will catch the error for you:
if (HIGH == butt3) {
Another issue ...
1
On the style of the code:
While I'm not saying the code is or isn't correct, there's some small tweaks you could make it to improve it's legibility:
Spacing
Write code like you would write English (in some sense :P). After commas you needs spaces, so do
def crossover(p1, p2): instead of def crossover(p1,p2):;
random.uniform(b[i][0], b[i][1]) instead of ...
1
For O(n) space, I think you need to switch from your top-down DP to bottom-up DP. That lets you control the evaluation order so you can for example go row by row, and store only the numbers of paths for the current row.
To simplify things, start with an imaginary row above the grid and say you have one path right above the real start cell and zero paths ...
Top 50 recent answers are included
