First, a definition, since it’s pretty important: A stable sort is one that’s guaranteed not to reorder elements with identical keys. Recommendations: Quick sort: When you don’t need a stable sort and average case performance matters more than worst case performance. A quick sort is O(N log N) on average, O(N^2) in the worst case. … Read more
I think of it as more a technique than an algorithm. It’s a technique that could be utilized in various algorithms. I think the technique is best understood with the following example. Imagine we have this array: [ 5, 7, 1, 4, 3, 6, 2, 9, 2 ] How would we find the largest sum … Read more
You will have to go to the formal definition of the big O (O) in order to answer this question. The definition is that f(x) belongs to O(g(x)) if and only if the limit limsupx → ∞ (f(x)/g(x)) exists i.e. is not infinity. In short this means that there exists a constant M, such that … Read more
Your sum v1 + (incident edges) + v2 + (incident edges) + …. + vn + (incident edges) can be rewritten as (v1 + v2 + … + vn) + [(incident_edges v1) + (incident_edges v2) + … + (incident_edges vn)] and the first group is O(N) while the other is O(E).
Recall that in Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) – the algorithm found the shortest path to it, and will never have to develop this node again – it assumes the path developed to this path is the shortest. But with negative weights – it might … Read more
Based on the highly scientific method of watching animated gifs I would say Insertion and Bubble sorts are good candidates.
Starting from root node and moving downwards if you find any node that has either p or q as its direct child then it is the LCA. (edit – this should be if p or q is the node’s value, return it. Otherwise it will fail when one of p or q is a direct … Read more
Initialize an array of 1001 integers with the values 0-1000 and set a variable, max, to the current max index of the array (starting with 1000). Pick a random number, r, between 0 and max, swap the number at the position r with the number at position max and return the number now at position … Read more
Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly. class MyObject { // The actual object public int ParentID { get; set; } public int ID { get; set; } } class … Read more
Here’s the best algorithm I know of (in Python) def prime_factors(n): “””Returns all the prime factors of a positive integer””” factors = [] d = 2 while n > 1: while n % d == 0: factors.append(d) n /= d d = d + 1 return factors pfs = prime_factors(1000) largest_prime_factor = max(pfs) # The … Read more