cheeyim
BAN USER- 1of 1 vote
Answers/*
- cheeyim in Singapore
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
# > 11
*/| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm
My method requires to traverse through the matrix, update the steps as long as it is an open space by (1) look through surrounding neighbors for guards (2) looks for open space with steps updated and simply add them up (3) look for open space and move towards there, therefore incrementing the steps. Time complexity is O(n^2).
public static void main(String args[]) {
char[][] arr = {{'O', 'O', 'O', 'G'}, {'W', 'G', 'O', 'O'}, {'O', 'O', 'W', 'G'}, {'W', 'O', 'O', 'O'}};
arr = updateMatrix(arr);
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {
if (j==0)
System.out.print(arr[i][j]);
else
System.out.print(" "+arr[i][j]);
}
System.out.print("\n");
}
}
private static char[][] updateMatrix (char arr[][]){
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr[i].length; j++) {
if (arr[i][j] == 'O') {
int step = 1;
step += lookSurrounding(arr, i, j, arr.length);
//to convert to int - RADIX = 10
arr[i][j] = Character.forDigit(step, 10);
}
}
}
return arr;
}
private static int lookSurrounding(char arr[][],
int row,
int col,
int arraySize) {
//represent Up, Down, Left, Right
Character[] surroundingVal = {'E', 'E', 'E', 'E'};
int existingStep = -1;
//up
if (row - 1 >= 0) {
surroundingVal[0] = arr[row-1][col];
existingStep = Character.isDigit(surroundingVal[0]) && Character.getNumericValue(surroundingVal[0]) > existingStep
? Character.getNumericValue(surroundingVal[0]) : existingStep;
}
//down
if (row + 1 < arraySize) {
surroundingVal[1] = arr[row + 1][col];
existingStep = Character.isDigit(surroundingVal[1]) && Character.getNumericValue(surroundingVal[1]) > existingStep
? Character.getNumericValue(surroundingVal[1]) : existingStep;
}
//left
if (col - 1 >= 0) {
surroundingVal[2] = arr[row][col - 1];
existingStep = Character.isDigit(surroundingVal[2]) && Character.getNumericValue(surroundingVal[2]) > existingStep
? Character.getNumericValue(surroundingVal[2]) : existingStep;
}
//right
if (col + 1 < arraySize) {
surroundingVal[3] = arr[row][col+1];
existingStep = Character.isDigit(surroundingVal[3]) && Character.getNumericValue(surroundingVal[3]) > existingStep
? Character.getNumericValue(surroundingVal[3]) : existingStep;
}
if (Arrays.asList(surroundingVal).contains('G'))
return 0;
else if (existingStep > -1 )
return existingStep;
else if (Arrays.asList(surroundingVal).contains('O')) {
int step = 1;
int index = Arrays.asList(surroundingVal).indexOf('O');
int newRow = row, newCol = col;
if (index == 0)
newRow = row - 1;
else if (index == 1)
newRow = row + 1;
else if (index == 2)
newCol = col - 1;
else if (index == 3)
newCol = col + 1;
step += lookSurrounding(arr, newRow, newCol, arraySize);
return step;
}
//cater for error
return 0;
}
public static boolean contiguousSum(int[] arr, int targetSum)
{
int max = 0;
for (int i=0; i<arr.length; i++) {
max = arr[i];
if (arr[i] >= targetSum)
continue;
for (int j=i + 1; j<arr.length; j++) {
max += arr[j];
if (max == targetSum)
return true;
else if (max > targetSum || arr[j] >= targetSum)
break;
}
}
return false;
}
public static void main(String args[]) {
final int[] numbers = {-9,-1,1,3,5};
PriorityQueue pq = squareOfSortedData(numbers);
while (!pq.isEmpty())
System.out.println(pq.poll() + ",");
}
public static PriorityQueue squareOfSortedData(final int[] data) {
PriorityQueue pq = new PriorityQueue();
if (data == null || data.length == 0) {
return pq;
}
for (int i = 0; i < data.length; ++i) {
pq.add(BigInteger.valueOf(data[i]).pow(2).intValue());
}
return pq;
}
Repfarleym761, Accountant at Adobe
Enjoy meeting up with my friends and family, and I currently volunteer as a guest columnist for my local paper ...
Time - O(N)
Space -O(N)
- cheeyim October 03, 2016