## Google Interview Question for Front-end Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 10 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.

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

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.

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

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.

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

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)

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

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.

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

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)``````

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)``````

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.

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.

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.

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 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();
llHashMap[poppedVal.arrival] = tempLL;
}
//O(n^2)
// 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){
if(llHashMap[departure]){ //if the head of this ll is a tail somewhere
var tailedLL = llHashMap[departure];
llHashMap[arrivals] = tailedLL;
delete llHashMap[departure];
}
}

}
}

}

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

}else{
while(currNode.nextNode!=null){

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

},
},
if(currNode){
}

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

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

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

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

}

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

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.

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

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

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

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

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

Build a graph and do topological sort.

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.

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

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, _]) => {
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)``````

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

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'}
])``````

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'}
])``````

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

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

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.