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

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

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

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.