Ancestor Queries - Google Top Interview Questions
Implement a data structure with the following methods: AncestorQuerier(Tree root) which instantiates the data structure with the given tree node. root only contains unique values int getAncestor(int val, int k) which returns the kth (0-indexed) ancestor of node with value val. If there's no kth ancestor, return -1. Constraints 0 ≤ n ≤ 100,000 where n is the number of nodes in root 0 ≤ m ≤ 100,000 where m is the number of calls to getAncestor Example 1 Input methods
View Solution →Border Crossing - Google Top Interview Questions
You are given two-dimensional lists of integers roads and countries as well as integers start and end. Each element in roads contains [x, y, weight] meaning that to travel from city x to y costs weight. Each element countries[i] represents all of the cities that belong to country i. Every city belongs to exactly one country. You are currently in city start and want to travel to city end. During this trip, you want to minimize country-to-country border hops as a first priority, and
View Solution →Cheapest Bus Route - Google Top Interview Questions
You are given a two-dimensional list of integers connections. Each element contains [f, t, id] meaning that bus id has a route from location f to location t. It costs one unit of money to get on a new bus, but if you stay on the same bus continuously, you only pay one unit. Return the minimum cost necessary to take the bus from location 0 to the largest location. Return -1 if it's not possible. Constraints n ≤ 1,000 where n is the number of bus stops m ≤ 1,000 where m is the
View Solution →Cheapest Cost to All Cities - Google Top Interview Questions
You are given two lists of integers costs_from and costs_to of the same length where each index i represents a city. Building a one-way road from city i to j costs costs_from[i] + costs_to[j]. You are also given a two-dimensional list of integers edges where each list contains [x, y] meaning there's already a one-way road from city x to y. Given that we want to be able to go to any city from city 0 (not necessarily in one path), return the minimum cost to build the necessary roads.
View Solution →Connected Road to Destination- Google Top Interview Questions
You are given integers sx, sy, ex, ey and two-dimensional list of integers roads. You are currently located at coordinate (sx, sy) and want to move to destination (ex, ey). Each element in roads contains (x, y) which is a road that will be added at that coordinate. Roads are added one by one in order. You can only move to adjacent (up, down, left, right) coordinates if there is a road in that coordinate or if it's the destination coordinate. For example, at (x, y) we can move to
View Solution →