# Questions tagged [algorithm]

40223 questions

1

votes

3

answer

498

Views

### Don't know what data structure to use for my algorithm

I'm trying to write my first algorithm and this is the pseudo code I am suppose to go off of. The algorithm is suppose to permute the set {0,1,2,3,4,5,6,7,8,9} for k spots. e.g n= set 0-9 so n=10 and r=k n^r permutations
so U={0,1,2,3,4,5,6,7,8,9} (singly linked list)
S is initially empty and let k=...

1

votes

4

answer

1.3k

Views

### Number guessing game

I've been given a 'broken algorithm' to fix. It's for the game 'Guess a number between 1-100' Where the computer answers within 7 questions/iterations.
The brief i've been given suggests only minimal changes need to be made to the algorithm, sorry if that's vague, i'm thinking the same thing.
Anywa...

1

votes

3

answer

107

Views

### determine if an array has the numbers a to b each once [duplicate]

This question already has an answer here:
How to tell if an array is a permutation in O(n)?
16 answers
Given an array A of size n, and two numbers a and b with b-a+1=n, I need to determine whether or not A contains each of the numbers between a and b (exactly once).
For example, if n=4 and a=1,b=4...

1

votes

2

answer

2.7k

Views

### How to Efficiently Calculate Nearest 2D points in JavaScript?

I have a set of locations that I want to display to a user in proximity order - closest to farthest - based on their current coordinates. Assume we have ~100 data points of locations which includes each one's latitude and longitude (in some kind of object or array), and we know the user's lat and lo...

1

votes

3

answer

394

Views

### fast inversion algorithm slower than math.h 1/sqrt function

i just want to learn why fast inversion algorithm is slower than math.h sqrt function. Here is my code sample
Code tries to demonstrate compare slow inversion and fast inversion. While debugging i see 1 seconds for slow inversion and 4 second for fast inversion. Where is the problem?
#include
#inclu...

1

votes

1

answer

1k

Views

### Insertion Sort algorithm ignoring first element

I am implementing a simple Insertion Sort in C++ shown below:
void insertion_sort(int a[], int size)
{
int temp;
for (int i = 2; i < size; i++)
{
temp = a[i];
int j = i - 1;
while (j > 0 && a[j] > temp)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
print_array(a, size);
}
cout = 0
then,
Original array:...

1

votes

2

answer

3.1k

Views

### 2D tile map generation with biomes

I would like to generate a 2D tile map with biomes (let's say : Desert, Grass, Snow).
I had a few ideas of algorithms, like putting a few random tiles and then trying to expand, but I have absolutely no idea on how to determine when to expand and when not to. (the tries I've made always end with an...

1

votes

1

answer

102

Views

### Can I make assumptions in BFS and DFS?

I'm reviewing the concepts of Depth-first search (DFS) and Breath-first search (BFS), but I always forget if I can assume some rules.
I know that in a DFS I will start with the root and go as far as I can, before come back, (...)
and in a BFS I will start visiting the root and all its neighbors, (....

1

votes

1

answer

919

Views

### Compressing coordinates in Fenwick tree

Let's say we have n empty boxes in a row. We are going to put m groups of coins in some consequtive boxes, which are known in advance. We put the 1st group of coins in boxes from i_1 to j_1, the 2nd group in boxes from i_2 to j_2 and so on.
Let be c_i number of coins in box i, after putting all the...

1

votes

3

answer

172

Views

### Longest common subsequence Algo

In Longest Common Subsequence (LCS) Problem, why do we match last chars for the string. For ex
Consider the input strings “AGGTAB” and “AXTXAYB”. Last characters match for the strings. So length of LCS can be written as:
L(“AGGTAB”, “AXTXAYB”) = 1 + L(“AGGTA”, “AXTXAY”)
Would...

1

votes

1

answer

97

Views

### Why is this Array getting modified? [duplicate]

This question already has an answer here:
How to clone a multidimensional array in java? [duplicate]
2 answers
I have an array called maze which in, theory, should get modified only in the updateMaze() method. This is because that is the final result I want to output to the console. The problem is...

1

votes

2

answer

138

Views

### Finding nodes that partition a Graph

I have a non-directed graph that represents the connectivity between regions of a map. I'd like to identify groups of nodes (regions) that could be removed without creating graph partitions.
What I have tried:
Walking the tree (BFS, DFS...), storing the depths and selecting the nodes with the higher...

1

votes

3

answer

1k

Views

### infinite loop in quicksort java

I try to realize an algorithm of quicksort, but when I run my code, it gives me an infinite loop, I don't understand, where I make mistake in partition method in my code:
public static int partition(int[] a, int p, int r)
{
int x = a[p];
int i = p;
int j = r + 1;
while(true)
{
while(a[i] < x)
{
i++...

1

votes

2

answer

25

Views

### Merge K sorted arrays of Length N

This is the problem as stated in the book:
Suppose you are given K sorted arrays each with n elements, and you want to combine them into a single array of kn elements. You use the following approach: first merge the first and second arrays, then merge the resulting array with the third array, then t...

0

votes

0

answer

5

Views

### What is the best way to assign a risk score to credit customers

I need to assign a risk score to credit customers. I have a history of on-time and late payments on credit accounts. I need to present a report that shows how risky a customer is based on their past history. My data looks like:
cust_id | acct_type | statement_date | payment_date | late
-------------...

1

votes

4

answer

1.2k

Views

### Faster GCD(n, m) in Java?

I'm working on something that's going to need to use the GCD algorithm quite a bit, and I'd like it to be as fast as possible. I've tried the normal method, binary method, and a memoisation method I thought would work better than it did. I copied the binary method from here, with minor tweaks.
I've...

1

votes

2

answer

503

Views

### Why is clear an O(n) operation for linked list?

According to attachment 1, linked list's clear operation is O(n).
I have a question about why is it so.
Here is how we implemented the linked list in class(java)
public class LinkedIntList {
private ListNode front;
......
}
And if I were to write a clear method for this linked list class, this is h...

1

votes

2

answer

88

Views

### What is the lowest bound for the algorithm?

Let an algorithm which get unsorted array with the size of n. Let a number k

1

votes

2

answer

2.5k

Views

### Difference between Tree Edges and Forward Edges

I was reading a book when I came across this question:
How can you tell the difference between Forward Edges and Tree Edges from the Discovery and Finish Time of that specific vertex in a graph when DFS is run on it?
What I've attempted so far is that: The main difference between Fwd. and Tree Edges...

1

votes

2

answer

1.9k

Views

### How to create a simple l-system in Processing

I want to create a simple l-system in Processing. I want to change every letter 'A' to 'AB' and every letter 'B' to 'A', starting with 'A'.
The result should look something like this:
A →
AB →
ABA →
ABAAB →
ABAABABA → etc...
(P.S. I don't know much about processing)

1

votes

1

answer

311

Views

### Time Complexity of Dependent for loop

string str = "abcdefghijklmnopqrstuvwxyz";
int sum = 0;
for(int i=0; i 0)
{
sum = val % 62;
val = val / 62;
}
}
I know that parent loop executes n+1 time and the child loop executes (val)^(1/62) times. For parent loop time complexity will be O(n) but don't find a way to calculate for child loop. So,...

1

votes

2

answer

910

Views

### (LeetCode) Contains Duplicate III

Given an array of integers, find out whether there are two distinct
indices i and j in the array such that the difference between nums[i]
and nums[j] is at most t and the difference between i and j is at most
k.
Hello!
I am kinda stumped by this question, to be honest. The solutions provided in the...

1

votes

1

answer

99

Views

### Don't understand how method “delete” work in linkedlist

please help me to understand how do method delete(with specify value) work?
I understood everything except this point.
I wrote method delete but don't understand how changing field next in Link "previous" weigh with Link first, I know that the next Link will be missed, but this Link also will be mis...

1

votes

1

answer

119

Views

### Iterative approach seems slower than recursive implemetation(coin change)

The problem from uva OJ
my solution with recursion
#include
using namespace std;
#define garbaze 0
//number of ways changes can be made
int coins[] = {garbaze,50,25,10,5,1}; //order does not matter//as in the //count_ways... function we are returning
//0 if which_coin_now is

1

votes

4

answer

643

Views

### Partial Ordered Comparator to Total Ordered Comparator

First of all: this is not a duplicate of the question Partial Ordered Comparator but rather builds on it.
My goal is to sort a list of objects (e.g. [2, "a", 1]) in-place such that after sorting no two integers are out of order.
For this, I used the implementation in this answer with the following p...

0

votes

0

answer

4

Views

### using Jenetics library in android studio

Please I want to know how to use the Jenetics Genetic Algorithm library in android studio. I am working on an interior design app using sceneform and a genetic algorithm.

0

votes

0

answer

14

Views

### I am writing a program that is supposed implement both insertion sort and merge sort with inputs of different sizes with inputs of different sizes

I am writing a program in c++ that is supposed implement both insertion sort and merge sort with inputs of different sizes. I am supposed to also compare the running times for different sizes of the arrays. The question is how can I change the size of the array dynamically I have been trying and ha...

1

votes

1

answer

729

Views

### Handling wildcard '*' operator in string matching using KMP-Algorithm?

How should I handle the case when the pattern to be matched contains the wildcard character, *, such as AB*C, which is present is the text, ABEFGCS (here * consumes characters EFG) using the KMP-Algorithm ?
What modification in the algorithm can solve this problem ?

1

votes

2

answer

1.8k

Views

### Given a number, return the count of numbers having non-repeating digits till that number starting from 1?

Let's assume it means two consecutive digits can not be the same.
If it means that all digits are unique the logic is very similar as well.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class solution {
public static void main(String[] args)...

7

votes

5

answer

235

Views

### Fast modulo 12 algorithm for 4 uint16_t's packed in a uint64_t

Consider the following union:
union Uint16Vect {
uint16_t _comps[4];
uint64_t _all;
};
Is there a fast algorithm for determining whether each component equals 1 modulo 12 or not?
A naive sequence of code is:
Uint16Vect F(const Uint16Vect a) {
Uint16Vect r;
for (int8_t k = 0; k < 4; k++) {
r._comps[k...

1

votes

1

answer

14

Views

### Make Greedy Algorithm Fail on Subset of Euro Coins

A greedy change-making algorithm is one that makes change by choosing the highest denomination of coin available until it reaches the amount of change it is trying to make. Surprisingly, this algorithm actually works for making change in the most efficient manner for US and Euro coin denominations!...

-1

votes

1

answer

34

Views

### Continuously count up then count back down? [on hold]

This is more an algorithm question but in a C++ language but I’m trying to wrap my head around how I would count up to 10 then back down to 0 in a continuous fashion.
0-1-2-3-4-5-6-7-8-9-10-9-8-7-6-5-4-3-2-1-0-1-2-3-4-5-6-7-8-9-10-9-8-7-6-5-4-3-2-1..
I’m guessing it would have to be two nested l...

-3

votes

1

answer

27

Views

### Prove or disprove that n^3=theta(n^2)

Just to clarify all the annoying, "this is your homework, we don't help with your homework" people. This is not my homework. This problem is in my professor's slides with no solution. So I am attempting to solve it my self. But I don't know if my solution is correct or not, I feel like it is though....

1

votes

1

answer

196

Views

### Use regex (javascript) to check if all letters in a string are consonants

The title is pretty self-explanatory; I want to develop an algorithm using regex that tests if a string contains ONLY consonants (in any order).
For example, if I had three strings to test:
1. ('happy')
2. ('apples')
3. ('sdfghjkl')
I would want the code to only return true for string number 3.
I th...

1

votes

1

answer

94

Views

### Solving a Recurrence Relation: T(n) = T(n-1) + n-1

I have been asked to solve that recurrence relation. I got the next solution: https://imgur.com/a/xWoTI40
So I decided to ask my teacher if it was right. He told me that it wasn't; and that this is the right solution: https://imgur.com/a/CGD0ta8
I'm totally clueless right now. The most I try to unde...

1

votes

1

answer

49

Views

### Implementing pairwise linear distance in Scala

Assume I have the following DataFrame in Scala Spark, where year year value is a String categorical representation, but there is an order in the data.
+-----+
|years|
+-----+
| 0-1|
| 1-2|
| 2-5|
| 5-10|
+-----+
I would like to create a resulting pairwise matrix, representing the "distance" for e...

1

votes

4

answer

73

Views

### Fastest way to compare each item in array with rest of array?

I have an array of items, and for each of the item in the array, I need to do some check against the rest of the items in the same array.
Here is the code I am using:
const myArray = [ ...some stuff ];
let currentItem;
let nextItem;
for (let i = 0; i < myArray.length; i++) {
currentItem = myArray[i]...

1

votes

1

answer

42

Views

### Maximum VALUE of interval which overlaps

This is a follow up question to this question:
Maximum no of overlaps of all time intervals
This is a known question of finding the most overlapping intervals given pairs of begin and end times.
I understand how to solve this question. I want to know how to solve a slight variation to the question....

1

votes

3

answer

60

Views

### ArrayList Integer - calculate average grade without considering extreme values

How to calculate average grades (arithmetic method) in such a way that the extreme grades (6) will be removed from list - and the smallest (1) will be removed from list?
import java.util.*;
import java.lang.*;
import java.io.*;
class ListOfGrades
{
public static void main (String[] args) throws jav...

2

votes

1

answer

27

Views

### Why Use A Doubly Linked List and HashMap for a LRU Cache Instead of a Deque?

I have implemented the design a LRU Cache Problem on LeetCode using the conventional method (Doubly Linked List+Hash Map). For those unfamiliar with the problem, this implementation looks something like this:
I understand why this method is used (quick removal/insertion at both ends, fast access in...