Distributed algorithm to compute the balance of the parentheses

This is an interview question: "How to build a distributed algorithm to compute the balance of the parentheses ?"

Usually he balance algorithm scans a string form left to right and uses a stack to make sure that the number of open parentheses always >= the number of close parentheses and finally the number of open parentheses == the number of close parenthe开发者_如何学运维ses.

How would you make it distributed ?

You can break the string into chunks and process each separately, assuming you can read and send to the other machines in parallel. You need two numbers for each string.

1. The minimum nesting depth achieved relative to the start of the string.

2. The total gain or loss in nesting depth across the whole string.

With these values, you can compute the values for the concatenation of many chunks as follows:

minNest = 0
totGain = 0
for p in chunkResults
  minNest = min(minNest, totGain + p.minNest)
  totGain += p.totGain
return new ChunkResult(minNest, totGain)

The parentheses are matched if the final values of totGain and minNest are zero.

I would apply the map-reduce algorithm in which the map function would compute a part of the string return either an empty string if parentheses are balanced or a string with the last parenthesis remaining.

Then the reduce function would concatenate the result of two returned strings by map function and compute it again returning the same result than map. At the end of all computations, you'd either obtain an empty string or a string containing the un-balanced parenthesis.

I'll try to have a more detailed explain on @jonderry's answer. Code first, in Scala

def parBalance(chars: Array[Char], chunkSize: Int): Boolean = {
    require(chunkSize > 0, "chunkSize must be greater than 0")

    def traverse(from: Int, until: Int): (Int, Int) = {
      var count = 0
      var stack = 0
      var nest = 0
      for (n <- from until until) {
        val cur = chars(c)
        if (cur == '(') {
          count += 1
          stack += 1
        }
        else if (cur == ')') {
          count -= 1
          if (stack > 0) stack -= 1
          else nest -= 1
        }
      }
      (nest, count)
    }

    def reduce(from: Int, until: Int): (Int, Int) = {
      val m = (until + from) / 2
      if (until - from <= chunkSize) {
        traverse(from, until)
      } else {
        parallel(reduce(from, m), reduce(m, until)) match {
          case ((minNestL, totGainL), (minNestR, totGainR)) => {
            ((minNestL min (minNestR + totGainL)), (totGainL + totGainR))
          }
        }
      }
    }

    reduce(0, chars.length) == (0,0)
}

Given a string, if we remove balanced parentheses, what's left will be in a form )))(((, give n for number of ) and m for number of (, then m >= 0, n <= 0(for easier calculation). Here n is minNest and m+n is totGain. To make a true balanced string, we need m+n == 0 && n == 0.

In a parallel operation, how to we derive those for node from it's left and right? For totGain we just needs to add them up. When calculating n for node, it can just be n(left) if n(right) not contribute or n(right) + left.totGain whichever is smaller.