Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

package test.grid;

import java.util.ArrayList;
import java.util.List;

public class TreeHouse {
    public static class Space {
        private int x;
        private int y;
        private String m_type;
        private Space[] m_neighbors;
        
        public boolean equals(Space s1){
            if(s1.x == x && s1.y == y){
                return true;
            }
            return false;
        }
        
        public int hashCode(){
            return x ^ y;
        }

        public String toString(){
            return "[" + m_type + "] ("  + x + "," + y + ")";
        }
        
        public Space(String type, int x, int y){
            this.m_type = type;
            this.x = x;
            this.y = y;
        }
        
        public void printNeighbors(){
            System.out.println("---- NEGIHBORS of " + this + " -----");
            int i = 0;
            for(Space s: m_neighbors){
                if(s != null)
                  System.out.println(i + " - " + s);                     
                else
                  System.out.println(i + " - NULL");                     
                
                i++;
            }
        }
        public String getType(){
            return m_type;
        }
        
        public void setNeighbors(Space[] neighbors){
            m_neighbors = neighbors;
        }
        
        public List<Space> traverse(List<Space> visitedMap){
            if(!visitedMap.contains(this)){
                visitedMap.add(this);
                for(Space s: m_neighbors){
                    if(s != null)
                       visitedMap = s.traverse(visitedMap);
                }
                
            }
            return visitedMap;
        }
    }
    
    public static void fillNeighbors(Space[] spaces){
        for(Space s1: spaces){
            Space[] neighbors = new Space[4];
            for(Space s2: spaces){

                if(s1.x - 1== s2.x && s1.y == s2.y){
                    neighbors[0] = s2;
                }  
                
                if(s1.x + 1 == s2.x && s1.y == s2.y){
                    neighbors[1] = s2;
                } 
                
                if(s1.x == s2.x && s1.y - 1== s2.y){
                    neighbors[2] = s2;
                }  
                
                if(s1.x == s2.x && s1.y + 1== s2.y){
                    neighbors[3] = s2;
                } 
                
             }
             s1.setNeighbors(neighbors);
        }
        
    }
    
    public TreeHouse() {
        super();
    }
    
    public static void main(String[] args){
        Space[] spaceList = new Space[] {
                new Space("TREE",0,0),
                new Space("EMPTY",0,1),
                new Space("EMPTY",0,2),
                new Space("HOUSE",0,3),
                new Space("EMPTY",0,4),
        new Space("EMPTY",1,0),
        new Space("EMPTY",1,1),
        new Space("EMPTY",1,2),
        new Space("EMPTY",1,3),
        new Space("HOUSE",1,4),
        new Space("HOUSE",2,0),
        new Space("HOUSE",2,1),
        new Space("TREE",2,2),
        new Space("HOUSE",2,3),
        new Space("EMPTY",2,4)

            };
        
        fillNeighbors(spaceList);
        
        /*for(Space s: spaceList){
            s.printNeighbors();
        }*/
        
        List<Space> visitedMap = new ArrayList<Space>(4);
        for(Space s: spaceList[0].traverse(visitedMap)){
            if("TREE".equals(s.getType()) ||
               "HOUSE".equals(s.getType()) ){
                   System.out.println(s);
               }
        }

    }
}

- Anon March 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- fatcat February 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- catfat February 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fatcat February 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- randombit March 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous June 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- just_do_it November 11, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More