Tag Info

Hot answers tagged

58

"N log N" is as good as you're going to get, and should be well understood by professional programmers. You can't expect there to be a single word to describe every complexity class that exists.


49

There is a jargon term linearithmic meaning exactly this. I don't believe that it's universally understood by all programmers, so if you're not careful then it will obscure more than it informs. Personally I don't normally use it, and if I did then I'd probably define it on first use, for example "this article considers linearithmic (O(N log N)) ...


11

It is sometimes called "loglinear", although that word actually means something different. I would just stick with "N log N", though, as @Philip's answer suggests.


8

Given a direct line of sight, the problem is obviously trivial. However, we are dealing with reflection. Properly finding out which parts of the scene can be seen is challenging when implementing reflection as part of a ray tracer, since this might miss some openings. A “binary search” between two promising angles is also not viable: due to the reflections, ...


7

A common way to read data coming into the computer is to buffer it from a stream. Streams sometimes have an undefined length. All we know for sure is we can "get next character from stream". Normally we'd add the character from the stream to the end of the buffer (think FIFO queue). The size of the buffer doesn't necessarily have to be the size of the ...


6

You can make use of the fact that when BoxIsFilledWithCubes(c,x,y,z) returns true, then it is not necessary to check in BoxIsFilledWithCubes(c,x+1,y,z) all those cubes in the coordinate range "(c,x,y,z)" again. You need only to check those cubes with the new x-coordinate c.x + (x+1). (Same is true for y+1, or z+1). More generally, by splitting up a box ...


6

Just extending Karl Bielefeldt idea for a 2 walls reflections: A and B are given (the tanks). You first must list all walls that A can see and a list of all walls B can see. Then you make pairs where the first wall is in the fist list and the second wall is different from the first wall and is in the second list. You need to make this test for all possible ...


5

It seems that what you're really trying to do is figure out if two nodes in a graph are in the same connected component. Specifically the graph is an undirected one in which the words of your dictionary are nodes, and two nodes are connected to each other by a vertex when they differ by exactly one letter, and are the same length. The root of the problem is ...


5

If you are allowed to remember past data, A* is indeed your best bet. I used it on Google's Ant AI challenge, which only has a small radius of view. The main difference with a limited field of view is you do a lot more walking around just to explore, but that's unavoidable. A* will give you a pretty good list of where to explore, without having to visit ...


5

Your solution seems to try to tackle average reading time of nodes and all paths from them. This will, of course, work, provided it's properly implemented. The problem with this approach is that the quantities you calculate are not reusable. The average reading time of a node depends on how you got to it. Hence the quadratic behaviour of your naive ...


5

Build up an octree with a leaf node aabb size of the size of your box. While traversing the octree you can cheaply merge nodes. Completely filled nodes are trivial to merge (new box = parent aabb), while for partially filled nodes, you can use a variant of your current algorithm to check merge-ability.


4

You are asking essentially for the secret of creativity. I'm sorry; there is no secret that anyone could tell you. Finding new solutions, concepts, proof etc. is, by definition, an unpredictable thing, and it's the most prominent thing that we haven't successfully computerized yet. (If it's any consolation to you, the way in which someone invented a clever ...


3

This answer is merely provided to reduce the frustration. In general, a person is better advised to learn how to conduct performance benchmarking properly before asking such a question. If your "keys" exclusively consist of consecutive integers, you can use an integer array. Zero-based consecutive integers can be used as array index as-is. Non-zero-based ...


3

First, your definition of your numbers can lead to non-fractions (e.g., p=2, q=0). Second, to summarize your idea: Store all your fractions as integers Perform an integer sort Convert all your integers back to fractions Seems like a lot of unnecessary memory and time when a lot of sorting algorithms can be done using a simple comparison sort and you can ...


3

Well, do you or don't you have the data in a normal database? If you do, there is no way around querying all possible matches from the data base (with a long query full of OR operators) and then sorting the result however you see fit. In other words, you're not looking for a search algorithm, but for sorting functions. You can only solve this problem with ...


3

This seems like a decision for business people to make, not developers. They do calculations and determine the rules by which your application will decide what parcel gets shipped by you, and what parcel gets shipped by third party. If I was to implement it, here is how I would go about it: Get quotes for each delivery company you can use. Factor in your ...


3

What you need is something that does Linear Programming. The various variables you would be using are called "Decision Variables" in the context of these methods. Linear Programming is a very mature technique and there are many packages and platforms available. There are also legions of resources for learning the techniques behind it as well if you want to ...


3

If looks like a O(n³) solution. Your instinct is correct: by resetting variables you are looping. Note: if we only consider the loop instruction we would, mistakenly, think it was O(∞). However the problem is O(n). Therefore you can do better.


3

To balance the other answer - this particular case is a question of math literacy rather than creativity. This is just a tiny piece of the centuries old baggage of knowledge that should have been imprinted into you in school (most likely together with the little Gauss story mentioned in the comments). While you don't need math to program, there are certain ...


3

prefix trie: It's a degenerate DFA without cycles. For implementation you have a int state and a int nextState[256] for each state. For Matching states you would make the state number for it negative so you know when it's reached.


3

You can take advantage of the fact that the angle leaving the ricochet must be the same as the angle entering it. For a given horizontal wall with y-coordinate c and two fixed tanks with coordinates (a,b) and (d,e), there is only one angle which satisfies the equation below. Just solve for x to get the distance along the wall at which you must aim. Two ...


2

A good guideline is that your tests should exercise all the code that you've written. If different inputs cause different code paths to be executed, it is a good idea to choose your test inputs so that every path is covered. More thorough testing also tries to ensure that every path is covered under different circumstances, particularly with extreme ...


2

In principle a search Trie is what you want, but you'd have to profile your actual data to find out when that actually performs better (it might always be worse unless you can find a cache-friendly layout). Edit based on comments: Are you matching a stream or discrete packets? If the former, and you need to handle matches spanning the boundary between ...


2

Because the factor log n grows slowly, a qualitative description for O(n log n) would be "almost linear". Depending on your audience the class of O(n log n) algorithms might be well known, as for example this is the case with fast sorting on n items by comparisons.


2

I believe the direct answer is simply that functions are not operators. From the page you linked: If the token is a function token, then push it onto the stack. This is all it needs to say, since the function case (prefix to postfix) is much simpler than the operator case (infix to postfix). For the follow-up questions: The notions of precedence and ...


2

You can solve this with a standard breadth-first search, with the addition of also storing the path taken to a node whenever you enqueue it in the to search queue. BFS algorithms avoid loops by keeping a visited or discovered set. Because they use a queue instead of a stack, they are not normally implemented using recursion, unless the implementation uses ...


2

Its a multipart piece of information you need to communicate. First off, you provide the timestamp. That is what you validate against for the 'was submitted within 15 minutes'. Secondly, you have a hash of the timestamp with some additional salt. The salt is known only to you (on the server). If the time stamp was altered, the hash of the altered time ...


1

I looked at the source code of the dictionary and noticed the use of "buckets". I'm not exactly sure how a dictionary sorts objects into buckets but it's a simple task with integers. The main problem, I've logiced, is converting the input into an index that's small as possible yet doesn't collide with other inputs' indexes to make the array the outputs are ...


1

It looks like you don't want >= and <=, because then touching boxes are considered colliding. Use > and < instead.


1

The best way is to divide the problem space first, so you only have to consider how many farmers want how many seeds of a particular fruit type and quality. You can do this in a single iteration. You need to know how many of each fruit and seed type is being requested. Then divide the number of seeds of each quality by the desired number, rounding down, and ...



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