Hot answers tagged

9

"Big O notation" is meaningless for this purpose. If you know n you can estimate the number of operations, but some operations are cheap (e.g. 1 cycle) and some operations are not (e.g. cache miss costing thousands of cycles); and the best estimate you can reach using this method is going to be dwarfed by "estimation error". Note: "Big O notation" is mostly ...


6

First, reduce the problem to a test of availabilities "per day". All your examples are using ranges for only one day, but if you also want to support a range like "Monday 10:00 to Wednesday 14:00", break this down into three tests for "Monday 10:00 to 23:59", "Thursday 00:00 to 23:59" and "Wednesday 00:00 to 10:00". For each day, store an interval ...


6

Not solvable. I tried a number of methods until i realized it couldn't be done. Assume a shape with area 4, which should be divided in 2 parts with area 2 each: The leftmost triangle and square must be part of shape 1, but it needs another triangle. The only place that could be taken from is the square to the right, but then the remainder is split in two ...


5

As I said in my comment to Doc Browns (otherwise excellent) answer, there is a matter of choice of square->triangle division which makes it slightly harder to device an algorithm. Also, you don't have to make it serially, but can do it in parallell, as some of my suggestions show. I made several heuristic approaches at first. Voronoi: Choose N points ...


4

What you are trying to do is variation on a Bin packing problem. Effectively you are placing items into bins (plaques) and trying to minimize the wasted space, since in your example wasted space directly corresponds to lost money. The wikipedia article shows how this can be done/solved. You may end up with an optimization problem on top of this, because you ...


4

It's not necessarily as bad as you think and may even be the most optimal representation if you have an index on parent_id. Let's say you're interested in the descendants of B above. In that case, you would first query for nodes which have parent_id matching the ID of B. That gives you D,E. Now query for nodes which have the parent ID of either of these. ...


3

The easiest way to resolve this is to shift how you're defining the end of their license term. Currently, I suspect you're using the natural approach of "User purchased base item for $N, so user has an expiration date of ..." In other words, the expiration date is determined at the time of purchase. The challenge with that approach comes about when you ...


3

A heuristic worth considering: Pick a random name and add it to a group. Scan the remaining names for the highest point match and add it to the group. Scan the remaining names for the highest total point match against the two grouped names and add it to the group. Scan the remaining names for the highest total point match against the three grouped names ...


3

The fact that a node can have two parents shouldn't prevent you from using a standard depth first search. As you describe it, a child with two parents is still independently part of two "solutions". The fact that there are at most two edges leaving each node simplifies things further. search(node): if node is null: // maybe a non-terminal parent's left ...


3

What are some reasons you may choose a worse runtime algorithm? By far the most common reason is that the "worse" algorithm is a lot simpler, or is the first solution I think of, and getting mathematically optimal performance just doesn't matter in the part of the code I'm currently working on. Which is most parts of the code. Another common reason is ...


3

You need some reliable benchmarks for the CPU in question, and for comparable CPUs, of which at least one is available to you. Then you develop the algorithm, measure it on the CPUs that you have, and taking the benchmark data, guess how long the other CPUs will take. Then you decide which CPUs might be able to handle your algorithm, and select the ones ...


2

This is what I finally ended up doing. I found a list of rules on this link that you need to follow when adding a suffix to a word. For example, when the word ends with "y", you replace the "y" with "i" unless the suffix you're adding is "ing". When the word ends with "e" you might have to drop the "e" if your suffix begins with a vowel and so on. And I ...


2

Common design Algorithmic Paradigms: Divide and conquer : Recursively breaking down a problem into two or more sub-problems of the same (or related) type. Dynamic programming : breaking it down into a collection of simpler subproblems. Example: Tower of Hanoi puzzle Greedy algorithm : the problem solving heuristic of making the locally optimal choice ...


2

You could do that. But as mentioned by Robert in the comments you could avoid a lot of trouble by using a library, such as Lucene. In your case (.NET) you should pick the Lucene.net port.


2

With an index on parent_id, I actually think this is a good way to organize the relationship, and we have been using it that way in many places. Also, I see no obvious better way, as the relationship is 1:N, so if you try to store parent->child, you need an extra table, and you end up with the same logic again. The core point is having the index on ...


2

The general strategy should be to remove the first piece of area A/n from your polygon P0 (where A is the total area), leaving you with a new polygon P1 of area A-A/n. Then repeat this producing a polygon P2, then P3, and after n repetitions, you have your solution. Note that it is possible at each step that you cannot find such a new piece where the ...


1

Your questions are very abstract and therefore mostly quite difficult to answer precisely, but here are some thoughts you may not have considered. Where is the list stored in memory? Is it literally stored in a way where first element is at memory index k, next element k+1, etc. That depends on what you mean by "list"! A C++ vector is stored ...


1

I did a stint at a huge printing company. I believe we ran into the same problem. Let me rephrase it. The constraints: An industrial printing plate costs X dollars to layout and fabricate. It's not an insignificant amount. Each printed sheet costs Y dollars. It's a smaller number but can add up. There are N unique "rectangles" to print. For the sake of ...


1

This is simpler than a tree because your result can only have one level. All you want is to group your array by category and then map each group into objects. The map part will just be rearranging things a little bit into your final desired structure. You won't need to filter the full list of videos inside the map like you're currently doing. Unfortunately, ...


1

An algorithm isn't actually very difficult. Given two numbers a and b, we can produce the results a + b, abs (a - b) (I don't know if negative numbers are allowed, in which case we can produce a - b and a + b), a * b, and possibly a / b or b / a if the result is an integer. So the possible results are a set of up to five numbers. Call this set S (a, b). ...


1

I've just been tasked with doing this for homework, and I thought I had a neat epiphany: Strassen's algorithm sacrifices the "breadth" of its pre-summation components in order to use less operations in exchange for "deeper" pre-summation components that can still be used to extract the final answer. (This isn't the best way to say it, but it's hard for me to ...


1

This is not a direct answer but it does not fit in a comment. I just want to elaborate MSalters comment - internally, NTFS already does what you are trying to do. It is a wrong impression about huge NTFS folder being slow. The wrong impression is usually due to the way some users interact with the folder - windows file explorer, which loads all entries when ...


1

It's not entirely obvious, but the type of algorithm you're looking for is called a space filling curve. The space here is the namespace of folders. XKCD had a 2D example a long time ago. It shows how the first 4 files would end up in /00/00 to /01/01 and the first 16 in in /00/00 to /03/03. Expanding the algorithm, the first 256 files end in /00/00 to ...



Only top voted, non community-wiki answers of a minimum length are eligible