Questions tagged [algorithm]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to algorithm design.

91,897 questions
3 views

Converting Recursive Tarjan to Iterative to find SCCs

So I've successfully implemented a recursive tarjan's that provides me the SCC of a graph My recursive implementation is as follows: public void DFSRecursive(long currentNode){ low[currentNode] =...
39 views

Space-efficient algorithm for checking if strings with backspaces are equal?

I was recently asked this question in an interview: Given two strings s and t, return if they are equal when both are typed into empty text editors. # means a backspace character. Input: S = "ab#...
17 views

Hash function returns same hash when keys have same length

I am looking for a hash function in java that for keys with same length returns the same hash. int index1 = hashmap.hash("xxx"); int index2 = hashmap.hash("yyy"); ...
24 views

B* (star) tree inserting method problem c#

Can anyone help me implement a B(star)* tree insert method in C#? This is a working B Tree implementation, but i need a split child modification to make the B star Tree work. I understand the logic ...
26 views

Universal hashing function probability [migrated]

Can somebody explain the following: U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}. I do not understand definition 2, and thus why amount of ...
59 views

C++ Insertion sort confusion

I'm trying to implement insertion sort on my own in C++. I know there are plenty of examples and I compared my solution with existing ones and don't see why mine isn't working. I know there are ...
24 views

Should I use two Hashmap for fast lookup on two entities instead of linear search of one hashmap?

I had an interview problem where I was asked to make an optimized solution to implement search on two instance: Student Number and class(only one per student). sn_to_class() should return class for ...
27 views

Element to delete in array give maximum gcd [on hold]

I want to ask how we can maximize the GCD of the numbers in an array by deleting one of the numbers (or all copies of a duplicated number). For example, if the array contains {..., 23, 23, 23, ...}, ...
31 views

How do you deal with data structures on leetcode with Golang? [on hold]

Noob question, Unlike Java, Golang doesn't have TreeSet, TreeMap, priorityQueue (except container/heap, still not easy to use), making it a bit harder to practice on Leetcode. Do you just implement ...
34 views

problem calculating minimum amount of coins in change using python

I have a homework assignment in which we have to write a program that outputs the change to be given by a vending machine using the lowest number of coins. E.g. £3.67 can be dispensed as 1x£2 + 1x£1 + ...
29 views

Monte Carlo study on R [on hold]

i have a problem. I hope that you will understand me: unfortunately my english is not very good. I need to write a R code for a simulation Monte Carlo. The latter is based on a bootstrap algorithm. I ...
31 views

Find Nth term of provided sequence

f(0) = p f(1) = q f(2) = r for n > 2 f(n) = af(n-1) + bf(n-2) + c*f(n-3) + g(n) where g(n) = n* n* (n+1) p,q,r,a,b,c are given The question is, How to find the nth term of ...
69 views

Various list concatenation method and their performance

I was working on an algorithm and in that, we are trying to write every line in the code such that it adds up a good performance to the final code. In one situation we have to add lists (more than ...
57 views

Find all nodes in between a path in a tree

I have a undirected tree with N nodes and N-1 edges, no self loops, and the entire tree is a single component. I need to find all nodes between any given two nodes in a tree. For example if tree is: ...
32 views

What is the complexity of this pseudo-code

I found this excersise in the exam and I ecountered difficulty to solve the problem. I can suppuse for sure the algorithm will take at least O(n) due the for, but I don't know how to approach the ...
32 views

How can do release query interval in java

I have two release version number. for example: oldVersion= 1.1.0 newVersion= 3.3.4 I want to create query in order to fetch other release version number between oldVersion and newVersion like 1.2....
32 views

Most efficient way to find path between two given vertices in a tree

I have a tree. Two vertices a,b are given as input and we need to print the path between them. One of the way to do it is by find all paths from a and print the path which ends with b.Is there any ...
25 views

To find the area of the multiple rectangles intersectng each other

There are N rectangular boxes(Bi) and each has a special value(Power) Pi. These rectangular boxes are placed in the first quadrants of the x-y plane. These boxes are represented by two coordinates,...
23 views

easeOutBack animation and Magnet Effect

is there some steering behaviors algorithm that I can set to make this effect ? https://gifyu.com/image/EMJ6 many nodes are connected to each other and move randomly Thanks!
58 views

How do I keep track of the shortest paths in the Dijkstra algorithm when using a min-priority queue?

I'm trying to implement Dijkstra's algorithm with a priority queue. From my understanding, "Dijkstra's algorithm" allows to to find the shortest 'paths', in that it will return a set of vertices ...
56 views

find the distinct elements in a range

I have an array A with N elements. 1 <= N < 10^6 1 <= A[i] <= 10^9 There are Q queries in form of L, R 1<= Q <= 10^5 For each query I need count of distinct elements in range L ...
32 views

Hash Implementation - Hash Function MAD Form

I am implementing a hash table in java and I have to define the hash function. I am following the MAD Form. I read in internet: The MAD method: h2(y) = [(ay + b) mod p] mod N, where N is the size ...
12 views

egg drop prblem using binary search

Can Egg dropping problem be solved using binary search without using dynamic programming or recursion. Understanding Egg Drop Algorithm for more than two eggs.
41 views

I would like to print the arithmetic sequence triangle

I would like to print the 'number' triangle like the below sequence. 1 2 4 7 11 3 5 8 12 6 9 13 10 14 15 assume that give n is 5. means that column will give 5 and column - 1. also, the ...
51 views

Example of same Preorder and Postorder traversal?

If only the root node is present then preorder and postorder traversal will be the same i.e root node only. What are other examples in which preorder and postorder traversal will be the same?
70 views

Get the primes in given range with provided conditions

This was asked during my interview. I have to write a program to find all the prime numbers which are having only odd digits in them for the given range. Eg: 31 is a prime number having only odd ...
53 views

Why is one of these dynamic programming solutions to a pathfinding robot faster than the other?

The Problem "There's a robot in the top left corner of the grid. The robot can only move right, or down. The grid can contain invalid/blocked cells that the robot cannot step onto. Verify if there is ...
43 views

How can I store a digit of an Integer I'm trying to separating?

The issue I'm having is, I want to take an integer and separate it. For example: The user enters: 23432. The console should print" 2 3 4 3 2. The issue I'm having is storing that digits. For example, ...
15 views

Radix Sort is an example of complexity algorithm P or NP?

The problem of ordering a vector by Radix Sort is an example of a complexity algorithm P? I do not know if it can be NP-Complete or just NP. void radixsort(int vector[], int size) { int i; ...
41 views

Repeat many times the same code with R and collect the final results

i have a problem. I hope that you will understand me. My english is not very good. I need to repeat B times (where B is at least one thousand) a R code that i write and collect the 1000 final results....
21 views

Optimal layout of nodes given pair-wise commmunication frequencies and link speeds

Here's the problem: You have a set of nodes in a fully connected graph. Every edge in the graph has a cost associated with it (delay). You also have a table of frequencies that tell you how often ...
25 views

Create a Sequence With Two of Each Element Satisfying Certain Distance Criteria

Given a sequence of distinct items Sa, we wish to create a sequence Sb (composed of the same items in Sa, but in a different order) such that the sequence S = Sa + Sb (sequence Sb appended immediately ...
36 views

Highlight text within a string

I have an algorithm which calculates the characters to highlight in text based on query. For example, if I pass to the algorithm text "1000, Brussels, Belgium" and query "1000 bruss" it will return ...
67 views

Number of occurrences of each distinct integer in given ranges for an array

Given an array of n integers (n <= 1e6) [a0, a1, a2, ... an-1] (a[i] <= 1e9) and multiple queries. In each query 2 integers l and r (0 <= l <= r <= n-1) are given and we need to return ...
17 views

What's wrong with the code for floodFill algorithm in R?

I've taken an algorithm from https://rosettacode.org/wiki/Bitmap/Flood_fill and test it with R language. Added diagonal neighnors matching (like Queeni floodfill <- function(row, col, tcol, rcol) {...
19 views

Grouping/clustering algorithms with uncertain distance metrics

I need some guidance on how to improve a clustering algorithm. The answer may be trivial, or impossible. I googled a lot, but I either don't understand the analogy between my problem and known ...
20 views

R code for algorithm about bootstrap prediction intervals for AR(p) model

i'm new here and also my english is not very good. I hope that you can understand me. I'm writing an R code for algorithm about bootstrapping an AR(p) model. The algorithm is following: Algorithm to ...
74 views

Find different digits among two numbers

I want to find the number of digits different between two numbers num1: 10110 num2: 10101 both the numbers are base 10 Desired Output: 2 Notice the last two digits of both the numbers, they are ...
20 views

Finding a partition of a graph with no edges crossing partition

I have a graph with a guarantee that it can be divided into two equal-sized partitions (one side may be 1 larger than the other), with no edges across this partition. I initially thought this was NP-...
36 views

Splitting a string into multiple spans based on a set of overlapping ranges

I need to split a string into multiple substrings based on a set of range values, with each substring tagged with the set of applicable ranges. There should be no overlap in the resulting collection ...
26 views

Is there a name for an algorithm to check whether an image contains a given shape?

Given a bit map defining the shape of some item I want to compute some level of confidence that a pixel map contains the shape. Is there a name for this type of algorithm or perhaps a method in ...
38 views

finding the best place for post station

the program should find the best city for building a post station in the country with cities which have same n distance, base on population and number of steps for going to each city from other cities....
14 views

How to find a optimal value of k to apply k-ary search

what algorithm will be used to determine the best value of k to apply k-ary search. e.g. I have array of size 10000 and what should be the size of the sub arrays on which can i apply k-ary search in ...
31 views

I'm writing with R an algorithm about prediction bootstrap intervals of autoregressive models. I don't understand what does a step mean. I report the steps of the algorithm: I don't understand step 3 ...
39 views

IndexError in implementation of Two Sum problem

I write an algorithm that sums up two numbers in a list so that it is equal to 15 or 13 or 7 then deletes those numbers from the original list and then repeats the process. Until there are no more or ...
15 views

Image filter kernel edge problems (Reflect values on edge)

I want to handle some edge problems that occur when using differently sized kernels on images. First of all: I know there are prebuilt options in opencv for handling these cases but since this is an ...
25 views

boost induce maximum common subgraph

I want to induce a small graph on a large graph. Both of these graphs are shown bellow. The vertices with same color are equivalent. small graph (subject to be induced) large graph (The smaller ...
73 views

Is is possible to move from (a,b) to (c,d)

The problem was to output whether it is possible to move from a given point (a,b) to target (c,d) We are restricted to positive co-ordinates only The following two moves are possible (a,b) -> (a+... 