Retiring a Great Interview Problem

Post by eru » Wed, Aug 10, 2011, 8:30 PM UTC

eru wrote: post #112

NY_Entrepreneur wrote: post #102

Earlier quoted context omitted.

One famous application of dynamic programming is finding shortest paths in directed acyclic graphs. Maybe should credit E. Dijkstra. As I recall, that is not regarded as the most efficient such algorithm, but I haven't considered that problem for years.

As far as I know Dijkstra's algorithm is the fastest path finding algorithm in general directed graphs without cycles of negative length. But you have to employ fibonacci heaps (or so) to get the best run-time. If you have some heuristics to guide your path finding, e.g. if you are trying to find paths on a map, then you can do better than Dijkstra's algorithm. See A*.

P.S. There's also Bellman-Ford.

Post by kragen » Fri, Aug 12, 2011, 1:21 AM UTC

nyellin wrote: post #116

kragen wrote: post #82

Earlier quoted context omitted.

At first glance, your statement is incorrect: there is no Python code to create a list here, and no list comprehensions. On further examination, though, string_join in stringobject.c invokes PySequence_Fast to convert its iterable argument into a sequence --- a temporary list, in this case --- so your statement that this code generates a temporary list is correct, although I suspect that this is more by accident than…

Why doesn't StringIO count as a string buffer?

Sir or madam,

you may have an excellent point, there. But I haven't looked at how cStringIO is implemented: does it construct a list of strings and then join them when they are requested, thus keeping alive all the string objects passed to it? Or does it concatenate the bytes into a buffer?

I just realized that the Python 3 memoryview object also provides the wherewithal to construct a string buffer, even in pure Python.

Re: Retiring a Great Interview Problem

Re: Retiring a Great Interview Problem