Tagged Questions
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.
2
votes
1answer
22 views
Using Insertion Sort return in sorted order the k smallest elements of an array
I'm prepping for software developer job interviews and reviewing algorithm questions. I can't figure out how to modify an Insertion Sort algorithm so that it returns in sorted order the k smallest ...
1
vote
1answer
29 views
How to know if a genetic algorithm is working?
It is important to benchmark your algorithm before applying it to a specific question. Otherwise, garbage in, garbage out. Having implemented a genetic algorithm (GA) with elitism, I have no idea how ...
1
vote
3answers
58 views
Using only Multiplication and Integers, how can I 'divide' a number?
The problem:
The API I'm using for building stacks in rapidweaver doesn't allow for division or floats, but I essentially want to divide a number by another number.
The relevant rules of the API:
...
2
votes
3answers
39 views
Dynamic pruning of a tree
My problem is this: I want to find all n length combinations of m possible digits such that the average of the digits is greater than a threshold value X.
For example, say length n=3 and digits are ...
0
votes
0answers
32 views
Calculating Day of the Week for any Date in C [duplicate]
I'm having trouble calculating the day of the week for a given date in C using the specific algorithm below. The function takes the day, month and year from the user then calculates a number from that ...
0
votes
1answer
45 views
Fast algorithm to count the number of 1 for binary number [duplicate]
If I have binary number 0111000111111,
Is there any fast algorithm to count the number of 1 ?
If 0111000111111 is a string(e.g "0111000111111")
Is there any fast algorithm to count the number of 1 ...
2
votes
3answers
23 views
How to create balanced groups
I have a game which can be played by groups of users competing with each other. The number of such groups is very small, under 10. The number of players is thousands.
When a user buys a ticket, a ...
0
votes
0answers
34 views
Array sorting using presorted ranking
I'm building a decision tree algorithm. The sorting is very expensive in this algorithm because for every split I need to sort each column. So at the beginning - even before tree construction I'm ...
0
votes
1answer
60 views
How to use C++ std::sets as building blocks of a class?
I need a data structure that satisfies the following:
stores an arbitrary number of elements, where each element is described by 10 numeric metrics
allows fast (log n) search of elements by any of ...
-3
votes
0answers
27 views
Algorithm for a Voucher program with four banks
Hello everyone i am making a school work and i need an algorithm to implement on a program
It uses vouchers to tell persons turn
It needs to use Qeueus
Bank A
Bank B
Bank C
Bank D
/* This is just ...
0
votes
0answers
18 views
why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm
We know Bellman Ford is an algorithm to find the negative cycle.
And here is the algorithm for Bellman Ford
Input: Given a graph G(V,E) and w(e) is weight
Output: Return Yes if negative cycle exists.
...
0
votes
0answers
25 views
Combination Optimization for Increasing Precision
I'm looking for a suggestion/ approach to the following problem:
I have a list of phrases that have been tagged by hand as either an adjective phrase
or a verb phrase. My program will identify what ...
-6
votes
2answers
48 views
Which Big-oh notation will be faster O(nloglog(n)) or O(n)?
I was reading about primes between two integers and I saw that sieve of eratosthenes time complexity is O(nlog(log(n))) where as normal sqrt(n) check takes O(n*sqrt(n)/logn) which is almost ...
-4
votes
0answers
24 views
Algorithm to calculate the probability of reaching the winning state in a finite state machine [on hold]
I would like to write an algorithm in Java to calculate the probability of reaching the winning state of a finite state machine, where an array of any number of coins can be entered at random.
The ...
0
votes
0answers
14 views
why getting segmentation fault in spoj-GSS1? [on hold]
http://www.spoj.com/problems/GSS1/..in this problem i am getting segmentation fault but i can't figure it out and as well as is my code is the correct solution for this problem..i am little bit ...
-5
votes
0answers
16 views
Step by step, from idea to the physical app [on hold]
Huge question which I have trouble to find an answer to.
Lets say I have an app idea. And I want to bring that idea into an app.
What are the steps? Request for proposal, design, algorithm, UML?
And I ...
android
3
votes
4answers
71 views
Amazon: Water collected between towers
I recently came across an interview question asked by Amazon and I am not able to find an optimized algorithm to solve this question:
You are given an input array whose each element represents the ...
-3
votes
0answers
22 views
best reference for algorithms for a beginner [on hold]
I'm recently starting to read/design/try to understand an algorithms. In simple I want to learn algorithms.
Previously when i started Java i used the below book as a reference to learn Java.
Head ...
1
vote
2answers
25 views
Segment tree with lazy propagation for multiple of 3
Abridged problem: You're given an array of n elements, initially they are all 0.
You will receive two types of query: 0 index1 index2, in this case you have to increase by one all elements in range ...
0
votes
1answer
22 views
Would it be worth creating an open CL version of my abstract algebra library?
I'm making an abstract algebra library in Python, and one of the things it does it takes the Cayley table (think of it as an abstract "multiplication" table, which doesn't have to obey the standard ...
0
votes
1answer
33 views
How to efficiently find the ideal column count for strings of a certain width?
I have n strings s1, s2, …, sn that I want to display in m columns on a terminal. Each column i has a certain width wi which is equal to the width of the longest entry in that column. Between each ...
-1
votes
0answers
16 views
Color quantization. BIRCH algorithm. Implementing a CF tree
I am trying to implement the BIRCH algorithm using matlab. But first, I need to fully understand its steps.
I have this 'intro' and a description involving steps.
BIRCH algorithm is used to cluster ...
-1
votes
0answers
13 views
Calculating the normal of a point on a heightfield
I have a spherical heightfield, defined by a function f(x, y, z) which returns the distance from the origin of the surface of the heightfield of a line which passes from the origin through (x,y,z).
...
0
votes
2answers
32 views
books / ways to learn data structures and algorithms? [on hold]
I'm a self taught Ruby on Rails engineer, and I'm looking to improve my CS understanding. However, most books about data structures and algorithms are written in Java/C/C++/etc, which I don't know. Is ...
0
votes
5answers
56 views
Python, work with list, find max sequnce length
for example test_list:
test_list = ['a', 'a', 'a', 'b', 'b', 'a', 'c', 'b', 'a', 'a']
what tool or algorithm i need to use, to get max sequences count, for this example:
'a' = 3
'b' = 2
'c = 1
0
votes
2answers
26 views
How to determine if locking order is in conflict
If I have empirical data on what locks were acquired in what orders by which thread and line of code, how can I then use that data to determine if locking order has deadlock potential?
l = lock
u = ...
11
votes
5answers
720 views
Prove a random generated number is uniform distributed
I was asked this question in an interview.
Given a random number generator to generate a number between [0,N), how
to prove this number is uniform distributed.
I am not sure how to approach ...
0
votes
2answers
45 views
Dynamic Programming: Find possible ways to reach destination
I'm trying to solve this problem, O(N^2) solution is simple, O(N) is possible, but I cannot think of how. Here's the question:
There are N cities and N directed roads in Steven's world. The cities ...
0
votes
1answer
19 views
Partial sorting to find the kth largest/smallest elements
Source : Wikipedia
A streaming, single-pass partial sort is also possible using heaps or
other priority queue data structures. First, insert the first k
elements of the input into the ...
8
votes
5answers
86 views
Removing runs from a 2D numpy array
Given a 2D numpy array:
00111100110111
01110011000110
00111110001000
01101101001110
Is there an efficient way to replace runs of 1 which are >= N in length?
For example, if N=3
00222200110222
...
2
votes
1answer
27 views
Decompose a network into components with equal number of vertices
I need to decompose a simple graph into components with equal fixed number of vertices.
For each component, all the vertices should be connected.
For example, for the network above, if we ...
-5
votes
1answer
59 views
Computing the overtimepay is my formula correct?
An employee is paid at a rate of 9.73 per hour for up to 40 hours worked per week. Any hours over that are paid at the over time rate of 1.5 times that.
My algorithm for this statement "Any hours ...
0
votes
2answers
46 views
Sorting coordinate points into paths
I am given a set of coordinates. The order of the coordinates are somewhat random, but the coordinates are clustered togheter to form different zones. I am struggling to create an algorithm to create ...
1
vote
2answers
131 views
In how many ways you can count till N using the numbers <= with N [duplicate]
in how many ways you can sum the numbers less or equal with N to be equal with n. What is the algorithm to solve that?
Example:
lets say that we have
n =10;
so there are a lot of combinations but ...
-5
votes
2answers
69 views
Find Difference Between Two Dates C
I am trying to take one date away from another in C and find the difference between them in days. However, this is much more complicated than it first appeared to me as I obviously have to allow for ...
0
votes
0answers
8 views
Does Kademlia iterativeFindNode operation store found contacts in the k-buckets?
Following the Kademlia specifications found at XLattice, I was wondering the exact working of the iterativeFindNode operation and how it is useful for bootstrapping and refreshing buckets. The ...
-2
votes
0answers
15 views
How to improve the pedometer results of step detection in android(not kitkat 4.4)?
I am trying to use the pedometer step detector (https://github.com/bagilevi/android-pedometer/blob/master/src/name/bagi/levente/pedometer/StepDetector.java) but not getting good results . So what i ...
5
votes
2answers
159 views
STL Efficient data structure for sparse data lookup
Situation:
Given some points with coordinate (x, y)
Range 0 < x < 100,000,000 and 0 < y <100,000,000
I have to find smallest square which contains at least N no of points on its edge ...
0
votes
2answers
20 views
How to test algorithm performance on devices with low resources?
I am interested in using atmel avr controllers to read data from LIN bus. Unfortunately, messages on such bus have no beginning or end indicator and only reasonable solution seems to be brute force ...
0
votes
1answer
40 views
order list of Lat long vertices to form a polygon in C#
I have list of Lat long that form a polygon around a center point. I would like to get ordered List of Lat-Long clockwise so as to connect Lat-Long Vertices in that ordered list and form non-convex ...
1
vote
2answers
30 views
Finding Nearest Node for Each Node
I have 2 sets of nodes - Set A and Set B. Each set is of size 25,000.
I am given a percentage (lets say 20%). I need to find the minimum distance such that 20% of the nodes in Set A are within that ...
0
votes
0answers
32 views
Programatically creating a triangle grid from centerpoint on graph
Im going to try to explain this as best as I can.
I have a centerpoint defined on a canvas element where I am using Kinetic JS to draw triangles.
What I want to do, is create an array of coordinates ...
1
vote
2answers
59 views
Is it possible to use Dijkstra's Shortest Path Algorithm to find the shortest Hamiltonian path? (in Polynomial Time)
I've read that the problem of finding whether a Hamiltonian path exists in a graph is NP-Complete, and since Dijkstra's Shortest Path Algorithm runs in Polynomial Time, it cannot be modified to find ...
3
votes
1answer
40 views
Just as there are cache oblivious and cache optimal algorithms, are there seek optimal algorithms?
Do cache (oblivious|optimal|aware) algorithms typically consider seek time in their model. If not are there examples of models that do consider seek time, and are there analysis of algorithms in this ...
0
votes
2answers
46 views
ACM: Create pattern given puzzle shape
I'm preparing for the ACM competition in my country and I'm pretty stuck with this problem, I don't know what algorithm to use either...
The problem is:
Given a puzzle pattern you need to tell if it ...
3
votes
1answer
40 views
What is the name for this special case of the Travelling Salesman involving dynamic edge costs?
This is a modeling / taxonomy question. Is there a name for this type of problem?
I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough ...
-2
votes
0answers
32 views
How to convert this seating algorithm to code? [on hold]
I am using PHP to generate a seating chart. The requirements are to make the table the most diverse mix of zip (postal) codes and job types possible. I select one person from the stack and then need ...
0
votes
1answer
20 views
Why is the state space the power set of the grid's dimensions? (edX CS 188.1x Artificial Intelligence)
I'm self-learning with the edX course CS 188.1x Artificial Intelligence. Since the course concluded a year ago, it is in "archive mode" and there are no teaching staff to help with the questions. This ...
-3
votes
0answers
34 views
Merge m sorted lists into one sorted list with worst case running time of O (n log m)
I'm prepping for software developer job interviews and have been working through algorithms questions. I'm stuck on a question involving heaps.
Give a O(n log m) time algorithm to merge m sorted ...
-2
votes
0answers
49 views
Determining whether two documents are the same [on hold]
Suppose I have a database entry for a user who has written a document. For instance, [name: "John Smith", title: "Article Matching: A Document"].
For each article a user has, I also have a short list ...
