Wie bekomme ich die größte Anzahl aufeinanderfolgender Ganzzahlen in einem sehr großen Array (verteilt über mehrere Maschinen)

Question

Ich wurde diese Frage in einem Interview gestellt. Der erste Teil war ziemlich einfach, in dem ich einen Code schreiben musste, um die maximale Anzahl aufeinanderfolgender Ganzzahlen in einem Array zu erhalten. Im Folgenden ist der Code, den ich schrieb:

int count = 0, max = 0; 
for(int i = 1; i < array.length; i++) { 
    if((array[i - 1] + 1) == array[i])) //curr is consecutive to prev 
      count++; 
    else 
      count = 0; //reset the counter as sequence is broken 

    //Keep track of maximum 
    if(count > max) 
     max = count; 
} 

System.out.println(max); //print the length of largest consecutive integers 

Der zweite Teil war Follow-up Frage darauf:

Wie würden Sie diese Logik modifizieren, um Arrays zu arbeiten, die in mehreren Rechnern gespeichert sind?

Answer 1

Sie können es die Reduce Parallel Pattern

Beispiel in Python (für schlechte namings sorry) mit implementieren:

def longest_seq(seq): 

    Result = namedtuple("Result", ["left", "left_n", "max_n", "right", "right_n", "is_const"]) 

    def _longest_seq(seq): 
     if 1 == len(seq): 
      x = seq[0] 
      return Result(left=x, left_n=1, max_n=1, is_const=True, right=x, right_n=1) 

     l_res = _longest_seq(seq[0: int(len(seq)/2)]) 
     r_res = _longest_seq(seq[int(len(seq)/2): len(seq)]) 

     left_n = l_res.left_n + r_res.left_n if l_res.is_const and l_res.right == r_res.left else l_res.left_n 
     right_n = r_res.right_n + l_res.right_n if r_res.is_const and r_res.left == l_res.right else r_res.right_n 
     max_n = max(l_res.max_n, r_res.max_n, l_res.right_n + r_res.left_n if l_res.right == r_res.left else 0) 
     is_const = l_res.is_const and r_res.is_const and l_res.right == r_res.left 

     return Result(left=l_res.left, 
         left_n=left_n, 
         max_n=max_n, 
         right=r_res.right, 
         right_n=right_n, 
         is_const=is_const) 

    return _longest_seq(seq).max_n 

Answer 2

Angenommen, wir die ganze Reihe von links nach rechts auf jeder Maschine sequentiell verteilen. Zum Beispiel werden wir für nur zwei Maschinen (machine1 und machine2) das Array 0.... i an machine1 und i + 1....n an machine2 verteilen. Von jeder Maschine können wir mehrere zusätzliche Informationen zusammen mit dem lokalen Maximum zurückgeben.

class result { 
    public int machineId; 
    public int maxSoFar; // the max value as your code 
    public int leftElement; // the leftmost element 
    public int leftLength; // number of times the leftElement appears consecutively in left 
    public int rightElement; // the rightmost element 
    public int rightLength; // number of times the rightElement appears consecutively in right 
}; 

Während zwei Maschinenergebnis Zusammenführen für jede Maschine, deren zwei machineId aufeinander folgend sind (z. 3 und 4), können wir wie folgt maximieren -

return Math.max(((machine1.rightElement == machine2.leftElement) ? machine1.rightLength + machine2.leftLength : 0), 
        Math.max(machine1.maxSoFar, machine2.maxSoFar));