Questions tagged [data-structures]
Questions regarding efficient storage and representation of data within a software application.
1
vote
1answer
32 views
Tracking revision history by recording events
I've got a requirement to create a data structure that allows for users to view revision history. Not just the history of a table, but the history of the entire structure at a given point in time.
A ...
29
votes
5answers
5k views
What is the most efficient way to store a numeric range?
This question is about how many bits are required to store a range. Or put another way, for a given number of bits, what is the maximum range that can be stored and how?
Imagine we want to store a ...
0
votes
1answer
53 views
Data structure to group unique objects and support moving between groups maintaining uniqueness
I'm looking for a data structure that supports this use case - there must be one out there!
A set of objects of type T can be stored in a Group, parameterised by the type T. A grouping has a ...
0
votes
2answers
88 views
Is this OOP class structure for an RPG good enough?
So I have built a Telegram bot where you can play a rpg. This is the class structure.
Creature
MobType <-- Creature
Mob <-- MobType <-- Creature
Mob1 <-- Mob <-- MobType <-- ...
-2
votes
1answer
115 views
How to obtain and store a subgraph of a graph in C++?
I have implemented a graph structure (for graphs having ~30,000 nodes and ~300,000 edges) as follows:
class graph;
class node;
class edge;
class graph
{
public:
graph(){};
vector<node*> ...
0
votes
0answers
62 views
What kind of diagram best represents the field-level mapping from one system component to another?
In my environment, we have multiple systems developed independently by different teams. Those teams frequently recreate the wheel because they're building applications, not building blocks.
As a ...
1
vote
1answer
128 views
What is the right algorithm to solve this problem?
The problem is -
We have a series of boxes (A, B, C, D, ...).
Each box contains bricks of different colours. For eg.
Box A - red, blue
Box B - blue, red, green
... and so on...
and there are ...
2
votes
1answer
116 views
How to model workflows
I'm building a helpdesk-type system, where there are:
Customer - can submit/resubmit tickets;
Manager - can review submitted tickets, assign to developers (one ticket to multiple developers), review ...
1
vote
1answer
109 views
What is the best way to handle the scenario in C++ where there are two methods that are identical, except one is const?
I am currently working on a program in which I encountered an issue (not for the first time) where I have two acessor methods for a data structure. The methods are identical, except one is const and ...
1
vote
1answer
181 views
Which programming pattern is best for checking which partition a number lies in?
I have an interval partitioned into “MECE” subintervals, and I want to check which subinterval a number lies in.
(MECE stands for “mutually exclusive & collectively exhaustive”, meaning the ...
1
vote
1answer
48 views
Explanation of how to resolve Hash conflicts in HAMT or hashtables in general
I am working on trying to understand HAMT and now am uncertain generally what to do when you run into a conflict in a hash. All I understand so far is you create a list to append the keys to, but I ...
5
votes
1answer
114 views
Working with “external” object IDs
I have often encountered a situation in which users of a program (not necessarily human, just an external agent) need to be able to reference objects of a class with a certain "external" identifier, ...
-2
votes
2answers
127 views
How to handle multiple versions of binary file format
I'm writing a reader for the custom binary file format used in one game. The format has multiple versions for example:
struct FileHeader
{
ushort version;
uint fieldX; // version 1
uint ...
0
votes
2answers
98 views
Some Suggestion about Data Modeling
I want to make a social game for Android. I am using NoSQL Based Database (MongoDB) and I am using NodeJs. I am using Android-Volley library to make POST and GET requests. But I am stucked on ...
4
votes
2answers
205 views
How can one interpret an Abstract Syntax Tree without recursion?
I am busy building an interpreter for a Rebol-like language. I have previously built a Lisp interpreter where I used recursion, but now I just want to use a stack and not rely on the recursion ...
0
votes
2answers
72 views
What is the best method to avoid company data duplication in mixed B2C and B2B product in account creation?
I'm building a user license portal, store, SSO, and mini CRM and admin for internal people to manage those users for a niche 3D software company, similar to Autodesk. Licenses are sold to both ...
2
votes
1answer
126 views
Do we include output space in space complexity?
For example. I have a function which generates an array with random numbers.
int[] generateNum(int n) {
int[] result = new int[n];
/* Logic to generate random number */
...............
...
0
votes
1answer
44 views
How a Merkle tree can work with Graph data, or a better data structure
I am looking at blockchain and trying to see how Merkle trees (or perhaps Merkle DAGs) can fit to a graph data structure with circular references.
For example, say I have this data model:
var ...
0
votes
1answer
140 views
Efficiency in Java: Object reference vs id reference
I have to represent a certain data structure, in which I have nodes that are related between them. Each node has its numeric id, and a list containing the next directly related nodes and another list ...
0
votes
0answers
20 views
How to combine multiple Tries for complex searching and filtering across tables?
Say I have a database with 100 tables. Scattered throughout the tables are some string columns for short things that could be considered usernames/tags/categories/hashtags/addresses/placenames/other ...
1
vote
1answer
29 views
Data Matching In VBA - Best way to deal with dynamic data and user entry?
Background
I am currently building this project with VBA, just to keep in the back of your mind when thinking about my question.
Imagine 2 adjacent blocks, in Excel. The first block is made up of ...
-6
votes
1answer
36 views
Give a list of a from area code and to area code and a distance between them,which data structure?
What data structure i can use to lookup given a fromCode and toCode apart from hashMap which results in more number of entries in the memory.
We are ok with log(n) efficiency also.
Example data:
...
2
votes
2answers
117 views
How to structure database for daily events?
I'm storing data which logs whether or not a user has logged their attendance for a given day. Some days are unimportant (holiday, weekend), so those are also stored.
The two requirements are that:
...
4
votes
2answers
238 views
Game Playing AI - Strategy to overcome the transposition table taking up too much memory?
I've made an engine that plays Connect Four using the standard search algorithms (minimax, alpha-beta pruning, iterative deepening, etc). I've implemented a transposition table so that the engine can ...
-1
votes
2answers
234 views
How to represent a directory structure in a binary tree?
I was just thinking about implementing a binary tree with its root pointing to the parent folder and then the children pointing to subdirs nested within to store a directory structure in a binary tree....
2
votes
1answer
97 views
Achievement System CRUD data structure
I'm developing this Achievement System and it must have a CRUD, that admins access to create new achievements and it's rules. I need some help with the Achievement CRUD data structure.
Rules sample
...
-3
votes
1answer
82 views
How to determine the collection type without access to the source code [closed]
How could you determine if a collection is implemented as an array or as a linked structure without access to the source code (assuming you can run the code)?
2
votes
2answers
156 views
Finding an efficient data structure and/or algorithm
I am tasked with an animated graph based on a timeline, and I am having trouble finding a suitable data structure and/or algorithm that's reasonably efficient. I have a working system suffering from ...
1
vote
1answer
70 views
A table for each field type or one all-in-one table model?
I am creating an application where users can create forms with many fields of text, numeric, date and select types.
The model will have a forms table referenced by responses table;
It also have the ...
1
vote
1answer
101 views
Managing heterogeneous data
The underlying problem is one I seem to run into a lot. You have a collection of objects with some things in common, but other information about the objects may apply to some of them but not to others....
1
vote
1answer
40 views
Dictionary Application: Suggestions for serialization format and data structure
I want to create a dictionary application.
One of the design guideline is performance in querying and showing up the definitions of words.
I would like some suggestions on two design choices:
Which ...
0
votes
2answers
60 views
What are formats to store geographic maps for a robot to travel point A to point B
Very beginner. Need to compute route from A to B for a robot. i would like to know how to store area map and compute the route. I can compute shortest path etc using algorithms e.g. dijkstra. What ...
1
vote
1answer
191 views
Binary Search Tree with ID and Duplicate Values
I'm having trouble finding resources for this implementation I'm trying to figure out. I want to save nodes in a binary search tree (self balancing) containing an ID and value
struct Score
{
int ...
2
votes
2answers
324 views
Can nested loop have linear time complexity
I was going through the traditional quick sort algorithm. I had a look on the partition algorithm in a couple of places and the implementation difference was very subtle. Here are the 2 approaches:
...
0
votes
1answer
66 views
Data Structure to join points by similarity measure
I have a series of points (x,y) and each point has a colour (in the LAB colour space). I need to associate points by similar colour and then spatially. So the end result is each point becomes part of ...
-2
votes
2answers
45 views
database/orm model design for contacts
I am building a internal crm which has contacts which are just people with first name, last name, email, phone etc. Contacts can be one or more types e.t.c. job candidates, hiring managers, customers, ...
1
vote
0answers
71 views
How to use lock-free FIFOs in multi-threading?
Computer-science wisdom says that a lock-free FIFO (queue) is the right way to synchronize shared data between two threads in a lock-free manner. I know what a queue is and how the lock-free property ...
0
votes
1answer
56 views
Subdomain matching
I am working on a small plugin for a DNS server. I have a static list of domain (sometimes subdomains too) names:
gaming.xyz.com
facebook.com
mail.example.com
blog.example.com
I want to check if a ...
2
votes
2answers
112 views
How to model JSON data so it can be easily de-serialized in to simple Java classes?
Context
Currently I'm struggling with correctly modeling a small instruction set I want to send as JSON to an Android application to generate a list of UI parts. Right now it's layered as pretty much ...
2
votes
1answer
85 views
trie iteration should include root?
I'm working on a trie data structure. My simple, initial understanding: trie data structures require a fixed root node. This node cannot be deleted.
When iterating through all nodes in a trie (in ...
2
votes
3answers
231 views
How should I implement custom database fields?
I'm building an app where end users can add custom fields to database tables. Think of it like a CRM app, where sometime you just need to add an extra field to your customer table. Pretty much all ...
0
votes
1answer
143 views
How fuzzy search is implemented for file paths
Say I have file paths like this:
my/long/directory/structure/index.js
my/long/directory/structure2/index.js
my/long/directory/structure3/index.js
my/long/directory/structure.../index.js
my/long/...
1
vote
1answer
85 views
Which datastructure to use for temporary storage of intermittent and asynchronous sensor data?
Here an outline of the setup:
Input data:
I have several sources for sensor input data (GPS, and a bunch of other sensor data from different sources).
All of those individual inputs consist of a ...
0
votes
1answer
100 views
Express unique recursive task system
I would like to express a task as either itself or a container for other tasks (recursively). The problem is that each task has to be one of two fundamental types: a goal or a routine. And, children ...
57
votes
16answers
11k views
How should I store “unknown” and “missing” values in a variable, while still retaining the difference between “unknown” and “missing”?
Consider this an "academic" question. I have been wondering about about avoiding NULLs from time to time and this is an example where I can't come up with a satisfactory solution.
Let's assume I ...
2
votes
1answer
625 views
How would you design a “multithreaded” LRU cache using C++ (unordered_map and Linkedlist)?
Please note that this is about a thread-safe LRU cache (not simply a LRU cache as specified in https://leetcode.com/problems/lru-cache/description/). It isn't a duplicate of LRU cache design question ...
1
vote
1answer
132 views
Find a string in list of strings
Background:
I am writing an application for a small embedded device. There is a static list of strings: currently about 500 strings and string length is 12 characters on average. The list might ...
0
votes
3answers
329 views
how can i return the median of a threaded binary search tree in constant time?
I'm having a trouble with understanding how to implement and find the median of a threaded binary search tree in constant time.
The tree consists of a worker's id and name.
The given details are ...
17
votes
9answers
3k views
How is polymorphism used in the real world? [closed]
I am trying to understand how Polymorphism is used in a real life project, but I can only find the classical example (or something similar to it) of having an Animal parent class with a methodspeak(), ...
2
votes
1answer
191 views
Data Structure for “Intuitive” Text Matching
I've noticed that text editors and such have a more-than-prefix/suffix-based pattern matching algorithm going on behind the scenes. And StackOverflow's tag matching algorithm does more than just ...
