Google Data Structures & Algorithms Interview Questions

PracticalCoder - "I am not clear on the relevance of the "list of valid words" to the original problem statement. It seems to have led the candidate to build a graph. Navigating a graph of all possible paths to the target word is computationally expensive, plus unnecessary as you are navigating the world of "possible" words, whereas to edit characters in a word, you don't necessarily need the intermediate words to be valid. Overall the answer to this problem seems to be to use dynamic programming. It would be g"See full answer

Pankaj G. - "Max distance can be between cat to rat or cat to bread. lets say it is x. I tried to find a path between rat and bread using DFS for every distance from cat(max upto x)."See full answer

Satyam S. - "Reversing a linked list is a very popular question. We have two approaches to reverse the linked list: Iterative approach and recursion approach. Iterative approach (JavaScript) function reverseLL(head){ if(head === null) return head; let prv = null; let next = null; let cur = head; while(cur){ next = cur.next; //backup cur.next = prv; prv = cur; cur = next; } head = prv; return head; } Recursion Approach (JS) function reverseLLByRecursion("See full answer

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

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

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

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

Gabriele G. - "Without using a recursive approach, one can perform a post-order traversal by removing the parent nodes from the stack only if children were visited: def diameterOfTree(root): if root is None: return 0 diameter = 0 stack = deque([[root, False]]) # (node, visited) node_heights = {} while stack: curr_node, visited = stack[-1] if visited: heightleft = nodeheights.get(curr_node.left, 0) heightright = nodehe"See full answer

Jordan Z. - "Maybe we can use this solution: 1, connect all the strings together, and add an integer value ahead each string. 2, use Huffmans algorithm to encode the step 1 result, to make the result size smaller. 3, return the root of Huffmans tree. This solution man be slower than the common serialize method, but it can save a lot of memory, I think, at lease doing serialize is mainly for tranfering data or storing data."See full answer

Noor M. - "Yes, I need to compare the first half of the first string with the reverse order of the second half of the second string. Repeat this process to the first half of the second string and the second half of the first string."See full answer

Steve M. - "def split_count(s): return 2**(len(s)-1) `"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

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

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

Guilherme F. - "A much better solution than the one in the article, below: It looks like the ones writing articles here in Javascript do not understand the time/space complexity of javascript methods. shift, splice, sort, etc... In the solution article you have a shift and a sort being done inside a while, that is, the multiplication of Ns. My solution, below, iterates through the list once and then sorts it, separately. It´s O(N+Log(N)) class ListNode { constructor(val = 0, next = null) { th"See full answer

Tiago R. - "function areSentencesSimilar(sentence1, sentence2, similarPairs) { if (sentence1.length !== sentence2.length) return false; for (let i=0; i (w1 === word1 && !visited.has(w2)) || (w2 === word1 && !visited.has(w1))); if (!edge) { "See full answer