## Why DFS and not BFS for finding cycle in graphs

Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack. Also if your graph is directed then you have to not just remember if you have … Read more

## RGB value base color name

So if you want distance between 2 colors (r0,g0,b0) and (r1,g1,b1) to detect closest color regardless of its intensity (that is what base color means in this case) you should Normalize color vectors to common size Compute distance Scale the result back // variables int r0,g0,b0,c0; int r1,g1,b1,c1,d; // color sizes c0=sqrt(r0*r0+g0*g0+b0*b0); c1=sqrt(r1*r1+g1*g1+b1*b1); // distance … Read more

## Big O when adding together different routines

The sum is indeed the worst of the three for Big-O. The reason is that your function’s time complexity is (n) => 3n + nlogn + nlogn which is (n) => 3n + 2nlogn This function is bounded above by 3nlogn, so it is in O(n log n). You can choose any constant. I just … Read more

## Fast solution to Subset sum

I respect the alacrity with which you’re trying to solve this problem! Unfortunately, you’re trying to solve a problem that’s NP-complete, meaning that any further improvement that breaks the polynomial time barrier will prove that P = NP. The implementation you pulled from Hacker News appears to be consistent with the pseudo-polytime dynamic programming solution, … Read more

## Previous power of 2

From Hacker’s Delight, a nice branchless solution: uint32_t flp2 (uint32_t x) { x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); return x – (x >> 1); } This … Read more

## Why do we ignore co-efficients in Big O notation?

The purpose of the Big-O notation is to find what is the dominant factor in the asymptotic behavior of a function as the value tends towards the infinity. As we walk through the function domain, some factors become more important than others. Imagine f(n) = n^3+n^2. As n goes to infinity, n^2 becomes less and … Read more

## How to find distance from the latitude and longitude of two locations?

The Haversine formula assumes a spherical earth. However, the shape of the earh is more complex. An oblate spheroid model will give better results. If such accuracy is needed, you should better use Vincenty inverse formula. See http://en.wikipedia.org/wiki/Vincenty’s_formulae for details. Using it, you can get a 0.5mm accuracy for the spheroid model. There is no … Read more

## Find all pairs of integers within an array which sum to a specified value

I don’t see why the hash table approach is inefficient, at least in algorithm analysis terms – in memory locality terms admittedly, it can be quite bad. Anyway, scan the array twice… First scan – put all the array elements in the hash table – O(n) total. Individual inserts are only amortized O(1), but a … Read more

## Simplest way to get the top n elements of a Scala Iterable

My solution (bound to Int, but should be easily changed to Ordered (a few minutes please): def top (n: Int, li: List [Int]) : List[Int] = { def updateSofar (sofar: List [Int], el: Int) : List [Int] = { // println (el + ” – ” + sofar) if (el < sofar.head) (el :: sofar.tail).sortWith … Read more

## Best way of calculating n choose k?

Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k): function choose(n, k) if k == 0 return 1 return (n * choose(n – 1, k – 1)) / k I wrote it recursively because it’s so simple and pretty, but you … Read more