Google Interview Question for Front-end Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 9 vote

Pop the flight boarding passes one at a time. Create a hash table of String to Integer. We're going to map the city to the net in and out. For departure, decrease value of net in and out, for arrival, increase value of net in and out. At the end, scan through the hash table to find +1, which is the destination, and -1, which is the departure.

- zd September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What happens if you there is a cycle? If you go from A -> B -> C -> D -> E but you also go from C->F->B? With your implementation there would be two destinations that are equally valid.

- Anonymous September 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What would happen if there were a cycle. Say you have (src, dst) pairs: (A,B), (B,C), (C,D), (D,E), (C,F), (F,B). In your solution there are two equally valid destinations, B and E. How would you choose which one is the final destination?

EDIT: sorry i commented the same thing twice, once before and once after signing in. I cannot remove the anonymous one.

- kirag0112 September 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thats a invalid scenario, with this loop, one will never be able to reach to the destination.

A->B, B->C, C->F, F->B....now what? how traveler is expected to complete the journey?

i hope that, there was a reason to use the "Flight boarding scenario"....from the question it looks like person was more interested in knowing how will this be implemented using JAVA Script (no hash table, no fancy DSs)

- lazy.coder September 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

make two arrays..one for departure and one for destination..start comparing departure array's element one by one with the destination array if we find the same element delete it from both the arrays and at last we will be left with departure and destination.

- dhruv November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

not javascript, but O(n) runtime complexity and O(n) memory:

class TripData{
    String origin;
    String destination;

    public TripData(String origin, String destination){
        this.origin = origin;
        this.destination = destination;
    }
}

public static TripData getTripData(TripData[] tickets){
    if(tickets == null){
        throw new NullPointerException();
    }
    if(tickets.length == 0){
        return null;
    }

    //build implicit graph of the tickets
    HashMap<String, TripData> originToTripData = new HashMap<String, TripData>();
    HashMap<String, TripData> destinationToTripData = new HashMap<String, TripData>();
    for(TripData tripSegment : tickets){
        originToTripData.put(tripSegment.origin, tripSegment);
        destinationToTripData.put(tripSegment.destination, tripSegment);
    }

    //do dfs search from any point in the destination map to find the real origin
    TripData startPoint = tickets[0];
    String origin = null;
    while(startPoint != null){
        origin = startPoint.origin;
        startPoint = destinationToTripData.get(startPoint.origin);
    }
        
    //do dfs search from any point in the origin map to find the real destination
    startPoint = tickets[0];
    String destination = null;
    while(startPoint != null){
        destination = startPoint.destination;
        startPoint = originToTripData.get(startPoint.destination);
    }

    return new TripData(origin, destination);
}

- zortlord September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach is:
- iterate through the stack
- store the cities in a hashmap. if the src city has not been stored yet, store it with a value of 1, otherwise it means that the src has become a destination and subtract by 5. (or any number > 1). if the end city has not been stored yet, store it was a value of 0, otherwise it would mean that end city is not the final destination.
- one its done, go through the hasmap and the city with a value of 0 is the destination, and the city with a value > 0 is the src.

def path(passes):
	cities = {}
	src = 0
	des = 0

	for tickets in passes:
		src = tickets[0]
		end = tickets[1]

		if src not in cities: cities[src] = 1
		else: cities[src] = cities[src] - 5
		if end not in cities: cities[end] = 0
		else: cities[end] = cities[end] - 5

	for cities, val in cities.items():
		print(cities, val)
		if val is 0: des = cities
		if val > 0: src = cities

	print(src,des)

- yony September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def path(passes):
	cities = {}
	src = 0
	des = 0

	for tickets in passes:
		src = tickets[0]
		end = tickets[1]

		if src not in cities: cities[src] = 1
		else: cities[src] = cities[src] - 5
		if end not in cities: cities[end] = 0
		else: cities[end] = cities[end] - 5

	for cities, val in cities.items():
		print(cities, val)
		if val is 0: des = cities
		if val > 0: src = cities

	print(src,des)

- yony September 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Looking at the boarding passes (A, B) (B, C)(C, D)(D, F), we can see only the departure and destination cities appear once. And the other cities appear twice.
So, we can build a HashMap to store the city name as key and departure/destination(boolean) as value.
Iterate all boarding passes, for each city, if it isn't contained in the hashmap, store it, otherwise, remove it.
Only the departure and destination cities leave in the hashmap after visiting all boarding passes. We are done.
It is O(n) time.

- roysongbb10 October 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Hashing with remaining 2 non collided elements will start,end , which can be differentiated with augmented data or further search. If 0 non collided elements -> circular.
2. Adjacency matrix with a row/column with all zeroes, if it not exists circular.
3. Graph traversal in incoming and outgoing direction to terminate when you have a node with 1 directed edge. Keep a visited flag to disambiguate circular path.

- ankushbindlish November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

No one goes on a business trip and never comes home.

Thus every destination and arrival is given twice. Making this unsolvable. Boom.

- Anonymous November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We create a HashMap of arrival against a linked list which is partial path. We take a linked List from HashMap, gets its head h, find the LinkedList against h append the current linked list agains this linked list
{{

var Stack = require('./Stack');
var LL = require('./LinkedList');
var stack = new Stack();

var boardingPassArr = [
{depart:'SFO',arrival:'NY'},
{depart:'NDLS',arrival:'MUM'},
{depart:'DUBAI',arrival:'BER'},
{depart:'PERTH',arrival:'TOKYO'},
{depart:'MUM',arrival:'HYD'},
{depart:'HYD',arrival:'LDN'},
{depart:'CCU',arrival:'SFO'},
{depart:'LDN',arrival:'CCU'},
{depart:'TOKYO',arrival:'DUBAI'},
{depart:'BER',arrival:'NDLS'},
]

//O(n)
for(var i = 0; i<boardingPassArr.length;i++){
stack.push(boardingPassArr[i]);
}

var llHashMap = {};

//O(n)
//we will map the linkedList against the last arrival
while(true){
var poppedVal = stack.pop();
if(!poppedVal)break;

var tempLL = new LL();
tempLL.add(poppedVal.depart);
tempLL.add(poppedVal.arrival);
llHashMap[poppedVal.arrival] = tempLL;
}
//O(n^2)
//we loop through the object, pick the linkedList, get the head , find the linkedList for which this head
// is the tail, then append it to the end of this
while(true){
if(Object.keys(llHashMap).length<=1)break;
for(var arrivals in llHashMap){
var ll = llHashMap[arrivals];
if(ll){
var departure = ll.getHead().name;
if(llHashMap[departure]){ //if the head of this ll is a tail somewhere
var tailedLL = llHashMap[departure];
var llHead = ll.getHead();
tailedLL.add(llHead);
llHashMap[arrivals] = tailedLL;
delete llHashMap[departure];
}
}

}
}



function LinkedList(){
this._head = null;
}
LinkedList.prototype = {

constructor:LinkedList,
add:function(node){
if(typeof node !='object'){
node = {
name:node,
nextNode:null
};
}

if(this._head==null){
this._head = node;
}else{
var currNode = this._head;
while(currNode.nextNode!=null){

currNode =currNode.nextNode;
}
currNode.nextNode = node;
}

},
getHead:function(){
return this._head||{};
},
removeNodesFromHead:function(){
var currNode = this._head;
if(currNode){
this._head = currNode.nextNode;
}

return currNode;
}

}


function Stack(){
this._array = [];
this._size = 0;
this.maxSize = 100;
}

Stack.prototype = {

constructor:Stack,

push: function(val){
if(this.isFull()){
console.log("Stack is Full");
}else if(val){
this._array[this._size] = val;
this._size++;
}
},
pop: function(){
var poppedVal;
if(this.isEmpty()){
console.log("This stack is empty now ");
}else{
this._size --;
poppedVal = this._array[this._size];
// delete this._array[this._size-1];
this._array.splice(this._size);

}
return poppedVal;
},
isFull:function(){
return this.maxSize==this._size;
},
isEmpty:function(){
return this._size==0;
},
getStack:function(){
return this._array;
}
}
}}

- Pratyush December 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function orderPasses(passList) {
  var orderedList = [];
  var count = passList.length * 2;
  var list;
  var len;
  if (Array.isArray(passList) && passList.length) {
    list = passList.slice();
    orderedList.push(list.shift());
    len = list.length + 1;
    while (orderedList.length < len && count) {
      for (var i = 0; i <= len; i++) {
        if (orderedList[0][0] === list[i][1]) {
          orderedList.unshift(list[i]);
          break;
        }
        if (orderedList[orderedList.length - 1][1] === list[i][0]) {
          orderedList.push(list[i]);
          break;
        }
      }
      count--;
    }
  }
  // to return the full itinerary
  //return orderedList.map(function(i) { return i.join(' to '); }).join('\n');

  // or for just the start and end cities
  return orderedList[0][0] + ", " + orderedList[len - 1][1];
}

- Troy February 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var tickets = [{ departure: 'Los Angeles', arrival: 'San Francisco'},{ departure: 'San Francisco', arrival: 'New York' },{ departure: 'Moscow', arrival: 'Mali' },{ departure: 'Barcelona', arrival: 'Moscow' },{ departure: 'New York', arrival: 'Barcelona' }];
var departures = [];
var arrivals = [];

var firstDeparture = '';
var finalDestination = '';


for (var i=tickets.length; i--;) {
	var ticket = tickets[i];
	var departure = ticket.departure;
	var arrival = ticket.arrival;
	departures.push(departure);
	arrivals.push(arrival);
}

for (var i=tickets.length; i--;) {
	if (arrivals.indexOf(tickets[i].departure) < 0) {
		firstDeparture = tickets[i].departure;
	}

	if (departures.indexOf(tickets[i].arrival) < 0) {
		finalDestination = tickets[i].arrival;
	}
}

- Tatiana March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var tickets = [{ departure: 'Los Angeles', arrival: 'San Francisco'},{ departure: 'San Francisco', arrival: 'New York' },{ departure: 'Moscow', arrival: 'Mali' },{ departure: 'Barcelona', arrival: 'Moscow' },{ departure: 'New York', arrival: 'Barcelona' }];
var departures = [];
var arrivals = [];

var firstDeparture = '';
var finalDestination = '';


for (var i=tickets.length; i--;) {
	var ticket = tickets[i];
	var departure = ticket.departure;
	var arrival = ticket.arrival;
	departures.push(departure);
	arrivals.push(arrival);
}

for (var i=tickets.length; i--;) {
	if (arrivals.indexOf(tickets[i].departure) < 0) {
		firstDeparture = tickets[i].departure;
	}

	if (departures.indexOf(tickets[i].arrival) < 0) {
		finalDestination = tickets[i].arrival;
	}

}

- Tatiana March 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works in JavaScript:

var map = {};
map.tkt1 = {
source : "A",
dest : "B"
};

map.tkt2 = {
source : "B",
dest : "C"
};

map.tkt3 = {
source : "C",
dest : "D"
};

map.tkt4 = {
source : "D",
dest : "F"
};

var findSourceDestination = function (map){
	var hashMap = {};
	for (var tkt in map){
      var s = map[tkt].source;
      var d = map[tkt].dest;
  	if (!(s in hashMap))
    	hashMap[s] = -1;
    else
    	hashMap[s] = hashMap[s] - 1;
    if (!(d in hashMap))
    	hashMap[d] = 1;
    else
    	hashMap[d] = hashMap[d] + 1;
    
  }
  console.log(hashMap);
};

findSourceDestination(map);

- vinodsamanth April 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Put <source,destination> in hashmap. Scan hashmap keys and if it does not exists in values, it's the source. Scan hashmp values and if it does not exist in the source it is the destination. To optimize at each stage while reading the pair, you can check for duplicates (search source in map values and search destination in map keys and replace the associative values with the new one). Finally you will have one pair left as source->destination.

- joy June 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function findStartEnd(tickets) {

    var departures = tickets.map(function(ticket) {
      return ticket.depart;
    });
    var arrivals = tickets.map(function(ticket) {
      return ticket.arrive;
    });

    function findExtraCity(a, b) {

      return a.filter(function(city) {
        return b.indexOf(city) === -1;
      })[0];
    }

    var start = findExtraCity(departures, arrivals);
    var end = findExtraCity(arrivals, departures);

    return start + ', ' + end;
}

findStartEnd( [{ depart: 'New York', arrive: 'Miami' }, { depart: 'Chicago', arrive: 'New York' }, { depart: 'Miami', arrive: 'Minneapolis' }, { depart: 'Seattle', arrive: 'Los Angeles' }, { depart: 'Minneapolis', arrive: 'Seattle' }]);

- andrew.m.henderson September 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
var ticket = tickets[i];
departures.push(ticket.departure);
arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
if(arrivals.indexOf(departures[i]) < 0) {
console.log("First Departure City is " +departures[i]);
}
if(departures.indexOf(arrivals[i]) < 0) {
console.log("First Departure City is " +arrivals[i]);
}
}
}

BizTrip();

- Anonymous October 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
	var ticket = tickets[i];
	departures.push(ticket.departure);
	arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
	if(arrivals.indexOf(departures[i]) < 0) {
		console.log("First Departure City is " +departures[i]);
	}
	if(departures.indexOf(arrivals[i]) < 0) {
		console.log("First Departure City is " +arrivals[i]);
	}
}
}

BizTrip();

- Anonymous October 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
	var ticket = tickets[i];
	departures.push(ticket.departure);
	arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
	if(arrivals.indexOf(departures[i]) < 0) {
		console.log("First Departure City is " +departures[i]);
	}
	if(departures.indexOf(arrivals[i]) < 0) {
		console.log("First Departure City is " +arrivals[i]);
	}
}
}

BizTrip();

- Gova October 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a graph and do topological sort.

- Amol November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That's a graph problem where a boarding pass (edge) connectes two cities (nodes).

The question is unclear: if we want any way to reach our destination, we can do any kind of traversal, such as a DFS.

If we're looking for the shortest path (most likely), then the best is to do 2 breath first search traversals at the same time, from departure and destination: as soon as they cross, we have our shortest path.

- Flo March 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

window.onload = function() {
  var boardingPasses = [
    {depart: 'LA', arrive: 'NY'},
    {depart: 'SEA', arrive: 'PHX'},
    {depart: 'PHX', arrive: 'LA'},
    {depart: 'LON', arrive: 'SEA'}
  ];
  var arrivals = [];
  var departures = []
  var departureCity;
  var finalDestination;
  
  boardingPasses.forEach(bp => {
    arrivals.push(bp.arrive);
    departures.push(bp.depart);
  });
  
  console.log('Departure city: ' + findUnique(departures, arrivals ));
  console.log('Final Destination: ' + findUnique(arrivals, departures));
};

function findUnique(a, b) {
  return a.filter(f => !b.includes(f));
}

- mmcdonald39 July 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

const flightStack = [
  ['B', 'C'],
  ['E', 'F'],
  ['C', 'D'],
  ['D', 'E'],
  ['A', 'B'],
];

const findRoute = stack => {
  const xs = flightStack
    .reduce((acc, [x, _]) => {
      acc.add(x);
      return acc;
  }, new Set());
  
  const [[_, dest]] = stack.filter(([_, x]) => {
    const exists = xs.has(x);
    if(exists)
      xs.delete(x)
    return !exists
  });
  return [xs.values().next().value, dest];
}

findRoute(flightStack)

- Javascripter October 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript solution.

Basically:
- The origin city cannot possibly be a destination city.
- The destination city cannot possibly be a origin city.

Therefore:

const flights = [
  ['B', 'C'],
  ['E', 'F'],
  ['C', 'D'],
  ['D', 'E'],
  ['A', 'B'],
];

const findRoute = flights => {
	let sources = [];
  let destinations = [];
  
	flights.map((flight, index) => {
  	sources.push(flight[0]);
    destinations.push(flight[1]);
  });
  
  let sourceFlight = sources.filter(source => !destinations.includes(source))[0];
  let destinationFlight = destinations.filter(destination => !sources.includes(destination))[0];
      
  console.log(sourceFlight, destinationFlight);
};

findRoute(flights);

- hodgef December 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function test(tickets) {
	const cities = {};
	for(let ticket of tickets) {
		let x = cities[ticket.source];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.source] = x-1;
		x = cities[ticket.dest];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.dest] = x+1;
    }
	let source, dest
	for(let city in cities) {
		if (cities[city] < 0) source = city;
		if (cities[city] > 0) dest = city;
    }
	return {source, dest};
}


test([
{source:'a',dest:'b'},
{source:'c',dest:'d'},
{source:'b',dest:'c'},
{source:'d',dest:'a'}
])

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

function test(tickets) {
	const cities = {};
	for(let ticket of tickets) {
		let x = cities[ticket.source];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.source] = x-1;
		x = cities[ticket.dest];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.dest] = x+1;
    }
	let source, dest
	for(let city in cities) {
		if (cities[city] < 0) source = city;
		if (cities[city] > 0) dest = city;
    }
	return {source, dest};
}

test([
{source:'a',dest:'b'},
{source:'c',dest:'d'},
{source:'b',dest:'c'},
{source:'d',dest:'a'}
])

- mail@tevel.info June 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

function Ticket(dep, dest) {
    this.dep = dep;
    this.dest = dest;
}

var t1 = new Ticket('AND', 'BOM');
var t2 = new Ticket('BOM', 'DEL');
var t3 = new Ticket('DEL', 'CCU');
var t4 = new Ticket('CCU', 'BHO');
var t5 = new Ticket('BHO', 'MAS');
var t6 = new Ticket('MAS', 'BHO');
var t7 = new Ticket('BHO', 'BLR');

var pileOfTickets = [t1, t2, t3, t4, t5, t6, t7];

function getTripEndpoints(arr) {
    var endPoints = {},
        rdep, rdest;

    pileOfTickets.forEach(function (ticket) {
        var dep = ticket.dep,
            dest = ticket.dest;
        if (endPoints[dep]) {
            delete endPoints[dep];
        } else {
            endPoints[dep] = dep;
            rdep = dep;
        }
        if (endPoints[dest]) {
            delete endPoints[dest];
        } else {
            endPoints[dest] = dest;
            rdest = dest;
        }
    });
    return [rdep, rdest];
}

getTripEndpoints(pileOfTickets);

- AbsoluteZero February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

function Ticket(dep, dest) {
    this.dep = dep;
    this.dest = dest;
}

var t1 = new Ticket('AND', 'BOM');
var t2 = new Ticket('BOM', 'DEL');
var t3 = new Ticket('DEL', 'CCU');
var t4 = new Ticket('CCU', 'BHO');
var t5 = new Ticket('BHO', 'MAS');
var t6 = new Ticket('MAS', 'BHO');
var t7 = new Ticket('BHO', 'BLR');

var pileOfTickets = [t1, t2, t3, t4, t5, t6, t7];

function getTripEndpoints(arr) {
    var endPoints = {},
        rdep, rdest;

    pileOfTickets.forEach(function (ticket) {
        var dep = ticket.dep,
            dest = ticket.dest;
        if (endPoints[dep]) {
            delete endPoints[dep];
        } else {
            endPoints[dep] = dep;
            rdep = dep;
        }
        if (endPoints[dest]) {
            delete endPoints[dest];
        } else {
            endPoints[dest] = dest;
            rdest = dest;
        }
    });
    return [rdep, rdest];
}

getTripEndpoints(pileOfTickets);

- AbsoluteZero February 18, 2016 | 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