In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning.

learn more… | top users | synonyms (1)

0
votes
1answer
937 views

Removing occurrences of characters in a string

I am reading this book, Programming Interviews Exposed by John Mongan et. al and in chapter 6 they are discussing removing all instances of characters in a src string using a removal string, e.g. ...
3
votes
2answers
6k views

Which way is more efficient for getting the space count?

I have just started reading Cracking the Coding Interview. One of the problems (specifically 1.4) after solving and then looking at the answer made me question the way it is done and decided to post ...
3
votes
1answer
363 views

How can I rewrite this linked-list manipulation as tail-recursive?

Given a liked list, I'd like to swap every pair of nodes as follows: input: a-b-c-d-e-f-g output: b-a-d-c-f-e-g If there's an odd number of nodes then the last node is tacked on as-is. This should ...
4
votes
2answers
394 views

Is this the right strategy to convert an in-level order binary tree to a doubly linked list?

So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question. This is the strategy I ...
4
votes
3answers
614 views

Finding an object on an infinite line

Question: There is an infinite line. You are standing at a particular point you can either move 1 step forward or 1 step backward. You have to search for an object in that infinite line. Your object ...
2
votes
2answers
97 views

Shape-Checking algorithm

I normally have a very intuitive approach to an efficient algorithm. In essence, I know what the bottleneck is, and how I can improve the algorithm. However, I'm now stuck and I am in the need of some ...
6
votes
0answers
250 views

Algorithm/data structure to answer “what recipes can I make with this set of ingredients?”

Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ...
2
votes
3answers
59 views

Find all circles that cover one point

I'm not sure if I've been searching using the wrong keywords, but I've tried so many different ways of wording this and I can't find a relevant answer. Basically, given a set of circles defined by ...
5
votes
1answer
230 views

Kth selection routine - Floyd Algorithm 489

I have recently come across a promising Kth selection routine that reportedly outperforms quickselect the Floyd, Rivest Select routine. This Wikipedia article provides a pseudocode version which I ...
1
vote
1answer
57 views

Need semi-efficient algorithm for 3-dimensional increasing sequence

I have a set of puzzle challenges for a prototype jigsaw puzzle kit, similar to commercial products offered by Thinkfun and Popular Playthings. I have a candidate list of 300 puzzle challenges and ...
0
votes
1answer
93 views

Measure and locate areas of similar value in an image

I saw this picture online and wanted to see if I could create an algorithm to give ordinary images an effect like this: http://justinlivi.net/wp-content/uploads/2011/01/Living_In_Digital.jpg My idea ...
16
votes
3answers
588 views

Is it possible to write a generalized string reverse function that works for all localisations and string types?

I was just watching the Jon Skeet (with Tony the Pony) presentation from Dev-Days. Although "write a string reverse function" is coding interview 101 - I'm not sure that it's actually possible to ...
2
votes
1answer
42 views

Best-matching comparative values using all items in array

I have two arrays of objects (items) in the exact same format. Each item represents a wager, and each array represents one of two outcomes for that wager (ex: Team A vs Team B). Both arrays look ...
3
votes
1answer
79 views

Algorithm to compute k-permutation without repeating and no duplicates

I have a set of integers, for example 1..20 and I want to get all possible combinations of that set drawing 5 numbers. So each combination has 5 numbers from that set of integers. But I don't want ...
-1
votes
2answers
74 views

Algorithm involving a stack for this problem [closed]

I'm having exams later this week and I literally don't have any clue on how to solve this question: You're given a row R1 of the following shape a1, a1, ..., R2, a1, ..., a1 R2 is a row of the same ...
1
vote
2answers
62 views

Given an array of n bits, how to generate every permutation with i 1's and n-i 0's?

It's simple enough to brute force a collection of strings and then filter for every occurrence with the required count of 1's. As n increases the number of possible permutations becomes very large, ...
0
votes
4answers
110 views

Pick highest score sum, but at least X from each region

Can you think of a solution to the following seemingly simple algorithmic problem? I am given a list of data points with scores and regions they belong to: [(9, A), (8, B), (7, A), (3, C), ...]. ...
3
votes
3answers
107 views

Find a line that is closest to scattered points

I came across the below interview question on Glassdoor: A scatter graph of points on a page, draw a horizontal line across the page such the the perpendicular y distance to the line from all ...
18
votes
5answers
4k views

Advantage in being the first to copyleft a new algorithm? [closed]

Say I have created a new (DSP) algorithm. Will I have some advantage if I open source the algorithm under copyleft licence (GPL etc.)? From what I know about licensing this should lock people out from ...
1
vote
0answers
76 views

Reversing dithering algorithms?

I was trying to make an implementation of the Floyd-Steinberg dithering algorithm in Python, and I was wondering, since Bitmaps files store their data starting from the bottom-left corner, would it be ...
1
vote
2answers
378 views

How can I rank teams based off of head to head wins/losses

I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then ...
-1
votes
0answers
28 views

Can I use a 3-dimensional simplex noise implementation to generate noise over a spherical surface?

Say, I want to generate noise over a sphere. I want to do this to procedurally generate three-dimensional 'blobs'. And use these blobs to generate low poly trees, somewhat like this: Can I ...
1
vote
1answer
888 views

Flowgraph Aptitude question

I recently looked a Flow-Graph question. Consider 8 boxes with following values Box 1 = 2 Box 2 = 7 Box 3 = 2 Box 4 = 1 Box 5 = 5 Box 6 = 7 Box 7 = 1 Box 8 = 4 Now follow the instructions: Put ...
5
votes
1answer
126 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
2
votes
0answers
25 views

Project a piece of image cut by N-vertex shape to a different N-vertex shape

I have an N-vertex shape that I cut out from an image, and I want to project it onto another shape with the same amount of vertices, but different. So, the image will get changed inside the ...
-1
votes
1answer
201 views

Program to look at the first say 5 characters of a word and return a string if that string is actually the first 5 characters of a word?

For example, say I have a string and it has the letters: RDNAL This is not an actual English word or it doesn't start an actual english word, so the program would skip this string and would avoid ...
2
votes
2answers
125 views

“Hand written” recursive descent parser with “catch all” rule

I'm trying to write a (scannerless) recursive descent parser with a "catch all" rule for the following "Mustache template" grammar (simplified here): content : (variable_tag | section_tag | ...
2
votes
1answer
85 views

Image segmentation - show or hide clusters

I'm trying to make a small program in c#, that will downsample image to specified amount of colors (using K-means). Then, user will be able to hide\show colored areas(clusters) in image. I've ...
0
votes
0answers
47 views

Matrix column dimension containing '>' in C [migrated]

I found a small C function that given a matrix, it removes the line 0 and the column 'i' and then put it in another matrix, everything in order to calculate the determinant of the simplified matrix , ...
4
votes
2answers
276 views

How to extract the active code path from a complex algorithm

I have been puzzled lately by an intruiging idea. I wonder if there is a (known) method to extract the executed source code from a large complex algorithm. I will try to elaborate this question: ...
0
votes
1answer
62 views

How can I map a number of points of a polygon to matching points of a larger rectangle?

Suppose I have 2D polygon image and a larger 2D rectangle image and that I have a collection of points for each that I want to align. For Example the polygon has point collection: [PA(a, b), PB(c, ...
6
votes
2answers
132 views

Algorithm for comparing hundreds of similar, but not identical documents

I have seen similar questions about text comparison, but none on such a large scale. I have a client with two sets of recordings of speeches, 250 and 550 recordings each. Each of the recordings in ...
0
votes
1answer
183 views

Min weight feedback edge set with DFS?

Exercise from The Algorithm Design Manual 6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. ...
1
vote
1answer
99 views

Sorting a large number of unknown items with multiple stacks

Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it. Problem: I have a single stack already populated with several thousands of unknown ...
2
votes
1answer
106 views

Closest Point to Moving Target

I have a target which is constantly moving, and only its current position is ever known. I also have about one hundred objects surrounding it, and for each of these only the current position is ...
5
votes
1answer
382 views

Does anybody recognize this scheduling problem? Is there an algorithm for it?

Consider the following problem: Description: There are n jobs J1...Jn with cycle times C1....Cn. Find a time quantum and a scheduling table considering that: any element of the table contains at ...
0
votes
3answers
158 views

Best algorithm to determine whether two arrays can be the same in a circular queue

I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example: Array1 = ['A','B','C','D'] Array2 = ...
0
votes
1answer
57 views

hashing algorithm to check inclusion in a set

The problem I am trying to solve is to validate if a username is already used before allowing an admin user to create a new user with that username. Currently I am doing an ajax request to check if ...
1
vote
2answers
205 views

Algorithm to detect if a word is spelled correctly

I am trying to develop a javascript spellchecker that doesn't use a dictionary, and can correctly, given a single word, detect if a word is spelled correctly or not. Right now, I just have a list of ...
0
votes
0answers
34 views

Algorithms for Academic Auditing?

I am trying to come up with an algorithm to perform academic auditing for college students. I never took an Algorithm course, any help is appreciated. Input: Degree requirements, Additional program ...
1
vote
3answers
264 views

Check distance between all elements in a list of numbers in O(n*lg(n))

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
2
votes
0answers
25 views

Optimizing trigram look ups with wildcards

I am working on creating a spell-checking service for Android (note: this is a platform- and language-neutral question) for Asturian, a minority Romance language. We're using hunspell as the base but ...
2
votes
1answer
162 views

What algorithm-family or problem-space description fits? Industrial process feeding ingredients to process

Our process continuously feeds (normally <= 8) ingredients from a choice of hundreds, using 3 feeders only. So if ingredient count X is > 3, 3 through X are stirred together in a batch process and ...
3
votes
0answers
183 views

Automatic Appointment Conflict Resolution

I'm trying to figure out an algorithm for resolving appointment times. I currently have a naive algorithm that pushes down conflicting appointments repeatedly, until there are no more appointments. ...
-3
votes
4answers
112 views

Time complexity of this loop [duplicate]

Is the time complexity for this loop O(n) or O(log n)? for(i=0;i<n/2;i++){} I am thinking, the time is proportional with the input size.
3
votes
3answers
157 views

What is the most efficient way to find a set of locations within a radius of a certain point?

Imagine a dataset of all the restaurants in the US (similar to Yelp, etc), how would you return a set of restaurants within a certain range of a particular zip code. (Assuming you have already a ...
0
votes
3answers
65 views

Algorithm to generate parallel path inside polygon

A path is defined as a list of 2D points (x,y) (and may be open or closed). Given a path p, what is an algorithm which generates a path p' which is "inside" p and at constant offset to p i.e. each ...
3
votes
3answers
134 views

How to determine if set of ordered coordinates form a simple curve?

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science. Eventually this seemed more suitable. Anyway, some background first: A closed curve, is ...
2
votes
2answers
196 views

How to iterate between these elements

I have an array of elements: int[] elem = new int[] {A, B, C}; I need to calculate the sum of ALL the combinations of those elements, where only some of the elements can be optionally selected. I ...
1
vote
2answers
248 views

Looking for the name of an algorithm (or technique)

I am searching for an article on the net which I can't find anymore. It was describing an algorithm to rank web pages. I am trying to remember the name of this algorithm or technique. The principle ...