RSS

Most votes on algorithm questions 10

Most votes on algorithm questions 10. #91 Is log(n!) = Θ(n·log(n))? #92 What's the best way to model recurring events in a calendar application? #93 How do I calculate a point on a circle’s circumference? #94 Find running median from a stream of integers #95 What are good examples of genetic algorithms/genetic programming solutions? #96 Skip List vs. Binary Search Tree #97 Understanding recursion #98 Given a number, find the next higher number which has the exact same set of digits as the original number #99 How to find the kth largest element in an unsorted array of length n in O(n)?

Read all the top votes questions and answers in a single page.

#91: Is log(n!) = Θ(n·log(n))? (Score: 235)

Created: 2010-01-19 Last updated: 2018-03-04

Tags: algorithm, math, recursion, complexity-theory, big-o

I am to show that log(n!) = Θ(n·log(n)).

A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nn to n·log(n) (i.e. log both sides of an equation), but that’s kind of working backwards.

What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn’t seem like a likely approach..

#91 Best answer 1 of Is log(n!) = Θ(n·log(n))? (Score: 328)

Created: 2010-01-19 Last updated: 2018-03-04

Remember that

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

You can get the upper bound by

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2) 

#91 Best answer 2 of Is log(n!) = Θ(n·log(n))?(Score: 43)

Created: 2011-11-03

I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.

It is a pretty simple argument:

n! (= 123*…*n) is a product of n numbers each less than or equal to n. Therefore it is less than the product of n numbers all equal to n; i.e., n^n.

Half of the numbers – i.e. n/2 of them – in the n! product are greater than or equal to n/2. Therefore their product is greater than the product of n/2 numbers all equal to n/2; i.e. (n/2)^(n/2).

Take logs throughout to establish the result.

See also original question in stackoverflow

#92: What's the best way to model recurring events in a calendar application? (Score: 233)

Created: 2008-09-17 Last updated: 2008-09-23

Tags: ruby, algorithm, calendar, data-modeling, recurrence

I’m building a group calendar application that needs to support recurring events, but all the solutions I’ve come up with to handle these events seem like a hack. I can limit how far ahead one can look, and then generate all the events at once. Or I can store the events as repeating and dynamically display them when one looks ahead on the calendar, but I’ll have to convert them to a normal event if someone wants to change the details on a particular instance of the event.

I’m sure there’s a better way to do this, but I haven’t found it yet. What’s the best way to model recurring events, where you can change details of or delete particular event instances?

(I’m using Ruby, but please don’t let that constrain your answer. If there’s a Ruby-specific library or something, though, that’s good to know.)

#92 Best answer 1 of What's the best way to model recurring events in a calendar application? (Score: 102)

Created: 2008-09-17

I would use a ‘link’ concept for all future recurring events. They are dynamically displayed in the calendar and link back to a single reference object. When events have taken place the link is broken and the event becomes a standalone instance. If you attempt to edit a recurring event then prompt to change all future items (i.e. change single linked reference) or change just that instance (in which case convert this to a standalone instance and then make change). The latter cased is slightly problematic as you need to keep track in your recurring list of all future events that were converted to single instance. But, this is entirely do-able.

So, in essence, have 2 classes of events - single instances and recurring events.

#92 Best answer 2 of What's the best way to model recurring events in a calendar application?(Score: 63)

Created: 2010-12-05 Last updated: 2013-09-02

Martin Fowler - Recurring Events for Calendars contains some interesting insights and patterns.

Runt gem implements this pattern.

See also original question in stackoverflow

#93: How do I calculate a point on a circle’s circumference? (Score: 230)

Created: 2009-05-08 Last updated: 2019-04-14

Tags: algorithm, math, trigonometry

How can the following function be implemented in various languages?

Calculate the (x,y) point on the circumference of a circle, given input values of:

  • Radius
  • Angle
  • Origin (optional parameter, if supported by the language)

#93 Best answer 1 of How do I calculate a point on a circle’s circumference? (Score: 612)

Created: 2009-05-08 Last updated: 2018-08-22

The parametric equation for a circle is

x = cx + r * cos(a)
y = cy + r * sin(a)

Where r is the radius, cx,cy the origin, and a the angle.

That’s pretty easy to adapt into any language with basic trig functions. Note that most languages will use radians for the angle in trig functions, so rather than cycling through 0..360 degrees, you’re cycling through 0..2PI radians.

#93 Best answer 2 of How do I calculate a point on a circle’s circumference?(Score: 51)

Created: 2009-05-08

Here is my implementation in C#:

    public static PointF PointOnCircle(float radius, float angleInDegrees, PointF origin)
    {
        // Convert from degrees to radians via multiplication by PI/180        
        float x = (float)(radius * Math.Cos(angleInDegrees * Math.PI / 180F)) + origin.X;
        float y = (float)(radius * Math.Sin(angleInDegrees * Math.PI / 180F)) + origin.Y;

        return new PointF(x, y);
    }

See also original question in stackoverflow

#94: Find running median from a stream of integers (Score: 230)

Created: 2012-05-18 Last updated: 2017-05-23

Tags: algorithm, heap, median

Possible Duplicate:
Rolling median algorithm in C

Given that integers are read from a data stream. Find median of elements read so far in efficient way.

Solution I have read: We can use a max heap on left side to represent elements that are less than the effective median, and a min heap on right side to represent elements that are greater than the effective median.

After processing an incoming element, the number of elements in heaps differ at most by 1 element. When both heaps contain the same number of elements, we find the average of heap’s root data as effective median. When the heaps are not balanced, we select the effective median from the root of heap containing more elements.

But how would we construct a max heap and min heap i.e. how would we know the effective median here? I think that we would insert 1 element in max-heap and then the next 1 element in min-heap, and so on for all the elements. Correct me If I am wrong here.

#94 Best answer 1 of Find running median from a stream of integers (Score: 393)

Created: 2012-05-18 Last updated: 2017-01-28

There are a number of different solutions for finding running median from streamed data, I will briefly talk about them at the very end of the answer.

The question is about the details of the a specific solution (max heap/min heap solution), and how heap based solution works is explained below:

For the first two elements add smaller one to the maxHeap on the left, and bigger one to the minHeap on the right. Then process stream data one by one,

Step 1: Add next item to one of the heaps

   if next item is smaller than maxHeap root add it to maxHeap,
   else add it to minHeap

Step 2: Balance the heaps (after this step heaps will be either balanced or
   one of them will contain 1 more item)

   if number of elements in one of the heaps is greater than the other by
   more than 1, remove the root element from the one containing more elements and
   add to the other one

Then at any given time you can calculate median like this:

   If the heaps contain equal amount of elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with more elements

Now I will talk about the problem in general as promised in the beginning of the answer. Finding running median from a stream of data is a tough problem, and finding an exact solution with memory constraints efficiently is probably impossible for the general case. On the other hand, if the data has some characteristics we can exploit, we can develop efficient specialized solutions. For example, if we know that the data is an integral type, then we can use counting sort, which can give you a constant memory constant time algorithm. Heap based solution is a more general solution because it can be used for other data types (doubles) as well. And finally, if the exact median is not required and an approximation is enough, you can just try to estimate a probability density function for the data and estimate median using that.

#94 Best answer 2 of Find running median from a stream of integers(Score: 58)

Created: 2012-05-21 Last updated: 2020-05-25

If the variance of the input is statistically distributed (e.g. normal, log-normal, etc.) then reservoir sampling is a reasonable way of estimating percentiles/medians from an arbitrarily long stream of numbers.

int n = 0;  // Running count of elements observed so far  
#define SIZE 10000
int reservoir[SIZE];  

while(streamHasData())
{
  int x = readNumberFromStream();

  if (n < SIZE)
  {
       reservoir[n++] = x;
  }         
  else 
  {
      int p = random(++n); // Choose a random number 0 >= p < n
      if (p < SIZE)
      {
           reservoir[p] = x;
      }
  }
}

“reservoir” is then a running, uniform (fair), sample of all input - regardless of size. Finding the median (or any percentile) is then a straight-forward matter of sorting the reservoir and polling the interesting point.

Since the reservoir is fixed size, the sort can be considered to be effectively O(1) - and this method runs with both constant time and memory consumption.

See also original question in stackoverflow

#95: What are good examples of genetic algorithms/genetic programming solutions? (Score: 230)

Created: 2009-10-08 Last updated: 2013-03-19

Tags: algorithm, artificial-intelligence, genetic-algorithm, evolutionary-algorithm

Genetic algorithms (GA) and genetic programming (GP) are interesting areas of research.

I’d like to know about specific problems you have solved using GA/GP and what libraries/frameworks you used if you didn’t roll your own.

Questions:

  • What problems have you used GA/GP to solve?
  • What libraries/frameworks did you use?

I’m looking for first-hand experiences, so please do not answer unless you have that.

#95 Best answer 1 of What are good examples of genetic algorithms/genetic programming solutions? (Score: 150)

Created: 2009-10-08

Not homework.

My first job as a professional programmer (1995) was writing a genetic-algorithm based automated trading system for S&P500 futures. The application was written in Visual Basic 3 [!] and I have no idea how I did anything back then, since VB3 didn’t even have classes.

The application started with a population of randomly-generated fixed-length strings (the “gene” part), each of which corresponded to a specific shape in the minute-by-minute price data of the S&P500 futures, as well as a specific order (buy or sell) and stop-loss and stop-profit amounts. Each string (or “gene”) had its profit performance evaluated by a run through 3 years of historical data; whenever the specified “shape” matched the historical data, I assumed the corresponding buy or sell order and evaluated the trade’s result. I added the caveat that each gene started with a fixed amount of money and could thus potentially go broke and be removed from the gene pool entirely.

After each evaluation of a population, the survivors were cross-bred randomly (by just mixing bits from two parents), with the likelihood of a gene being selected as a parent being proportional to the profit it produced. I also added the possibility of point mutations to spice things up a bit. After a few hundred generations of this, I ended up with a population of genes that could turn $5000 into an average of about $10000 with no chance of death/brokeness (on the historical data, of course).

Unfortunately, I never got the chance to use this system live, since my boss lost close to $100,000 in less than 3 months trading the traditional way, and he lost his willingness to continue with the project. In retrospect, I think the system would have made huge profits - not because I was necessarily doing anything right, but because the population of genes that I produced happened to be biased towards buy orders (as opposed to sell orders) by about a 5:1 ratio. And as we know with our 20/20 hindsight, the market went up a bit after 1995.

#95 Best answer 2 of What are good examples of genetic algorithms/genetic programming solutions?(Score: 90)

Created: 2009-10-15 Last updated: 2014-07-30

I made a little critters that lived in this little world. They had a neural network brain which received some inputs from the world and the output was a vector for movement among other actions. Their brains were the “genes”.

The program started with a random population of critters with random brains. The inputs and output neurons were static but what was in between was not.

The environment contained food and dangers. Food increased energy and when you have enough energy, you can mate. The dangers would reduce energy and if energy was 0, they died.

Eventually the creatures evolved to move around the world and find food and avoid the dangers.

I then decided to do a little experiment. I gave the creature brains an output neuron called “mouth” and an input neuron called “ear”. Started over and was surprised to find that they evolved to maximize the space and each respective creature would stay in its respective part (food was placed randomly). They learned to cooperate with each other and not get in each others way. There were always the exceptions.

Then i tried something interesting. I dead creatures would become food. Try to guess what happened! Two types of creatures evolved, ones that attacked like in swarms, and ones that were high avoidance.

So what is the lesson here? Communication means cooperation. As soon as you introduce an element where hurting another means you gain something, then cooperation is destroyed.

I wonder how this reflects on the system of free markets and capitalism. I mean, if businesses can hurt their competition and get away with it, then its clear they will do everything in their power to hurt the competition.

Edit:

I wrote it in C++ using no frameworks. Wrote my own neural net and GA code. Eric, thank you for saying it is plausible. People usually don’t believe in the powers of GA (although the limitations are obvious) until they played with it. GA is simple but not simplistic.

For the doubters, neural nets have been proven to be able to simulate any function if they have more than one layer. GA is a pretty simple way to navigate a solution space finding local and potentially global minimum. Combine GA with neural nets and you have a pretty good way to find functions that find approximate solutions for generic problems. Because we are using neural nets, then we are optimizing the function for some inputs, not some inputs to a function as others are using GA

Here is the demo code for the survival example: http://www.mempko.com/darcs/neural/demos/eaters/ Build instructions:

  • Install darcs, libboost, liballegro, gcc, cmake, make
  • darcs clone --lazy http://www.mempko.com/darcs/neural/
  • cd neural
  • cmake .
  • make
  • cd demos/eaters
  • ./eaters

Eaters Screenshot

See also original question in stackoverflow

#96: Skip List vs. Binary Search Tree (Score: 230)

Created: 2008-11-02 Last updated: 2018-03-12

Tags: algorithm, language-agnostic, data-structures, binary-tree, skip-lists

I recently came across the data structure known as a skip list. It seems to have very similar behavior to a binary search tree.

Why would you ever want to use a skip list over a binary search tree?

#96 Best answer 1 of Skip List vs. Binary Search Tree (Score: 266)

Created: 2008-11-03 Last updated: 2021-02-03

Skip lists are more amenable to concurrent access/modification. Herb Sutter wrote an article about data structure in concurrent environments. It has more indepth information.

The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.

Update from Jon Harrops comments

I read Fraser and Harris’s latest paper Concurrent programming without locks. Really good stuff if you’re interested in lock-free data structures. The paper focuses on Transactional Memory and a theoretical operation multiword-compare-and-swap MCAS. Both of these are simulated in software as no hardware supports them yet. I’m fairly impressed that they were able to build MCAS in software at all.

I didn’t find the transactional memory stuff particularly compelling as it requires a garbage collector. Also software transactional memory is plagued with performance issues. However, I’d be very excited if hardware transactional memory ever becomes common. In the end it’s still research and won’t be of use for production code for another decade or so.

In section 8.2 they compare the performance of several concurrent tree implementations. I’ll summarize their findings. It’s worth it to download the pdf as it has some very informative graphs on pages 50, 53, and 54.

  • Locking skip lists is insanely fast. They scale incredibly well with the number of concurrent accesses. This is what makes skip lists special, other lock based data structures tend to croak under pressure.
  • Lock-free skip lists are consistently faster than locking skip lists but only barely.
  • transactional skip lists are consistently 2-3 times slower than the locking and non-locking versions.
  • locking red-black trees croak under concurrent access. Their performance degrades linearly with each new concurrent user. Of the two known locking red-black tree implementations, one essentially has a global lock during tree rebalancing. The other uses fancy (and complicated) lock escalation but still doesn’t significantly outperform the global lock version.
  • lock-free red-black trees don’t exist (no longer true, see Update).
  • transactional red-black trees are comparable with transactional skip-lists. That was very surprising and very promising. Transactional memory, though slower if far easier to write. It can be as easy as quick search and replace on the non-concurrent version.

Update
Here is paper about lock-free trees: Lock-Free Red-Black Trees Using CAS.
I haven’t looked into it deeply, but on the surface it seems solid.

#96 Best answer 2 of Skip List vs. Binary Search Tree(Score: 86)

Created: 2015-02-02 Last updated: 2015-02-02

First, you cannot fairly compare a randomized data structure with one that gives you worst-case guarantees.

A skip list is equivalent to a randomly balanced binary search tree (RBST) in the way that is explained in more detail in Dean and Jones' “Exploring the Duality Between Skip Lists and Binary Search Trees”.

The other way around, you can also have deterministic skip lists which guarantee worst case performance, cf. Munro et al.

Contra to what some claim above, you can have implementations of binary search trees (BST) that work well in concurrent programming. A potential problem with the concurrency-focused BSTs is that you can’t easily get the same had guarantees about balancing as you would from a red-black (RB) tree. (But “standard”, i.e. randomzided, skip lists don’t give you these guarantees either.) There’s a trade-off between maintaining balancing at all times and good (and easy to program) concurrent access, so relaxed RB trees are usually used when good concurrency is desired. The relaxation consists in not re-balancing the tree right away. For a somewhat dated (1998) survey see Hanke’s ‘‘The Performance of Concurrent Red-Black Tree Algorithms’’ [ps.gz].

One of the more recent improvements on these is the so-called chromatic tree (basically you have some weight such that black would be 1 and red would be zero, but you also allow values in between). And how does a chromatic tree fare against skip list? Let’s see what Brown et al. “A General Technique for Non-blocking Trees” (2014) have to say:

with 128 threads, our algorithm outperforms Java’s non-blocking skiplist by 13% to 156%, the lock-based AVL tree of Bronson et al. by 63% to 224%, and a RBT that uses software transactional memory (STM) by 13 to 134 times

EDIT to add: Pugh’s lock-based skip list, which was benchmarked in Fraser and Harris (2007) “Concurrent Programming Without Lock” as coming close to their own lock-free version (a point amply insisted upon in the top answer here), is also tweaked for good concurrent operation, cf. Pugh’s “Concurrent Maintenance of Skip Lists”, although in a rather mild way. Nevertheless one newer/2009 paper “A Simple Optimistic skip-list Algorithm” by Herlihy et al., which proposes a supposedly simpler (than Pugh’s) lock-based implementation of concurrent skip lists, criticized Pugh for not providing a proof of correctness convincing enough for them. Leaving aside this (maybe too pedantic) qualm, Herlihy et al. show that their simpler lock-based implementation of a skip list actually fails to scale as well as the JDK’s lock-free implementation thereof, but only for high contention (50% inserts, 50% deletes and 0% lookups)… which Fraser and Harris didn’t test at all; Fraser and Harris only tested 75% lookups, 12.5% inserts and 12.5% deletes (on skip list with ~500K elements). The simpler implementation of Herlihy et al. also comes close to the lock-free solution from the JDK in the case of low contention that they tested (70% lookups, 20% inserts, 10% deletes); they actually beat the lock-free solution for this scenario when they made their skip list big enough, i.e. going from 200K to 2M elements, so that the probability of contention on any lock became negligible. It would have been nice if Herlihy et al. had gotten over their hangup over Pugh’s proof and tested his implementation too, but alas they didn’t do that.

EDIT2: I found a (2015 published) motherlode of all benchmarks: Gramoli’s “More Than You Ever Wanted to Know about Synchronization. Synchrobench, Measuring the Impact of the Synchronization on Concurrent Algorithms”: Here’s a an excerpted image relevant to this question.

enter image description here

“Algo.4” is a precursor (older, 2011 version) of Brown et al.’s mentioned above. (I don’t know how much better or worse the 2014 version is). “Algo.26” is Herlihy’s mentioned above; as you can see it gets trashed on updates, and much worse on the Intel CPUs used here than on the Sun CPUs from the original paper. “Algo.28” is ConcurrentSkipListMap from the JDK; it doesn’t do as well as one might have hoped compared to other CAS-based skip list implementations. The winners under high-contention are “Algo.2” a lock-based algorithm (!!) described by Crain et al. in “A Contention-Friendly Binary Search Tree” and “Algo.30” is the “rotating skiplist” from “Logarithmic data structures for multicores”. “Algo.29” is the “No hot spot non-blocking skip list”. Be advised that Gramoli is a co-author to all three of these winner-algorithm papers. “Algo.27” is the C++ implementation of Fraser’s skip list.

Gramoli’s conclusion is that’s much easier to screw-up a CAS-based concurrent tree implementation than it is to screw up a similar skip list. And based on the figures, it’s hard to disagree. His explanation for this fact is:

The difficulty in designing a tree that is lock-free stems from the difficulty of modifying multiple references atomically. Skip lists consist of towers linked to each other through successor pointers and in which each node points to the node immediately below it. They are often considered similar to trees because each node has a successor in the successor tower and below it, however, a major distinction is that the downward pointer is generally immutable hence simplifying the atomic modification of a node. This distinction is probably the reason why skip lists outperform trees under heavy contention as observed in Figure [above].

Overriding this difficulty was a key concern in Brown et al.’s recent work. They have a whole separate (2013) paper “Pragmatic Primitives for Non-blocking Data Structures” on building multi-record LL/SC compound “primitives”, which they call LLX/SCX, themselves implemented using (machine-level) CAS. Brown et al. used this LLX/SCX building block in their 2014 (but not in their 2011) concurrent tree implementation.

I think it’s perhaps also worth summarizing here the fundamental ideas of the “no hot spot”/contention-friendly (CF) skip list. It addapts an essential idea from the relaxed RB trees (and similar concrrency friedly data structures): the towers are no longer built up immediately upon insertion, but delayed until there’s less contention. Conversely, the deletion of a tall tower can create many contentions; this was observed as far back as Pugh’s 1990 concurrent skip-list paper, which is why Pugh introduced pointer reversal on deletion (a tidbit that Wikipedia’s page on skip lists still doesn’t mention to this day, alas). The CF skip list takes this a step further and delays deleting the upper levels of a tall tower. Both kinds of delayed operations in CF skip lists are carried out by a (CAS based) separate garbage-collector-like thread, which its authors call the “adapting thread”.

The Synchrobench code (including all algorithms tested) is available at: https://github.com/gramoli/synchrobench. The latest Brown et al. implementation (not included in the above) is available at http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Does anyone have a 32+ core machine available? J/K My point is that you can run these yourselves.

See also original question in stackoverflow

#97: Understanding recursion (Score: 229)

Created: 2009-04-04 Last updated: 2015-03-25

Tags: algorithm, recursion, tail-recursion

I’m having major trouble understanding recursion at school. Whenever the professor is talking about it, I seem to get it but as soon as I try it on my own it completely blows my brains.

I was trying to solve Towers of Hanoi all night and completely blew my mind. My textbook has only about 30 pages in recursion so it is not too useful. Does anyone know of books or resources that can help clarify this topic?

#97 Best answer 1 of Understanding recursion (Score: 619)

Created: 2009-04-04 Last updated: 2019-08-20

How do you empty a vase containing five flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing four flowers.

How do you empty a vase containing four flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing three flowers.

How do you empty a vase containing three flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing two flowers.

How do you empty a vase containing two flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing one flower.

How do you empty a vase containing one flower?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing no flowers.

How do you empty a vase containing no flowers?

Answer: if the vase is not empty, you take out one flower but the vase is empty so you’re done.

That’s repetitive. Let’s generalize it:

How do you empty a vase containing N flowers?

Answer: if the vase is not empty, you take out one flower and then you empty a vase containing N-1 flowers.

Hmm, can we see that in code?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, couldn’t we have just done that in a for loop?

Why, yes, recursion can be replaced with iteration, but often recursion is more elegant.

Let’s talk about trees. In computer science, a tree is a structure made up of nodes, where each node has some number of children that are also nodes, or null. A binary tree is a tree made of nodes that have exactly two children, typically called “left” and “right”; again the children can be nodes, or null. A root is a node that is not the child of any other node.

Imagine that a node, in addition to its children, has a value, a number, and imagine that we wish to sum all the values in some tree.

To sum value in any one node, we would add the value of node itself to the value of its left child, if any, and the value of its right child, if any. Now recall that the children, if they’re not null, are also nodes.

So to sum the left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.

So to sum the value of the left child’s left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.

Perhaps you’ve anticipated where I’m going with this, and would like to see some code? OK:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Notice that instead of explicitly testing the children to see if they’re null or nodes, we just make the recursive function return zero for a null node.

So say we have a tree that looks like this (the numbers are values, the slashes point to children, and @ means the pointer points to null):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

If we call sumNode on the root (the node with value 5), we will return:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Let’s expand that in place. Everywhere we see sumNode, we’ll replace it with the expansion of the return statement:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Now see how we conquered a structure of arbitrary depth and “branchiness”, by considering it as the repeated application of a composite template? each time through our sumNode function, we dealt with only a single node, using a single if/then branch, and two simple return statements that almost wrote themsleves, directly from our specification?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

That’s the power of recursion.


The vase example above is an example of tail recursion. All that tail recursion means is that in the recursive function, if we recursed (that is, if we called the function again), that was the last thing we did.

The tree example was not tail recursive, because even though that last thing we did was to recurse the right child, before we did that we recursed the left child.

In fact, the order in which we called the children, and added the current node’s value didn’t matter at all, because addition is commutative.

Now let’s look at an operation where order does matter. We’ll use a binary tree of nodes, but this time the value held will be a character, not a number.

Our tree will have a special property, that for any node, its character comes after (in alphabetical order) the character held by its left child and before (in alphabetical order) the character held by its right child.

What we want to do is print the tree in alphabetical order. That’s easy to do, given the tree special property. We just print the left child, then the node’s character, then right child.

We don’t just want to print willy-nilly, so we’ll pass our function something to print on. This will be an object with a print( char ) function; we don’t need to worry about how it works, just that when print is called, it’ll print something, somewhere.

Let’s see that in code:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

In addition to the order of operations now mattering, this example illustrates that we can pass things into a recursive function. The only thing we have to do is make sure that on each recursive call, we continue to pass it along. We passed in a node pointer and a printer to the function, and on each recursive call, we passed them “down”.

Now if our tree looks like this:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ [email protected]
       /\
       @@

What will we print?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

So if we just look at the lines were we printed:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

We see we printed “ahijkn”, which is indeed in alphabetical order.

We manage to print an entire tree, in alphabetical order, just by knowing how to print a single node in alphabetical order. Which was just (because our tree had the special property of ordering values to the left of alphabetically later values) knowing to print the left child before printing the node’s value, and to print the right child after printing the node’s value.

And that’s the power of recursion: being able to do whole things by knowing only how to do a part of the whole (and knowing when to stop recursing).

Recalling that in most languages, operator || (“or”) short-circuits when its first operand is true, the general recursive function is:

void recurse() { doWeStop() || recurse(); } 

Luc M comments:

SO should create a badge for this kind of answer. Congratulations!

Thanks, Luc! But, actually, because I edited this answer more than four times (to add the last example, but mostly to correct typos and polish it – typing on a tiny netbook keyboard is hard), I can’t get any more points for it. Which somewhat discourages me from putting as much effort into future answers.

See my comment here on that: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

#97 Best answer 2 of Understanding recursion(Score: 36)

Created: 2009-04-04

Your brain blew up because it got into an infinite recursion. That’s a common beginner mistake.

Believe it or not, you already understand recursion, you’re just being dragged down by a common, but faulty metaphor for a function: a small box with stuff that comes in and out.

Think instead of a task or procedure, such as “find out more about recursion on the net”. That’s recursive and you have no problem with it. To complete this task you might:

a) Read a Google's result page for "recursion"
b) Once you've read it, follow the first link on it and...
a.1)Read that new page about recursion 
b.1)Once you've read it, follow the first link on it and...
a.2)Read that new page about recursion 
b.2)Once you've read it, follow the first link on it and...

As you can see, you’ve been doing recursive stuff for a long time without any problems.

For how long would you keep doing that task? Forever until your brain blows up? Of course not, you will stop at a given point, whenever you believe you have completed the task.

There’s no need to specify this when asking you to “find out more about recursion on the net”, because you are a human and you can infer that by yourself.

Computer’s can’t infer jack, so you must include an explicit ending: “find out more about recursion on the net, UNTIL you understand it or you have read a maximum of 10 pages”.

You also inferred that you should start at Google’s result page for “recursion”, and again that’s something a computer can’t do. The complete description of our recursive task must also include an explicit starting point:

“find out more about recursion on the net, UNTIL you understand it or you have read a maximum of 10 pages and starting at www.google.com/search?q=recursion

To grok the whole thing, I suggest you try any of these books:

  • Common Lisp: A Gentle Introduction to Symbolic Computation. This is the cutest non-mathematical explanation of recursion.
  • The little schemer.

See also original question in stackoverflow

#98: Given a number, find the next higher number which has the exact same set of digits as the original number (Score: 229)

Created: 2012-02-20 Last updated: 2012-02-24

Tags: algorithm

I just bombed an interview and made pretty much zero progress on my interview question. Can anyone let me know how to do this? I tried searching online but couldn’t find anything:

Given a number, find the next higher number which has the exact same set of digits as the original number. For example: given 38276 return 38627

I wanted to begin by finding the index of the first digit (from the right) that was less than the ones digit. Then I would rotate the last digits in the subset such that it was the next biggest number comprised of the same digits, but got stuck.

The interviewer also suggested trying to swap digits one at a time, but I couldn’t figure out the algorithm and just stared at a screen for like 20-30 minutes. Needless to say, I think I’m going to have to continue the job hunt.

edit: for what its worth, I was invited to the next round of interviews

#98 Best answer 1 of Given a number, find the next higher number which has the exact same set of digits as the original number (Score: 278)

Created: 2012-02-20 Last updated: 2016-09-02

You can do it in O(n) (where n is the number of digits) like this:

Starting from the right, you find the first pair-of-digits such that the left-digit is smaller than the right-digit. Let’s refer to the left-digit by “digit-x”. Find the smallest number larger than digit-x to the right of digit-x, and place it immediately left of digit-x. Finally, sort the remaining digits in ascending order - since they were already in descending order, all you need to do is reverse them (save for digit-x, which can be placed in the correct place in O(n)).

An example will make this more clear:

123456784987654321
start with a number

123456784 987654321
         ^the first place from the right where the left-digit is less than the right  
         Digit "x" is 4

123456784 987654321
              ^find the smallest digit larger than 4 to the right

123456785 4 98764321
        ^place it to the left of 4

123456785 4 12346789
123456785123446789
         ^sort the digits to the right of 5.  Since all of them except 
         the '4' were already in descending order, all we need to do is 
         reverse their order, and find the correct place for the '4'

Proof of correctness:

Let’s use capital letters to define digit-strings and lower-case for digits. The syntax AB means “the concatenation of strings A and B". < is lexicographical ordering, which is the same as integer ordering when the digit-strings are of equal length.

Our original number N is of the form AxB, where x is a single digit and B is sorted descending.
The number found by our algorithm is AyC, where y ∈ B is the smallest digit > x (it must exist due to the way x was chosen, see above), and C is sorted ascending.

Assume there is some number (using the same digits) N' such that AxB < N' < AyC. N' must begin with A or else it could not fall between them, so we can write it in the form AzD. Now our inequality is AxB < AzD < AyC, which is equivalent to xB < zD < yC where all three digit-strings contain the same digits.

In order for that to be true, we must have x <= z <= y. Since y is the smallest digit > x, z cannot be between them, so either z = x or z = y. Say z = x. Then our inequality is xB < xD < yC, which means B < D where both B and D have the same digits. However, B is sorted descending, so there is no string with those digits larger than it. Thus we cannot have B < D. Following the same steps, we see that if z = y, we cannot have D < C.

Therefore N' cannot exist, which means our algorithm correctly finds the next largest number.

#98 Best answer 2 of Given a number, find the next higher number which has the exact same set of digits as the original number(Score: 95)

Created: 2012-02-20 Last updated: 2015-04-30

An almost-identical problem appeared as a Code Jam problem and has a solution here:

http://code.google.com/codejam/contest/dashboard?c=186264#s=a&a=1

Here’s a summary of the method using an example:

34722641

A. Split the sequence of digits in two, so that the right part is as long as possible while remaining in decreasing order:

34722 641

(If the entire number is in decreasing order, there’s no bigger number to be made without adding digits.)

B.1. Select the last digit of the first sequence:

3472(2) 641

B.2. Find the smallest digit in the second sequence that is larger than it:

3472(2) 6(4)1

B.3. Swap them:

3472(2) 6(4)1
->
3472(4) 6(2)1
->
34724 621

C. Sort the second sequence into increasing order:

34724 126

D. Done!

34724126

See also original question in stackoverflow

#99: How to find the kth largest element in an unsorted array of length n in O(n)? (Score: 228)

Created: 2008-10-30 Last updated: 2012-09-15

Tags: performance, algorithm, big-o

I believe there’s a way to find the kth largest element in an unsorted array of length n in O(n). Or perhaps it’s “expected” O(n) or something. How can we do this?

#99 Best answer 1 of How to find the kth largest element in an unsorted array of length n in O(n)? (Score: 176)

Created: 2008-10-30 Last updated: 2017-10-21

This is called finding the k-th order statistic. There’s a very simple randomized algorithm (called quickselect) taking O(n) average time, O(n^2) worst case time, and a pretty complicated non-randomized algorithm (called introselect) taking O(n) worst case time. There’s some info on Wikipedia, but it’s not very good.

Everything you need is in these powerpoint slides. Just to extract the basic algorithm of the O(n) worst-case algorithm (introselect):

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.
    
    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)
    
    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

It’s also very nicely detailed in the Introduction to Algorithms book by Cormen et al.

#99 Best answer 2 of How to find the kth largest element in an unsorted array of length n in O(n)?(Score: 120)

Created: 2008-10-31 Last updated: 2015-09-01

If you want a true O(n) algorithm, as opposed to O(kn) or something like that, then you should use quickselect (it’s basically quicksort where you throw out the partition that you’re not interested in). My prof has a great writeup, with the runtime analysis: (reference)

The QuickSelect algorithm quickly finds the k-th smallest element of an unsorted array of n elements. It is a RandomizedAlgorithm, so we compute the worst-case expected running time.

Here is the algorithm.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

What is the running time of this algorithm? If the adversary flips coins for us, we may find that the pivot is always the largest element and k is always 1, giving a running time of

T(n) = Theta(n) + T(n-1) = Theta(n2)

But if the choices are indeed random, the expected running time is given by

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

where we are making the not entirely reasonable assumption that the recursion always lands in the larger of A1 or A2.

Let’s guess that T(n) <= an for some a. Then we get

T(n) 
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

and now somehow we have to get the horrendous sum on the right of the plus sign to absorb the cn on the left. If we just bound it as 2(1/n) ∑i=n/2 to n an, we get roughly 2(1/n)(n/2)an = an. But this is too big - there’s no room to squeeze in an extra cn. So let’s expand the sum using the arithmetic series formula:

i=floor(n/2) to n i  
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

where we take advantage of n being “sufficiently large” to replace the ugly floor(n/2) factors with the much cleaner (and smaller) n/4. Now we can continue with

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

provided a > 16c.

This gives T(n) = O(n). It’s clearly Omega(n), so we get T(n) = Theta(n).

See also original question in stackoverflow


Notes:
  1. This page use API to get the relevant data from stackoverflow community.
  2. Content license on this page is CC BY-SA 3.0.
  3. score = up votes - down votes.