Bloomberg LP Interview Question Applications Developers
Country: United States
Interview Type: Phone Interview
Isn't this nLogn complexity? map.insert takes logn and it's performed in another n loop
public String findPath (String [] airports){
HashSet <String> set = new HashSet<> ();
HashMap<String,String> map = new HashMap<> ();
for (int i = 0 ; airports.length - 2 >= i ; i += 2){
map.put(airports[i], airports[i+1]);
set.add(airports[i+1]) ;
}
String from = null ;
for (String c : airports) {
if (!set.contains(c))
from = c ;
}
StringBuilder sb = new StringBuilder ();
sb.append(from) ;
while (map.containsKey(from)) {
sb.append("->") ;
sb.append(map.get(from)) ;
from = map.get(from) ;
}
return sb.toString() ;
}
This can solved by the following.
- Add the pairs(JFK -> LXA, SNA -> RKJ, LXA -> SNA ) in List to a hashMap as key value pair.
- Maintain a visited set which just holds the city names.
- Then start fetching the elements from the start element in the list from hashMap. While fetching add the key in the visited Set.
- Add the retrieved key value pair in the result list which you are going to return
- Stop when you cannot find value for the given key or the retrieved value is already in the visited set(which will stop a cycle).
Count the occurences of the city.
the city that are appearing only once are going to be source and destination.
Pick any one of them and if there is a pplace exists that can be reached from there, then for sure its source,else other one is source.Once you get the source just start traversing.
public class FindPath {
public static void main(String[] args) {
List<String> listOfAirPorts = new ArrayList<String>();
listOfAirPorts.add("JFK");
listOfAirPorts.add("LXA");
listOfAirPorts.add("SNA");
listOfAirPorts.add("RKJ");
listOfAirPorts.add("LXA");
listOfAirPorts.add("SNA");
// check if the even string is present in any odd string. if not present then it's the departure airport
String departure = null;
String firstDestination = null;
int departureId = 0;
boolean depFoundInDest = false;
for(int i=0; i < listOfAirPorts.size(); i=i+2) {
for(int j=1; j < listOfAirPorts.size(); j=j+2) {
if(listOfAirPorts.get(i).equals(listOfAirPorts.get(j))) {
depFoundInDest = true;
}
}
if (!depFoundInDest) {
departure = listOfAirPorts.get(i);
firstDestination = listOfAirPorts.get(i+1);
departureId = i;
} else {
depFoundInDest = false;
}
}
// since they are in pairs and we know the departure,
// we can start with departure, take it's destination, find the departure element of the destination,
// so on and so forth until we cannot find a departure for a destination
String path = loopList(departure, firstDestination, listOfAirPorts);
System.out.println(path);
}
private static String loopList(String departure, String destination, List<String> listOfAirPorts) {
for(int i=0; i < listOfAirPorts.size(); i=i+2) {
if(listOfAirPorts.get(i).equals(destination)) {
departure = departure + "-->" + destination;
return loopList(departure, listOfAirPorts.get(i+1), listOfAirPorts);
}
}
departure = departure + "-->" + destination;
return departure;
}
}
Imagine that each string is a node in a graph G. Then each pair represents an edge E between the nodes. (i) Buld this graph G and (ii) then explore it by a DFS or BFS from source node. A DFS example is below:
// G - undirected graph, v - vertex (location id)
int[] pathTo;
boolean[] isVisited[];
public Iterable findPath(Graph G, int source, int destination) {
int N = G.V(); // # of vertices (locations)
for (int k=0; k<N; k++) { // init arrays
pathTo[k] = -1;
isVisited[k] = false;
}
// DFS path search
dfs(G, source);
// Path does not exist
if (pathTo[destionation] == -1) return null;
// Backtrack while pushing to the stack
Iterable out<Integer> = Stack<Integer>();
int aux = pathTo[destination];
while(aux != -1) {
out.push(aux);
aux = pathTo[aux];
}
return out;
}
public void dfs (Graph G, int v) {
if (isVisited[v])
return;
isVisited[v] = true;
// recursively visi all adjacent nodes
for (int w : G.adjacent(v))
if (!isVisited[w]) {
dfs(G, w);
pathTo[w] = v;
}
}
What I suggest is:
Take a hashmap <src, (pointer, dest)> = city and pointer to node in doubly linked list
Take a doubly linked list with string value of city
Now for each (source, dest.) pair in vector
take source city from vector and try to find in hashmap
if not found
try to find destination city in hashmap
if found
using the pointer value from hashmap prepend this (source, dest) pair to DLL and also update hashmap for source city
if not found create linked pair of nodes (source, dest) and update hashmap with source city
if found
there is some error in input
Finally the head and tail of DLL will be the given source and destination and this DLL can be converted to required vector
I did it with using hashmap and just printing it recursively. Let me know if anything wrong with that. Interesting question btw.
package testing;
import java.util.HashMap;
/**
*
* @author Chetan
*/
public class airportProblem {
public static void main(String[] args){
String[] arr = {"JFK","LXA","SNA", "RKJ", "LXA", "SNA"};
HashMap z1 = new HashMap();
for(int i = 0; i < arr.length; i = i+2)
{
z1.put(arr[i], arr[i+1]);
}
String source = "", destination = "";
boolean inKeys, inValues;
for(int i = 0; i < arr.length; i++)
{
inKeys = z1.keySet().contains(arr[i]);
inValues = z1.values().contains(arr[i]);
if(inKeys && !inValues)
source = arr[i];
else if (!inKeys && inValues)
destination = arr[i];
}
System.out.println("source = " + source + " destination = " + destination);
printMapRecursive(z1, source);
}
public static void printMapRecursive(HashMap z1, String Node){
System.out.print(Node + " ");
if(z1.get(Node) == null)
return;
else
{
printMapRecursive(z1, z1.get(Node).toString());
}
}
}
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector<string> findPath(vector<string> airports) {
map<string, string> paths;
set<string> visited;
vector<string> output;
for (int i = 0; i <= airports.size()-2; i+=2) {
paths[airports.at(i)] = airports.at(i+1);
visited.insert(airports.at(i+1));
}
string from;
for (int i = 0; i < airports.size(); i++) {
if (visited.find(airports.at(i)) == visited.end()) {
from = airports.at(i);
}
}
int first = 1;
while (paths.find(from) != paths.end()) {
if (!first) {
output.push_back("->");
}
else {
first = 0;
}
output.push_back(from + "->" + paths[from]);
from = paths[from];
}
return output;
}
public class AirportNode{
private String name;
private ArrayList<AirportNode> from = new ArrayList<AirportNode>();
private ArrayList<AirportNode> to = new ArrayList<AirportNode>();
private int longestPath = 0;
public AirportNode(String name){
this.name = name;
}
public String Name(){
return name;
}
public int LongestPathDistance(){
return longestPath;
}
public void addFrom(AirportNode n){
from.add(n);
n.updateLongestPath(this);
}
public void addTo(AirportNode n){
to.add(n);
n.addFrom(this);
}
public void updateLongestPath(AirportNode n){
if(n.LongestPathDistance()>=longestPath){
longestPath = n.LongestPathDistance()+1;
to.remove(n);
to.add(0, n);
for(AirportNode f : from)
f.updateLongestPath(this);
}
}
public AirportNode getLongestPathNode(){
return to.size() == 0 ? null : to.get(0);
}
}
public String findPath (String [] airports){
HashMap<String,AirportNode> map = new HashMap<String,AirportNode> ();
for (int i = 0 ; airports.length - 2 >= i ; i += 2){
AirportNode d = null;
if(!map.containsKey(airports[i])){
d = new AirportNode(airports[i]);
map.put(airports[i],d);
}else
d = map.get(airports[i]);
AirportNode a = null;
if(!map.containsKey(airports[i+1])){
a = new AirportNode(airports[i+1]);
map.put(airports[i+1],a);
}else
a = map.get(airports[i+1]);
d.addTo(a);
}
AirportNode n = null;
for(String d:map.keySet()){
if(n == null ||
n.LongestPathDistance()<map.get(d).LongestPathDistance())
n = map.get(d);
}
StringBuilder sb = new StringBuilder ();
sb.append(n.Name()) ;
while ((n = n.getLongestPathNode()) != null) {
sb.append("->") ;
sb.append(n.Name()) ;
}
return sb.toString() ;
}
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Vector v = new Vector();
v.add("JFK");
v.add("LXA");
v.add("SNA");
v.add("RKJ");
v.add("LXA");
v.add("SNA");
findpath(v);
}
public static void findpath(Vector<String> v)
{
HashMap<String,String> map = new HashMap<String,String>();
ArrayList<String> list = new ArrayList<String>();
String depart="";
for(int i = 0; i < v.size(); i++)
{
//build map
map.put(v.get(i),v.get(++i));
}
//find departure airport
for(int i = 0; i<v.size(); i=i+2)
{
if(!map.containsValue(v.get(i)))
{
depart = v.get(i);
break;
}
}
String airport = depart;
for(int i = 0; i < v.size()/2 +1; i++)
{
if(i<v.size()/2)
System.out.print(airport+"=>");
else
System.out.print(airport);
airport = map.get(airport);
}
}
}
#include <algorithm>
#include <vector>
#include <iostream>
#include <stack>
#include <sstream>
#include <queue>
#include <cassert>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> findPath(const vector<string>& airports) {
unordered_map<string, string> next;
unordered_set<string> hasPre;
for (int i = 0; i < airports.size(); i += 2) {
next[ airports[i] ] = airports[i+1];
hasPre.insert(airports[i+1]);
}
string start;
for (int i = 0; i < airports.size(); i++) {
if (hasPre.find(airports[i]) == hasPre.end()) {
start = airports[i];
break;
}
}
string node = start;
vector<string> path;
while (next.find(node) != next.end()) {
path.push_back(node);
node = next[node];
}
path.push_back(node);
return path;
}
};
int main() {
string data[] = {"JFK", "LXA", "SNA", "RKJ", "LXA", "SNA"};
vector<string> airports;
for (int i = 0; i < 6; ++i) {
airports.push_back(data[i]);
}
Solution solution;
vector<string> path = solution.findPath(airports);
for (string node : path) {
cout << node << " ";
}
cout << endl;
}
O(n) complexity.
Maintain a set --> just to get all unique airports
Maintain a map --> for paths
Maintain a reverse map
The idea is to find the destination first (destination: one doesn't have start node and only end node)... And then backtrack using reverse map..
private static void airportPath() {
String[] arr = {"jfk", "lxa", "sna", "rkj", "lxa", "sna"};
Set<String> airports = new HashSet<>();
Map<String, String> path = new HashMap<>();
Map<String, String> reversePath = new HashMap<>();
for (int i=0; i<arr.length-1; i=i+2) {
path.put( arr[i], arr[i+1] );
reversePath.put(arr[i+1], arr[i]);
airports.add(arr[i]); airports.add(arr[i+1]);
}
String[] result = new String[airports.size()];
int counter = result.length-1;
// find destination : one doesn't have start node and only end node
String destination = "";
for (String s : airports) {
if (!path.containsKey(s)) {
destination = s;
}
}
result[counter] = destination;
// start from destination and backtrack
for (int i=counter-1; i>=0; --i) {
result[i] = reversePath.get(destination);
destination = result[i];
}
for (String i : result) {
System.out.println(i);
}
}
How about O(n) complexity and O(n) memory:
- zortlord January 07, 2015public static ArrayList<String> getPath(String[] arr){ HashSet<String> fromSet = new HashSet<String>(arr.length / 2); HashMap<String, String> toMap = new HashMap<String, String>(arr.length / 2); from(int i = 0; i < arr.length -1; i += 2){ fromSet.add(arr[i+1]); toMap.put(arr[i], arr[i+1]); } String start = null; for(String str : toMap.getKeys()){ if(!fromSet.contains(str)){ start = str; break; } } ArrayList<String> results = new ArrayList<String>(arr.length / 2 + 1); while(start != null){ results.add(start); start = toMap.get(start); } return results; }