Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
class Space {
constructor( x, y, type ) {
this.x = x;
this.y = y;
this.type = type;
this.left = undefined;
this.right = undefined;
this.up = undefined;
this.down = undefined;
}
visit( visited ) {
let hash_code = this.toString();
if( !visited.hasOwnProperty(hash_code) ) {
['left','right','up','down'].forEach( element => {
if( this[element] ) {
this[element].visit(visited);
}
},this);
visited[hash_code] = this;
}
return visited;
}
toString() {
return "["+this.x+"_"+this.y+"]";
}
}
let start = {}; // Should be assigned elsewhere
start.visit({}).values().filter( element => {
return (element.type=='tree' || element.type=='house');
}).forEach( element => {
// This is going to call .toString() method
console.log(element);
});
class Space {
constructor( x, y, type ) {
this.x = x;
this.y = y;
this.type = type;
this.left = undefined;
this.right = undefined;
this.up = undefined;
this.down = undefined;
}
visit( visited ) {
let hash_code = this.toString();
if( !visited.hasOwnProperty(hash_code) ) {
['left','right','up','down'].forEach( element => {
if( this[element] ) {
this[element].visit(visited);
}
},this);
visited[hash_code] = this;
}
return visited;
}
toString() {
return "["+this.x+"_"+this.y+"]";
}
}
let start = {}; // Should be assigned elsewhere
start.visit({}).values().filter( element => {
return (element.type=='tree' || element.type='house');
}).forEach( element => {
console.log(element);
});
class Space {
constructor( x, y, type ) {
this.x = x;
this.y = y;
this.type = type;
this.left = undefined;
this.right = undefined;
this.up = undefined;
this.down = undefined;
}
visit( visited ) {
let hash_code = this.toString();
if( !visited.hasOwnProperty(hash_code) ) {
['left','right','up','down'].forEach( element => {
if( this[element] ) {
this[element].visit(visited);
}
},this);
visited[hash_code] = this;
}
return visited;
}
toString() {
return "["+this.x+"_"+this.y+"]";
}
}
let start = {}; // Should be assigned elsewhere
start.visit({}).values().filter( element => {
return (element.type=='tree' || element.type='house');
}).forEach( element => {
console.log(element);
});
I think(?) this is a Breadth First Search (BFS) problem on a graph structure
This could be implemented as an Adjacency Matrix data structure, but
the criteria in the question specified a Space class with two members.
class Space {
constructor(value){
this.value = value
this.neighbors = []
}
addNeighbors(left, right, up, down) {
this.neighbors = [left, right, up, down]
}
}
function findAll(start) {
// BFS to find all the Houses and Trees
// Keep track of visited
const visited = new Map()
// Use queue for BFS
const queue = []
// enqueue start node and set as visited
queue.push(start)
visited.set(start, true)
// Process the queue of nodes traversing the graph
while(queue.length !== 0) {
const space = queue.shift()
if(space.value !== '0') {
console.log(space.value)
}
for (const s of space.neighbors) {
if (s !== null) {
if (visited.get(s) !== true) {
visited.set(s, true)
queue.push(s)
}
}
}
}
}
////////////////////////////
// Testing Solution
////////////////////////////
// Setup grid
const s00 = new Space('T')
const s01 = new Space('0')
const s02 = new Space('0')
const s03 = new Space('H')
const s04 = new Space('0')
const s10 = new Space('0')
const s11 = new Space('0')
const s12 = new Space('0')
const s13 = new Space('0')
const s14 = new Space('0')
const s20 = new Space('H')
const s21 = new Space('H')
const s22 = new Space('T')
const s23 = new Space('H')
const s24 = new Space('0')
s00.addNeighbors(null, s01, null, s10)
s01.addNeighbors(s00, s02, null, s11)
s02.addNeighbors(s01, s03, null, s12)
s03.addNeighbors(s02, s04, null, s13)
s04.addNeighbors(s03, null, null, s14)
s10.addNeighbors(null, s11, s00, s20)
s11.addNeighbors(s10, s12, s01, s21)
s12.addNeighbors(s11, s13, s02, s22)
s13.addNeighbors(s12, s14, s03, s23)
s14.addNeighbors(s13, null, s04, s24)
s20.addNeighbors(null, s21, s10, null)
s21.addNeighbors(s20, s22, s11, null)
s22.addNeighbors(s21, s23, s12, null)
s23.addNeighbors(s22, s24, s13, null)
s24.addNeighbors(s23, null, s14, null)
// Call findAll
findAll(s13)
BFS
private static class Space{
String type;
Space[] neighbours;
public Space(String type){
neighbours = new Space[4];
this.type = type;
}
public void addNeighbours(Space left, Space right, Space up, Space down){
neighbours = new Space[]{left, right, up, down};
}
public String getType(){
return type;
}
}
private static class QueueEntry{
Space space;
int x, y;
public QueueEntry(Space space, int x, int y){
this.space = space;
this.x = x;
this.y = y;
}
}
public static List<Space> findAll(Space start){
List<Space> ans = new ArrayList<>();
Map<Integer, Map<Integer, Space>> visitedMap = new HashMap<>();
Queue<QueueEntry> queue = new LinkedList<>();
queue.offer(new QueueEntry(start,0,0));
while(!queue.isEmpty()){
QueueEntry qe = queue.poll();
if(qe.space != null) {
if(!visitedMap.containsKey(qe.x)){
visitedMap.put(qe.x, new HashMap<>());
}
if (!visitedMap.get(qe.x).containsKey(qe.y)) {
visitedMap.get(qe.x).put(qe.y, qe.space);
queue.offer(new QueueEntry(qe.space.neighbours[0], qe.x, qe.y - 1));
queue.offer(new QueueEntry(qe.space.neighbours[1], qe.x, qe.y + 1));
queue.offer(new QueueEntry(qe.space.neighbours[2], qe.x -1, qe.y));
queue.offer(new QueueEntry(qe.space.neighbours[3], qe.x+1, qe.y));
if(qe.space.getType() != "O"){
ans.add(qe.space);
}
}
}
}
return ans;
}
public class TraverseGridGivenACell {
class Space {
String occupant;
// assume four neighbors, always in order up , down, left, right
// some neighbors can be null if cell is on edge / is corner
Space[] neighbors;
}
static short UP = 0;
static short DOWN = 1;
static short LEFT = 2;
static short RIGHT = 3;
static String TREE = "tree";
static String HOUSE = "house";
static String EMPTY = "";
/**
* 1) get to a known corner , using top left corner
* 2) traverse grid and count
* start at beginning of row and go right
* move down to next row
*/
public int traverseAndCountCellsOfType(Space startCell, String type) {
if (type == null || type != TREE || type != HOUSE || type != EMPTY){
return 0;
}
if (startCell == null) { return 0; }
// get to a known corner , using top left corner
Space origin = startCell;
while (origin.neighbors[LEFT] != null){
origin = origin.neighbors[LEFT];
}
while (origin.neighbors[UP] != null){
origin = origin.neighbors[UP];
}
// traverse grid and count
int res = 0;
Space rowStartCell = origin;
while (rowStartCell != null) {
Space cell = rowStartCell;
while (cell != null){
if(type.equals(cell.occupant)) {res++;}
cell = cell.neighbors[RIGHT];
}
rowStartCell = rowStartCell.neighbors[DOWN];
}
return res;
}
}
- Anon March 12, 2018