Tag Info

Hot answers tagged

6

A topological sort algorithm can sort a collection of data according to some set of rules as you have specified, where not all pairs have a pre-defined ordering. Typically the rules only define a partial ordering, so there are multiple possible orderings and topological sorting chooses an arbitrary one. If there's a contradiction in the rules you have ...


5

The concept you are looking for is known as "Hysteresis" (Wikipedia). But don't waste too much time reading the article, as your situation is rather simple. You have a number of inputs, which have states, and you also have a "logical state" (person in or out of home) which you need to compute out of them. The "logical state" cannot simply be a direct ...


4

You can use a variable with 3 possible states: someone at home nobody at home indeterminate These states are mutually exclusive, so it will make sense to use them for modeling. Whenever the door gets opened, set the state to "indeterminate". Whenever the door gets closed, start a timer, and when the timer ends, you change the state to "someone at home" ...


4

The input array that you have is: 0, 3, 3, 7, 5, 3, 11, 1 Imagine that the array instead would be this: 0, 1, 3, 3, 3, 5, 7, 11 If the array were organized like that, then you could loop through the array and more easily count pairs. 0 --> 1 1 --> 3, 3, 3 3 --> 3, 3, 5 3 --> 3, 5 3 --> 5 5 --> 7 7 --> 11 That's 1 + 3 + 3 + 2 + 1 ...


4

Addition of many elements to the end is O(m + logn), where m is the number of elements to be added. These operations would be O(n + m), and if m = n then they are almost as fast as addition to the end. In practice, they would be many orders of magnitude faster than if the user implemented them naively. However, for small numbers of elements, they would ...


3

Premature optimization is the root of all evil. -- Donald Knuth Any decent operating system is going to solve the jumping-around problem for you, using memory caches of disk blocks. Solving that problem by accumulating an unnecessary list of filenames creates a new problem of memory consumption - how well will the first version work with 50,000,000 files? ...


3

Your question is a little unclear as the title asks for an algorithm, but you also ask for a data structure. I will describe what I did with a similar issue, dealing with music. The way I approached it was with a series of string transformations that produced a string with as much ambiguity removed as possible. A few of the rules: Remove all whitespace ...


2

In this answer I will focus on the thinking part and less on the coding part. In other words, if the thinking is not correct, the code will probably not give the result you expected, even if the code implements your thinking faithfully. I will just point out the flaw in the code part, without going into detail: listOfPossibleTeams contained all possible ...


2

1) Let's assume that t.count() is a linear-time operation with respect to the size of the bitset (it probably isn't on real hardware, but ignore that). Then it would be correct to say that the algorithm is O(M*N^2), for the obvious reason that you have an M-iteration-loop (t.count()) inside an N-iteration-loop inside an N-iteration-loop. That might be ...


2

I would begin by sanitizing the input data much like @Steven Burnap and then calculate the Levenshtein distance between the input and all known movie titles. Return the top couple results. Since there's likely to be a high degree of variation between your users' input and your list of known movie titles, an exact string search algorithm isn't a good fit. ...


2

Possible? Yes. You should be able to download a word list (example) and compare each word's first five letters with your string, however it isn't going to be very efficient. IMHO. If you need to check more than a few words, then it may be useful to look into optimizations. For example, you could precompute a giant HashMap which contains all valid 5 letter ...


2

I would think of it as a graph: Creating a topological sorting would give you a valid order to process the nodes in. Note there can be multiple topological sorts. Whether you need to worry about that depends on if you need one solution or all the solutions. In this case, there is only one topological sort: c, b, a. You start with c, add it to the ...


2

This is not an answer, but a long comment. I voted for closing as "too broad". This comment explains my rationale. At the end of this comment I have some suggestion, but it is out-of-topic. Unfortunately the question is too broad to be answered here. There are decades of research on algorithm human facial expression recognition. The "public ...


1

The core concern here should probably not be disk costs, but correctness and intent. If you intend to do more than just insertion of the files in the list, you may want to prefer the accumulate-then-insert solution, as that gives you a consistent list of files to do further work with. It also lets you use bulk insertion functionality to your database ...


1

In other words, the whole database would have to undergo some major reindexing (recalculating all the matches) every time a new person is added. The strategy in such cases is to maintain a smaller, cached dataset ("delta"), in this case containing new people added throughout the day, which gets merged into the database on a daily basis - could be at night, ...


1

State diagram with timing is great way to model your situation. This is both understandable and easy to implement. The "movement detected" could be understood as transition from movement being detected to no movement being detected. You could make it better if you had "movement started", "movement ended" and "movement continues" transitions.


1

If you're talking about a user training an AI to learn what's important and what isn't based off of their calendar and some sort of feedback, then it's going to be a lot less work for them to just mark the appointment as important/not important with a flag or something when they're making it. If you're talking about an AI trying to learn what is and isn't ...


1

Let me graphically represent this problem. We have 4 integers A, B, C, D (for simplicity, I assume that those 4 integers are ordered). A-------------B-------------C-------------D We are looking for a way to get from each integer to each other so that each integer is only visited once and there is no other way for wich the "distance" is higher. For ...


1

I know what you are thinking. You are thinking that if you could somehow enumerate the digits after the decimal point, you could count them. But whether you use a string or any other mechanism, there is a fundamental problem: how do you know when to stop counting? Converting the number to a string might sound like an easy solution, but that's only ...


1

I don't really think any existing algorithm is going to work in your case. In your case, you are not looking for similarity between strings, but if strings contain similar values. Levenstein distance is about similarity of strings, not if strings contain similar values. In your case, the simplest algorithm would be (pseudocode). Get name of each file ...


1

Yes, your analysis and algorithms are correct. But it can be made better by trading off memory for performance IF the amount of possible characters in string is limited (eg. it is not full Unicode). Basically, you can use hash-map to keep count of every character in O(n)*O(1) and then go through the list in O(1) (because the count of all possible characters ...


1

Your problem addresses the pidgeonhole principle (http://en.wikipedia.org/wiki/Pigeonhole_principle). It simply sais that if you got N items and you want to put them into M containers, where N is greater than M, then at least one container has to hold at least ceil(N/M) (Where ceil(x) is the smallest integer greater than or equal to x) items. You can solve ...


1

I would check out http://www.fusu.us/2013/07/printing-binary-tree-boundary.html. It uses additional data structures but is but runs in linear time with a single traversal. The stacks used in the linked solution would not be necessary if you were not worried about the order in which the boundary is printed. In this case you could do your favorite linear tree ...


1

I've never applied it to rigorously prove the cost of some algorithm or data structure but I believe what you're looking for is the Idealized-cache model. The idea is to do Big O analysis where the cost is the number of cache block transfers instead of atomic machine instructions. E.g. Traversing an array under that model is O(n/B) where n is the number of ...


1

You have large graph and you made it even larger. Martinc C. Martin advised using lathes only when needed, so i will not go into this. One of things that could help you, is tranform your graph into smaller graphs. First simplification that helped me a lot (I worked with road networks of europian states) was "removing" nodes with digree 1 and 2 recursively. ...



Only top voted, non community-wiki answers of a minimum length are eligible