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.
0
votes
1answer
32 views
Python Bisection Search Logic Error- Returning Inaccurate Results
I am trying to solve the third problem on this MIT OCW assignment. It requires that you calculate the monthly payment needed to clear a given debt in one year using the bisection search method. I am ...
-4
votes
1answer
15 views
Alghorithm, help me with output
I have an algorithm :
def generate (last, cur):
if (cur>100):
print cur
return generate(cur, last+cur)
Then, I have two questions. What will this function print?
And, how to modify ...
0
votes
0answers
17 views
Algorithm challenge dynamic programming
Please find the question description in the image below
image URL: https://i.stack.imgur.com/2KWn2.png
Please help me with the algorithm.
It looks knapsack problem .. but there are differences
in ...
1
vote
0answers
14 views
When estimating worst-case execution time T(x,y) of an algorithm, should I count if statements?
When estimating worst-case execution time T(x,y) of an algorithm, should I count if statements?
def foobar(x,y):
result = 0
for i in range(x):
for j in range(y):
if self....
0
votes
1answer
9 views
Flowdroid's paper in PLDI'14
I recently read the paper about Flowdroid, but I got very confused with the algorithm of on-demand alias analysis.
When n is assignment in line 14, why construct d3 replacing rhs by lhs in d2, not ...
-1
votes
2answers
46 views
Divide an array element into consecutive sets and find the smallest sum
Let's say i have an array:
*the number is within the range 0-100
*the array length is within the range 0-10
*the size of each sets is within the range 0-3
int[] MyArray = {9,1,3,3,2,4,4,2,1,6}; //...
2
votes
1answer
36 views
How to implement a constraint solver for 2-D geometry?
I have a set of metallic sliding pieces which are constrained to the x and y axis in following way:
I would need to maximize the horizontal distance among all pieces constrained by the same slider ...
54
votes
7answers
24k views
How to understand the knapsack problem is NP-complete?
We know that the knapsack problem can be solved in O(nW) complexity by dynamic programming. But we say this is a NP-complete problem. I feel it is hard to understand here.
(n is the number of items. ...
1
vote
0answers
18 views
are there two known strings(contains displayable character only, ascii encoding) have same md5 hash
I know there is known pair of binary files which have the same md5 hash, but are there two known ascii strings (contains displayable chars only, contains only a-z A-Z 0-9 better) have same md5 hash?
2
votes
2answers
38 views
Algorithm - Implement two functions that assign/release unique id's from a pool
I am trying to find a good solution for this question -
Implement two functions that assign/release unique id's from a pool. Memory usage should be minimized and the assign/release should be fast, ...
-3
votes
0answers
20 views
Solutions to fair distribution programming problems
I have run into a wall since I attended a coding contest. I think this problem falls into the category of fair distribution, but I am not sure.
I am attaching the problem here.
I have come out with ...
-2
votes
0answers
14 views
I'm working on a code for an industrial engineering assignment. I must predict when to ship a product to a customer based on trends in our database
This is a matlab assignment based on data from MySQL. Help would be great! If you can help me with any specific part, let me know which part you are referencing. Hopefully someone can help me. Thanks ...
-3
votes
0answers
16 views
How to initialize a Candy Crush gameboard
It's an open-mind interview question with constraints:
appear to be random
no three-match at the beginning
must have a valid first move
3
votes
5answers
4k 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 ...
2
votes
2answers
27 views
Determine if we can obtain a target color by mixing colors from a list
Given a list of colors(RGB values) L and a color C, determine if we can mix 2 or more colors from the list L to obtain C. The colors from the list can be mixed in any proportion.
1
vote
2answers
49 views
Modify a binary search tree
I am trying to write a method for a binary search tree class to modify a balanced a normal tree which makes the tree have nodes only on one side.
From the order in which the elements are appearing in ...
-4
votes
1answer
18 views
Amazon Echo - Ask for an algorithm to avoid the background command
Amazon Echo - the algorithm to avoid the ambiguous background command from the voice record being played:
This is a hypothetical question based on the principle that it could happen: If one uses ...
4
votes
1answer
66 views
Newton's method program (in C) loop running infinitely
This code(attached with the post) in C uses Newton - Raphson method to find roots of a polynomial in a particular interval.
This code works perfectly fine for some polynomials like x^3 + x^2 + x + 1 ...
2
votes
0answers
38 views
+100
Mix two non-opaque colors with “hue” blend mode
I want to implement color blending as described in the W3C compositing and blending spec. (I'm doing this in JavaScript but the language shouldn't really matter for solving my problem.)
It worked out ...
0
votes
1answer
59 views
Sort a big number list (100k) as quickly as possible using limited operations [on hold]
I have two list : list A containing a set of random numbers and list B empty. I have to sort the list A.
I can make limited operations on these two lists like :
move the first element of list A or ...
89
votes
14answers
45k views
Explain how finding cycle start node in cycle linked list work?
I understand that Tortoise and Hare's meeting concludes the existence of loop, but how does moving tortoise to beginning of linked list while keeping the hare at meeting place, followed by moving both ...
-1
votes
0answers
17 views
How to apply k nearest neighbor on multiple set of data
I have few question regarding on how to apply k nearest neighbor on a large set of attributes , I did understand the logic behind it and what are the things that should be computed and calculated
So ...
18
votes
11answers
6k views
Check if the given string follows the given pattern
A friend of mine just had his interview at Google and got rejected because he couldn't give a solution to this question.
I have my own interview in a couple of days and can't seem to figure out a way ...
1
vote
1answer
36 views
List performance optimization
Is there any chance to optimise next line of code:
val adj: Array[ListBuffer[Int]] = Array.fill(n)( ListBuffer[Int]())
...
..
val sourceVertexes = inGraph.zipWithIndex.filter(v => a....
0
votes
2answers
32 views
Heuristics for the Asymmetric Traveling Salesman
I am using A* in order to solve the Asymmetric Traveling Salesman problem.
My state representation has 4 variables:
1 - Visited cities (List)
2 - Unvisitied cities (List)
3 - Current City (Integer)
...
0
votes
0answers
12 views
k edge-disjoint paths from v to u
If there exist k edge-disjoint paths from u to v in graph G, then does there exist k edge-disjoint paths from v to u in G?
As per my thinking it can have k edge disjoint path in the residual graph G' ...
1
vote
4answers
52 views
Algorithm to define pairs from a list
Christmas is coming: it is time to determine who is going to make a gift to whom. I'm looking for such an algorithm.
Taking a list (1 to 10) for instance, create random pairs ensuring that:
...
0
votes
1answer
35 views
Find max-size sorted submatrix using dynamic programming
i'm trying to solve a dynamic programming problem, consisting in having a matrix, find the max-size sorted submatrix.
I want to use dinamic programming to find the solution, but I don`t get the ...
0
votes
1answer
93 views
Decreasing Loop Interval by 1 in C/C++
Let's say I have 15 elements. I want to group them such a way that:
group1 = 1 - 5
group2 = 6 - 9
group3 = 10 - 12
group4 = 13 - 14
group5 = 15
This way I'll get elements in each group as below:
...
0
votes
0answers
23 views
Stable Marriage - pairs or couples? [on hold]
Should I use the name Pair for methods, classes and variables when solving Stable Marriage Problem or Couple? In the context of marriage, it is sounds normal to me (as a foreigner) to say "Married ...
-1
votes
0answers
27 views
Algorithm to sort users into teams (based on minimum/maximum number for each team)
I am trying to come up with an algorithm for sorting and assigning teams to a fixed number of users. The majority of algorithms that I've found assume the number of groups to divide by; I would like ...
25
votes
10answers
28k views
Fast algorithm for searching for substrings in a string
I'd like an efficient algorithm (or library) that I can use in Java to search for substrings in a string.
What I would like to do is:
Given an input string - INSTR:
"BCDEFGH"
And a set of ...
-3
votes
1answer
70 views
java:Adopting in algorithm?
Birthday probability problem
here is the algorithm which i follow, bit i still face problem. The algorithm is
To simplify the problem, we make the assumption that each day of the year (except ...
android
0
votes
1answer
31 views
Finding peak in a one dimensional array based on divide & conquer strategy [on hold]
I'd like to implement Divide & Conquer technique for finding a peak in a one-dimensional array. My code is based on this lecture:
def p1d(A,i,j):
m=(i+j)//2
if ((A[m-1]<=A[m]) and (A[m+...
2
votes
2answers
48 views
How do I delete lines from a file 'in-place' without creating a temporary file?
I wrote 3 separate test cases for a program that I was writing. Unfortunately I filled up my hard drive doing so, maybe about 300+ gbs. I'd like to take samples from each test case file, and delete ...
0
votes
3answers
40 views
Multiple edge weights single-source Dijkstra's Algorithm (updated) [on hold]
Updated:
I am currently working on small project, where I want to implement Dijkstra's Algorithm (single source) to find shortest path through multiple edge weights.
For instance, instead of just ...
-1
votes
0answers
35 views
Implement a data structure using RandomAccessFile java
I have the following problem to solve and I am going to tell you about my effort in a second.
Input is a tab-delimited file containing points on the genome. Each point is defined by
chromosome, ...
-1
votes
1answer
31 views
c++: Trying to save an image created to a .jpg file but the image won't open
I'm using c++ in visual studio and i have an algorithm that creates an image for the n-body simulation problem. the algorithm itself works however i need to store the image to be able to prove that ...
1
vote
1answer
11 views
The reason of calling heapify from the middle of the array when building a heap
When building the heap, we start calling max_heapify(A,i) from the middle of the tree, i.e. floor(n/2), until the root in decreasing fashion to maintain heap property. I've read some reasons behind ...
1
vote
5answers
11k views
Implement “For loop” on prolog
How to Implement using recursion and cut-off cycle of the counter
(like for i: = 1 downto N do <operator>) ?
0
votes
2answers
42 views
Creating a circular arc tangent to two curves with specified radius
The operation mentioned in the title is common in many Computer Aided Design (CAD) softwares such as AutoCAD, where it is called fillet. However, I found it is really difficult to implement this ...
2
votes
1answer
257 views
Complexity in tilde notation of nested for loops
How do I find the complexity in tilde notation of the following algorithm:
for (int j = 0; j < N; j++) {
for (int k = j + 1; k < N; k++) {
array[k] = array[j];
}
...
0
votes
3answers
35 views
Array Index Out of Bounds Exception Merge Sort Procedure Java
I was implementing this merge sort procedure but it's throwing out of bounds exception and i can't figure why it's doing so I checked all the array parameters are satisfied but its still having the ...
0
votes
2answers
105 views
how to calculate the time complexity of kurskal's algorithm which is may be O(E log E) = O(E log V).?
Please tell me the procedure that how to calculate the time complexity of Kruskal's theorem?
I know the algorithm of Kruskal algorithm but didn't know the pseudo code and calculation of time ...
0
votes
1answer
33 views
Match an abbrevations like “ccd” , “bbq”, “phd” etc to most similar string from a set of strings
I have a list of abbrevations like "ccd" , "bbq", "phd" etc.
For example let's take "bbq" , we try to map this abbrevation to a list of strings,
Barbeque Nation - The actual answer should be this
...
0
votes
0answers
11 views
How Soukup's algorithm actually works?
Can anyone please explain me how Soukup's algorithm actually work? I tried to google it but i didn't find any satisfactory solution. I am unable to understand how DFS is working in this algo and how ...
2
votes
3answers
70 views
How to adapt Dijkstra's algorithm to work with weighted graph
This piece of code works to implement Dijkstra's algorithm for unweighted graph. What should I change to work with a weighted graph? The edges of my graph are double values, there's any chance to use ...
-1
votes
1answer
24 views
What is the time complexity for given snippet?
for i = 1 to n do
for j = 1 to i do
for k = 1 to j do
What is its time complexity in terms of 'n'?
0
votes
0answers
9 views
Shortest-path algorithm: multiple source, closest destination
Algorithms like the Bellman-Ford algorithm and Dijkstra's algorithm exist to find the shortest path from a single starting vertex on a graph to every other vertex. Their multiple source version can be ...
0
votes
4answers
51 views
javascript algorithm to auto fit multiple images
I was looking for a function which would take the overall width, max height, min height parameters as the input and fit multiple images in the given overall width adjusting their width.
So for an ...
