Google L3-L4 Question Compilation from Discussion

Find all possible buddy words from the given list of strings (lower alpha). E.g., for 'abc' a buddy could be 'cde', for 'gyr' a buddy could be 'hzs'.

Similar to LeetCode problem: Swim in Rising Water.

There is a chess contest between N players. Each chess player has a distinct rank (positive integer number from 1 to N). We assume that in a chess game between two players, the player ranked higher always wins. The ranks remain constant during the contest. Unfortunately, we don't know the player ranks. But we know the outcome of M games in the following format: Player #1 won #2, Player #2 won #4, ... Given the results of M games above, are there any players whose rank can be precisely determined?

Consider a social network with n users. You have been given vector<vector<int>> friends, where friends[i][0] and friends[i][1] are friends. A person 'a' can view profile of 'b' if they are friends or have an indirect common friend. Find out how many profiles each user can view. Constraint: n <= 10^5, friends.size() <= n. E.g.: n = 7, friends = [{1,2}, {2,3}, {3,4}, {5,6}, {6,7}], result = [4,4,4,4,3,3].

Given a string 's', find the number of unique palindromic substrings. Constraints: s.size() <= 5000. E.g.: s = "aacaa", result = 5 ["a", "c", "aa", "aca", "aacaa"].

You are given multiple cities and a city A, each city is at a distance represented by time it takes to reach it. You are given n favorite cities. Find the shortest time to reach any of the favorite cities and return the time required.

Given a binary tree, return the maximum binary subtree size where all values of nodes are equal. Example: 2 2 2 2 2 2 3 Ans: 3.

String expression evaluation. Ex: 2a+2b-(a-b). Ans: a+3b.

Imagine you are standing at an incoming conveyor belt of items that need to be packaged into boxes of exactly three items that all fit together and placed on a second, outgoing, conveyor belt. You have sufficient storage space to place items off to the side while you wait for a full triplet that all fit together. Conveyor belt items are floating point numbers. Three items that "fit together" means that all items are within distance 'd' of each other. Once a 3-tuple is formed, those items must be discarded (should not be considered for future tuples). Input example: input_stream = [1.0, 11.0, 12.0, 13.0, 2.0, 3.0], d = 3. Output: [[11.0, 12.0, 13.0], [1.0, 2.0, 3.0]]. Distance is calculated by absolute values of the items (e.g., |1.0-2.0| = 1 <= 3, |2.0 - 3.0| = 1 <= 3, |1.0-3.0| = 2 <= 3). Input will not be given as an array but instead is a stream of numbers. Follow Up: If instead of just floating point numbers, you were given points on an X-Y plane, how would you modify the solution?

Given a node in a Binary Search Tree (BST), find the next largest (inorder successor) and next smallest (inorder predecessor) node. It is guaranteed that these nodes always exist (i.e. the input node will never be the smallest or largest node in the BST). You are only given a pointer to the node, and each node has a parent pointer. The structure is as follows: struct Node { int value; Node* left_child; Node* right_child; Node* parent; }; Consider this BST: 4 /
2 6 / \ /
1 3 5 7 If the given node is 3, the next largest (successor) is 4, the next smallest (predecessor) is 2.

Given a source, destination, and a corrupted node in a graph, find if it is possible to reach the destination from the source without traversing the corrupted node (BFS/DFS). Follow Up: Return the minimum distance of every node from the source node, assuming all edge weights are 1.

Given 2 strings, return if they are buddies. Two strings are buddies if the distance between each character of the strings is the same. dist('a', 'b') = 1 and dist('b', 'a') = 25. Also, dist('z', 'a') = 1. Follow Up: Given a list of strings, group all buddies together.

You are given a list of N elements. Each element is a tuple (value, can_decrement) where value is an integer (positive or negative), can_decrement is a boolean indicating how the value can be adjusted: If True, you are only allowed to decrement the value. If False, you are only allowed to increment the value. You are allowed to increment/decrement each number as much as you want, but only in the allowed direction. Your task is to determine whether it's possible to transform all values into a valid permutation of [1, 2, ..., N]. If it's possible, return the mapping in the form {original: transformed}. If it's not possible, return an empty dictionary. Follow Up: How many elements can be moved from the decrement list to the increment list and still allow a permutation to be made?

LeetCode problem: Move Pieces to Obtain a String.

You have a very large number, e.g., 2123470299109372, and a given integer k (e.g., k=6). You need to find the largest k-digit number which is a subsequence of the original number. Example: ans=999372.

An uncle wants to buy gifts for his nephew. The nephew provides a list of gifts, where each gift has: day (the day the gift is available for purchase) and price (the cost of the gift on that day). Example: (3, 4), (4, 2), (6, 4), (10, 5). The uncle saves $1 per day and can only buy a gift on the specified day. If he skips a gift, he cannot buy it later. The goal is to determine the maximum number of gifts he can purchase.

Given security logs with timestamps for entry and exit of users, determine: the maximum occupancy of the building at any given time, and the time at which that peak occupancy occurred.

Given an integer n, return a license plate number following this pattern: Ranges: 00000-99999, A0000-Z9999, AA000-ZZ999, AAA00-ZZZ99, AAAA0-ZZZZ9, AAAAA-ZZZZZ. Helper Functions Provided: padToBeginning(reqLen, charToPad, value): Pads the given character at the beginning of a string to achieve the required length. Example: padToBeginning(9, '0', '123') = 000000123. alpha(value): Converts an integer into an alphabetic sequence. Example: alpha(0) = A, alpha(25) = Z, alpha(26) = AA.

You are designing a JSON webpage viewer with the ability for users to save and load previously viewed JSON documents. The website sends/receives the complete state of the world from the webpage to the backend server on each update/save. The state of the world is stored in SimpleJSON. The client has the original document D1 and the modified document D2, where D2 is D1 + (delta). You begin profiling the application and notice that for very large JSON documents being saved it's very slow -- even if no change has been produced! Optimise the space-efficiency of saving the changes for a given SimpleJSON document where you are given 'old_doc' and 'new_doc'. Follow up: Json can be nested json.

A linked list problem where each node contains a value, a next pointer, and a hash computed using the current node’s value and its next node. Tasks included: Insert a node at the head of the list; Validate the linked list by traversing and verifying the hash of each node; Inserting a node at position k using recursion (which requires updating the hash values of all nodes from position k up to the head).

For given intervals inputs [from, to, name], return non-overlapping intervals [from, to, name(s)]. Example: Input [10, 100, David], [50, 150, Alex], [200, 300, Joe]. Output [10,50, David], [50, 100, (David, Alex)], [100, 150, Alex], [200, 300, Joe].

LeetCode problem: Design Search Autocomplete System.

Design a movie recommendation system. Each movie has a title and a rating. If movie A is similar to movie B, and movie B is similar to movie C, we will also consider movie A as similar to movie C (transitive property). Given a movie from the list, return its N similar movies with the highest rating. For example, if we have the following four movies: "Movie A" with rating 6, "Movie B" with rating 7, "Movie C" with rating 8, "Movie D" with rating 9, and the process has determined the following similarities: "Movie A" is similar to "Movie B", "Movie B" is similar to "Movie C".

Given a list of ranges, find the indices of ranges that contain a given number. LeetCode problem: Most Beautiful Item for Each Query. Example: ranges = { (3, 9) , (2, 8) , (5, 10) }. f(3) should return {0, 1}. f(9) should return {0, 2}.

You have an array of sequences, where each sequence has some values in order. You have to create a single result sequence where the relative order of elements within each original sequence stays as it is. Example: [[1,2,15,8], [2,4,7,8], [2,3,7,15]]. Output: 1,2,3,4,7,15,8 or 1,2,4,3,7,15,8. False case: [[1,6,4], [4,1]].

Given a matrix of size n * m (where n >=3 and m >= 3), find the number of 3 * 3 submatrices that have the maximum number of ones.

Strings are associated with points, like: [ ["cat.animal", 5], ["animal", 10], ["lion.animal", 15], ["tiger.cat.animal", 20] ]. Each string contributes its points to itself and any of its parent nodes (e.g., 'cat.animal' is a parent of 'tiger.cat.animal', 'animal' is a parent of 'cat.animal'). The goal is to return only the leaf strings (i.e., strings that don't have any children) along with their total aggregated points. Expected output: [ ["lion.animal", 25], # 15 (self) + 10 (animal) ["tiger.cat.animal", 35] # 20 (self) + 10 (animal) + cat.animal(5) ]. Only two leaf nodes exist in this case: 'lion.animal' and 'tiger.cat.animal'.

Given an array like arr = [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1]. Goal: Find the maximum continuous window where all elements are 0. Follow-up: Given that we can flip at most K 1s to 0s, find the longest window that becomes all zeros after flipping.

Given two cities A and B, where you need to collect profit. The cost of switching between the cities is given as negative, e.g., -5. Find the maximum profit you can collect, given you can start from any city and switch as many times as you want. Example: A = [2, 3, 4, 5, 6], B = [4, 3, 6, 5, 8], switch Cost = -5.

The question was to create a string replacement library. Given a map of string replacements, replace the value in the input string. Example: Map: {USER => admin, HOME => /%USER%/home}. Input: I am %USER% My home is %HOME%. Output: I am admin My home is /admin/home. Follow-up: He later modified the question to include something like a loop. We need to figure out how to detect and handle that. Example: Map: {USER => admin, HOME =>/%USER%/%PATH%/, PATH => %HOME%}.

Given multiple files (represented as arrays of strings/words), find the maximum length of a common prefix between any two files. Sample input: String[] file1 = {"hello", "world", "abc", "xyz"}; String[] file2 = {"hello", "world", "abc", "xyz1"}; String[] file3 = {"hello", "world", "abc2", "xyz"}; String[] file4 = {"hello", "world", "abc1", "xyz2"}. Answer for this is 3 ("hello", "world", "abc") which matches in file1 and file2.

Problem: Given a chat log file, find the top N most talkative users along with their total word count. Example Log: 10:00 < John > Hi, How is everyone?, 10:05 < Amy > Hello John, 10:06 < Maria > Great, Having my morning coffee, 13:00 < John > Let's meet this weekend, 13:30 < Amy > Woahoo. Helper Function Provided: parseLog(filepath): Returns the word count of each message. Example Output: [{'John', 4}, {'Amy', 2}, {'Maria', 5}, {'John', 4}, {'Amy', 1}]. Follow-up Questions: Optimize for better complexity. Implement the parseLog() function.

Given an unweighted and undirected graph, there are some friends on some nodes and some cafes on other nodes. We want to find a cafe such that the maximum distance travelled by any of the friends to reach that cafe is minimal (minimax problem). Sample input: Friends - 1,7. Cafes - 5,6. Edges - 1 2, 2 3, 3 4, 4 5, 3 6, 7 5, 7 3. Example distances: Friend 1 to cafe 5 is 4, to cafe 6 is 3. Friend 7 to cafe 5 is 3, to cafe 6 is 2. Cafe 6 is the answer since max distance travelled by both friends (max(3,2)=3) is less compared to cafe 5 (max(4,3)=4). If its impossible to reach a cafe then return null. There could be cycles in graph.