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.
-1
votes
2answers
39 views
Algorithm for searching a domain name in list of wildcard
I have a list of domain name that contains wildcard ('*' character)
Example:
*.google.com
*.domain.com
...
It contains nearly 1 million domains.
The data will be stored on a mongodb or redis ...
0
votes
1answer
69 views
Why the search time for TreeSet is O(nlogn)?
In my naive opinion it should be O(n) in worst case since Tree could get spindly and unbalanced.
-1
votes
1answer
92 views
How to solve this algorithmic problem? Is there a polynomial exact algorithm?
The problem goes like this:
There are n piles of wooden planks and m machines, let xi be the number of planks in i-th pile. The machines produce different parts for chairs; each machine requires a ...
-3
votes
1answer
111 views
What's the best algorithm to assign unique ID/serial numbers to a group of identical objects?
to make this question easier to visualize, let's call this the "chicken mesh problem".
Suppose you have a rooster and a number (suppose it is 30) of baby chickens.
Goal: Allow the rooster to ...
0
votes
0answers
26 views
Implementing my own Integer.toBinaryString(int n) method [migrated]
Our senior developer gave us (trainees/jr. developers) a small exercise and that is to make our own Integer.toBinaryString(int n) implementation. This is the answer I came up with. I would just like ...
3
votes
3answers
68 views
Say we have a group of N person, and each person might want to sell or buy one of the M items, how to find a closed path among them for an exchange?
Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,
person 1 has item A, C, D, and wants item F
person 2 has item B, C, and wants E
...
1
vote
1answer
75 views
Get Unique random numbers within predefined limits
I am looking for an efficient algorithm to get unique (non repeated) x amount of integer random numbers that are within the y and z limits.
e.g. I want x random integer numbers that are bigger or ...
1
vote
1answer
80 views
Majority voting algorithm, there are n people and m candidates but m is known
The question is long, so I will paraphrase it briefly
Q: There are n people voting to choose the chair of the committee. Each person can vote for one person that has unique id (it is positive integer ...
1
vote
0answers
21 views
Check if a point is deviating from a path made by a set of line segments
I'd like to know or have other ideas --other than my solution-- about how to check if a car on a given position (lat, lng) is getting away (let's say a distance D away) from the path where the car ...
0
votes
1answer
66 views
Why isn't this combinatorial solution equivalent to the recursive solution for finding the number of “paths”?
Here's the problem:
Given an m x n array, get the number of different paths from the top left corner to the bottom right corner, if you can only move down, right, and diagonally down & right.
...
8
votes
3answers
233 views
Picking the most calorie-even arrangement of meals
Suppose I eat five meals a day, and since there are seven days in a week, I have recipes for seven of each meal, for 35 recipes in total. Each recipe has a calorie count. Each day must contain one ...
22
votes
8answers
1k views
You are given a file which contains all possible numbers on a 32-bit architecture. 4 numbers are missing from that file. Find the 4 missing numbers
This is an interview question that I've run across a few times, and I'm really not sure how to solve it given that four numbers are missing. I'm familiar with algorithms for finding one or two numbers ...
-1
votes
2answers
63 views
What programming environments can be used to illustrate and benchmark the unoptimized space complexity of an algorithm?
What programming language along with implementation and compiler can I use to study the pure, unoptimized space complexity of an arbitrary algorithm? And what methods can I use to do so?
For example,...
0
votes
1answer
23 views
Validating combinations based on rule sets (or similar mechanism)
Let's say I've got many functions and each function accepts an unordered list (order does not matter). For each function I want to see if this list is valid based on certain rules (a knowledgebase ...
2
votes
1answer
180 views
What is this Algorithm called? [Traveling Salesman Problem]
I've been thinking about the Traveling Salesman Problem. In examining it and grids of cities, I noticed that I could frequently pick out the shortest route just by staring at it. Granted, I couldn't ...
4
votes
1answer
170 views
Implementing the Cashier's Algorithm in a vending machine
This code golf question got me thinking.
I wasn't even aware that the Cashier's Algorithm was a formal thing.
Reading it, and Googling around, I see that all solutions seem to concern themselves ...
3
votes
1answer
81 views
Efficiently consuming a rate-limited service
So my exact case is that I have ~1400 domains on an ancient, self-hosted bind server and I'm looking to migrate them to a hosted service. The trouble is that the hosted service's API has a rate limit ...
2
votes
1answer
77 views
Future data integrity (n years)
So recently, I had a client ask me to restructure his Database hierarchy which consisted mainly of changing table names and column names and creating cross-references to stop red locks.
He later ...
6
votes
5answers
424 views
Splitting integer so that both sides are prime numbers
The problem
You're given an n number. Check if that n number can be splitted in half so that both sides of a | are prime numbers.
Example:
Input Output
223 2|23
123 Not possible to split.
My ...
3
votes
1answer
280 views
Why are pure functions easier to reason about?
In computer programming (I code in c#), why are pure functions easier to reason about?
From my own experience, I find that pure functions are easier to reason about because they lack side effects, ...
-4
votes
0answers
43 views
Generate List of Swap Pairs
Given a starting array of 6 elements (S) and a final array (F) of the same 6 elements but in arbitrary order, what is the algorithm for generating the minimal list of swap pairs that takes (S) as ...
1
vote
0answers
89 views
Sorting Lower Bound in the Comparison Model (Nuts & Bolts Problem)
Problem:
Assume that we are given n bolts and n nuts of different sizes, where each bolt exactly matches one nut. Our goal is to find the matching nut for each bolt. The nuts and bolts are too similar ...
0
votes
1answer
61 views
how to reach all nodes in a Tree Structure where end of the tree is unknown
There is a XML link, which provides the children of any parentID given.
http://www.browsenodes.com/xml.php?action=BrowseNodeInfo&node=1036592
Then you can run the URL again with a children ID ...
0
votes
2answers
79 views
Small Search Engine Algorithm for Document Word Search
I have to design and implement an algorithm for my university project that searches a given set of documents based on the keywords/query given. Assume that each document contain few sentences and ...
0
votes
3answers
216 views
Mental model for working with linked list [closed]
I have been doing some practice problems on LinkedList but more than half of my time is spent on managing null pointer issue in my code, provided I have to keep track of current, previous and runners ...
-4
votes
0answers
65 views
Algorithm to generate series of number
I need to generate all combination of numbers which will start from 1 and end to n.
There is a catch the series should take only the adjacent number. For example for series of n=3 the number ...
2
votes
2answers
259 views
Can the gold mine problem be solved using divide-and-conquer?
There's a well-known dynamic programming problem that goes by the name of the "gold mine." You have a n x n grid, each cell of which contains a certain value of coins. You begin at the bottom left ...
1
vote
0answers
83 views
Improve performance with recursive apporach in quaternary numeral system [migrated]
How can performance be improved with the following approach to determine
n=3 results in a(3) = 42: 000, 002, 003, 020, 021, 022, 030, 031, 032,
033, 100, 102, 103, 110, 111, 113, 130, 131, 132, ...
5
votes
1answer
175 views
What does “the standard stateless functional view of algorithms” mean?
From Kelvin Murphy's review on Algorithms (4th Edition) by Sedgewick and Wayne
For data structures, it is obviously natural to use classes, but they
also adopt this approach for many algorithms, ...
0
votes
2answers
55 views
Searching, storing, and finding graph attributes and vertices
I've been reading the 3rd edition of [Algorithms][1] by Cormen, Leiserson, Rivest and Stein. For DFS and BFS their algorithm loops through all the vertices first and colors them white.
1) If the ...
4
votes
5answers
359 views
Should quickselect modify the input array or not?
I have recently implemented quickselect, an algorithm for computing k-th smallest element of an array, which, roughly speaking, works by repeatedly partitioning the array around a pivot and suitably ...
-2
votes
0answers
37 views
Runtime of quicksort algorithm by finding pivot in O(log n) [duplicate]
If the pivot/median of an array is found in O(log n), what is the worst case runtime for an efficient use of the quick sort algorithm?
This would be different from the standard worst case runtime of ...
7
votes
1answer
315 views
Marking grid points within a small circle on a sphere
I have a small circle (on a sphere) with given center and radius and I want to mark grid points which are within the small circle.
The grid itself is discretised in evenly spaced longitude and ...
0
votes
2answers
99 views
How to evenly distribute objects along an array so neighbours get equidistant?
I have R objects, where R >= 3.
I have a N-sized array, where N > R.
I would like to determine in which indexes of the array I must put the R objects so the distance between any two neighbors ...
1
vote
3answers
258 views
Find if any pair exists in an unsorted array?
I have come across a programming question in which I have to determine :
Does there exists at least one pair in a given unsorted array such
that
|i - j| <= K and |A[i] - A[j]| <= x
?
...
0
votes
1answer
112 views
Can you name this square root algorithm on an unsigned integer through the manipulation of the binary number?
Apparently this algorithm is well known.
The algorithm will build the square root answer bit by bit starting from the left-most bit to the last.
Let's say we will support squaring up to a 8 bit ...
2
votes
4answers
278 views
How, why or when would you use your own data structure instead of Collections Framework?
While most of the top IT companies will ask you (during the interview) to solve a problem applying some data structure, is it good if you define your own class for that data structure?
Like if I know ...
-2
votes
1answer
249 views
Fastest way to retrieve data in an area based on xy coordinates?
So I have an unsorted data set with x and y float coordinates as keys. The data is in a txt file. It looks like this:
x,y,data;
x2,y2,data2;
etc
I need to retrieve all data in a specific ...
9
votes
2answers
277 views
Coverage - flaw in the algorithm - how to get rid of its use?
Introduction
Many of the mainline vector graphics rendering engines have an algorithmic flaw in them. They render each shape separately, and antialias by calculating pixel coverage and then compose ...
0
votes
4answers
163 views
How the dividing Step in Merge Sort have Constant Time Complexity?
I am highly confuse while calculating time complexity of Merge Sort Algorithm.
Specifically on the Dividing Step.
In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".
How ...
3
votes
2answers
81 views
Remove gaps between non-overlapping segments of an array of time elements
I have an array of elements, each with a start time and an end time.
These form a timeline, some of which overlap, and others that do not (and have a gap between groups of overlapping elements).
I ...
0
votes
2answers
131 views
How to Create a Parser that Operates in Reverse
I've got my answer to this in the comment of the one I checked. Which Algorithm Approach Should I Take to Generate Lambda Expressions in Java? but I don't exactly know where to look in terms of ...
-1
votes
1answer
42 views
How to fit k-length arrays to number of bigger arrays?
I have n number of one-dimensional arrays similar to:
[0,0,0,0,0,1,1,1,0,0,1,1,...]
0's and 1's indicating occupation.
And k number of smaller arrays similar to:
[2,2,2], [2,2], [2], [2,2,2,2]
...
16
votes
3answers
1k views
What algorithm is used by elevators to find the shortest path to travel floor orders?
I'm trying to simulate an elevator, as always I started very simple by taking only a single order at a time, then added memory to the elevator in the form of queues so that floors are traveled in the ...
-2
votes
1answer
68 views
How to explain this method to find the least common multiple of the first n natural numbers?
This is the Project Euler question #5. The statement is pretty much finding the least common multiple of the first n natural numbers. So for example, the least common multiple of 1, 2 .. 10 is 2520.
...
0
votes
1answer
34 views
Batch insert a group of elements into a sorted list and get their indices
I'm working on an update process which inserts items into a sorted list, and processes those items' indices in the sorted list.
To help me with this, I created a sorted list with an "insert" method ...
2
votes
7answers
403 views
Do we really need efficient algorithms? [duplicate]
I'd like to ask why people devote their time to research algorithms and their efficiency so extensively when computers nowadays are so fast.
Trying to come up with an answer I thought that maybe my ...
2
votes
1answer
112 views
Getting the number of bits set in a large integer
I have a large integer N < 10^2500. I need to get the number of bits set in its binary representation. The number is given in base 10 in a file. Here's how I'm doing it right now :
I made a class ...
0
votes
3answers
181 views
Algorithm to minimize duration
I have times for start and stop and date of service, like this:
2000-01-01 23:00 23:20
2000-01-01 23:50 00:10
2000-01-01 00:20 00:30
The end time of the second period and the third period ...
-1
votes
4answers
274 views
Algorithm to generate all possible images of a particular size in 256 colours
I was having a discussion with a friend on the Infinite Monkey Theorem and that's when this came up. Suppose we want to generate an image of size 60 x 80 i.e. 4800 pixels and we want to use 8bpp (bits ...
