Questions tagged [algorithm]
An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
4,460
questions
0
votes
2answers
11 views
Using Token Bucket to rate limit function calls
This program is my attempt at solving the below problem:
We have a function which is going to be called by multiple threads. The problem is to find a way to limit the number of times this function is ...
3
votes
2answers
177 views
10 Kinds of People Open Kattis Problem Time Limit Exceeded C++
I am trying to solve the open kattis problem '10 kinds of people' (https://open.kattis.com/problems/10kindsofpeople) using a best-first search algorithm and c++.
10 Kinds of People
The world is made ...
3
votes
2answers
150 views
Finding sum in an array
I have this program finding 2 numbers in the array (unsorted) so that its sum equal to the target sum. Here is my program:
...
3
votes
1answer
56 views
Number of inversions on a segment
I was trying to do this question and I get TLE on one the test cases (the actual link to the question will ask you to login).
What is an inversion?
An inversion of an element is the number of ...
1
vote
0answers
31 views
Algorithm to find bucket and item indices from power of two bins?
So this is building off of Algorithm for dividing a number into largest "power of two" buckets?. Here is a slight modification of the answer from there:
...
3
votes
1answer
56 views
Marching Square algorithm (2)
The following source code is a solution to the Marching Square problem.
The explanation of using random numbers in ambiguous cases can be found here.
...
3
votes
1answer
78 views
Mergesort in python
My mergesort implementation currently takes a very long time, for a list with 1 million elements it takes over 130 seconds to get the list sorted.
Could someone kindly have a look at my code and ...
4
votes
1answer
61 views
Checking if a value is in the RGB range and then increment/decrement
Is there a better way to check if the variable x is in the 0-255 range and:
if x is less than 255, add ...
2
votes
1answer
45 views
Binomial Expansion Calculator
So i wrote a program with the documentation for my fx cg50 calculator's micropython to calculate various items, each of which are:
Pascal Triangle Entry
Pascal Triangle Level/Entire Row
Binomial ...
2
votes
3answers
62 views
Efficiently calculate the value of an arithmetic sequence
I need to calculate the value for the following function:
$$f(n) = -1 + 2 - 3 + ... + -1^n$$
The time limit to calculate a given value of \$n\$ is less than 1 second. My approach does not meet that ...
2
votes
1answer
56 views
Projecteuler.net Problem 2 using collection pipeline Pattern
I solve projecteuler.net Problem 2 deferent way
Generate number from 1 to range ex 100 and get the even number
Get Fibonacci numbers from list
Reduce array
I have one problem with a large set of ...
3
votes
2answers
78 views
Is the following divide and conquer recursive algorithm for the exponentiation more efficient than the iterative one for large numbers?
I have the two following algorithms. My analysis says that both of them are \$\mathcal O(m^24^n)\$ i.e they are equivalent for big numbers (more than 32 bits). Is this right? Note that ...
3
votes
1answer
65 views
Sudoku Solver using rules of Sudoku and backtracking
This code tries to solve the sudoku board using the rules of sudoku. When it does not make progress in solving, it assumes a cell value and tries again. Please review my code and help me understand ...
3
votes
1answer
44 views
Data analysis code (finds coincidences in three sets of data)
I've written the following data analysis code (using just a couple lines from CERN's ROOT data analysis framework). It's designed to find coincidences in three sets of data (timestamps from an ...
4
votes
1answer
77 views
Multiple Pandas Ranking Operations within a Loop - Better Optimization and Performance
I have implemented the following code which works as intended. However, I would like to improve my code in terms of performance and efficiency
Code in Question
...
2
votes
2answers
78 views
Different approach Union Find
I am studying algorithms and I did this "Union Find Like" algorithm.
I have one array of objects with a reference and I make the union pointing to the same reference instead of have two int[]...
3
votes
1answer
75 views
Sorts and data structures: a bucket sort
I am currently going through and implementing basic algorithms and data structures as I feel I didn't learn enough about this during my Data Structures and Algorithms unit. So far I've done the ...
0
votes
0answers
64 views
Kattis: “watering Grass” Interval covering problem, why is my code so slow?
im currently practicing, doing a python implementation of this challenge: https://open.kattis.com/problems/grass
Problem described here:
...
2
votes
0answers
30 views
Insertion sort for std::forward_list
I'm practicing writing insertion sort for std::forward_list. But I find myself creating many variables and using many if statements. Looking for inputs on how to make the function more efficient, ...
15
votes
2answers
2k views
C++ chess game engine using Minimax and alpha-beta pruning;
My chess game is over, everything has been finished, except for some special (like en passant)moves.
The main part of the game is its engine which I have coded using the Minimax algorithm with alpha-...
0
votes
0answers
20 views
Finding strongly connected components in a directed graph using Kosaraju's algorithm
I'm working through Stanford's algorithms course on edX.
One of the programming assignments is to find strongly connected components using Kosaraju's algorithm, on a graph with ~875,000 vertices. My ...
2
votes
2answers
65 views
Exponentiation by squaring in x64 Linux Assembly
I am learning some assembly for a compiler project I am working on and I have come across the Exponentiation by Squaring algorithm when it came to calculating x ^ n. To get a grasp on how the ...
4
votes
2answers
73 views
JavaScript Priority Queue implementation using a binary heap
I'm currently going over Robert Sedgewick's Algorithms book. For the implementation of A priority queue using a binary heap I implemented the code using ES6. I believe to have more experience with ...
3
votes
1answer
84 views
Bubble Sort In C++
I'm learning modern C++ and also algorithms, and am doing some practice by coding up some simple algorithms. Also trying to use templates whenever possible as I'm quite unfamiliar with generic ...
5
votes
1answer
141 views
6
votes
1answer
139 views
Python: Astar algorithm implementation
I have implemented Astar algorithm for a problem on an online judge relating to maze given start and end positions along with a grid representing the maze. I output the length of the path along with ...
3
votes
1answer
174 views
Memory/Time usage on substring search code
I have implemented a substring search, which works as expected and provides the right output. On some edge cases tho, I get either Memory or Time limit exceeded because:
the string length is too big
...
0
votes
2answers
148 views
Sum of 2 numbers in an array [closed]
I have this problem to solve:
Given an integer \$z\$ and an array \$a\$ of distinct integers sorted in ascending order, find two numbers, \$x\$ and \$y\$, belonging to the array such that \$x + y = z\...
3
votes
1answer
104 views
Sentinel linear search
I'm pretty new to algorithms, and it's my first attempt to implement sentinel linear search in JS. I'm wondering if it can be improved.
...
9
votes
2answers
1k views
Can I draw a square with pixels more efficiently?
I'm drawing a square on a window using an implementation of Xlib. I put a colored pixel with my_pixel_put at a specific (...
2
votes
0answers
62 views
Marching Square algorithm
The following source code is a solution to the Marching Square problem.
The explanation of using random numbers in ambiguous cases can be found here.
...
4
votes
2answers
237 views
Floyd-Warshall Path Reconstruction
Below is the implementation for the Floyd-Warshall algorithm, which finds all-pairs shortest paths for a given weighted graph.
The function floyd_warshall takes a ...
1
vote
0answers
42 views
LeetCode 146: LRU Cache (Go)
Posting my code for LeetCode's LRU Cache, if you'd like to review, please do so, thank you for your time!
Problem
Design and implement a data structure for Least Recently Used (LRU) cache. It should ...
5
votes
1answer
38 views
Selection Sort Java and Analysis
I have written a selection sort code in java. I know its very elementary algorithm, but since i am learning, so wanted your input about the quality of the code. Please have a look at the code:
package ...
1
vote
1answer
60 views
Priority Queue implementation for top k frequent elements leetcode in Ruby
While working on the following leetcode problem: https://leetcode.com/problems/top-k-frequent-elements/ I used a Priority Queu implementation in Ruby. I have learned how to implement a Priority Queu ...
2
votes
1answer
28 views
Update UNIX-like system user profile picture with its GitHub account's one
Seeking to learning and have fun, I wrote out this script (what I expected to be) self explanatory and would appreciate some comments on that.
I published it as a gist and tried to do my best on what ...
3
votes
1answer
68 views
LeetCode 310: Minimum Height Trees
Posting my code for a LeetCode problem, if you'd like to review, please do so. Thank you for your time!
Problem
For an undirected graph with tree characteristics, we can choose any node as the root. ...
7
votes
0answers
55 views
A* using a Priority Queue
I've implemented an A* with a priority queue. I am not getting any performance issues in this little game that I am making but it would be interesting to know how to improve this.
I am doing a few o(n)...
1
vote
1answer
47 views
LeetCode 1206: Design Skiplist
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
Design a Skiplist without using any built-in libraries.
A Skiplist is a data ...
5
votes
2answers
165 views
C++ Practice on STL templates and algorithms
I have implemented the following program below for an assignment for practice on STL templates and algorithms. All I'm doing is implementing the code for the printing of empty files, un-empty files, ...
5
votes
2answers
85 views
Optimizing performance of randomly generated pygame maze game
I made a random maze generator that is also playable. The performance is crap and I'd like to improve it. I'll be working on this for a few more days to make it run better myself, but just thought I'd ...
3
votes
0answers
70 views
Smashing two heaviest stones until at most one stone is left - counting number of stone comparisions
Based on this question:
Heaviest Stone algorithm time complexity
Problem:
We have a collection of stones, each stone has a positive integer weight.
Each turn, we choose the two heaviest stones and ...
3
votes
2answers
34 views
Merge Sort Implementation and Optimization
This is Merge Sort that i implemented, i feel i can make it better esp the combination function.
So i split the code into functions because i don't like seeing a bunch of spaghetti code in a single ...
3
votes
0answers
46 views
LeetCode 1263: Minimum Moves to Move a Box to Their Target Location ||
I'm posting a follow-up code on this question, which seems to be a version of Sokoban.
If you'd like to review, please do so. Thank you for your time!
Problem
Storekeeper is a game in which the ...
2
votes
0answers
80 views
Ugly Number problem using dynamic programming
I am learning Dynamic Programming and tried to solve the nth ugly number problem using it. Here's my code for the problem in Java:
...
3
votes
1answer
102 views
In-place merge two sorted array
First post.
Can you please review my code and help me improve my coding. Please also suggest improvements if there is a miss in this post.
Problem Statement
Given two sorted arrays ...
2
votes
1answer
62 views
LeetCode 1263: Minimum Moves to Move a Box to Their Target Location
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
Storekeeper is a game in which the player pushes boxes around in a warehouse trying ...
8
votes
2answers
60 views
Line wrapping text utility using fixed-size arrays
As an exercise, I've made a text processing utility that wraps arbitrarily long lines of text, but only using fixed-size arrays and other basic C features.
I have mostly programmed in Python, C++ and ...
5
votes
1answer
73 views
LeetCode 928: Minimize Malware Spread II
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you for your time!
Problem
(This problem is the same as Minimize Malware Spread, with the differences bolded.)
...
1
vote
1answer
72 views
LeetCode 839: Similar String Groups III
I'm posting my code for a LeetCode problem. If you'd like to review, please do so. Thank you!
Problem
Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that ...
