shwetabh11
BAN USERA slightly modified version of MergeSort does the trick here. Modification required to keep a track of the original index of the value.
public class P1 {
private int[] mainArray;
private int[] auxiliaryArray;
public P1(int[] a) {
mainArray = a;
auxiliaryArray = new int[a.length];
}
private int[][] sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return new int[][]{{a[lo]}, {lo}};
}
int mid = (lo + hi) / 2;
int[][] sorted1 = sort(a, lo, mid);
int[][] sorted2 = sort(a, mid + 1, hi);
return merge(sorted1, sorted2);
}
private int[][] merge(int[][] sorted1, int[][] sorted2) {
int[][] consolidatedArray = new int[2][sorted1[0].length + sorted2[0].length];
int index1 = 0, index2 = 0, offset = 0;
for (int x = 0; x < sorted1[0].length + sorted2[0].length; x++) {
if (index1 < sorted1[0].length && index2 < sorted2[0].length) {
if (sorted1[0][index1] < sorted2[0][index2]) {
consolidatedArray[0][x] = sorted1[0][index1];
consolidatedArray[1][x] = sorted1[1][index1];
auxiliaryArray[sorted1[1][index1++]] += offset;
} else {
consolidatedArray[0][x] = sorted2[0][index2];
consolidatedArray[1][x] = sorted2[1][index2++];
offset++;
}
} else if (index1 < sorted1[0].length) {
consolidatedArray[0][x] = sorted1[0][index1];
consolidatedArray[1][x] = sorted1[1][index1];
auxiliaryArray[sorted1[1][index1++]] += offset;
} else if (index2 < sorted2[0].length) {
consolidatedArray[0][x] = sorted2[0][index2];
consolidatedArray[1][x] = sorted2[1][index2++];
}
}
return consolidatedArray;
}
public int[] countOfLessThanOrEqualTo() {
sort(mainArray, 0, mainArray.length - 1);
return auxiliaryArray;
}
//test client
public static void main(String[] args) {
int[] a = new int[]{44, -3, 6, 1, 8, 6, 33, 99, 6, 2, 1};
P1 p1 = new P1(a);
a = p1.countOfLessThanOrEqualTo();
for (int x = 0; x < a.length; x++) {
System.out.print(p1.auxiliaryArray[x] + " ");
}
}
}
public class MakeTheRobotsMeet {
private int count = -1;
private boolean moveOpposite = false;
public void makeRobotsMeet(Robot robot) {
count++;
//make sure that both the robots move at least once
if (count == 0 || count == 1) {
//arbitrarily chosen to move each robot towards left
robot.moveLeft();
}
if (robot.onTopOfParachute()) {
robot.noOperation();
moveOpposite = true;
} else if (moveOpposite) {
robot.moveRight();
} else {
robot.moveLeft();
}
}
//test client
public static void main(String[] args) {
Robot robot1 = new Robot(10, 56);
Robot robot2 = new Robot(56, 10);
MakeTheRobotsMeet makeTheRobotsMeet = new MakeTheRobotsMeet();
while (!robot1.didWeMeet(robot2)) {
makeTheRobotsMeet.makeRobotsMeet(robot1);
makeTheRobotsMeet.makeRobotsMeet(robot2);
}
}
}
//Sample Robot implementation
public class Robot {
private int parachuteLocationOfThisRobot, parachuteLocationOfTheOtherRobot;
private int currentLocation;
public Robot(int parachuteLocationOfThisRobot, int parachuteLocationOfTheOtherRobot) {
currentLocation = parachuteLocationOfThisRobot;
this.parachuteLocationOfThisRobot = parachuteLocationOfThisRobot;
this.parachuteLocationOfTheOtherRobot = parachuteLocationOfTheOtherRobot;
}
public void moveLeft() {
currentLocation--;
}
public void moveRight() {
currentLocation++;
}
public void noOperation() {
return;
}
public boolean onTopOfParachute() {
return currentLocation == parachuteLocationOfThisRobot || currentLocation == parachuteLocationOfTheOtherRobot;
}
public boolean didWeMeet(Robot otherRobot) {
return currentLocation == otherRobot.currentLocation;
}
public int getCurrentLocation() {
return currentLocation;
}
}
May be a stupid question - are you assuming that all the the numbers are available at the same time?
- shwetabh11 July 09, 2014I ask because the question uses the word "stream" which suggests to me that we need to compute the median of the numbers available to us, and then recompute it as and when the user/system supplies more numbers
I suspect that your array-based heap solution may not scale well in such situation. What do you think?