Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Single iteration streaming java solution for http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/ This solution is ideal if myIntArray could be very large (i.e. > 1m ints) but with a limited range (i.e. 0-10) I would probably use a stack based solution if the range could be highly variable (0-10m) with the number of ints being relative…
package test;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class PuddleCounter {
public long calculateVolume(int[] myIntArray) {
long total = 0;
int pendingTotals[] = new int[0];
int lastMax = 0;
int lastInt = 0;
for (int thisInt : myIntArray) {
if (thisInt >= lastMax) {
for (int pendingTotal : pendingTotals) {
total += pendingTotal;
}
pendingTotals = new int[thisInt];
lastMax = thisInt;
} else {
if (thisInt < lastMax) {
for (int i = thisInt; i<lastMax;i++) {
pendingTotals[i]++;
}
}
if (lastInt < thisInt) {
for (int i = 0; i<thisInt;i++) {
total += pendingTotals[i];
pendingTotals[i] = 0;
}
}
}
lastInt = thisInt;
}
return total;
}
@Test
public void test() {
assertEquals(12, calculateVolume(new int[]{ 2,5,1,2,3,4,7,7,6,3,5 }));
assertEquals(10, calculateVolume(new int[]{ 2,5,1,2,3,4,7,7,6 }));
assertEquals(1, calculateVolume(new int[]{ 1,0,1 }));
assertEquals(5, calculateVolume(new int[]{ 5,0,5}));
assertEquals(1, calculateVolume(new int[]{ 0,1,0,1,0 }));
assertEquals(1, calculateVolume(new int[]{ 1,0,1,0 }));
assertEquals(3, calculateVolume(new int[]{ 1,0,1,2,0,2 }));
assertEquals(1, calculateVolume(new int[]{ 5,1,0,1 }));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.