Google Interview Question for Backend Developers


Country: United States




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

This can be done by simple DFS, extending for only 2 edges.
Worst case complexity would be O(n2)

/**
  	
    0->1 100
    1->2 200
    2->3 50
    0->3 400
    1->3 100

      0    1   2     3
    0 0   100  0    400
    1 100  0   200  100 
    2 0   200  0    50 
    3 400 100  50   0 
  */
  
  public static void main(String[] args){
  
    int[][] nodes = new int[][]{{0, 100, 0, 400}, {100, 0, 200, 100}, {0, 200, 0, 50}, {400, 100, 50, 0}};
    int org = 0;
    int dest = 3;
    
    List<Integer> visited = new ArrayList<Integer>();
    visited.add(org);
    int n = mincost(nodes, org, dest, 0, 0, Integer.MAX_VALUE, visited);
  	System.out.println(n);
  }
  
  public static int mincost(int[][] nodes, int org, int dest, int hops, int cost, int mincost, List<Integer> visited){
  	
    if(org == dest){
      if(hops < 4){
      	mincost = Math.min(mincost, cost);
      }
      return mincost;
    }
    if(hops > 3)
      return mincost;
    
    int[] connections = nodes[org];
    int n = connections.length;
    
    for(int i = 0; i < n; i++){
      if(connections[i] != 0 && !visited.contains(i)){
        visited.add(i);
      	mincost = mincost(nodes, i, dest, hops+1, cost+connections[i], mincost, visited);
        visited.remove(new Integer(i));
      }
    }
    return mincost;
  }

- sudip.innovates November 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a directed weighted graph out of the given list ( a-100->b , b -200->c, e-200->f, ...). Then you can either use BFS or dijkstra and stop after two followup. Keep track of the parent node and the distance.
I would prefer dijkstra (with a good datastructure) over BFS because dijkstra follows the shortest path while BFS that just all possible steps.

- Scavi November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ELDVN is it not O((M + N) log N) for Dijkstra?

- Scavi November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(NlogN + MlogN) = O(MlogN), I think.

- ELDVN November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in a connected, sparse graph: M = N-1 in a dense graph M=O(N^2), therefore we can express the runtime with M alone as well.... negative tickets prices would be cool though

- Chris November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Dijkstra does not seem appropriate to me, for two reasons. First, it finds shortest (cheapest) paths from a given source to ALL reachable nodes. That makes it very wasteful, since we only want the cheapest path from x to y. Second, and more importantly, Dijkstra always adds ONE NODE per cycle, but it NEVER cares how many hops are needed. This problem is constrained to a maximum of 3 hops (two transfers).

To find the cheapest path from one given node to another given node, you want something more like a double-ended search. Basically BFS for one hop out from x, and BFS for one hop out from y (along INCOMING arcs), then scan through once more to link them up.

- Rob November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dijkstra does not seem appropriate to me, for two reasons. First, it finds shortest (cheapest) paths from a given source to ALL reachable nodes. That makes it very wasteful, since we only want the cheapest path from x to y. Second, and more importantly, Dijkstra always adds ONE NODE per cycle, but it NEVER cares how many hops are needed. This problem is constrained to a maximum of 3 hops (two transfers).

To find the cheapest path from one given node to another given node, you want something more like a double-ended search. Basically BFS for one hop out from x, and BFS for one hop out from y (along INCOMING arcs), then scan through once more to link them up.

- Rob November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rob. That's correct. Using a bidirectional BFS it's easy to find the subgraph that contains the shortest path. But what if the subgraph still contains millions of links. Yes, there are only 3 hops, but each node can have 1 million weighted edges. It would be 1,000,000 ^ 3 paths to scan.

- Alex November 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Alex This is Rob replying. A few thoughts. In the actual hypothetical context of flights, google tells me there are 17,678 commercial airports in the entire world, so surely no node in this ACTUAL question has even 10^4 edges. But if we generalize to the abstract problem without thinking about actual airports/flights, then the algorithm I wrote was (degree)^2, not (degree)^3. My first step is to pre-process the list of all flights into a dictionary (if not originally given as such). Then, if there are 10^6 flights out of x, and 10^6 flights into y, I check the 10^12 possible "middle links". Each lookup in the dict takes O(1) time, so the overall running time would be O(degree^2). There is certainly room for significant optimizations, depending on what the actual data is like. For example, if you find a direct flight or a two-edge flight in the first two rounds, then you can prune your search significantly when sifting through the three-edge possibilities.

#flights = [(('a','b'), 200) , (('c','d'), 300), (('a','c'), 150) , (('b','d'), 600), (('a','e'), 250), (('e','f'), 3), (('f','d'), 100), (('a','f'), 600)]
#out: find_cheapest_flight('a', 'd', f, out , inc) --> (353, [('a', 'e'), ('e', 'f'), ('f', 'd')])
def process_flights(flights):
    flight_dict = dict(flights)
    outgoing = dict() # key = a, value = [(b, 200), (c, 100)]
    incoming = dict() # key = c, value = [(a, 100)]
    for flight in flights:
        origin, dest = flight[0]
        fare = flight[1]
        if origin in outgoing:
            outgoing[origin].append((dest, fare))
        else:
            outgoing[origin] = [(dest, fare)]
        if dest in incoming :
            incoming [dest ].append((origin, fare))
        else:
            incoming [dest ] = [(origin, fare)]
    return flight_dict, outgoing , incoming


def find_cheapest_flight(x, y, flight_dict, outgoing , incoming):
    if x not in outgoing or y not in incoming:
        print 'Sorry, no flights service those cities.'
        return None
    cheapest_route = []
    cheapest_fare = 10**10
    if (x,y) in flight_dict:
        cheapest_route = [(x,y)]
        cheapest_fare = flight_dict[(x,y)]
    for flight in outgoing[x]:
        city1, fare = flight
        if (city1, y) in flight_dict:
            if fare + flight_dict[(city1, y)] < cheapest_fare :
                cheapest_fare = fare + flight_dict[(city1, y)] 
                cheapest_route = [(x, city1), (city1, y)]
        for flight in incoming[y]:
            city2, fare3 = flight
            if (city1, city2) in flight_dict:
                fare2 = flight_dict[(city1, city2)]
                if fare + fare2 + fare3 < cheapest_fare :
                    cheapest_fare =fare + fare2 + fare3
                    cheapest_route = [(x, city1), (city1, city2), (city2, y)]
    return cheapest_fare, cheapest_route

- robshowsides November 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Rob. That's correct. But to me it looks simpler and more efficient to use Dijkstra, limiting number of hops to 2. To make it correct, when we reach a node, we consider 2 criteria - cost, and number of hops. E.g. if we reach the node with 1 hop and $50 cost, and the node already has a label of 2 hops and $10, the new node also survives, because it contains something better in the criteria.
Alternatively, we can use the bidirectional BST to find the 3-hop subgraph (just marking its nodes as enabled), and in the subgraph, we can use a regular Dijkstra to find the actual cheapest path.

- Alex November 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

isnt it a BFS? and at most 3 levels.

- zyfo2 November 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

If price can not negative:
Djikstra algorithm O(MlogN)
Otherwise:
Ford-Bellman algorithm O(NM)

where is M = Edges, N = vertexes;

- ELDVN November 25, 2017 | 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