Tag Info

New answers tagged

7

There is no error in your line of thought, you've just described something very close to how the original Java garbage collector worked The original Java virtual machine [6] and some Smalltalk virtual machines use indirect pointers, called handles in [6],to refer to objects. Handles allow easy relocation of objects during garbage collection since, with ...


12

All problems in computer science can be solved by another level of indirection … except for the problem of too many layers of indirection Your approach does not immediately solve the problem of garbage collection, but only moves it up one level. And at what cost! Now, every memory access goes through another pointer dereference. We can't cache the ...


11

Updating references is not the only thing that requires a pause. The standard algorithms commonly grouped under "mark-sweep" all assume that the entire object graph remains unaltered while it's being marked. Correctly handling modifications (new objects created, references changed) requires rather tricky alternative algorithms, like as the tri-color ...


-1

I don't think this is the proper site for knowing the exact implementation of apple's shuffle: It's going to be patented and highly unlikely to be shared. But, if the question is how are "shuffles" done: Here's a very basic implementation done in pseudocode list<song> songsPlayed = new List<song>(); list<song> songsNotPlayed = ...


0

What about using an hermeneutic approach give every recipy certain points based on different criteria. E.g buying an ingredient 5 points for every ingredient. The one with lowest points wins


0

The approach that I would take is a least-errors approach. 1) Create a set of symbols to represent each food stuff. 2) Represent the contents of your fridge as a string of symbols. The string is ordered and multiple items are represented as multiple symbols. Liquids, etc, should be represented by multiple cup-fractions (i.e., 6 x 1/4 cup of milk). 3) ...


6

This is the Exact Cover problem, one of the original 21 problems shown by Karp to be NP-complete in his classic 1972 paper that established the importance of NP-completeness. Wikipedia's description is: given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in ...


0

sounds like a path finding problem, you start at a node X and want to move several steps with the least cost. cost is increased when you buy things and stays the same when you don't. I suggest a flood-fill or minimax with alfa-beta culling until you find a node where your fridge is empty. (after which you will need to buy anyway)


3

As depicted here, what you are looking for is the 1st-order 2-dimensional Voronoi diagram under the Manhattan, or L1-metric. This is a quite non-trivial problem (to solve efficiently), fortunately with many existing algorithms and software. You actually want the subset of the Voronoi diagram that coincides with the discrete grid defined by your matrix ...


2

Some questions, then a suggestion. Have you tried your code with the same images and masks as the article. Do you get the same results? Did you try switching masks in the original? A quick scan of the source code tells me that this code is not easy to verify. It's not written in a way to ensure correctness, and it's not testable. I thought I found a ...


6

I did some empirical simulation of a simplified version of this system. It seems intuitive that one could use a binary search, modified with a weight factor to bias the "midpoint" selection toward lower numbers. Another answer proposed 300 (so choosing a midpoint that is 1/300 of the way from the left to the right), but I wanted to check this. I wrote a ...


2

I am not a statistician, but it seems to me that guessing 1/300 of the overall range would get you the answer most quickly, a weighted binary search. So, the first guess is (1/300) * 2^64 The second guess is either on success (1/300) * (1/300) * 2^64 or on failure (1/300) + (1/300) * (2^64 - (1/300)) etc.


0

Any such solution is incredibly fragile as that page is liable to change without prior notice, breaking the application that relies on it having that specific layout. Even worse than that, such code almost universally violates the terms of use of the website you're leeching data from. Most websites that allow you to use their data will have an API to get ...


0

Ultimately you're going to need to write a "cost" function, and then use some algebraic technique to find the maximum(s). If you wanted a quick-and-somewhat-dirty answer, you could use a Genetic Algorithm to propose, test, and incrementally improve answers until you got a good one. But it wouldn't be guaranteed to be the best. However, it could provide ...


0

It looks like this just prints the raw file. It's up to you to determine how to parse it. I'd assume that you're not expected to parse an arbitrary page, just pages in the same class as the samples you've been given. full HTTP parser is not expected, just an ad-hoc solution using java string functions.


8

Depending on your version of SQL Server, windowing functions will do what you want. 2008 has limited support but 2012 adds nearly all of the standard. The over clause is used for things exactly like this, it is also available in the express versions as well. http://technet.microsoft.com/en-us/library/ms189461.aspx Windowing functions are used to perform ...


0

Every processor has its own set of buckets, so that step 3 can be done locally. However, this is the wrong place for your data: you don't want it to be organized first by originating processor then by bucket, you simply want it sorted by bucket. Thus a "transpose" operation to invert the "indexing" of the data, so that it's organized by bucket first, then by ...


1

According to this website, this comparison is used to determine where exactly the zero crossing is if it seems to occur between two pixels. If there are multiple valid edges, which one is closest to the boundary? Obviously, the one with the smallest absolute value is the one closest to the zero crossing! There are many other ways to localize the edge, some ...


0

My understanding of adaptive Huffman coding is that its implementation requires a weighted tree, and then weights are being operated on, so a standard binary tree, or binary search tree, or a heap, cannot be used 'as is'. In fact, a BST doesn't seem very appropriate, whereas a heap might be a good start, given that (in Vitter's algorithm at least) nodes must ...


0

To avoid having to enumerate every sequence, it is enough to observe that in any repeated subsequence the first two elements of each occurrence must be the same. In other words, every repeated pair could be the start of a longer repeated subsequence and every number that does not begin a repeated pair could not. So in your example, the repeated pairs are ...


0

You need a data structure and a way to manipulate it. One possibility is a tree. Each node of the tree (except the root) contains a value equal to a number in the input sequence, but the same value may (in fact usually will) occur in multiple nodes of the tree. Each node also contains a list of "starting points", which could just be the relative positions ...


0

With all due respect, I find most answers and comments so far kind of confusing, and there is no straight answer yet. For instance there is no point speaking of heuristics (thus of A* algorithm) since we do not have any information to help guide the search, and besides the issue as clearly stated is not search or performance, but the matter of node ...


0

Since nobody provided the details yet, here is your answer with correction: Enqueue the root node S. Queue = [S], Path = [] Dequeue S and examine it. Queue = [], Path = [S] Enqueue S's children, A and C. Queue = [A, C], Path = [S] Dequeue A and examine it. Queue = [C], Path = [S, A] -> All correct so far A has no children. Dequeue C and examine it. ...


-1

You might do in a vimdiff-like version: Step 1: identifying added, deleted and modified sentences. Step 2: for each modified sentence, locate the first and the last changed words, and cut anything not between these two words. If you need to keep coherent more grammar structure, look at the internals of http://www.languagetool.org/ or another shown on ...


0

You can easily see that if a point you are searching for it's at the same distance from two or more points, then they must all be at a distance such that d(a,b) is even. Given this, you can iterate over all the pairs {a,b} of fixed points, and add to your set of result points all the matrix points that are half the distance d(a,b) from both the points you ...


-1

Your goal is not to write unit tests and pass them, but to make sure that your program fits its requirements. The only way you can do this, is to precisely define your requirements in the first place. For example, you mentioned "three weekly inspections at random times". I'd say the requirements are: (a) 3 inspections (not 2 or 4), (b) at times that are not ...


1

One way to shuffle a list is to assign random numbers to each element in the list and sort by those numbers. We can extend that idea, we just have to pick weighted random numbers. For example, you could use random() * weight. Different choices will produce different distributions. In something like Python, this should be as simple as: items.sort(key = ...


1

First, lets work from that the weight of a given element in the list to be sorted is constant. It is not going to change between iterations. If it does, then For illustration lets use a deck of cards where we want to weight the face cards to the front. weight(card) = card.rank. Summing these, if we don't know the distribution of weights is indeed O(n) ...


0

I've used something like this to perform weighted random selection: Set running total to 0 For each item in the list, increment the total by item's eight and set and index or mark the item with the new total Pick a random number between 0 (inclusive) and the total (exclusive) Find (binary search?) the first item whose mark/index does not exceed the random ...


3

(Edit: Sorry, I missed that you wanted to visit all nodes in the graph, disregard my first answer, as I thought you wanted to find a path from point A to point B, rather than a path through every point.) The name of the problem you're trying to solve is the Travelling Salesman Problem. If you mean by "fully connected" a graph that is not disconnected, ...


0

First, you can get the time complexity down to O(n), while keeping the same space complexity. You can do this by filling visited in a single run of printBottom: void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[]) { if(node == NULL) return; if(lev[hd-min] < level){ ...


-1

The randomness of digits of pi (or for that matter any other sequence) can be arguably tested by so-called 'battery tests'. One popular battery test is George Marsaglia's Diehard Battery Test. There is also NIST Special publication 800-22 that describes a number of such tests and the results of applying these tests to a number of physical constants, ...


0

Sounds like a decision tree to me. Make a graph. Start with a root node, then for its children list all the movies that A could watch first. For each child, store the length of the movie and add nodes for each movie that A could watch after that child's movie ends. (i.e., you step out of theater 7 at 10:02 am and check the other 49 theaters to see ...


3

Let's go with this formulation: Another variant of the question goes like this: given a matrix with sorted rows, and sorted columns, find Kth smallest. Let M(1,1) denote the corner of the matrix with the smallest number and let M(n,n) be the corner with the highest number. (obviously they both are on the same diagonal of M). Now let's think of ...


0

If you have a pair of numbers a[i] and b[j] then the next value will be a[i+1] + b[k] with k<=j or a[k] + b[j+1] with k <= i. This means that you can get the next number by: int newI = i+1; int newJ = j; for(;newJ>=0 && a[i]+b[j]<a[newI]+b[newJ];newJ--){} int newI2 = i; int newJ2 = j+1; for(;new2I>=0 && ...


1

First create a list, indexed by vertical line, recording the maximum level found on that line. Walk the tree one time to fill in this list. At this point every list[vertical] entry contains the level that can be seen in the bottom view of the tree. Then walk the tree again, printing out each node whose level matches the maximum found on its line. int ...


0

There are still some things about your question that are unclear, but it seems like your rule for "bottom" is a node that does not have grandchildren. The following function will print all nodes that meet this definition of bottom: // Print out nodes that don't have grandchildren void printBottom2(Node *root) { if (root->left) { // recursive ...



Top 50 recent answers are included