Tag Info

New answers tagged

0

Ben Aaronson's answer is much better than either of my attempts, but I think the main reason is the technique he uses to iterate through the tree, using two Node pointers instead of one, rather than the more object-orientated style. The whole thing can be inlined, which allows a direct comparison with my version and shows that it is indeed more elegant, ...


0

There is no way to do what you want to do in Java. Java doesn't offer the freedom of C when dealing with pointers. The only pointers Java has are object references. Your first attempt is therefore as good as you can do in Java. You have to distinguish the case of left, right and root insertion. If creating and initializing the node is complex, you can ...


0

You can avoid the repetition by creating the new child Nodes earlier and defaulting them to empty, rather than using null to represent an empty Node. The body of your while loop might look something like: Node child = node.right; if (k < node.key) child = node.left; if (child.isEmpty()) { child.set(k, v); child.left = new Node(); //Could ...


5

Part of the problem is that you're not following good OO principles. In this case, the one that's probably most applicable is "Tell, don't ask": If you want a Node to add a child, you should tell it to add a child, you shouldn't ask it to expose all the relevant information you need then go ahead and add the child for it. Likewise, if (because you're doing ...


-2

`void delete( root, val ) { node = findNode( root, &par ); nodePred = node->pred; nodeSucc = node->succ; if ( nodeSucc ) nodeSucc->pred = nodePred; if( nodePred ) nodePred->succ = nodeSucc; // Node delete the node as usual as only parent child relation changes and // succ pred relation will still ...


0

I think that the first problem you have is the problem at hand: the conversion of a BST to a linked list. You probably want the elements sorted; you need to check the inorder traversal of trees, there is an easy, recursive solution that will solve your problem. The second problem, the 'bigger' one is how you learn algorithms after years of professional ...


1

You can use a derived mergesort you can grab chunks of the stack and sort them separately (standard divide and conquer) then you can simply merge as follows: struct node{ int element; node* next; } node* merge(node* begin1, node* end1, node* begin2, node* end2){ node* head; node* tail; if(begin1==end1)return begin2; ...


3

If just allocating objects for your smaller test cases are using several GB of RAM, and many small objects, you are right to worry about your larger cases. I would sit down and think carefully about your data needs for a larger test case. If it is pushing what you are comfortable with, I would radically restructure your program. For inspiration, read ...


0

Sometimes people use a head node with no data (a.k.a. a sentinel) rather than handling a NULL pointer for an empty list. This is discussed at Head node in linked lists on Stack Overflow and mentioned at sentinel node on Wikipedia. This can simplify code due to not needing special case handling for empty lists. The Wikipedia page also suggests it can improve ...


1

I am looking for a way of saying: Increase the weight of o1 by 1. Increase the weight of o2 by 1. Increase the weight of o1 by 1. Now give me the results sorted by their weight. This seems like a job for a priority queue, where the priority_number is the weight you want to assign.


3

Read some good algorithmic books (e.g. Knuth the art of computer programming). Learn several container algorithms techniques (hash tables, trees & balanced trees, linked lists, vectors, ...). Study some free software (hint: installing and using Linux is useful). Look on SourceForge and GitHub to find some of them. Learn several programming languages ...


0

For sorting you can override __lt__ and others compare function: import heapq class Item(object): def __init__(self, o, weight): self.o = o self.weight = weight def increase_weight(self, amount=1): self.weight += amount def __lt__(self, other): return self.weight < other.weight def __str__(self): ...


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): ...


1

Use a class class Thing(object): def __init__(self, o): self.o = o self.weight = weight You can make a list of Things, or a dict, or whatever works for you.


-1

You're asking for an SQL operation on a NOSQL database which seems rather illogical to me. That's approaching NOSQL with an SQL mindset, which you should let loose. For the problem you state I would say look into a NOSQL solution that provides full-text indexing like Apache Solr or Sphinx


1

The problem with a hash table implementation based directly on an array is that some of operations on it will inevitably require linear time array resizing (i.e., creating a bigger/smaller array and copying all data to it). There are multiple standard algorithms that approach this problem, like Linear Hashing or Cuckoo Hashing. Not so long ago another ...


1

Are you guaranteed to get to any rectangle from any other? (are there any gaps?) I'm presuming so, otherwise you can't determine what the relative coordinates are for the map. In that case, pick one arbitrarily and make that 0,0. Then it becomes a simple matter of walking the graph and assigning coordinates. If you require no negatives, then you'll need a ...


0

I don't fully follow what's going from your answer, but a couple of comments: 1. You should use contiguous memory. At the very least, at the outer level (for the x-y coordinates) you should have a single vector, not a vector of vectors. A vector is basically a pointer to a contiguous block of memory. A vector of vectors is a contiguous block of pointers, to ...


3

A priority queue can have any implementation, like a array that you search linearly when you pop. All it means is that when you pop you get the value with either the minimum or the maximum depending. A classic heap as it is typically referred to is usually a min heap. An implementation that has good time complexity (O(log n) on push and pop) and no memory ...


2

I think that what you wrote about concrete vs abstract is correct. Where you say that splay heaps, binomial heaps are different implementations of heaps though, I think it is more correct to say they are different types of heaps. Heap I think of as a category of implementation that generally guarantees not only the same interface, but also same access times. ...


1

I hope it's ok to answer my own question. I believe I have found the optimal (without overcomplicating the problem) data structure for my problem. There was at least minor idiocy on my part for not recognising this earlier. The data doesn't need to be accessed by (x,y,z) but instead by (x, y, range of z (say 0 - 3)). This give a C++ struct as follows: ...


8

Yours is a common-enough problem that the solution is has a name: an anticorruption layer. This is a layer that translates between an external API with an undesirable structure and the desired internal structure of your app. The idea is to limit the "corruption" of the undesired structure to as small a part of your code as possible. The external API ...



Top 50 recent answers are included