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,570
questions
3
votes
1answer
32 views
tic-tac-toe algorithm improvement in C
I 've made a tic-tac-toe game in C, I want some tips on how to improve it since the program is a little bit too long. (500 lines with comments)
How I done the game:
Mapped a 3x3 Matrix like the board ...
1
vote
1answer
41 views
Binary Radix Sort implementation on linked list
I am trying to implement binary radix sort in C which sorts a linked list of integers stably. Although my algorithm has a time complexity of O(log2(k).n) (where k ...
0
votes
1answer
38 views
How to reduce time complexity of obstacle calculation in a grid map? (python)
How can I change the function calc_obstacle_map(self, ox, oy) to get an equivalent result that runs as fast as possible? The time complexity of ...
0
votes
2answers
60 views
Solve binomial coefficient without lookup
I want to solve for n in the expression (binomial coefficient):
\$y=\frac{n^2+n}2\$
let y = (Math.pow(n, 2) + n) / 2;
I know ...
4
votes
1answer
98 views
Searching for an idiomatic Rust implementation of Minimum Edit Distance (LeetCode #72)
I am solving LeetCode Dynamic Programming challenges (this one is #72, at https://leetcode.com/problems/edit-distance).
Here below, I've implemented a Rust solution for the minimum edit distance ...
0
votes
0answers
26 views
Randomized Algorithm for finding optimal path in graph
Note: the optimal path can be chosen as the shortest path or the longest path
I made a randomized algorithm for finding random paths in a graph. The graph has weights on the edges. For non-cyclic ...
3
votes
1answer
82 views
Substring search in Java
I am trying to make an algorithm that will find the index of a given substring (which I have labeled pattern) in a given String (...
0
votes
0answers
37 views
Count the different positions reached in a cycle of permutations
I have come across a problem on cyclic permutations. It is about swapping numbers around.
It starts out with input N < 100,000 which makes the first N natural numbers as orders: 1 2 3 ... N-1 N
...
-1
votes
1answer
57 views
need some guidance for better coding practice [closed]
Given a int optimumMemory and int[] array with list of available memories find the pair of indexes of memories whose sum of the values will be equal to the optimumMemory?
If there exists more than one ...
1
vote
1answer
89 views
std::vector Allocator-Aware Implementation
I've just finally finished implementing std::vector. I'm currently re-implementing whatever I can in the hope to learn more of how data structures works.
I tried to ...
0
votes
1answer
63 views
Find a sum using just two different digits
The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the ...
2
votes
1answer
56 views
Geeks for Geeks: Trapping Rain Water Problem - time limit exceeded
Problem Statement:
Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the ...
1
vote
1answer
73 views
Simplest possible Tic Tac Toe AI in Python
Last week I challenged myself to create the smallest possible code for a Tic Tac Toe game with an AI as opponent. Smallest possible in regards to say least number of characters used. The requirements ...
3
votes
1answer
68 views
Namespace list to directory structure
Namespace list to directory structure
Motivation
I have a list of namespaces I extracted from types, and I which to create a directory structure, that represents these namespaces. So that I can place ...
0
votes
1answer
24 views
Greedy algorithms to find minimum number of coins (CS50)
I'm taking CS50, an Introduction to CS, and we're asked to do the following task:
Suppose that a cashier owes a customer some change and in that cashier’s drawer are quarters (25¢), dimes (10¢), ...
1
vote
2answers
171 views
Determine whether bitwise-OR of sub-array is odd
Problem:
Given an array A of N integers, you will be asked Q queries. Each query consists of two integers L and R. For each query, find whether bitwise OR of all the array elements between indices L ...
2
votes
1answer
41 views
Optimizing code that reads a JSON file and a CSV file and compares them and outputs to a file
I have written this code that reads a JSON and CSV files compares them and outputs to a text file This output file will contains the association that my program has created in the following format
<...
2
votes
1answer
27 views
Combinatorial Geometry Algorithm (synthetic)
I created an algorithm to solve in synthetic geometry. This problem states that these points are a scalar (real) number. The goal is to first make the possible triangles from the line segments. Then ...
2
votes
1answer
98 views
Algorithm Optimization — Automatic Dimensionality of PCA
I have implemented (rather, edited the implementation of) a technique to automatically detect the optimal number of dimensions for PCA, based off of this paper.
This was inspired by ...
0
votes
1answer
75 views
C++ Coding Exercise - Maximum unit to load into a truck given it size
You are assigned to put some amount of boxes onto one truck. You are given a 2D vector of box_types where box_type[0] is the number of a type of box and box_type[1] ...
3
votes
1answer
27 views
Another Sliding Window - find each `k-size` window the maximum num. from an integer array/list
I've searched this site and find many similar questions, but not exactly the same as the one I'll post.
This attempts to solve Leetcode 239:
You are given an array of integers ...
0
votes
1answer
68 views
Advent of Code 2020 - Day 1: finding 2 or 3 numbers that add up to 2020
Next: Advent of Code 2020 - Day 2: validating passwords
Problem statement
I decided to take a shot at Advent of Code 2020 to exercise my Rust knowledge. Here's the task for Day 1:
Day 1: Report ...
3
votes
1answer
47 views
Distribute items based on the time duration
I just finished a small assignment and I would like to get some feedback about the implementation here. Basically, it was all about distributing items ("talks" in this case) throughout the ...
0
votes
1answer
47 views
Find the largest element in a sorted array with increasing consecutive differences, smaller than x, in O( log(logmax_value)
I want to find the largest element in a sorted array, where the differences between the consecutive elements of the array are increasing, that is smaller than x.
For example:
...
1
vote
0answers
39 views
Monotonic stack - complexity analysis
I tried following the official solution of LC975 (https://leetcode.com/problems/odd-even-jump/), using a monotonic stack - i.e., I reimplemented their solution (Approach 1) from python in C++.
TLDR ...
1
vote
3answers
74 views
Implementing a Lift (Kata on Codewars)
I solved the following Kata on Codewars:
https://www.codewars.com/kata/58905bfa1decb981da00009e/train/cpp
It was a lot of fun to solve it.
Here everything you need to know so no need to use the link.
...
3
votes
1answer
56 views
Bancroft's method implementation
Background
I've written an algorithm to solve the three-dimensional Time Difference of Arrival (TDoA) multi-lateration problem. That is, given the coordinates of n ...
0
votes
2answers
66 views
Python Combinatory Algorithm - A Binomial Coefficient application with n mutable and k fixed to 2
This question came from a real use case.
I had a data frame with different columns each one containing data from a data source and I wanted to design a hypothesis test to prove or not if the data had ...
6
votes
1answer
107 views
2D Matrix in C++20 and Strassen's algorithm
I wrote C++20 implementation of a simple matrix class and its usage in Strassen's \$O(n^{lg_2{7}})\$ matrix multiplication algorithm.
Live demo: https://wandbox.org/permlink/JaSC8fQccFbcl1QY
(For n = ...
-1
votes
1answer
82 views
Simplifying for loops that includes conditions with better linq queries
The code below selects all items that are locked. How can I optimise it?
ShopItemData doesn't contain a field for locked/unlocked.
...
2
votes
4answers
89 views
Is this an efficient/correct way to get largest Prime factor?
Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms.
...
5
votes
2answers
86 views
Moving average algorithm that preserves the integral and number of points
I need to smooth a noisy signal. I think that the moving average algorithm would be fine. However, I want the following conditions to be satisfied:
The total integral (the sum of all values) before ...
0
votes
2answers
43 views
Identifying indices of non-delimited characters in a string, supporting greater than 1 length of delimiters
The code below takes a string that potentially contains a true match for a delimiter. There can be multiple delimiters located anywhere in the string. We need to obtain the indices that are not a ...
0
votes
0answers
57 views
Creating a deck for a card game
Some friends and I were playing the game Spot It, which has x cards each with y symbols on them, from a potential of ...
3
votes
0answers
66 views
Modified Tarjan's algorithm for reporting the edges within the strongly connected component
As described in his paper, Tarjan's algorithm reports only the nodes of the strongly connected components. For my use, I would also like to also have the edge list of the components (so that I can run ...
2
votes
1answer
95 views
Find minimal modulo-sum of pairs from two lists
Recently I appeared for an job challenge organised on HackerEarth.
Question:
There are two teams T1 and T2. Power of each player is represented in array. The rules of game are as follow.
There are ...
5
votes
0answers
39 views
calculating upper bound on normalized weighted levenshtein distance
Current implementation
I am using a normalized weighted Levenshtein distance for two utf32 strings with the following costs (insertion: 1, deletion: 1, replacement: 2). The normalization is performed ...
4
votes
2answers
162 views
Maintaining Maximum Social Distance
So I wrote this simple program to place a certain number of people on a list of seats whilst maintaining maximum social distance.
Given that there is at least one ...
2
votes
1answer
40 views
JavaScript function for the get the formatted date of tomorrow
I need a JavaScript-function which always computes the date of the next day. Then returns the date as a string, formatted in the way: dd.mm.yyyy
I wrote this code:
...
1
vote
1answer
42 views
How can I make this function that checks whether a number is a palindrome better?
I have this code:
export function is_palindrome(num: number): boolean {
return [...num.toString()].reverse().join("") === num.toString();
}
which ...
0
votes
0answers
12 views
Find alignable blocks of digits between different bases
In cases where two radices are powers of a common sub-case (e.g., base 8 and base 16 are both powers of base 2), it is possible to align blocks of digits between representations to make converting ...
3
votes
2answers
92 views
Finding max amount of integers in list that add up to target
Introduction
1) Problem description:
Suppose you are managing files. You are given a text file, where in the first line are storage's volume of the server and the amount of users in total that is in ...
0
votes
1answer
74 views
Is there a better “Go” way to implement LC Add Two Numbers solution
Problem Statement:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the ...
5
votes
1answer
96 views
RUST: How can I optimize this password cracking algorithm?
I made this project in my free time to try to crack a 4x hashed md5 with a couple of hints but I'm looking for ways I can optimize this algo because it's pretty slow and I know you could probs use ...
3
votes
1answer
61 views
Matching brackets in Rust
I implemented the solution to the classic Matching Brackets problem:
Given a string containing brackets [], braces {}, parentheses (), or any combination thereof, verify that any pairs are matched and ...
5
votes
4answers
835 views
Finding integer with the most natural dividers
Problem description: You are given a segment [568023; 569230]. Find integer within given range that has the most natural dividers. If 2 or more integers are found, return the lowest integer among them....
5
votes
1answer
178 views
A-star pathfinding algorithm
I'm working on a school project where I need to implement the pathfinding algorithm. The requirements are that it needs to find the path in at most a few seconds and ideally in less than 1 second. I'...
3
votes
3answers
129 views
Generic Vector implemented in C language
I am on the way implementing my own STL-like library in C language. The main reasons are learning DS&A better, as well as the C language itself. Here I am trying to implement Vector (a.k.a. array-...
0
votes
1answer
44 views
Faster way to intersect arrays
I need to intersect lots of arrays with each other. Those arrays are like:
...
3
votes
1answer
38 views
Return n largest nonzero entries of an array
For something I'm working on, I need a function that takes in a one-dimensional array vec of integers and returns a boolean array of the same shape indicating where ...
