Amazon Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
package com.example;
/*
Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:
Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")
*/
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
public class AirportPairs {
public static void orderAirports(Map<String, String> sortedMap){
Map<String, String> orderedMap = new LinkedHashMap<>();
Map.Entry<String, String> next = sortedMap.entrySet().iterator().next();
String key = next.getKey();
while(sortedMap.size() > orderedMap.size()){
orderedMap.put(key, sortedMap.get(key));
key = sortedMap.get(key);
}
System.out.println(orderedMap);
}
public static void main(String[] args){
Map<String, String> stringTreeMap = new TreeMap<>();
stringTreeMap.put("ITO", "KOA");
stringTreeMap.put("ANC", "SEA");
stringTreeMap.put("LGA", "CDG");
stringTreeMap.put("KOA", "LGA");
stringTreeMap.put("PDX", "ITO");
stringTreeMap.put("SEA", "PDX");
orderAirports(stringTreeMap);
}
}
import java.util.Arrays;
import java.util.stream.Collectors;
public class scratch
{
public static void main(String[] args)
{
String[][] input = {
{"ITO", "KOA"}, {"ANC", "SEA"}, {"LGA", "CDG"}, {"KOA", "LGA"}, {"PDX", "ITO"}, {"SEA", "PDX"}
};
printPairs(input);
sortPairs(input);
printPairs(input);
}
private static void sortPairs(String[][] input)
{
// Loop 1 - find first of Loop3's invariants: input[ 0 ] = ( open, connected )
for (int i = 0; i < input.length; i++) {
int j = 1;
for (; j < input.length; j++) {
if (input[i][0].equals(input[j][1])) {
break;
}
}
if (j == input.length) {
swapPairs(i, 0, input);
break;
}
}
// Loop 2 - find second of Loop3's invariants: input[ N - 1 ] = ( connected, open )
for (int i = 0; i < input.length; i++) {
int j = 1;
for (; j < input.length; j++) {
if (input[i][1].equals(input[j][0])) {
break;
}
}
if (j == input.length) {
swapPairs(i, input.length - 1, input);
break;
}
}
// Loop 3 - invariants input[ 0 ] = ( open, connected ]
// input[ N - 1 ] = [ connected, open )
for (int i = 2; i < input.length - 1; i++) {
int j = i - 1;
for (; j >= 0; j--) {
if (input[j + 1][0].equals(input[j][1])) {
break;
}
swapPairs(j, j + 1, input);
if (input[j + 1][0].equals(input[j][1])) {
break;
}
}
}
}
private static void swapPairs(int i, int j, String[][] pairs)
{
String[] temp = pairs[i];
pairs[i] = pairs[j];
pairs[j] = temp;
}
private static void printPairs(String[][] input)
{
for (String[] pair : input) {
System.out.print(Arrays.stream(pair).collect(Collectors.joining(",", "(", ")")));
}
System.out.println();
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace something
{
public class AirportOrdering
{
public AirportOrdering()
{
Dictionary<string, string> unorderedList = new Dictionary<string, string>();
unorderedList.Add("ITO", "KOA");
unorderedList.Add("ANC", "SEA");
unorderedList.Add("LGA", "CDG");
unorderedList.Add("KOA", "LGA");
unorderedList.Add("PDX", "ITO");
unorderedList.Add("SEA", "PDX");
foreach (KeyValuePair<string, string> element in unorderedList)
{
Console.WriteLine($"{element.Key}, {element.Value}");
}
Console.WriteLine("----------------OUTPUT---------");
Dictionary<string, string> orderedList = GetOrderedList(unorderedList);
foreach (KeyValuePair<string, string> element in orderedList)
{
Console.WriteLine($"{element.Key}, {element.Value}");
}
Console.ReadKey();
}
public Dictionary<string, string> GetOrderedList(Dictionary<string, string> unorderedList)
{
Dictionary<string, string> orderedList = new Dictionary<string, string>();
KeyValuePair<string, string> startAirport = new KeyValuePair<string, string>();
startAirport = unorderedList.Where(u => unorderedList.ContainsValue(u.Key) == false).FirstOrDefault();
if (startAirport.Key == null)
return orderedList;
orderedList = orderList(startAirport, unorderedList);
return orderedList;
}
public Dictionary<string, string> orderList(KeyValuePair<string, string> startPt, Dictionary<string, string> unorderedList, Dictionary<string, string> currentList = null)
{
if (currentList == null)
currentList = new Dictionary<string, string>();
if (currentList.Count() == unorderedList.Count() || startPt.Key == null)
return currentList;
currentList.Add(startPt.Key, startPt.Value);
KeyValuePair<string, string> next = new KeyValuePair<string, string>();
next = unorderedList.Where(u => u.Key == startPt.Value).FirstOrDefault();
orderList(next, unorderedList, currentList);
return currentList;
}
}
}
List1=[("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")]
sourcelist2=[]
destlist3=[]
for i,j in List1:
sourcelist2.append(i)
destlist3.append(j)
print(sourcelist2)
print(destlist3)
for i in range(len(sourcelist2)):
if sourcelist2[i] not in destlist3:
sourcelist2[0],sourcelist2[i]=sourcelist2[i],sourcelist2[0]
destlist3[0],destlist3[i]=destlist3[i],destlist3[0]
elif destlist3[i] not in sourcelist2:
print("I was here")
destlist3[len(destlist3)-1],destlist3[i]=destlist3[i],destlist3[len(destlist3)-1]
sourcelist2[len(destlist3)-1],sourcelist2[i] = sourcelist2[i], sourcelist2[len(destlist3) - 1]
for i in range(len(sourcelist2)-2):
a=sourcelist2.index(destlist3[i])
sourcelist2[a],sourcelist2[i+1]=sourcelist2[i+1],sourcelist2[a]
destlist3[a],destlist3[i+1]=destlist3[i+1],destlist3[a]
print(sourcelist2)
print(destlist3)
List1=[("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")]
sourcelist2=[]
destlist3=[]
for i,j in List1:
sourcelist2.append(i)
destlist3.append(j)
print(sourcelist2)
print(destlist3)
for i in range(len(sourcelist2)):
if sourcelist2[i] not in destlist3:
sourcelist2[0],sourcelist2[i]=sourcelist2[i],sourcelist2[0]
destlist3[0],destlist3[i]=destlist3[i],destlist3[0]
elif destlist3[i] not in sourcelist2:
print("I was here")
destlist3[len(destlist3)-1],destlist3[i]=destlist3[i],destlist3[len(destlist3)-1]
sourcelist2[len(destlist3)-1],sourcelist2[i] = sourcelist2[i], sourcelist2[len(destlist3) - 1]
for i in range(len(sourcelist2)-2):
a=sourcelist2.index(destlist3[i])
sourcelist2[a],sourcelist2[i+1]=sourcelist2[i+1],sourcelist2[a]
destlist3[a],destlist3[i+1]=destlist3[i+1],destlist3[a]
print(sourcelist2)
print(destlist3)
def print_route(dict_of_airport_pairs, start_airport):
airport = start_airport
route = []
while airport in dict_of_airport_pairs:
old_airport = airport
airport = dict_of_airport_pairs[airport]
route.append((old_airport, airport))
return route
def find_route(airport_pairs):
dict_of_airport_pairs = dict(airport_pairs)
for airport in dict_of_airport_pairs:
if airport not in dict_of_airport_pairs.values():
return print_route(dict_of_airport_pairs, airport)
def runOnce():
print find_route((("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")))
case class Visit(from: String, to: String)
object Main {
def order(visits: Seq[Visit], ordered: Seq[Visit] = Seq()): Seq[Visit] =
if (visits.isEmpty) {
ordered
} else {
if (ordered.isEmpty) {
order(visits.tail, Seq(visits.head))
} else {
// find preceding visit of first visit of currently oredered visits
val (preceding, nonPreceding) = visits.partition(_.to == ordered.head.from)
// find succeeding visit of last visit of currently ordered visits
val (succeeeding, nonSucceeding) = nonPreceding.partition(ordered.last.to == _.from)
order(nonSucceeding, preceding ++ ordered ++ succeeeding)
}
}
def main(args: Array[String]): Unit = {
val unorderedVisits = Seq(
Visit("ITO", "KOA"),
Visit("ANC", "SEA"),
Visit("LGA", "CDG"),
Visit("KOA", "LGA"),
Visit("PDX", "ITO"),
Visit("SEA", "PDX")
)
println(order(unorderedVisits))
}
}
public Dictionary<string,string> OrderAirportPair(Dictionary<string,string> airportPairs){
Dictionary<string,string> orderPair = new Dictionary<string,string>();
string lastValue = "";
for(int i=0;i<airportPairs.Count;i++){
if(i==0){
var temp = airportPairs.OrderBy(ap=>ap.Key).First();
orderPair.Add(temp.Key, temp.Value);
lastValue = temp.Value;
continue;
}
if(!orderPair.ContainsKey(lastValue)){
orderPair.Add(lastValue, airportPairs[lastValue]);
lastValue = airportPairs[lastValue];
}
}
return orderPair;
}
def find_route(airport_pairs):
'''
x is just to simpilified these when running the code for debug which don't need
to re-enter all the time
'''
x = (("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"),
("PDX", "ITO"), ("SEA", "PDX"))
dict_of_airport_pairs = dict(x)
r = {}
small_va = ""
for airport,data in dict_of_airport_pairs.items():
if small_va == "":
small_va = airport
else:
if airport < small_va:
small_va = airport
r[small_va] = dict_of_airport_pairs[small_va]
i = 0
while i < len(dict_of_airport_pairs)-1:
small_va = dict_of_airport_pairs[small_va]
r[small_va] = dict_of_airport_pairs[small_va]
i += 1
return r
def find_route(airport_pairs):
'''
x is just to simpilified these when running the code for debug which don't need
to re-enter all the time
'''
x = (("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"),
("PDX", "ITO"), ("SEA", "PDX"))
dict_of_airport_pairs = dict(x)
r = {}
small_va = ""
for airport,data in dict_of_airport_pairs.items():
if small_va == "":
small_va = airport
else:
if airport < small_va:
small_va = airport
r[small_va] = dict_of_airport_pairs[small_va]
i = 0
while i < len(dict_of_airport_pairs)-1:
small_va = dict_of_airport_pairs[small_va]
r[small_va] = dict_of_airport_pairs[small_va]
i += 1
return r
function route(map) {
var sortedRoute = new Map();
var keys = [ ...map.keys()].sort();
sortedRoute.set(keys[0],map.get(keys[0]));
for(var [key, val] of sortedRoute) {
if(map.has(val))
sortedRoute.set(val,map.get(val))
}
return ([...sortedRoute]);
}
var map = new Map();
map.set("ITO", "KOA");
map.set("ANC", "SEA");
map.set("LGA", "CDG");
map.set("KOA", "LGA");
map.set("PDX", "ITO");
map.set("SEA", "PDX");
console.log(route(map));
public static void main(String[] args) {
Map<String, String> stringTreeMap = new TreeMap<>();
stringTreeMap.put("ITO", "KOA");
stringTreeMap.put("ANC", "SEA");
stringTreeMap.put("LGA", "CDG");
stringTreeMap.put("KOA", "LGA");
stringTreeMap.put("PDX", "ITO");
stringTreeMap.put("SEA", "PDX");
Map<String, String> orderedMap = new LinkedHashMap<>();
//first find starting point
String first="";
for (String key : stringTreeMap.keySet()) {
if(!stringTreeMap.values().contains(key)){
first = key;
break;
}
}
System.out.println(first);
String key = first;
while(orderedMap.size() < stringTreeMap.size()){
orderedMap.put(key,stringTreeMap.get(key));
key = stringTreeMap.get(key);
}
System.out.println(orderedMap);
}
package com.example;
/*
Write a method that can take in an unordered list of airport pairs visited during a trip, and return the list in order:
Unordered: ("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")
Ordered: ("ANC", "SEA"), ("SEA", "PDX"), ("PDX", "ITO"), ("ITO", "KOA"), ("KOA", "LGA"), ("LGA", "CDG")
*/
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;
public class AirportPairs {
public static void orderAirports(Map<String, String> sortedMap){
Map<String, String> orderedMap = new LinkedHashMap<>();
Map.Entry<String, String> next = sortedMap.entrySet().iterator().next();
String key = next.getKey();
while(sortedMap.size() > orderedMap.size()){
orderedMap.put(key, sortedMap.get(key));
key = sortedMap.get(key);
}
System.out.println(orderedMap);
}
public static void main(String[] args){
Map<String, String> stringTreeMap = new TreeMap<>();
stringTreeMap.put("ITO", "KOA");
stringTreeMap.put("ANC", "SEA");
stringTreeMap.put("LGA", "CDG");
stringTreeMap.put("KOA", "LGA");
stringTreeMap.put("PDX", "ITO");
stringTreeMap.put("SEA", "PDX");
orderAirports(stringTreeMap);
}
}
Scala solution:
- guilhebl May 09, 2018object FindAirportRoutes { def main(args: Array[String]): Unit = { val a = Seq(("ITO", "KOA"), ("ANC", "SEA"), ("LGA", "CDG"), ("KOA", "LGA"), ("PDX", "ITO"), ("SEA", "PDX")) printOrderedRoute(a) } def printOrderedRoute(a : Seq[(String,String)]) : Unit = { val sources = a.groupBy(_._1).map { case (k,v) => (k,v.length)} val destinations = a.groupBy(_._2).map { case (k,v) => (k,v.length)} val origin = sources.filter(p => destinations.getOrElse(p._1, 0) < p._2) def dfs(source :String, tickets: Seq[(String,String)], path: Seq[(String,String)]): Unit = { if (tickets.isEmpty) { println(path) } else { tickets.filter(_._1.equals(source)).foreach { t => dfs(t._2, tickets.filterNot(x => t._1 == x._1 && t._2 == x._2), path :+ t) } } } // try all possible origin tickets origin.foreach(or => dfs(or._1, a, Seq.empty[(String, String)])) } } // prints: ((ANC,SEA), (SEA,PDX), (PDX,ITO), (ITO,KOA), (KOA,LGA), (LGA,CDG))