## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

In this approach, there is a possibility of a gap between x coordinates of two points whose y range overlaps and extends the whole room

Comment hidden because of low score. Click to expand.
0
of 2 vote

I think this question it should be using union find to solve it

Comment hidden because of low score. Click to expand.
0
of 0 vote

correct me if my ideas are incorrect

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can assume few things here, discussing with the interviewer:
room is an inifinite grid, with each box in a grid of length 2r and the sensor is placed in the center of the box, we have such infinite sensors in the grid

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

// 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));
}

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) {
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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
Comment hidden because of low score. Click to expand.
0
of 0 vote
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

// 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));
}

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) {
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;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

// 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));
}

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) {
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;
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.