Tag Info

3

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem. We maintain a list of intervals $[a_1,b_1],[a_2,b_2],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a_i,b_i$ in a hash table. Given a new integer $c$, we ...

3

For any pair of adjacent strings, you can find a constraint of the form $\sigma < \tau$ on the order of the symbols which is necessary in order for this pair of strings to be lexicographically ordered. This doesn't require any fancy data structure. Putting all of these constraints together in a directed graph, you can determine whether such an order ...

2

In a BST, a lookup for an key that isn't present traces out a path through that tree that ends at either that key's successor or that key's predecessor. We'll use this property to get the desired $O(m + n)$ bound. To begin with, suppose that what you're searching for is smaller than all other keys in the tree or bigger than all the keys in the tree. In that ...

2

The accounting method relies on two arguments. The first is that in any sequence of $n$ operations, you never run out of coins. That is, however you choose to distribute the coins and pay for the operations, no sequence of operation will lead your scheme to a negative balance. The question remains of what this has to do with running time. Now the second ...

1

To make our life easier, we always assume that the convex hull of the triangulation consists of three points. If it is not, just add three points far away and triangulate. Then, the important thing is that those points that we remove are always internal points, never on this outerface that is a triangle. The reason why we want them to be independent, is ...

1

I think you are right in 1,2,5. I didnt really understand your proof for 5, since it should be different from 1. Also, the proof for 1 can be greatly simplified: $A[i]\le A[2i],A[2i+1]$ is the definition of the minimality property in the heap, and you can directly show that using the fact your list is ordered. About 3, try to create a big heap such that the ...

1

I think this is a reasonable approach. To make it more solid, I suggest replacing Murmur3 with a cryptographic hash, such as SHA256. Then we get a kind of guarantee: it is believed to be intractable to find a collision for the hash function. In other words, for all engineering purposes, we expect you will never in your lifetime encounter a pair of inputs ...

1

It doesn't significantly increase the speed, the increase will just be a constant at best. Essentially, you still search the same tree, just in a different ordering, and that means you will still do $O(\log(n))$ operations to search a number. It might be useful to think of this as just two separate BSTs, one for odd numbers and one for even numbers. So, this ...

1

You want Union-Find with deletions (Kaplan et al. 2002, and Alstrup et al. 2005). You can do deletion in constant time, but it's non-trivial.

1

As other people have already said in the comments, the best way to learn is through a university. This is not necessarily because a book does not cover the same material but becasue you need (1) structure and (2) someone to check that what your understanding is sufficient and your solutions to problems are correct. As a software engineer, you already know ...

1

Check out this and this. I prefer the former one cause the number of subjects is relatively small, and they are the core fundamentals.

1

Well, yea. But you need to define formally what a "type of tree" could be. General trees, are described by the mathematical notion of a tree graph. Given some ordering on the nodes of the tree, and some definition of which node is the root of the tree, you can perform the "pre-order" and "post-order" traversals. The algorithms ...

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