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)

3
votes
3answers
362 views

questions on a particular algorithm

Upon searching for a fast primr algorithm, I stumbled upon this: public static boolean isP(long n) { if (n==2 || n==3) return true; if ((n&0x1)==0 || n%3==0 || n<2) return false; ...
7
votes
4answers
963 views

finding houses within a radius

During an interview I was asked given the following: A real estate application that lists all houses that are currently on the market (i.e., for sale) within a given distance (say for example the user ...
0
votes
2answers
244 views

Given number which equals the sum of some of the 10 numbers. How to determine that given number contains one of 10 numbers?

I have: ten numbers: +1, +2, +4, +8, +16, +32, +64, +128, +256, +512. flag == sum of some of this ten numbers. How to determine that sum contains 2 or 32?
10
votes
3answers
393 views

Efficient Bus Loading

This is something I did for a bus travel company a long time ago, and I was never happy with the results. I was thinking about that old project recently and thought I'd revisit that problem. Problem: ...
8
votes
4answers
3k views

How common are generic-case exponential time algorithms in production software?

I know that exponential time algorithms should generally be avoided but are sometimes necessary. A case being the Traveling Salesman. How common are such algorithms in production software? Are these ...
7
votes
2answers
530 views

What is the algorithm for expiring items in key-value storage?

I was thinking on how current key-value storages implement "expire date" for items. Currently I have 2 variants for that in my mind: they don't do anything (keep expired data), and only do check ...
9
votes
5answers
3k views

Improving performance for grepping over a huge file

I have FILE_A which has over 300,000 lines and FILE_B which has over 30 million lines. I created a Bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new ...
17
votes
8answers
2k views

Strategy/algorithm to divide fair teams based on history

We are a group of people playing floorball together on a regular basis. Every session starts with the daunting task of dividing teams... So what would be better than an application to pick teams ...
23
votes
5answers
8k views

Return random `list` item by its `weight`

I have, for example, this table +-----------------+ | fruit | weight | +-----------------+ | apple | 4 | | orange | 2 | | lemon | 1 | +-----------------+ I need to return random ...
22
votes
6answers
17k views

Why is quicksort better than other sorting algorithms in practice?

This is a repost of a question on cs.SE by Janoma. Full credits and spoils to him or cs.SE. In a standard algorithms course we are taught that quicksort is O(n log n) on average and O(n²) in the ...
3
votes
1answer
356 views

Grouping numbers to minimize group-means

I need to find a way or an algorithm that groups members of a given data set (of positive integers) so that the difference between group means is minimized (not maximized, as usual). There are two ...
2
votes
2answers
475 views

Algorithm to minimize distance variance between 2D coordinates

I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together. Say I have List 1: 205|200 220|210 200|220 ...
8
votes
6answers
1k views

How do the algorithms to solve problems encountered in interviews translate into real world solutions? [closed]

I have recently finished an undergraduate course in computer science and I am looking for a job. During the search I encountered several interesting (and tough) problems that needed clever algorithms ...
11
votes
5answers
369 views

Convert list of 24-hour-precipitation values into total-by-hour

Let's say I have a list of precipitation values by hour, each showing how much rain happened in the prior 24 hours, ordered by date. For example: { '2012-05-24 12:00': 0.5, // .5" of rain from ...
3
votes
1answer
200 views

Algorithms for pairing a rating system to an assignment queue

Attempting to research how to allow a group of people to effectively rank a set of objects (each group member will have contributed one object to the group), and then assign each member an object ...
3
votes
4answers
380 views

How to implement a system to hide spammed user content?

I'm trying to work out a good way to manage user submitted content and create a method to determine when spammed/poor content should be hidden. The aim is to create comment voting similar to youtubes ...
7
votes
2answers
2k views

Algorithm for finding overlapping times

Part of our ERP system is a sub-system for running background jobs. We track a variety of meta-data about our jobs in a table including timestamps for submitted, started, and end times. I'm creating ...
3
votes
1answer
215 views

Logic required to solve a problem relating to location of objects

I have raised a question on dba.stackexchange.com but as the heart of my question is in fact to do with logic I have raised a more general representation of my issue here. I think it is the right ...
2
votes
4answers
5k views

What sorting algorithm does STL use?

I recently started using <vector.h> library and I was wondering, since all the operations are already implemented, IF the method of the sorting algorithm is the most efficient one. Everything ...
3
votes
1answer
677 views

How can this deterministic linear time selection algorithm be linear?

Im trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as ...
2
votes
1answer
308 views

What alogrithm is used on the smart cards for the DNSSEC Trusted Community Representatives?

I've been doing some reading about DNSSec and am interested in the algorithm that they chose to use when splitting the trusted key up between the 7 Trusted Community Representatives (TCR). I ...
5
votes
1answer
444 views

Firefighting allocation problem

I'm trying to develop a model to work on an assignment problem in the firegifhter area. Given n firefighters, m trucks and z ongoing fires, each with a danger level, try and allocate the resources in ...
1
vote
2answers
234 views

Fuzzy search for a sub-string without tokens

Let's say I have the following lines: Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit. Phasellus congue nisi vel lorem dignissim tristique. (tag) Etiam vulputate lacus nec velit ...
13
votes
5answers
5k views

What would be the Impact of P=NP? [closed]

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
7
votes
2answers
1k views

Are nested loops always O(n^k)?

If I have a loop within another loop, yet I know the inner loop will only run once, will this algorithm still be O(n^2)? For i = 1 to n do For j = 1 to i do If (i==j) do ...
6
votes
3answers
3k views

What algorithm(s) can be used to achieve reasonably good next word prediction?

What is a good way of implementing "next-word prediction"? For example, the user types "I am" and the system suggests "a" and "not" (or possibly others) as the next word. I am aware of a method that ...
2
votes
3answers
885 views

How do programs like subversion detect when a file has been edited as opposed to created/deleted?

This is my first question here so I hope it is not off topic. Although I am using the Linux inotify library to listen for changes to files, and I compare use of that against the Subversion program, I ...
3
votes
4answers
405 views

What is the algorithm to copy a region of one bitmap, into a region in another?

In my project (and I am sure many others), I need to copy a subset (R2) of one bitmap image (R1), into a region (R3) in another, where the destination region can be any size (stretching and scaling ...
3
votes
3answers
990 views

Algorithm which suggests synonyms based on some term?

Is there an algorithm which I can use in order to generate synonyms for some term (word) in respect of a spam. I am writing a simple spam filter. For example, I set that the app must omit a word ...
7
votes
3answers
1k views

What is the Bible of Hashing?

Is there a Cormen-like reference on Hashes and Hashing? This particular structure has seen little attention in my CS education for some reason but I'd like to learn more as they seem to be everywhere. ...
1
vote
2answers
183 views

Trying to sort the coefficients of the polynomial (z-a)(z-b)(z-c)…(z-n) into a vector

So I have a factored polynomial of the form (z-a)(z-b)(z-c)...(z-n) for n an even positive integer. Thus the coefficient of z^k for 0 <= k < n will be the sum of all distinct n-k element ...
2
votes
1answer
1k views

Keeping binary search tree balanced

I am educating myself on algorithms and data structures. For that, I am doing a simple program that would read lines like this: bdhj 168.24 dahf 42.88 dhfa 128.92 First column represents an account ...
1
vote
3answers
1k views

How do I approach this PHP/MYSQL query?

I have a reservation system that I have coded and my final task is to allow the user to enter a set of dates and then show them all available options. The reservation table is set up with unit_id, ...
1
vote
7answers
11k views

Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
11
votes
5answers
18k views

Determining if an Algorithm is O (log n)

I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it? I know with O(n), you usually have a single ...
10
votes
6answers
2k views

Is it inefficient to concatenate strings one at a time?

I recall back from my days of programming in C that when two strings are joined, the OS must allocate memory for the joined string, then the program can copy all the string text over to the new area ...
12
votes
8answers
3k views

Find a “hole” in a list of numbers

What is the fastest way to find the first (smallest) integer that doesn't exist in a given list of unsorted integers (and that is greater than the list's smallest value)? My primitive approach is ...
4
votes
1answer
316 views

The Wikipedia animation for Maze generation using DFS isn't consistent wrt the written algorithm given there, isn't it?

Please have a look at this link: http://en.wikipedia.org/wiki/Maze_generation#Depth-first_search Here, the theoretical algorithm given is: Consider the space for a maze being a large grid of ...
3
votes
1answer
3k views

Magic square check for N×N matrix with minimum complexity

Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)? I did see someone ...
5
votes
2answers
10k views

Real life examples of P, NP, NP hard ,NP Complete problems [closed]

I need to know the real life or real time examples of above mentioned problems thanks!!
5
votes
5answers
2k views

Structuring database for multi-object “activity” and “following” functionalities

I am working on a web application which operate with different types of objects such as user, profiles, pages etc. All objects have unique object_id. When objects interact it may produce "activity", ...
2
votes
4answers
1k views

Is it possible to efficiently store all possible phone numbers in memory?

Given the standard North American phone number format: (Area Code) Exchange - Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections ...
7
votes
2answers
2k views

Does LINQ require significantly more processing cycles and memory than lower-level data iteration techniques?

Background I am recently in the process of enduring grueling tech interviews for positions that use the .NET stack, some of which include silly questions like this one, and some questions that are ...
2
votes
2answers
626 views

Algorithm for creating cluster groups on two criteria

I would like to group a population based on two criteria. I will use an analogy to simplify my question. Let's say I want n number of groups. I want to populate those groups based on person's age and ...
30
votes
4answers
3k views

What's the difference between recursion and corecursion?

What's the difference between these? Recursion Corecursion On Wikipedia, there is little information and no clear code explaining these terms. What are some very simple examples explaining these ...
9
votes
4answers
3k views

Are there currently any modern, standardized, aptitude test for software engineering? [closed]

Background I am a working software engineer who is in the midst of seeking out a new contract for the next year or so. In my search, I am enduring several absurd technical interviews as indicated by ...
1
vote
4answers
148 views

Possible applications of algorithm devised for differentiating between structured vs random text

I have written a program that can rapidly (within 5 sec on a 2GB RAM desktop, 2.33 Ghz CPU) differentiate between structured text (e.g English text) and random alphanumeric strings. It can also ...
136
votes
13answers
12k views

Is it just me or is this a baffling tech interview question? [closed]

Background I was just asked in a tech interview to write an algorithm to traverse an "object" (notice the quotes) where A is equal to B and B is equal to C and A is equal to C. That's it. That is ...
1
vote
6answers
319 views

Catching an error?

Is catching an error with try ... catch a better practice than catching an error with proper analysis/error check? For instance, removing from an empty list: Does surround with a try catch clause ...
5
votes
2answers
1k views

What is this algorithm for converting strings into numbers called?

I've been doing some work in Parsec recently, and for my toy language I wanted multi-based fractional numbers to be expressible. After digging around in Parsec's source a bit, I found their ...