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.
1
vote
1answer
14 views
Checking if given preorder traversal is valid BST
I was writing code to check from preorder traversal if it is a valid BST.
e.g preorder traversal 1,2,4,3,5 is valid BST while 1,3,4,2 is not
I built whole tree from that preorder sequence and then ...
0
votes
0answers
16 views
Parsing an ad-hoc tree
I have a flat file that appears as follows:
Soccer
+Team:US
++Shirt:Red & White Stripes
++Shorts:Blue
++Players:17
+++Active:11
++++Forward:2
++++Midfield:4
++++Defense:4
++++Goalkeeper:1
...
0
votes
0answers
14 views
Chinese character recognition
For research purpose, I want to develop a web app using node JS that recognize mandarin character and it can also recognize what I write in a provided canvas (html 5).
So what should I use for the ...
0
votes
1answer
24 views
different binomial coefficient algorithm's efficiency compare
I've compared two algorithms to calculate binomial coefficient C(n, k) as bellow, #1 uses formula to calculate, #2 uses dynamic programming.
#include <stdio.h>
#include <sys/time.h>
...
-1
votes
0answers
24 views
Permutations using a 2D array
I need to write a short program that is able to output the permutations of the input which can be one of the following integers: 1, 2, 3, 4, 5 or 6. I need to store the permutations of in a 2D array ...
0
votes
0answers
21 views
Finding Shape Outlines Within a Bitmap?
So, I've been working out this problem for a few hours now, hopefully there's nothing obvious I am missing. I have a bitmap file and I would like to create a List such that the list just contains ...
0
votes
0answers
29 views
Aren't there any faster algorithms to solve cubic equations?
I'm looking for a fast algorithm which solves cubic equation. Complex roots are not needed.
Currently, I'm using the algorithm written in the following URL. Aren't there any faster ones?
...
0
votes
1answer
14 views
Finding the running time when it comes to constants?
I am attempting to answer some questions that I've come across. I have been watching some videos regarding running time of algorithms. From what I understood, you have to count each operation in an ...
1
vote
1answer
23 views
Find the smallest subset of overlapping intervals
Consider a question to find a minimum dominating set of an interval graph. In the context of interval scheduling, it is converted to the question below:
There are multiple intervals which may or may ...
0
votes
1answer
42 views
How to solve this programming contest exercise
I stumbled upon this algorithm question, I couldn't get any better approach than brute force, can someone guide me please?
Given a M * N grid of characters (A,B). You are allowed to flip any
...
-1
votes
0answers
37 views
a hash algorithm that return unique value and 16 or less Char string
Hello guys: I am trying to use some kind of algorithm to give me a unique value for a string value. For a different string i want different hashed value <= 16 characters long. I have checked some ...
0
votes
2answers
15 views
How to best get the data out of a lookup table
I have a few product lines with products that have various features. I have a list of drawings made for each product, and below is a sample of what the product lines, products, and features are ...
0
votes
0answers
21 views
Integer Time Series compression
Is there a well known documented algorithm for (positive) integer streams / time series compression, that would:
have variable bit length
work on deltas
My input data is a stream of temperature ...
0
votes
1answer
48 views
Iterate through all possible values in array which give 1 in sum
I have an array of 4 values. For example: [0.1, 0.1, 0.5, 0.3] (sum of elements = 1)
How to iterate though all possible values with increment 0.1 to get in sum 1.
example:
[1.0, 0.0, 0.0, 0,0]
[0.9, ...
1
vote
3answers
53 views
Sorting an array which is already sorted, Except one element which is out of order
I was preparing for a competition and came across this question, which I can't comprehend.
Consider a set of 'n' elements in an array, which is sorted except for one element that appears out of ...
0
votes
1answer
17 views
Server side algorithm for Web based Polling/Voting System [on hold]
Background:
I am implementing a web based polling system, the system lets users create Polls with a question and some options. The other users can cast their vote for any of the choices. The question ...
0
votes
1answer
47 views
Resolve this java algorithm for Dice for Risk game
like in risk game I have to roll dices, but I don't want to use the Random.nextInt() method for each roll.
For some reasons I have already the result of the attack, and I want to simply generate the ...
0
votes
2answers
38 views
Finding the merging node of two linked list?
I have gone through this link where accepted
answer depict below algorith to find merging node
1) Traverse the two linked list to find M and N.
2) Get back to the heads, then traverse |M - ...
-2
votes
1answer
42 views
Caesar Crypher/Decypher Program. C++
I'm working on a school project, my project is a Cypher and Decypher program that works with Caesar Algorithm.
My program has to have the following characteristics:
The program must give the user ...
1
vote
1answer
36 views
Find the length of the longest contiguous sub-array in a sorted array in which the difference between the end and start values is at most k
I have a sorted array, for example
[0, 0, 3, 6, 7, 8, 8, 8, 10, 11, 13]
Here, let's say k = 1 so the longest sub-array is [7, 8, 8, 8] with length = 4.
As another example, consider [0, 0, 0, 3, 6, ...
0
votes
2answers
23 views
Find best label position group of coordinates/polygon
I have a sitiation where I want to place a pointer on a map.
The problem is how to calculate the position of this pointer in vb.Net.
I can have 3 sitiations:
A single point
A way point, 2 or more ...
4
votes
2answers
146 views
Make a one sequence if possible [on hold]
A sequence of integers is a one- sequence if the difference between any two consecutive numbers in this sequence is -1 or 1 and its first element is 0.
More precisely: a1, a2, ..., an is a ...
0
votes
0answers
11 views
R & Partykit: Creating decision tree based on own conditions [on hold]
The available CHAID package gives me limited use of the algorithm, therefore I decided to create the algorithm myself. I arrived at the point that the algorithm is working, but I have no clue on how ...
1
vote
0answers
21 views
Highlight the difference between two XML documents, starting by structure-difference
(some examples here are PHP but the question is generic)
A XML document, essentially, is a specialization of a MIME's text/plain, a human-readable string. With DOM we can also normalize the two ...
1
vote
1answer
43 views
kth smallest element with duplicates
Have a problem where i am ask to write a program to find the kth order statistic of a data set consisting of character and their occurences. For example i have a data set consiting of B,A,C,A,B,C,A,D; ...
0
votes
1answer
33 views
Suggestions for an algorithm which requires math functions
I need some suggestions,here is my problem:
I have about 800 function names that I need to associate with a list of data couples 'a' and 'b' with 'a' and 'b' between 0 and 10 ,these couples must be ...
0
votes
2answers
58 views
Algorithm suggestion - search on number list
I have 7 digit number list. And I am required to perform search operation on the list. Input of program will be like this 5xx9xx1 . Minimum 3 digits will be known. And index of known digits are not ...
0
votes
4answers
68 views
Game score simple alghoritm
Depend of the percent completion level of my game i will display some messages, i made up this pseudo code it probably doesn't work is just for you to get the point.
What would it be a "pro" way of ...
-3
votes
1answer
42 views
Finding a minmuim swaps in an array
I have found a problem on a net for generating some sequence.
A = [A1, A2, ..., AN]
and
where A1 < A2 < ... < Am > Am+1 > ... > AN for some index m, with m between 1 and N ...
1
vote
2answers
27 views
equalence testing of n objects
Assume that we are given 'n' objects and a subroutine that takes two inputs and says if they are equivalent or not (e.g. it can give output as 1 if they are equal).
I need to come up with an ...
0
votes
1answer
25 views
MATLAB how to output a matrix in a parfor circulation?
I normally replace the for in MATLAB code with parfor, but all the 2 dimension matrix did not work.
Code
parfor k=1 : n
sonic = data1((1+(k-1)*2400):(2400*k));
signal1 = (sonic(1:2400))./100;
Ar = ...
2
votes
1answer
34 views
given array find all combinations of elements that give sum
I've been asked the following question in an interview. Although I've answered it using an n-ary tree, I've been told it wasn't "good enough". So, I'm curious, what's the optimal solution for it.
...
0
votes
0answers
15 views
CLRS 2-1 solution?
So I'm doing self study with this book and was doing the same problem stated in this thread:
Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is ...
0
votes
5answers
91 views
Simplify bool function
I wrote this function that returns true/false. My head is stuck on this return algorithm and I can not manage to simplify it. Can you please help me? I know It can be simpler regarding return values ...
0
votes
0answers
25 views
How can I find contiguous areas of color in SVG?
In my process I need to start with an SVG image made exclusively by lines, similar to the starting point of a color-by-numbers drawing. Shapes in the image have no fill, but there is no guarantee that ...
0
votes
1answer
41 views
Linear-time constant-space permutation generator
Is there a generator function f(i,j,n) that returns, in deterministic constant time and space, the ith element (0<=i<n) of the jth permutation (0<=j<n!) of the first n integers? If so, how ...
0
votes
2answers
32 views
Solving recurrence equations for a given algorithm with FLOOR
Hello I am completely lost as to how to find the recurrence equation related to the given algorithm.
C(i, j, x)
if i=j then
if A[i] = x
return YES
else
return NO
...
1
vote
1answer
23 views
Solving non-homogeneous linear recurrence relation in O(log n) time
I saw this question about solving recurrences in O(log n) time with matrix power: Solving a Fibonacci like recurrence in log n time
The recurrence relations in this question are homogeneous.
Is ...
-2
votes
0answers
24 views
Users don't get program making best guess [on hold]
I've inherited a program whose task is to make the best guess at a number of variables associated with a product based on some known information. We have a test dataset based on historical data, and ...
4
votes
2answers
176 views
Father, two sons, 999 paintings
This is a question for a job application:
"A father has two sons and 999 paintings. Each painting has a different value: first is worth 1, second is worth 2 and so on, until the final painting is ...
1
vote
2answers
33 views
Tight asymptotic of brute-force algorithm for creating matrix
Consider the following problem:
Given an array R of n elements, construct a matrix M such that M[x,y] = ∑k=x...y R[k]
I need to calculate the tight asymptotic bound... e.g. big-theta(algorithm)
I ...
0
votes
1answer
30 views
Is this a proper algorithm that would accept graph G if it's connected?
I wanted to ask and see if this suffices in creating a polynomial time algorithm given a Graph P? Just want to double check.
On input (P,u,v) where P is an undirected graph with nodes u and v:
...
0
votes
0answers
16 views
even/odd clas for a total count of data, using TOTAL number of results - Thymeleaf
Here is some code, I have to figure out when to make it two columned vs. four etc.
which I have to add columned data based on results in list (As the height of the nested div will be in a modal box ...
0
votes
0answers
15 views
Twitter timeline images: vertical alignment math/algorithm
This is more of a math puzzle, but I'm trying to adapt it to my PHP application
I have an app that tweets out images to a connected account
However Twitter doesn't show the whole image; only a part ...
0
votes
1answer
24 views
How to construct a Hamilton path from a complete directed graph
Given a directed graph.
Any 2 vertices are adjacent. The edge connecting a pair of vertices may be uni-directional or bi-directional.
How do I find a Hamilton path?
Side notes:
Wikipedia says "A ...
-3
votes
2answers
41 views
how to print the old result and the new result which makes the new result the old result
Today I had this crazy idea, I tried to make something similar to the SHA-3 algorithm and now I need to test it.
Example with MD5
If I encrypt the letters test with MD5 I will get: ...
-4
votes
0answers
31 views
Take all elements of a Queue Q2 and append it to the end of Q1 in Constant Time O(1)
I am given the following classes Queue<E>, LinkedQueue<E> and SinglyLInkedList<E>
I am allowed to make changes (I.e introduce new mutator methods in the above classes.
I have to ...
0
votes
1answer
9 views
Collision detection between two axis aligned boxes only on one side of a plane
I need to check a collision between two axis aligned boxes. One of these boxes has been "sliced" by a plane, and it should only collide on one side of this plane. How can I detect if the collision ...
0
votes
3answers
55 views
Calculating power function in logn time and constant space
This question I encountered while giving the interview.
Lets say I wanted to calculate power(x, n) which is x^n.
The best algorithm I know is calculating pow(x, n) in O(logn) time but that is a ...
0
votes
1answer
72 views
O(N*log(log(N))) algorithm for Codility's Peaks?
The task description is here: https://codility.com/demo/take-sample-test/peaks
It's also here: Codility Peaks Complexity
First, I tried solving this myself but was only able to come up with what I ...
