juha
BAN USER
Comments (4)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
The algorithm is so simple. Calculate the sum and find the split point where both ends has the biggest difference.
int maxDiff(int[] nums) {
int total = 0;
for (int i = 0;i < nums.length;i++) {
total += nums[i];
}
int bestDiff = 0, subTotal = 0;
for (int i = 0;i < nums.length;i++) {
subTotal += nums[i];
// total = sub + remain
int diff = Math.abs(subTotal  total) + Math.abs(total  subTotal  total);
if (diff > bestDiff) {
bestDiff = diff;
}
}
return bestDiff;
}

juha
October 16, 2017 Comment hidden because of low score. Click to expand.
0
of 0 vote
If go through the lists taking the minimum number from each list gives the correct result. Probably there is room for optimization but the whole data set must be visited in any case.
class MinCommonRange {
static int[] minNums(int[][] rows) {
int bestMin = 1, bestMax = 1;
int[] rowIndexes = new int[rows.length];
while (true) {
int minRow = 1;
int min, max;
min = max = rows[0][rowIndexes[0]];
// Get min and max for current set
for (int i = 0;i < rows.length;i++) {
int[] row = rows[i];
int rowIndex = rowIndexes[i];
int num = row[rowIndex];
if (num <= min) {
// The lowest num which can be increased
if (rowIndex < row.length  1) {
minRow = i;
}
min = num;
}
else if (num > max) {
max = num;
}
}
// The new best range
if (bestMin < 0  bestMax  bestMin > max  min) {
bestMin = min;
bestMax = max;
}
// End of numbers
if (minRow < 0) {
break;
}
rowIndexes[minRow]++;
}
return new int[] { bestMin, bestMax };
}
public static void main(String[] args) {
int[] range = minNums(new int[][] {
new int[] { 4, 10, 15, 24, 26 },
new int[] { 0, 9, 12, 20 },
new int[] { 5, 18, 22, 30 }
});
System.out.println("Range: " + range[0] + " to " + range[1]);
}
}

juha
October 11, 2017 Comment hidden because of low score. Click to expand.
0
of 0 vote
A simple O(nm) solution that goes through the pixels "p" which with dimension w x h.
static void findLonelyPixels(int[] p, int w, int h) {
int rowPixels[] = new int[h];
int columnPixels[] = new int[w];
for (int x = 0;x < w;x++)
columnPixels[x] = 1;
int i = 0;
for (int y = 0;y < h;y++) {
rowPixels[y] = 1;
for (int x = 0;x < w;x++,i++) {
if (p[i] != 0) {
rowPixels[y] = rowPixels[y] < 0 ? x : 1;
columnPixels[x] = columnPixels[x] < 0 ? y : 1;
}
}
}
for (int y = 0;y < h;y++) {
int x = rowPixels[y];
if (x >= 0 && columnPixels[x] >= 0) {
System.out.println("Lonely pixel: " + x + "," + columnPixels[x]);
}
}
}

juha
October 02, 2017 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Using a sliding window the complexity is O(m + n). Expects that the char range is 0  255 so a hashmap could be better option.
 juha October 19, 2017