Google Coding Interview Questions

叶 路. - "from collections import deque def updateword(words, startword, end_word): if end_word not in words: return None # Early exit if end_word is not in the dictionary queue = deque([(start_word, 0)]) # (word, steps) visited = set([start_word]) # Keep track of visited words while queue: word, steps = queue.popleft() if word == end_word: return steps # Found the target word, return steps for i in range(len(word)): "See full answer

Yeshwanth D. - "Was this for an entry level engineer role?"See full answer

Anonymous Prawn - "Would be better to adjust resolution in the video player directly."See full answer

Karan K. - "2 Approaches: 1) The more intuitive approach is doing a multi-source BFS from all cats and storing the distance of closest cats. Then do a dfs/bfs from rat to bread. Time Complexity: O(mn + 4^L) where L is path length, worst case L could be mn Space Complexity: O(m*n) 2) The first approach should be fine for interviews. But if they ask to optimize it further, you can use Binary Search. Problems like "Finding max of min distance" or "Finding min of max" could be usually solved by BS. "See full answer

Rahul M. - "Idea for solution: Reverse the complete char array Reverse the words separated by space. i.e. Find the space characters and the reverse the subarray between two space characters. vector reverseSubarray(vector& arr, int s, int e) { while (s reverseWords(vector& arr ) { int n = arr.size(); reverse(arr, 0, n - 1"See full answer

Kofi N. - "const mergeIntervals = (intervals) => { const compare = (a, b) => { if(a[0] b[0]) return 1 else if(a[0] === b[0]) { return a[1] - b[1] } } let current = [] const result = [] const sorted = intervals.sort(compare) for(let i = 0; i = b[0]) current[1] = b[1] els"See full answer

Ajay U. - "// C++ program to print the count of // subsets with sum equal to the given value X #include using namespace std; // Recursive function to return the count // of subsets with sum equal to the given value int subsetSum(int arr[], int n, int i, int sum, int count) { // The recursion is stopped at N-th level // where all the subsets of the given array // have been checked if (i == n) { // Incrementing the count if sum is // equal to 0 and returning the count if (sum == 0)"See full answer

J R. - "These are a set of utilities used to manage the heap memory as part of an application. The C standard library implements these functions. malloc(bytes) takes a number of bytes and returns a pointer to the start of the allocated buffer. If the allocation failed, a null pointer is returned instead. calloc(count, size) behaves like malloc(count * size), but also zero-initializes the allocated buffer, assuming the allocation succeeded. realloc(ptr, size) takes a pointer to a previously al"See full answer

Babaa - "Function signature for reference: def calculate(servers: List[int], k: int) -> int: ... To resolve this, you can use binary search considering left=0 and right=max(servers) * k so Example: servers=[1,4,5] First server handle 1 request in let's say 1 second, second 4 seconds and last 5 seconds. k=10 So I want to know the minimal time to process 10 requests Get the mid for timeline mid = (left+right)//2 -> mid is 25 Check how many we could process 25//1 = 25 25//4=6 25//5=5 so 25 + 6 +"See full answer

Sohum S. - "I would assume that this is similar to an intervals question. Meeting Rooms II (https://www.lintcode.com/problem/919/?fromId=203&_from=collection) on Leetcode seems like the closest comparison, it's a premium question so I linked Lintcode. I'm assuming that we also need to just return the minimum number of cars used. You need to sort for the most optimal solution, so you're constrained by an O(nlogn) time complexity. So any sorting solution could work (using a heap, sorting the array input arra"See full answer

Shikha S. - "Binary serach on E range"See full answer

Tiago R. - "function serialize(list) { for (let i=0; i 0xFFFF) { throw new Exception(String ${list[i]} is too long!); } const prefix = String.fromCharCode(length); list[i] = ${prefix}${list[i]}; console.log(list[i]) } return list.join(''); } function deserialize(s) { let i=0; const length = s.length; const output = []; while (i < length) { "See full answer

Jeff S. - " class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } function diameterOfTree(root) { if (root === null || root.left === null & root.right === null) { return 0; } function countBranch(node, count) { if (node.left === null && node.right === null) { return count; } let left = node.left === null ? 0 : countBranch(node.left, count+1); let right = no"See full answer

Matthew K. - " function climbStairs(n) { // 4 iterations of Dynamic Programming solutions: // Step 1: Recursive: // if (n <= 2) return n // return climbStairs(n-1) + climbStairs(n-2) // Step 2: Top-down Memoization // const memo = {0:0, 1:1, 2:2} // function f(x) { // if (x in memo) return memo[x] // memo[x] = f(x-1) + f(x-2) // return memo[x] // } // return f(n) // Step 3: Bottom-up Tabulation // const tab = [0,1,2] // f"See full answer

Batman X. - "def friend_distance(friends, userA, userB): step = 0 total_neighs = set() llen = len(total_neighs) total_neighs.add(userB) while len(total_neighs)!=llen: s = set() step += 1 llen = len(total_neighs) for el in total_neighs: nes = neighbours(friends, userA, el) if userA in nes: return step for p in nes: s.add(p) for el in s: total_neighs.add(el) return -1 def neighbours(A,n1, n2): out = set() for i in range(len(A[n2])): if An2: out.add(i) return out"See full answer

Guilherme M. - "Question: An array of n integers is given, and a positive integer k, where k << n. k indicates that the absolute difference between each element's current index (icurrent) and the index in the sorted array (isorted) is less than k (|icurr - isorted| < k). Sort the given array. The most common solution is with a Heap: def solution(arr, k): min_heap = [] result = [] for i in range(len(arr)) heapq.heappush(min_heap, arr[i]) "See full answer

Rick E. - " O(n) time from typing import List def generate_parentheses(n: int): res = [] def generate(buf, opened, closed): if len(buf) == 2 * n: if n != 0: res.append(buf) return if opened < n: generate( buf + "(", opened + 1, closed) if closed < opened: generate(buf + ")", opened, closed + 1) generate("", 0, 0) return res debug your code below print(generate_parentheses(1"See full answer

Anonymous Quail - " from typing import List def least_interval(tasks: List[str], n: int) -> int: pass # your code goes here if n == 0: return len(tasks) dictionary = {} total_sum = len(tasks) output = 0 for t in tasks: if t in dictionary: dictionary[t] += 1 else: dictionary[t] = 1 dictLen = len(dictionary) while total_sum > 0: for key in dictionary.keys(): if dictionary[key] > 0: "See full answer