I came across a regular expression library http://laurikari.net/tre/ and also http://hackage.haskell.org/package/regex-tdfa , but I could not find anything about this "tagged DFA" approach that they are using: neither on the pages of these libraries, nor in google (incl.scholar). Anyone know what it is about? ...
Hi folks, I have defined a C#-class, that shall be the elements of a directed graph (basically a tree, but an element can have multiple parents - I do not know if there is a special name for that). Each element shall now all its children and all its parents. It exposes those lists as IEnumarable public interface IMyClass { public IE...
For no reason other than fun I implemented a Trie today. At the moment it supports add() and search(), remove() should also be implemented but I think that's fairly straight forward. It is fully functional, but filling the Trie with data takes a little too much for my taste. I'm using this list as datasource: http://www.isc.ro/lists/twl...
Hi, I have a module which supports creation of geographic objects using a company-standard interface. After these objects are created, the update_db() method is called, and all objects are updated into a database. It is important to have all objects inserted in one session, in order to keep counters and statistics before updating a pro...
Hello! I have a PHP web app that generates a somewhat complex report from our database. The resulting data structure to populate the report is a big ol' array, and it's heavily nested, and it's kind of a pain to dig into to find just one thing. Ideally I'd like to have some kind of data structure that I can just query, like a database....
I'm looking for a way to represent a "family tree" (family tree is an elaborate metaphor) in PHP. This means that children will need to inherit from two (or more) parents. Here are the requirements: 1, 2, or more parents Bonus points if I can attach metadata like a last name or relationship status Here is my non-working attempt (no ...
The graph is arguably the most versatile and valuable data structure of all. I can store single variables, lists, hashes etc., and of course graphs, with it. Given this, are there any languages that offer inline / native graph support and syntax? I can create variables, arrays, lists and hashes inline in Ruby, Python and Javascript, but...
Hi, Could someone direct me to some tutorial on Tree Data Structures using C. I tried googling but most implementations are for C++ or Java.If someone can point me to some online tutorials that are in C it would be great. Thanks.. ...
Hi, I have studied Tries and Suffix Trees and wanted to implement the same.... Please share some weblinks where in i can get an idea about the structure and basic idea of implementation to start with....... Any good examplee, if included... would be a pluss... Implementation in C....... Thankss.. ...
Given a sequence of integers, there are a number of queries. Each query has a range [l, r], and you are to find the median of the given range [l, r] The number of queries can be as large as 100,000 The length of the sequence can be as large as 100,000 I wonder if there is any data structure can support such query My solution: I con...
I want to improve my programming skills for a future job interview (and for myself) and I am looking for some book or text that has only problems and solutions (in some general language like C or in pseudo code) that illustrate basic algorithms and data structures. Problems that I expect to find are for example: find sub string in a ...
Possible Duplicates: How to sort in-place using the merge sort algorithm? Regarding in-place merge in an array Given an array of size N, which is divided into two sets of sorted integers(0 to P and P+1 to N-1). How would you sort this array using constant extra space (O(1)) and in O(n) time. For e.g A = {1,3,5,7,2,4,6,8}, h...
We have many documents that consists of words. What is most appropriate way to index the documents. A search query should support the AND/OR operations. The query runtime should be efficient as possible. Please describe the space required for the index. The documents contain words only(excluding AND/OR) and the query contains words and...
How to do it? What design patterns? Ideally would be sample code in the answer. ...
I'm going to develop my own message queue implementation in Java and I need to distribute the queue content across multiple servers so that it would provide reliability and redundancy. In addition to that I need to persist the queue content into the file system. Can somebody tell me what is the most suitable distributed data structure...
M is a 2D matrix of integers (nXm) they are sorted in both row and column Write a function search(int s) that return the exact location of the number or Null. What would be the most efficient way to do so? ...
suppose you need to implement container of a T items, which its value could be retrieved by numeric index (which is random access) and by name (as string). which one is better in term of performance of common operation such as retrieval, adding, and removing the items: (in this case retrieval by index need to be implemented by walking...
I've embarked on a project that is proving considerably more complicated than I'd first imagined. I'm trying to plan a system that is based around boolean (true/false) questions and answers. Users on the system can answer any questions from a large set of boolean (true/false) questions and be presented with a list showing the most simila...
Hi, Wanted to write a program to implement a dictionary of words using Tries Data Structure. Please tell me the structure for the implementation so that I could start the program, as i haven't got any article on internet, for Tries Implementation.. The confusion is, that when we search through the word, and we get through the word at...
This were the questions I was asked in the interview fews days back and I was not sure about the approach. Suggestions would be highly appreciated: How can I have implement PriorityQueue interface to get queue() method in O(1) and dequeue() method in O(n). How can I have implement PriorityQueue interface to get queue() method in O(n) a...