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

Abinash S. - " def hasgoodsubarray(nums, k): if not nums: return False if k == 0: for i in range(len(nums)): if nums[i] == 0 and nums[i + 1] == 0: return True return False map = {0:-1} sum = 0 for i,val in enumerate(nums): sum += val rem = sum % k if rem in map: if i - map[rem] >= 2: return True else: map[rem] = i return False print(hasgoods"See full answer

Erjan G. - "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_str = "".join(chars) return reversed_str `"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

Jessica R. - "a top-down recursive solution with memoization in python: from typing import List from functools import cache def changeSigns(nums: List[int], S: int) -> int: @cache def dp(i, curr_sum): if i == len(nums): if curr_sum == S: return 1 return 0 return dp(i+1, currsum + nums[i]) + dp(i+1, currsum - nums[i]) answer = dp(0, 0) if answer == 0: return -1 return answer `"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

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

Curly T. - "One thing is not clear to me, We encoded the length of the word to a character, but the max number which can be converted to char ascii is 255. How will it work for length till 65535?"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

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

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

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

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

Divya R. - "static TreeNode buildTree(int] preorder, int[] inorder) {//[2, 4, 5 if(preorder.length==0 || preorder.length!=inorder.length) { isNull=true; return null; } int parentElem=preorder[0];//2 int index=-1; index=binarySearch(inorder, parentElem);//3 //1 if(index==-1) { isNull=true; return null; } TreeNode root=new TreeNode(parentElem); int preOrder=0; int ind=-1; if(index>0) { int[] leftInOrder=Arrays.copyOfRange(inorder, 0, index); //[4, 2, 5]//[4] ind=binarySearch(preorder, inorder[index"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