Find the number of disjoint sets
c++,algorithm,data-structures,disjoint-sets,disjoint-union
Each union operaiton on two items a,b in Disjoint Set Data Structure has two possible scenarios: You tried to unite items from the same set. In this case, nothing is done, and number of disjoint sets remain the same. You united items from two different sets, so you basically converged...
Why this DFS code is not working in some cases?
This should work: public static void PrintDFS(){ int source = 0; int numberOfNodes = arr[source].length; int [] visited = new int[numberOfNodes]; int v; stack.push(source); while (!stack.isEmpty()){ v = stack.pop(); if(visited[v]==0) { visited[v] = 1; System.out.println(v); for(int i=0;i<numberOfNodes;i++){ if(arr[v][i]==1) stack.push(i); } } } } The main issue in the original code...
Binary Search - Best and worst case
3. is indeed correct, as you will need to go through the algorithm and terminate at the "worst" stop clause, where the list is empty, needed log(n) iterations. 1. is not correct. The best case is NOT when the first element is the target, it is when the middle element...
Is it possible to create an ordering for a list of generic elements?
c++,algorithm,data-structures,binary-tree
There is no such feature in C++ (as of 2015, hence including all standards up to C++14). However, Bjarne Stroustrup has written a proposal to add default comparison operators to the standard. What this essentially does is generating a comparison operator for you, in case you don't declare these operators...
How does Redis Cluster handle replication for sorted sets ZSET (and others)?
data-structures,redis,sortedset
Redis' replication is operation-based, meaning that the slaves get the stream of write commands from the master. The replication mechanism isn't related to the clustering functionality and works the same whether used in a cluster or by a standalone Redis server. The replication is extremely reliable but note that it...
find the biggest possible number comprised of the digits of of a given number
Best I can do is O(1) space and O(log(N)) time. Pretty sure it's impossible to do any better because at the bare minimum you have to analyze each digit in the input, which is log(N) right there. The short answer is, sort the digits of N in descending order. Pseudocode:...
Write and read 3D arrays in R
Your issue is that you are using write.table to do this, so it is (I believe) coercing your array to a table. If you are looking to save it and don't mind that it would be in an R-specific format, you can easily use the save and load functions. save(v.arr,file...
Dequeue algorithm
algorithm,data-structures,queue,deque
There are two common ways to implement a deque: Doubly linked list: You implement a doubly linked list, and maintain pointers to the front and the end of the list. It is easy to both insert and remove the start/end of the linked list in O(1) time. A circular dynamic...
Matlab: how to sum fields of two equivalent structures?
Here is a solution, for any depth of struct The code of the script (or MATLAB command) a(1).x=1; a(1).y=2; a(1).z.w=3; a(2).x=4; a(2).y=5; a(2).z.w=6; c=a(1); c = returnStruct(c, a(2)); %{ you can also sum any amount of structs for i=2:length(a) c=returnStruct(c, a(i)); end %} with the recursive function function rs =...
Getting wrong value in variable in c using structs
You are using "%d" to print a float. That leads to undefined behavior. Instead of printf("\nEl valor del cociente es: %d",(polinomio_->polinomio->cociente)); use printf("\nEl valor del cociente es: %f",(polinomio_->polinomio->cociente)); // ^^^ ...
Efficiently transferring elements between arrays
javascript,arrays,optimization,memory-management,data-structures
splice is pretty harmful for performance in a loop. But you don't seem to need mutations on the input arrays anyway - you are creating new ones and overwrite the previous values. Just do function doTransfers() { var A_pending = []; var B2_pending = []; for (var i = 0;...
What does it mean to “close over” something?
A closure is a pair consisting of a code pointer and an environment pointer. The environment pointer contains all of the free variables of a given function. For example: fun f(a, b) = let fun g(c, d) = a + b + c + d in g end val g...
Djikstra Algorithm
c++,algorithm,data-structures,dijkstra,shortest-path
In minDistance(), if (includ[v] == false && dist[v] <= min) min = dist[v]; min_index = v; You missed { }. min_index = v; is executed no matter the condition is true or false....
Why would one use a heap over a self balancing binary search tree?
data-structures,tree,heap,binary-search-tree,avl-tree
A heap may have better insert and merge times. It really depends on the type of heap, but typically they are far less strict than an AVL because they don't have to worry about auto balancing after each operation. A heap merely guarantees that all nodes follow the same style...
Datastructure related. Find all arrays elements greater than or equal to given input
java,algorithm,data-structures,graph-algorithm
The approach that comes to mind could be to keep an ordered list of the orders and perform a binary search for the limit amount. All orders before that point in the ordered list will be less than the limit amount. // Generate a random array of numbers Random r...
How to integrate different data struct into one ? Any design pattern or exprience?
c++,design-patterns,data-structures,struct,architecture
The keyword here is abstraction. Here is one way of doing it : #include <iostream> struct s1 { int s1Price; int s1Volume; }; struct s2 { int s2Price; int s2Volume; }; class Idata { public: virtual ~Idata() {} public: virtual int getPrice() = 0; virtual int getVolume() = 0; };...
undirected weighted graph data structure in c++
c++,class,c++11,data-structures,graph
I advise you to use a Link structure, to represent an edge in the graph: struct Link { Node *N; float weight; } Then each Node can contain vector<Link> neighbors; This way there is no duplication of Nodes. There is a duplication of weights, since if Node A has a...
Singly linked list, why is the list empty (head == NULL)?
c++,list,c++11,data-structures,singly-linked-list
You have to remember that arguments to functions are by default passed by value, which means that the arguments value is copied and the function only works on the copy and not the original. Now take the append function, when you pass the head argument the pointer is copied into...
What is meant by complexity of O(log n)?
algorithm,data-structures,tree,binary-tree,binary-search-tree
I'd call your understanding not quite correct. The big-O notation does not say anything about an exact amount of steps done. A notation O(log n) means that something is approximately proportional to log n, but not neccesarily equal. If you say that the number of steps to search for a...
How does inorder+preorder construct unique binary tree?
algorithm,data-structures,binary-tree,inorder,preorder
Start with the preorder traversal. Either it is empty, in which case you are done, or it has a first element, r0, the root of the tree. Now search the inorder traversal for r0. The left subtree will all come before that point and the right subtree will all come...
Difference in performance of adding elements in Treeset directlt vs transferring from arraylist?
java,arraylist,data-structures,treeset
TreeSet.addAll(c) method does the optimization only if the c is an instance of SortedSet. In other cases it just iterates over the collection and adds elements one by one. Therefore, it does not make any sense to put elements into ArrayList first and then use TreeSet.addAll(list) method. You will get...
Bubble sort on linked list
c,sorting,data-structures,struct,linked-list
Change you swap function void swap(cart **ptr1, cart **ptr2){ cart *temp = *ptr1; *ptr1 = *ptr2; *ptr2 = temp; } What you do is passing a pointer and change its value locally. You need to pass the address of the pointer (pointer to a pointer) instead. Make sure where you...
Understanding queue arithmetic in data structures
You want to think circularly here in terms of relative, circular ranges instead of absolute, linear ones. So you don't want to get too hung up on the absolute indices/addresses of FRONT and REAR. They're relative to each other, and you can use modulo arithmetic to start getting back to...
Does separating read/write operations improve program efficiency?
java,algorithm,performance,file-io,data-structures
This depends on the way you implement parallelism in your data crunching part. At the moment you sequentially read everything - then crunch the data - then write it. So even if you broke it into 3 threads each one depends on the result of the previous. So unless you...
TreeSet not Re-Ordering Itself after Values in it are Changed
java,data-structures,order,comparator
The TreeSet won't reorder itself when you change the value of the elements. You have to take the elements out and re-add them if you want them to remain ordered: Node first = ts.pollFirst(); first.s--; ts.add(first); ...
C++ - need suggestion on 2-d Data structure - size of 1-D is not fixed
To memory management will be fine using STL (dynamic memory alloc), performance will go down because is dynamic and doesn't do direct access. If you're in complete dispair you may use a vector of pairs, with the first as an static array and the second, the count of used elements....
What part of my code is making my performance suffer? (Codility's MaxCounter)
java,algorithm,data-structures,big-o,time-complexity
Instead of calling Arrays.fill(answer, minimumValue); whenever you encounter a "max counter" operation, which takes O(N), you should keep track of the last max value that was assigned due to "max counter" operation, and update the entire array just one time, after all the operations are processed. This would take O(N+M)....
popStack pops out data that I didn't push (stack adt)
for (i = 0; i < 2; i++) { ... pushStack (stack, &i); // Push address of i } You are pushing (same) address of i twice. Which after loop end contains 2. When you pop back, you get the address which contains 2 and hence the output is 2...
Removing a node from a LinkedList (C#)
c#,data-structures,linked-list,hashtable
You'll want to loop through the list until the next node is the one you want to delete. Then set the current to the next nodes next node. public void Delete(string value) { if (head == null) return; if (head.Value == value) { head = head.Next; return; } var n...
JAVA-passing the root in method arguments of a Binary Tree
You are trying to access an instance variable from a static context. The main method is static. Hence it cannot refer to the instance variable root of the Tree class. This should not even compile. Typically, what you would do in this case, is to make your findMax(Node) method private....
Stack, Queue, Tree?
It cannot be a queue, because a queue only supports "popping" the oldest item (FIFO: first in first out), and 1 is inserted last.
How to write a structure into a file in PHP?
You could write your structure to a file with file_put_contents as you have outlined in your post. You can serialize and unserialize the arrays or objects into the file using the following documentation: http://php.net/manual/en/function.serialize.php http://php.net/manual/en/function.unserialize.php So it would look like this: file_put_contents($fileName, serialize($MyStructure), FILE_APPEND); ...
“Must use 'struct' tag to refer to type 'node'”
Let's look at the first snippet: typedef struct node { char * fx; // function node * gx; // left-hand side char * op; // operator node * hx; // right-hand side } node; gx and hx occur in the middle of the struct node/node type definition, before the typedef...
Does C have a shorthand way of initialize a struct with malloc and set its fields?
c,data-structures,struct,initialization,malloc
You can write your own wrapper function: static node *getNewNode(char *fx) { node *p = calloc(1, sizeof *p); if(p && fx) { p->fx = malloc(strlen(fx) + 1); if(!p->fx) { free(p); p = null; } else { strcpy(p->fx, fx); } } return p; } Later you can call this as: node...
Combine two or more columns into one in a table
sql-server,data-structures,combinations
This can be done by a simple update statement: Update table Set colC = colC + char(13) + char(10) + colD +char(13) + char(10) + colE Note that char(13) + char(10) is a line break. After you verify that the data was copied, use alter table to drop colD and...
Basic Python code not Working
python,algorithm,data-structures
Following points need to apply code: Define lower and upper limit outside of for loop becsue if we define inside while loop, every time lo and hi variable will create with 0 and 100 value respectively. Give variable name according to variable work. lower = 0 higher = 100 God...
Best C++ approach to store unique elements
Here is an example of how you could create and use such a structure // Example program #include <algorithm> #include <array> #include <iostream> #include <set> int main() { std::array<std::set<double>, 4> bins = {std::set<double>{1.0, 2.0, 5.0}, std::set<double>{7.0, 2.0}, std::set<double>{3.0, 9.0 ,1.0}, std::set<double>{7.0, 0.0, 1.0, 4.0}}; bins[1].insert(3); for (auto const& bin :...
Slow Python Red Black Tree Performance
python,data-structures,red-black-tree
I did quick profiling of your program with cProfile. It seems, that most amount of time is spent in color function. [email protected]:/vagrant$ python -m cProfile tree.py 4227046 function calls (3801045 primitive calls) in 3.498 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.006 0.006 3.498 3.498...
What is the best way to iterate two hashmap in same loop in java?
java,data-structures,collections
There really isn't a better option than for (Map.Entry<String, String> entry1 : map1.entrySet() { String key = entry1.getKey(); String value1 = entry1.getValue(); String value2 = map2.get(key); // do whatever with value1 and value2 } ...
Error Queue implementation using Linked List
c++,data-structures,linked-list,queue
void enQueue(int x){ Node* temp = NULL; //Node* temp = new Node; temp->data = x; //BOOM temp->next = NULL; if(front == NULL && rear == NULL){ front = rear = NULL; //What? return; } rear->next = temp; rear = temp; } You are assigning to an invalid address. This will...
Unknown Data Structure?
There is no "name" for this that I know of, but an array of linked list nodes would work quite well for this. Traditionally linked lists are separate and simply a row of items pointing to the next. However, there is no reason why certain linked list nodes cannot point...
Initialize Const variable of struct
No that code does not make sense. The pin member is const so you can't assign to it except in the initializer. The pin member, is not a pointer so assgning malloc() to it is not going to compile correctly. I think you need to remove const from the struct...
Maximum width of a Binary Tree using preorder traversal
c++,data-structures,tree,binary-tree,binary-search-tree
The main work is being done in getMaxWidthRecur. It's initially given the parameter level = 0. The level parameter is incremented by 1 whenever we recurse down one level in the tree. The recursion will hit each node in the tree exactly once, and for each node in the tree,...
WPF Reading / writing JSON vs XML
c#,json,xml,wpf,data-structures
Theoreretical advantage of XML is that you can have some sort of querying using xpath and potentionally work with larger sets of data. Specifically in WPF you have XmlDataProvider, where you can databind your UI controls directly to xml nodes. That's theory. In real world, you will almost for sure...
Creating an Array of Arrays in Julia
arrays,data-structures,julia-lang
You can construct your array of arrays like so: # Initialize an array that can contain any values listOfLists = Any[] # Push some arrays into the array push!(listOfLists, [1, 2, 3]) push!(listOfLists, [4, 5]) push!(listOfLists, ["Julia", "rocks"]) # You now have an array containing arrays listOfLists # 3-element Array{Any,1}:...
Insertion with implementing 'Linear Hashing'
I have now reimplemted it completely and found a lot of errors e.g. implicit recursion of the split and rehash functions.
Program to disintegrate a number into fibonacci numbers
It can be reduced to subset-sum problem, where the set is the fibonacci numbers smaller/equals the given number. First generate all numbers smaller/equals the given number n. C-like pseudo code: int i = 1; int* arr = //sufficiently large array arr[0] = arr[1] = 1; while (arr[i] <= n) {...
How to delete doubly linked list data and return it?
c++,data-structures,linked-list,doubly-linked-list
Assuming head is at position p == 0, then you should first check that head is not the last element since the list will be empty if it is. Then you simply iterate over the list until the desired position and set temp's prev->next to temp->next and similarly temp's next->prev...
Search B-Tree in O(log(t)*h)
You can do a binary search to find the key you need within one node. Or, better, store all keys and links within a node in a binary search tree....
Need help coming up with best structure for declaring/populating many arrays of XYZ data
arrays,vb.net,visual-studio-2010,data-structures
Another approach is to use a structure with the basic data then some generic lists to contain the data. it's type safe. fairly resource neutral, and keeps all the objects inside one object. I tend to wrap the generic like this to simplify passing the top level data object to...
read variable excel data into variant with the same format
excel,vba,excel-vba,variables,data-structures
You could force test to be an array with only one cell, if the last column is B or less : ' Define Last Column with a value LastCol = Sheets("Filter").Cells(20, Sheets("Filter").Columns.Count).End(xlToLeft).Column Col_Letter = Split(Cells(1, LastCol).Address(True, False), "$")(0) If LastCol <= 2 Then ReDim test(1 To 1, 1 To 1)...
Choosing the data structure for orgaininsng data with list of values in java
I would do this: Map<Integer, List<String>> dataMap = new HashMap<>(); dataMap.put("B1".hashCode()+"RtyName".hashCode(), Arrays.asList("weepn", "weepfnb", "eedgeft", "xbteehy")); dataMap.put("B1".hashCode()+"rtyRate".hashCode(), Arrays.asList("deed", "ww", "terrty", "hteetyure")); dataMap.put("B2".hashCode()+"RtyName".hashCode(), Arrays.asList("SSSweepn", "wpefSSSnb", "GGeGdgeft", "xbteYYYYhy")); dataMap.put("B2".hashCode()+"rtyRate".hashCode(), Arrays.asList("WWded", "wTeTYw", "YYYYtrerty",...
Perform insert,search and delete queries on an array in less than O(n) time and using O(1) auxillary space
arrays,data-structures,time-complexity
Here's an implementation that still has O(n) runtime for insert and delete, but which gets lookups running in time O(log n). Have as your data structure a dynamically-allocated, sorted array with no slack space. To perform a lookup, just use binary search in time O(log n). To do an insertion,...
Given a BST, and a node in BST, make that node, as new root of the tree
algorithm,data-structures,tree,binary-search-tree
In the general case, your algorithm needs perform a series of tree manipulations in the form of sub-tree rotation (as described in @Quicky's answer). The algorithm should look like this: While node_to_be_root is not the root of the whole tree: Rotate the sub-tree where the node_to_be_root is the pivot and...
Why is the hash table resized by doubling it?
java,performance,algorithm,data-structures,hashtable
Q: But most textbooks say that the best size for the table is a prime number. Regarding size primality: What comes to primality of size, it depends on collision resolution algorithm your choose. Some algorithms require prime table size (double hashing, quadratic hashing), others don't, and they could benefit...
What is the current size of Stack?
algorithm,data-structures,stack
You popped a total number of 10-3 = 7 elements, since 3 of the pops did not change the state (and size) of the stack, so only 7 pops did. You pushed a total of 25 elements. Top operations do not change the state (and size) of the stack,...
How to create structure in MATLAB with many repeated substructures in an efficient way?
Here is one idea to create the Left field. You could try to adapt it to create the other fields as well: myStruct.Left = cell2struct(repmat({repmat(struct('x', [], 'y', [], 'z', []), 3, 1)}, 18, 1), num2cell('A':'R'), 1); ...
Implement queues in java [duplicate]
When you write koka.pas = null, there is no koka whose pas you can set. You must initialize that somehow.
Algorithm to find k neighbors in a certain range?
algorithm,data-structures,graph-algorithm,nearest-neighbor,point-clouds
Your problem is part of the topic of Nearest Neighbor Search, or more precisely, k-Nearest Neighbor Search. The answer to your question depends on the data structure you are using to store the points. If you use R-trees or variants like R*-trees, and you are doing multiple searches on your...
Print data-structure/ Data-type hierarchy
Please see if the following fits your requirements: def ppt(data): if isinstance(data, int): return "Int()" elif isinstance(data, str): return "Str()" elif isinstance(data, list): if len(data) == 0: return "List()" else: return "List()<" + ", ".join([ppt(item) for item in data]) + ">" elif isinstance(data, dict): if len(data) == 0: return "Dict()"...
Why do the same hash keys have different order when printing?
perl,sorting,data-structures,hash,perl-data-structures
When printing a hash there are a few different notions of order that are relevant: "insertion order", "sort order" and "random". See the ENVIRONMENT section of the perlrun documentation for a discussion of ways you can control this behavior and for the reasons why the default is to use hash...
C - Is realloc'ing arrays to arrays twice the size efficient in dynamic data structures?
As with all "most efficient" questions, the only way to know is to measure the actual performance in real-life conditions. Generally speaking, there can be big performance gains from having items in consecutive memory locations, as that's almost always the most cache-friendly layout for any algorithm that's processing the items...
List of Elements to Boolean Array
python,arrays,numpy,data-structures,scipy
Well, here are several ways for achieving this: Map Using Python's map built-in function you can do that easily. animal_list = ['cat', 'elephant'] your_list = ['dog', 'horse', 'cat', 'shark', 'cancer', 'elephant'] res = map(lambda item: item in animal_list, your_list) print res Output [False, False, True, False, False, True] List comprehension...
Implementing a List data structure in java
Well, for starters... display() is not a method of class linkedList (note: naming convention should be LinkedList). display() is a method of Lista. That is why the IDE is telling you 'display() is undefined for the type linkedList' Just quickly looking at your code for what you need to do......
Is there a mistake in this illustration?
java,data-structures,linked-list,singly-linked-list
The way I see it the code seems wrong and previous should have been set to position before it was actually changed. Something like this: public void add(Object element) { previous = position; if(position == null) { addFirst(element); position = first; } else { Node newNode = new Node(); newNode.data...
strlen returning wrong value
You are not copying the nul terminator, a c string needs a '\0' at the end, so if it has 4 characters it uses 5 bytes, the last one being '\0' which is not copied in your loop. You should however use strcpy() instead of copying they bytes one by...
Java - Most efficient structure for quick retrieval
look at set (Hashset, enumset) and hash (HashMap,linkedhash...,idnetityhash..) based implementations, they have a speed complexity of O(1) for the contains() method. this is a great link to use...
How to determine there are no running jobs or consumer process exit
No one answer my question, but I came up a solution on my own. step 1. Before the producer starting to put jobs into the queue, I set a flag key: SET dispatch.finished 0. step 2. After the producer finished putting all jobs into the queu, change the flag: SET...
Hierarchy data structure wih efficient query algorithm
java,algorithm,data-structures
If your data fits into memory then you can implement this by putting a Set of children in each node of the hierarchy and then walking the sets to determine if the path is valid, for example class University { private Set<Major> majors; } class Major { private Set<Student> students;...
How to properly instantiate a MultiSet (created on my own) using Python
python,data-structures,multiset
It looks like you're conflating two things: data structures - using Python (or any other language, basically), you can implement linked lists, balanced trees, hash tables, etc. mapping semantics - any container, but an associative container in particular, has a protocol: what does it do when you insert a key...
Why is this structure being sent by parameter?
c,visual-studio,data-structures,parameter-passing,pass-by-reference
Because you are passing the address of the pointer, which is not the address of the struct, just remove the & in the first version void iterations(Block64 *blocks) { printf("This is the first char: %c", get_64bBlocks_char(blocks, 0, 0)); } since you are passing a pointer, then you don't need to...
strcmp performance in C
c,string,algorithm,data-structures
Yes, this is in O(n) in the average and worst case, where n is the length of the shorter of both given strings. You could also express that as O(min(m,n)) with m and n being the lengths of both strings, respectively. But no, O(n) doesn't mean that it needs exactly...
Is it possible to load a particular range of a serialized python dictonary from hard disk?
how did you serialize the data? (pickle/json/...) also note that elements in a dictionary are not sorted (except if you used a collections.OrderedDict). so retrieving a range of elements may not give what you expect. if the amount of data you are trying to handle exceeds the memory wouldn't it...
How do I create a dictionary that indexes the location of certain keys?
python,dictionary,indexing,data-structures
From what I understand, you want a dictionary that is capable of returning the keys of dictionaries within dictionaries if the value the key's are associated with match a certain condition. class SubclassedDictionary(dict): def __init__(self, new_dict, condition=None, *args, **kwargs): super(SubclassedDictionary, self).__init__(new_dict, *args, **kwargs) self.paths = [] self.get_paths(condition) def _get_paths_recursive(self, condition,...
Is there a data-structure similar to JSON in JAVA? [closed]
java,json,data-structures,associative-array
If you want a 'generic' collection, why not use a Guava MultiMap ? A collection that maps keys to values, similar to Map, but in which each key may be associated with multiple values. You can visualize the contents of a multimap either as a map from keys to nonempty...
Datastructure choice issue
python,list,python-2.7,data-structures,tuples
Sounds like you're describing a dictionary (dict) # Creating a dict >>> d = {'Date': "12.6.15", 'FilePath': "C:\somewhere\only\we\know"} # Accessing a value based on a key >>> d['Date'] '12.6.15' # Changing the value associated with that key >>> d['Date'] = '12.15.15' # Displaying the representation of the updated dict >>>...
Load Dictionary Text File Into Java
java,dictionary,data-structures,hashmap
While your input does not look exactly like JSON, you might be able to preprocess[1] it in a simple way to make it valid JSON. Because JSON is probably much more widespread and therefore better supported than your custom format. If your problem then is JSON deserialization, then take a...
Given binary tree create linkedlist of all the nodes at each depth (BFS or DFS)
Here is some code which will solve your problem: Map<Integer, List<Node>> mapOfLinkedList = new HashMap<Integer, LinkedList<Node>>(); void addNode(Node root, int level) { List levelList = mapOfLinkedList.get(level); // get List for current level if (levelList == null) { levelList = new LinkedList<Node>(); } levelList.add(root); // add Node to the current level...
Does C have any tools for doing string addition?
c,string,algorithm,data-structures,tree
If your C standard library is GNU or *BSD, then you probably have asprintf available. You may need to enable a feature test macro to use it, though. If you don't have asprintf available, it can easily be defined in terms of the C standard vsnprintf function. asprintf returns the...
Implement two stack in one array
If you are trying to implement it this way that both stacks start from left side of the array. Push and pop won`t be O(1). Since the elements of both stacks will be intermixed among each other and you have to maintain whether a position belongs to stack1 or stack2...
Get duplicate values from dictionary
With your current structure, you're in a bit of trouble because you don't necessarily have an easy way to compare two List<string> to see if they are equal. One way to work around this is to create a custom List<string> comparer that implements IEqualityComparer<List<string>>. However, since you have a list...
Trial division for primes with immutable collections in Scala
algorithm,scala,data-structures,functional-programming
According to http://docs.scala-lang.org/overviews/collections/performance-characteristics.html Vectors have an amortised constant cost for appending, prepending and seeking. Indeed, using vectors instead of lists in your solution is much faster def primes(n: Int) = { @tailrec def divisibleByAny(x: Int, list: Vector[Int]): Boolean = { if (list.isEmpty) false else { val (h +: t) =...
How much time the fastest supercomputer will take to run this code? [closed]
java,performance,algorithm,data-structures,time-complexity
A very rough estimation follows. According to wikipedia, the fastest supercomputer at the time of writing has 33.86 petaflops. We have: 33.86 petaflops = 33.86 * 10^15 ~= 3 * 10^16 FLOPS The recursive algorithm requires about phi^n operations, where phi is the golden ratio, equal to ~1.618. We have:...
Is doubly linked list a non linear data structure or linear data structure?
data-structures,doubly-linked-list
Non-linear data structures are those data-structure in which the elements appear in a non-linear fashion,which requires two or more than two-dimensional representation . The elements may OR mayn't(mostly) be stored in contiguous memory locations,rather in any order/non-linearly as if you have skipped the elements in between. Accessing the elements are...
String Pattern Matching Algorithm Used in Different Applications [on hold]
arrays,string,algorithm,file,data-structures
For instance a single string matching is the z-algorithm. It's the fastest matcher.
Type constraints become huge and unreadable for simple code
haskell,design-patterns,data-structures,typeclass
Your particular example could be solved by using ^-^ and liftI2 (/) instead of - and / respectively. This reduces the constraint to (Foldable f, Metric f, Ord a, Floating a). Using ConstraintKinds you can make constant aliases to reduce cluster: type OrderedField a = (Ord a, Floating a) type...
Which is the correct way to dynamically use variating static data
I would store this configuration values in an external YAML file. Your configuration file could looke like this: # config/providers.yaml provider_a: url: 'http://url_for_login_form.com/' name: 'name_of_form' fields: - name: 'name_of_field' value: 'value_for_it' - name: 'another_field' value: 'another_value' provider_b: url: 'http://...' ... You could load that file with YAML.file_file that returns nested...
Find root of minimal height which is not BST
algorithm,data-structures,tree,binary-tree,binary-search-tree
Rather than jumping right into an algorithm that works here, I'd like to give a series of observations that ultimately leads up to a really nice algorithm for this problem. First, suppose that, for each node in the tree, you knew the value of the largest and smallest values in...
cut the tree by removing edges
java,data-structures,graph,tree,edge
You need to add a method for disconnecting a child from a parent node. That would look something like this: private void disconnectChild(Node child) { children.remove(child); } You would then call this method from your disconnect() method like so: private void disconnect() { if (parent != null) { parent.disconnectChild(this); parent...
RedBlack Tree Implementation
c++,algorithm,data-structures,tree
There is nothing wrong with this code. According to wikipedia: 'These constraints enforce a critical property of red–black trees: that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that...
How do I keep load factor small in my hash table?
data-structures,hashtable,quadratic-probing
The implication is that at some point (when you would exceed a load factor of 0.5 in this case), you'll have to allocate a new table (which is bigger by some factor, maybe 1.5 or 2, and then rounded up to the nearest prime number) and copy all the elements...
Trie Data Structure in Finding an Optimal Solution
java,algorithm,data-structures,tree,trie
One reason this program get TLE (keep in mind that time constraint is 1 sec): Each time you create a Batman object, it will create an array with length [26], and it is equivalence to adding a loop with n = 26. So, you time complexity is 26*5000*5000 = 650000000...
Doubly Linked List, MergeSort, getting undefined and unreliable results
c,algorithm,data-structures,mergesort,doubly-linked-list
A bottom up merge sort is more appropriate for sorting a linked list. An efficient method for doing this is to use an array of pointers to the first nodes of lists, where the number of nodes pointed to by array[i] is 2^i (2 to the power i), or array[i]...
Visualization of TreeMap and LinkedHashMap in Java
java,data-structures,treemap,linkedhashmap
The source code for the normal implementations is in the src.zip file that comes with the Oracle JDK installs. TreeMap: As indicated in its documentation, it is a Red-Black tree. The critical code for simple forwards iteration over the keys is the method static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t). It recursively...