Google Data Structures & Algorithms 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

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

Anonymous Prawn - "Would be better to adjust resolution in the video player directly."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

Anonymous Possum - "#inplace reversal without inbuilt functions def reverseString(s): chars = list(s) l, r = 0, len(s)-1 while l < r: chars[l],chars[r] = chars[r],chars[l] l += 1 r -= 1 reversed = "".join(chars) return reversed "See full answer

Alejandro C. - "1 - Oder list of Kid Position and Sellers Positions (ascending) 2 - Implement a method to check distant 'e' for every kid pos (finding nearest seller and checking if sellerpos - currkid_pos < e, for all kid pos) 3 - Calculate mid from 0 to the 'max post' in between both kids and seller list: (max(max(k) -min(k), max(s) - min(s))) 4 - Perform binary search to find distance 'e' that satisfy step '2'"See full answer

Yugaank K. - "A recursive backtracking solution in python. def changeSigns(nums: List[int], S: int) -> int: res = [] n = len(nums) def backtrack(index, curr, arr): if curr == S and len(arr) == n: res.append(arr[:]) return if index >= len(nums): return for i in range(index, n): add +ve number arr.append(nums[i]) backtrack(i+1, curr + nums[i], arr) arr.pop() "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

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

Bless M. - "You can ask some clarifying questions like 1) Ask if the list is already sorted or not 2) is zero included in the list ? 3) Natural numbers are usually positive numbers ( clarify they are non negatives) Solution : 1) If sorted use two pointers and sort them in O(N) 2) if not sorted , -ve / only +ve numbers in the list doesn't matter - the easiest solution is Use a priority queue and push the number and its square in each iteration Finally return the list returned by the priority Queue. N"See full answer

Tiago R. - "class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } function exploreSubtree(node) { let leftHeight = 0; let rightHeight = 0; let maxDiameter = 0; // visit left if (node.left) { const leftVisit = exploreSubtree(node.left); leftHeight = leftVisit.height + 1; maxDiameter = Math.max(maxDiameter, leftVisit.maxDiameter); } // visit right if (node.right) { con"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

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

Tiago R. - "function generateParentheses(n) { if (n < 1) { return []; } if (n === 1) { return ["()"]; } const combinations = new Set(); let previousCombinations = generateParentheses(n-1); for (let prev of previousCombinations) { for (let i=0; i < prev.length; i++) { combinations.add(prev.slice(0, i+1) + "()" + prev.slice(i+1)); } } return [...combinations]; } `"See full answer

Tiago R. - "function addChildren(root, val, inorder) { const rootInOrderIndex = inorder.indexOf(root.value); const childrenInOrderIndex = inorder.indexOf(val); if (childrenInOrderIndex < rootInOrderIndex) { if (!root.left) { root.left = new TreeNode(val); } else { addChildren(root.left, val, inorder); } } else { if (!root.right) { root.right = new TreeNode(val); } else { addChildren(root.right,"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

Nitin P. - "public static void sortBinaryArray(int[] array) { int len = array.length; int[] res = new int[len]; int r=len-1; for (int value : array) { if(value==1){ res[r]= 1; r--; } } System.out.println(Arrays.toString(res)); } `"See full answer