Google Interview Question Software Engineers
Country: United States
example output for true (thief CAN make it) case:
```
$ cd thief-vs-sensors/
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(3, 8, 1)
(2, 9, 2)
(8, 0, 1)
(2, 7, 3)
(9, 8, 1)
Can thief make it?
Sensor group now contains: [(3, 8, 1)] .
Sensor group now contains: [(3, 8, 1), (2, 9, 2)] .
Sensor group now contains: [(8, 0, 1)] .
Sensor group now contains: [(3, 8, 1), (2, 9, 2), (2, 7, 3)] .
Sensor group now contains: [(9, 8, 1)] .
true
```
example output for false (thief CANNOT make it) case:
```
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(3, 7, 4)
(2, 3, 4)
(7, 2, 2)
(0, 2, 2)
(6, 1, 3)
Can thief make it?
Sensor group now contains: [(3, 7, 4)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2), (0, 2, 2)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2), (0, 2, 2), (6, 1, 3)] .
false
```
code for above, ThiefVsSensors.java:
import java.util.Set;
import java.util.HashSet;
public class ThiefVsSensors {
public static void main(String args[]) {
// get some example data
int roomWidth = 10; int roomHeight = 10;
int maxR = 5;
// generate some random sensors distributed in the room
Set<Sensor> sensors = getSensorsToCheck(5, roomWidth, roomHeight, maxR);
System.out.println("Room size: 10x10");
System.out.println("Sensors:");
for (Sensor sensor : sensors) {
System.out.println(sensor.toString());
}
System.out.println("\n\n\n");
System.out.println("Can thief make it?");
try {
System.out.println(canThiefMakeIt(10, 10, sensors));
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
private static boolean canThiefMakeIt(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
// if any sensors are outside the room throw an exception
validateSensorsForRoom(roomHeight, roomWidth, sensors);
// combine any sensors which are touching by ensuring they are added to a sensor group
Set<SensorGroup> sensorGroups = new HashSet<SensorGroup>();
for (Sensor sensor : sensors) {
SensorGroup sensorGroupForSensor = null;
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.intersectsWith(sensor)) {
sensorGroupForSensor = sensorGroup;
break;
}
}
// if no existing SensorGroup intersects with this sensor, start a new one with this just sensor in it
if (sensorGroupForSensor == null) {
sensorGroupForSensor = new SensorGroup();
sensorGroups.add(sensorGroupForSensor);
}
sensorGroupForSensor.add(sensor);
}
// compute the min y and max y for each sensor cluster
// if any clusters have min y <= 0 and max y >= roomHeight, return false
// otherwise, return true
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.coversRoomYRange(roomHeight)) {
return false;
}
}
return true;
}
private static void validateSensorsForRoom(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
int numSensors = sensors.size();
for (Sensor sensor : sensors) {
if (sensor.x >= roomWidth || sensor.x < 0) {
throw new Exception("sensor " + sensor.toString() + " has x coordinate out of bounds");
}
if (sensor.y >= roomHeight || sensor.y < 0) {
throw new Exception("sensor " + sensor.toString() + " has y coordinate out of bounds");
}
}
}
// generate a random set of sensors to test
private static Set<Sensor> getSensorsToCheck(int numSensors, int maxX, int maxY, int maxR) {
Set<Sensor> sensors = new HashSet<Sensor>();
// add sensors here
for (int i=0; i < numSensors; i++) {
Sensor sensor = new Sensor((int)Math.round(Math.random() * maxX), (int)Math.round(Math.random() * maxY), (int)Math.round(Math.random() * maxR));
sensors.add(sensor);
}
return sensors;
}
private static class Sensor {
public int x;
public int y;
public int r;
public Sensor(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
public String toString() {
return "(" + this.x + ", " + this.y + ", " + this.r + ")"; // (x,y,r)
}
public boolean intersectsWith(Sensor other) {
int xdiff = this.x - other.x;
int ydiff = this.y - other.y;
int rcomb = this.r + other.r;
return xdiff*xdiff + ydiff*ydiff <= rcomb*rcomb;
}
}
private static class SensorGroup {
Set<Sensor> sensors = new HashSet<Sensor>();
public boolean intersectsWith(Sensor sensor) {
for (Sensor sensorInGroup : sensors) {
if (sensorInGroup.intersectsWith(sensor)) {
return true;
}
}
return false;
}
public void add(Sensor sensor) {
this.sensors.add(sensor);
System.out.println("Sensor group now contains: " + this.toString() + " .");
}
public boolean coversRoomYRange(int roomHeight) {
int minY = roomHeight;
int maxY = -1;
for (Sensor sensor : this.sensors) {
int minYForSensor = sensor.y - sensor.r;
int maxYForSensor = sensor.y + sensor.r;
if (minYForSensor < minY) { minY = minYForSensor; }
if (maxYForSensor > maxY) { maxY = maxYForSensor; }
}
return minY <= 0 && maxY >= roomHeight;
}
public String toString() {
String output = "[";
for (Sensor sensor : this.sensors) {
if (!output.equals("[")) { output += ", "; }
output += sensor.toString();
}
output += "]";
return output;
}
}
}
example output for true (thief CAN make it) case:
---
$ cd thief-vs-sensors/
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(3, 8, 1)
(2, 9, 2)
(8, 0, 1)
(2, 7, 3)
(9, 8, 1)
Can thief make it?
Sensor group now contains: [(3, 8, 1)] .
Sensor group now contains: [(3, 8, 1), (2, 9, 2)] .
Sensor group now contains: [(8, 0, 1)] .
Sensor group now contains: [(3, 8, 1), (2, 9, 2), (2, 7, 3)] .
Sensor group now contains: [(9, 8, 1)] .
true
---
example output for false (thief CANNOT make it) case:
---
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(3, 7, 4)
(2, 3, 4)
(7, 2, 2)
(0, 2, 2)
(6, 1, 3)
Can thief make it?
Sensor group now contains: [(3, 7, 4)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2), (0, 2, 2)] .
Sensor group now contains: [(3, 7, 4), (2, 3, 4), (7, 2, 2), (0, 2, 2), (6, 1, 3)] .
false
---
ThiefVsSensors.java:
import java.util.Set;
import java.util.HashSet;
public class ThiefVsSensors {
public static void main(String args[]) {
// get some example data
int roomWidth = 10; int roomHeight = 10;
int maxR = 5;
// generate some random sensors distributed in the room
Set<Sensor> sensors = getSensorsToCheck(5, roomWidth, roomHeight, maxR);
System.out.println("Room size: 10x10");
System.out.println("Sensors:");
for (Sensor sensor : sensors) {
System.out.println(sensor.toString());
}
System.out.println("\n\n\n");
System.out.println("Can thief make it?");
try {
System.out.println(canThiefMakeIt(10, 10, sensors));
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
private static boolean canThiefMakeIt(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
// if any sensors are outside the room throw an exception
validateSensorsForRoom(roomHeight, roomWidth, sensors);
// combine any sensors which are touching by ensuring they are added to a sensor group
Set<SensorGroup> sensorGroups = new HashSet<SensorGroup>();
for (Sensor sensor : sensors) {
SensorGroup sensorGroupForSensor = null;
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.intersectsWith(sensor)) {
sensorGroupForSensor = sensorGroup;
break;
}
}
// if no existing SensorGroup intersects with this sensor, start a new one with this just sensor in it
if (sensorGroupForSensor == null) {
sensorGroupForSensor = new SensorGroup();
sensorGroups.add(sensorGroupForSensor);
}
sensorGroupForSensor.add(sensor);
}
// compute the min y and max y for each sensor cluster
// if any clusters have min y <= 0 and max y >= roomHeight, return false
// otherwise, return true
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.coversRoomYRange(roomHeight)) {
return false;
}
}
return true;
}
private static void validateSensorsForRoom(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
int numSensors = sensors.size();
for (Sensor sensor : sensors) {
if (sensor.x >= roomWidth || sensor.x < 0) {
throw new Exception("sensor " + sensor.toString() + " has x coordinate out of bounds");
}
if (sensor.y >= roomHeight || sensor.y < 0) {
throw new Exception("sensor " + sensor.toString() + " has y coordinate out of bounds");
}
}
}
// generate a random set of sensors to test
private static Set<Sensor> getSensorsToCheck(int numSensors, int maxX, int maxY, int maxR) {
Set<Sensor> sensors = new HashSet<Sensor>();
// add sensors here
for (int i=0; i < numSensors; i++) {
Sensor sensor = new Sensor((int)Math.round(Math.random() * maxX), (int)Math.round(Math.random() * maxY), (int)Math.round(Math.random() * maxR));
sensors.add(sensor);
}
return sensors;
}
private static class Sensor {
public int x;
public int y;
public int r;
public Sensor(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
public String toString() {
return "(" + this.x + ", " + this.y + ", " + this.r + ")"; // (x,y,r)
}
public boolean intersectsWith(Sensor other) {
int xdiff = this.x - other.x;
int ydiff = this.y - other.y;
int rcomb = this.r + other.r;
return xdiff*xdiff + ydiff*ydiff <= rcomb*rcomb;
}
}
private static class SensorGroup {
Set<Sensor> sensors = new HashSet<Sensor>();
public boolean intersectsWith(Sensor sensor) {
for (Sensor sensorInGroup : sensors) {
if (sensorInGroup.intersectsWith(sensor)) {
return true;
}
}
return false;
}
public void add(Sensor sensor) {
this.sensors.add(sensor);
System.out.println("Sensor group now contains: " + this.toString() + " .");
}
public boolean coversRoomYRange(int roomHeight) {
int minY = roomHeight;
int maxY = -1;
for (Sensor sensor : this.sensors) {
int minYForSensor = sensor.y - sensor.r;
int maxYForSensor = sensor.y + sensor.r;
if (minYForSensor < minY) { minY = minYForSensor; }
if (maxYForSensor > maxY) { maxY = maxYForSensor; }
}
return minY <= 0 && maxY >= roomHeight;
}
public String toString() {
String output = "[";
for (Sensor sensor : this.sensors) {
if (!output.equals("[")) { output += ", "; }
output += sensor.toString();
}
output += "]";
return output;
}
}
}
example output for true (thief CAN make it) case:
---
$ cd thief-vs-sensors/
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(5, 3, 0)
(9, 7, 2)
(1, 4, 0)
(6, 2, 1)
(9, 3, 4)
Can thief make it?
Sensor group now contains: [(5, 3, 0)] .
Sensor group now contains: [(9, 7, 2)] .
Sensor group now contains: [(1, 4, 0)] .
Sensor group now contains: [(6, 2, 1)] .
Sensor centers for (9, 7, 2) and (9, 3, 4) are 4.0 units apart, less than the sum of the sensor radiuses 6
Sensor group now contains: [(9, 7, 2), (9, 3, 4)] .
true
---
example output for false (thief CANNOT make it) case:
---
$ javac ThiefVsSensors.java
$ java ThiefVsSensors
Room size: 10x10
Sensors:
(2, 2, 1)
(1, 7, 1)
(6, 2, 4)
(5, 8, 3)
(5, 2, 3)
Can thief make it?
Sensor group now contains: [(2, 2, 1)] .
Sensor group now contains: [(1, 7, 1)] .
Sensor centers for (2, 2, 1) and (6, 2, 4) are 4.0 units apart, less than the sum of the sensor radiuses 5
Sensor group now contains: [(2, 2, 1), (6, 2, 4)] .
Sensor centers for (6, 2, 4) and (5, 8, 3) are 6.0827627 units apart, less than the sum of the sensor radiuses 7
Sensor group now contains: [(2, 2, 1), (6, 2, 4), (5, 8, 3)] .
Sensor centers for (2, 2, 1) and (5, 2, 3) are 3.0 units apart, less than the sum of the sensor radiuses 4
Sensor group now contains: [(2, 2, 1), (6, 2, 4), (5, 8, 3), (5, 2, 3)] .
false
---
ThiefVsSensors.java:
import java.util.Set;
import java.util.HashSet;
public class ThiefVsSensors {
public static void main(String args[]) {
// get some example data
int roomWidth = 10; int roomHeight = 10;
int maxR = 5;
// generate some random sensors distributed in the room
Set<Sensor> sensors = getSensorsToCheck(5, roomWidth - 1, roomHeight - 1, maxR);
System.out.println("Room size: 10x10");
System.out.println("Sensors:");
for (Sensor sensor : sensors) {
System.out.println(sensor.toString());
}
System.out.println("\n\n\n");
System.out.println("Can thief make it?");
try {
System.out.println(canThiefMakeIt(10, 10, sensors));
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
private static boolean canThiefMakeIt(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
// if any sensors are outside the room throw an exception
validateSensorsForRoom(roomHeight, roomWidth, sensors);
// combine any sensors which are touching by ensuring they are added to a sensor group
Set<SensorGroup> sensorGroups = new HashSet<SensorGroup>();
for (Sensor sensor : sensors) {
SensorGroup sensorGroupForSensor = null;
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.intersectsWith(sensor)) {
sensorGroupForSensor = sensorGroup;
break;
}
}
// if no existing SensorGroup intersects with this sensor, start a new one with this just sensor in it
if (sensorGroupForSensor == null) {
sensorGroupForSensor = new SensorGroup();
sensorGroups.add(sensorGroupForSensor);
}
sensorGroupForSensor.add(sensor);
}
// compute the min y and max y for each sensor cluster
// if any clusters have min y <= 0 and max y >= roomHeight, return false
// otherwise, return true
for (SensorGroup sensorGroup : sensorGroups) {
if (sensorGroup.coversRoomYRange(roomHeight)) {
return false;
}
}
return true;
}
private static void validateSensorsForRoom(int roomHeight, int roomWidth, Set<Sensor> sensors) throws Exception {
int numSensors = sensors.size();
for (Sensor sensor : sensors) {
if (sensor.x >= roomWidth || sensor.x < 0) {
throw new Exception("sensor " + sensor.toString() + " has x coordinate out of bounds");
}
if (sensor.y >= roomHeight || sensor.y < 0) {
throw new Exception("sensor " + sensor.toString() + " has y coordinate out of bounds");
}
}
}
// generate a random set of sensors to test
private static Set<Sensor> getSensorsToCheck(int numSensors, int maxX, int maxY, int maxR) {
Set<Sensor> sensors = new HashSet<Sensor>();
// add sensors here
for (int i=0; i < numSensors; i++) {
Sensor sensor = new Sensor((int)Math.round(Math.random() * maxX), (int)Math.round(Math.random() * maxY), (int)Math.round(Math.random() * maxR));
sensors.add(sensor);
}
return sensors;
}
private static class Sensor {
public int x;
public int y;
public int r;
public Sensor(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
public String toString() {
return "(" + this.x + ", " + this.y + ", " + this.r + ")"; // (x,y,r)
}
public boolean intersectsWith(Sensor other) {
int xdiff = this.x - other.x;
int ydiff = this.y - other.y;
int rcomb = this.r + other.r;
// do it a little less efficiently to have nicer logging
// return xdiff*xdiff + ydiff*ydiff <= rcomb*rcomb;
if (xdiff*xdiff + ydiff*ydiff <= rcomb*rcomb) {
float dist = (float)Math.sqrt(xdiff*xdiff + ydiff*ydiff);
System.out.println("Sensor centers for " + this.toString() + " and " + other.toString() + " are " + dist + " units apart, less than the sum of the sensor radiuses " + rcomb);
return true;
}
return false;
}
}
private static class SensorGroup {
Set<Sensor> sensors = new HashSet<Sensor>();
public boolean intersectsWith(Sensor sensor) {
for (Sensor sensorInGroup : sensors) {
if (sensorInGroup.intersectsWith(sensor)) {
return true;
}
}
return false;
}
public void add(Sensor sensor) {
this.sensors.add(sensor);
System.out.println("Sensor group now contains: " + this.toString() + " .");
}
public boolean coversRoomYRange(int roomHeight) {
int minY = roomHeight;
int maxY = -1;
for (Sensor sensor : this.sensors) {
int minYForSensor = sensor.y - sensor.r;
int maxYForSensor = sensor.y + sensor.r;
if (minYForSensor < minY) { minY = minYForSensor; }
if (maxYForSensor > maxY) { maxY = maxYForSensor; }
}
return minY <= 0 && maxY >= roomHeight;
}
public String toString() {
String output = "[";
for (Sensor sensor : this.sensors) {
if (!output.equals("[")) { output += ", "; }
output += sensor.toString();
}
output += "]";
return output;
}
}
}
general idea: combine two sensors if these two sensors intersect with each other, and store their y range{(min_y, max_y)} which can reach in the room. If some union sensors' y_range satisfies min_y<=0 and max_y<=room_width, then thief cannot reach the right side, otherwise the thief can reach right side
- lixx3527 July 09, 2019