Distributed algorithm to compute the balance of the parentheses

Question

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 parentheses.

How would you make it distributed ?

Answer 1

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.