Tag Info

Hot answers tagged

33

You've overlooked the key characteristic of the logarithm base. Because i is divided by 2 in each iteration, the running time is logarithmic with base 2. And log2(500) ~ 8.9 What you are looking at is log10(500) ~ 2.7 (logarithm with base 10) By the way, the reason why the base is often omitted in runtime discussions (and your calculator ...


8

A good guideline that helps knowing when to create a "large", general and abstract solution, and when to just solve the specific problem, is The Rule Of Three. The Rule Of Three is often applied to duplication: i.e. "if code is duplicated more then twice, move it to a function". However it also applies to the abstraction vs. solving-the-specific-problem ...


7

In addition to Michael Borgwardt's answer, the tilde character in front of each answer should be read as "proportional to". So if you doubled N (say, from 500 to 1000), you would see that the run time (or, in this case, number of stars printed) would increase by a factor which would be equal to (log1000 / log 500), which is independent from which base you ...


5

To calculate the mode from an unreasonably large data set (or stream) containing only a finite number of discrete elements (such as integers in a small range), use a table to count the occurrence of each element, where the element in the data set is the key in our table. We then go through the data set and increment that element's counter. At any point we ...


4

Well it recursively calculates x2 + (x-1)2 + (x-2)2 + ⋯ + 22 + 1.


4

Lets take an array of size n. There 2n possible subarrays of this array. Lets take the example array of size 4: [1, 2, 3, 4]. There are 24 sub arrays. Sub array of the empty set ([]) is the 0th one (0000). The subarray of [1], is the second one (0001), the subarray of [2] is the second one... (0010) and the subarray [1, 2] is the third one (0011). You ...


3

I'm reasonably sure that's an NP-hard problem. To find a 'perfect' solution you have to try every possibility exhaustively, and that is exponential. One approach would be to use the greedy fit and then try to improve it. That could be by taking a badly placed image (one of the last ones) and finding another place to put it, then taking that image and moving ...


3

If "spare time" is defined as the time in between the events, then your list format makes it very easy to convert you list of events to a list of spare times: Add midnight to both the start and end of your list Go over the new list and remove any interval of less than 0 seconds (or whatever threshold you want). With your example events, this would give ...


3

You should be able to adapt Dijkstra's algorithm. Just add two points A & B to your graph, which are connected to one of the subgraphs each. Then calculate the shortest path between the two points A & B. The shortest path between the two subgraphs should be the path that you get after removing A & B from the result.


3

As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best. However, you could come up with a procedure that returns a list of numbers like that: Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' ...


3

Use a HashSet which will not add an element if it is already there, its contains() implementation pretty well optimized provided you have a decent hashCode implementation.


3

You can use a Double-End Priority Queue for this. There are a number of implementation methods available and the structure is routinely available in many libraries. Most Java libraries call it a MinMaxPriorityQueue though. It offers O(1) retrieval of Min and Max (Newest/Oldest) in O(1) time. In order to fulfill your space requirement, you'd need to use an ...


3

I will try my hand at an answer, and fully expect to hear what's wrong with it soon. :) So first, I think the problem may be more easily tackled by thinking of the pair of ranges instead as defining a rectangle. Suppose you have [(0,2), (3,4)]. Another way to view this is the rectangle in Cartesian coordinates of (0,3) to (2,4). Overlap of both ranges can ...


3

the algorithm itself is easy: create an array with all the weights' cumulative sum. After that you generate a [0-1) uniform random number and just binary search that number multiplied with the sum of the weights and the index will be the number you will need to generate.


2

This looks like a knapsack-type problem. No shortcuts. Form a permutation of each of the possible selectsions, enumerate them, and pick any that fall with the range. The problem definition could be improved by specifying exactly how selections are made eg one of out each set?


2

If you want to visit all nodes then you have a variation of the traveling salesman problem. given that you are allowed to visit a node multiple times you can generate any missing with a cost of the shortest path between the 2 nodes. For example to get to V3 from V1 you need to pass V2, you can add an edge between V1 and V3 with a cost of (V1,V2)+(V2,V3). ...


2

This is NP-hard. If you have a solution for this problem, then you can use it on a graph with all edge weights set to 1. Then the resulting path will have the same number of nodes as the graph if and only if there is a Hamiltonian path. Since determining the existence of a Hamiltonian path is NP-hard even without finding specific solutions, any solution to ...


2

Simple, as long as you know how many. You need N numbers called V1 to Vn. The required sum is S. Generate N random numbers (in any convenient range). They are R1 to Rn. Calculate their sum as SR. Scale each number so Vn = Rn * S / SR. You may produce a tiny rounding error, but I doubt this will be a problem. If the number N is supposed to be random, ...


2

The basic approach is: Identify all the factors. Assign a weight to each factor. If the factor itself has a scale, assign a scaling formula (eg linear, log, capped, whatever) based on additional weights. If there are dependencies, express those as a formula based on additional weights. Add up all the resulting values. The problem now is that you have a ...


2

For a genetic algorithm you need chromosomes and a fitness function. The chromosomes represent choices of route. Looks like 5 chromosomes, one for each city in order, but there could be a smarter way. The fitness function is calculated from the chosen route. Score higher for visiting more cities and for shorter distance and lower cost of the chosen route. ...


2

The simple way to tell how "close" one solution is to another is to determine its standard error. Standard error is the standard deviation of answers you get. Then you divide the distance between two solutions by the standard error. If the answer is less than 1, that's pretty close, because you could get that big of a difference just by randomness. If less ...


2

This is not solvable if the required number of appointments cannot be written as a sum of the available Package.Quantity numbers. But maybe that requirement is too strict. Why not say that you want to offer the client the cheapest available sum of packages? E.g. if he wants 8 appointments but you can't match 8, you give him e.g. 5+4 packages. Let your ...


2

The mode is the most commonly occurring single value. Fairly obviously, you just have to count occurrences of each value as it arrives and then at the end search the counts to find the largest. There are some interesting variations. If and only if (a) the values are integers (b) you know the range in advance (c) you know the upper bound of the count then ...


2

Yes, there are two better and faster approaches. Simpler problem : for each tile, choose the best thumb (with possible duplication). Ok, that's cheating, but can only lead to better visual result. Your take is algorithmically more interesting, and boils down to "linear assignment problem", assuming you take MSE as match costs whose sum must be minimal. ...


2

This is the sum of squares of natural numbers. The sum of first n natural numbers can be represented mathematically by: n*(n+1)*(2n+1)/6


2

The function can be written in a more mathematical form as: unknown(1) = 1 unknown(x) = unknown(x - 1) + x * x [if x is not 1] To see why this is the same as the sum of squares, you can substitute the second line into itself recursively and observe the pattern that emerges: unknown(x) = unknown(x - 1) + x * x ...


2

You could of course store the weight in each object, or store a directory of instances in the class, if you create or control the classes. If not, you may be interested in the Counter class, a dictionary that maps into numeric values. It can be extended to map objects to weights. Here's a sketch: from collections import Counter class Weights(object): ...


2

Third time's the charm, I hope. I combined my original idea to sort the list first with Snowman's suggestion of using set theory. The basic algorithm is: Sort the pairs in lexicographic order by the first range. Group adjacent pairs by if just the first ranges overlap. I prove below that lexicographically sorted ranges will never overlap without being ...


2

You want to enumerate recursively the set of sublists of 1 :: 2 :: 3 :: 4 :: [] which sums to 5. (The :: is the OCaml notation for the list construction.) The recursive step in list processing is splitting the list in its head 1 and its tail 2 :: 3 :: 4 :: [] — can we describe our set in these terms? There is two kinds of sublists of 1 :: 2 :: 3 :: 4 :: [] ...


1

If the last tiles are your problem, you should try to place them early on, somehow ;) One approach would be to look at the tile that is the furthest away from the top x% of its matches (intuitively I'd go with 33%) and place that on its best match. That's the best match it can get anyway. Furthermore you could choose not to use the best match for the worst ...



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