Google Algorithm Interview Tips: Communication, Execution, Optimization

"Let me make sure I understand the problem:
- We have an array of integers
- We need to find two numbers that sum to a target
- Can there be duplicates in the array?
- Should I return indices or the values themselves?
- What if no solution exists?"

"I think I'll use a hash map approach:
1. Iterate through the array
2. For each number, check if (target - number) is in the map
3. If yes, I found the pair; if no, add the current number to the map
4. Time: O(n), Space: O(n)

The brute force would be nested loops O(n²), but the hash map is better."

"Let me test with the example [2, 7, 11, 15], target = 9:
- i=0, num=2, target-num=7, not in seen, add 2 to seen: seen={2}
- i=1, num=7, target-num=2, IS in seen, return [0, 1]
Great, it works.

What about edge cases?
- Empty array: The loop doesn't run, we return undefined (or -1, depending on spec)
- Array with one element: Same, loop runs once, no pair found
- Duplicates: If we had [2, 2] with target 4, we'd find it correctly"

"The current solution is O(n) time, O(n) space.

For two-pointer approach, we could:
1. Sort the array: O(n log n)
2. Use left/right pointers to find the pair: O(n)
3. Total: O(n log n) time, O(1) space (in-place)

The hash map is better in practice (O(n) vs O(n log n)), but two-pointers uses constant space. Trade-offs."

// Good
for (let i = 0; i < arr.length; i++) {
  const current = arr[i];
  if (map.has(target - current)) {
    return [map.get(target - current), i];
  }
  map.set(current, i);
}

// Less good (pseudocode)
for each num in arr:
  if seen has (target - num):
    return pair
  seen[num] = true

// Bad: missing declaration
function twoSum(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    // oops, what's 'result'? declared where?
    if (result[0] === target) { }
  }
}

// Good: declared at top
function twoSum(arr, target) {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    // ... use seen
  }
  return -1; // or throw error
}

// Use 2 spaces, consistently. Helps readability in plain text
function solve(arr) {
  const map = new Map();
  for (let i = 0; i < arr.length; i++) {
    const complement = target - arr[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(arr[i], i);
  }
  return -1;
}

// Without helper: dense
function solve(graph) {
  const visited = new Set();
  const result = [];
  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node]) {
      dfs(neighbor);
    }
  }
  for (const node in graph) {
    dfs(node);
  }
  return result;
}

// With helper: Clearer structure
function dfs(node, graph, visited, result) {
  if (visited.has(node)) return;
  visited.add(node);
  result.push(node);
  for (const neighbor of graph[node]) {
    dfs(neighbor, graph, visited, result);
  }
}

function solve(graph) {
  const visited = new Set();
  const result = [];
  for (const node in graph) {
    dfs(node, graph, visited, result);
  }
  return result;
}

// Bad: obvious comments
const arr = [1, 2, 3];
const len = arr.length; // Get the length

// Good: explains intent
const arr = [1, 2, 3];
const len = arr.length; // Exclude last element in loop (sliding window)

// Good: explains algorithm choice
const seen = new Map(); // Hash map for O(1) lookup (vs. set which loses indices)

Let me trace through with arr = [2, 7, 11, 15], target = 9:

i=0, arr[0]=2, target-2=7, seen={}, no match, seen.set(2, 0) → seen={2→0}
i=1, arr[1]=7, target-7=2, seen has 2! Return [0, 1]

Correct!

"I'm stuck on how to optimize this beyond brute force. Could you give me a hint?
The slow part is checking every pair... is there a data structure that would help?"

"Let me code the happy path first: assume the array is sorted and has a solution.
Then I'll add complexity for unsorted arrays and edge cases."

"The slow part is finding duplicates. What data structure makes 'have I seen this before?'
O(1)? ... A set or hash map. Let me try that approach."

"Let me code the brute force solution: nested loops, O(n²). It's not optimal,
but it works. Then I can optimize if time allows."

"I'm not sure what you mean by 'optimize for space'. Do you mean I should avoid
extra data structures, or just minimize overall memory usage?"

const map = {};
map['key'] = 'value';
if ('key' in map) { }

// Problem: All keys are converted to strings
const map = {};
map[1] = 'one';
map['1'] = 'two'; // Overwrites! 1 and '1' are the same key

const map = new Map();
map.set(1, 'one');
map.set('1', 'two'); // Different keys! 1 and '1' are distinct

if (map.has(1)) { } // O(1) lookup
const value = map.get(1);
map.set(key, value);
map.delete(key);
/////// Iterate
for (const [key, value] of map) { }

const seen = new Set();
seen.add(value);
if (seen.has(value)) { }
seen.delete(value);

// Iterate
for (const value of seen) { }

// Access
arr[0]; // O(1)
arr.length;

// Mutate
arr.push(value);        // O(1) amortized, add to end
arr.pop();              // O(1), remove from end
arr.unshift(value);     // O(n), add to start (shifts everything)
arr.shift();            // O(n), remove from start

// Copy/slice
const copy = arr.slice(); // Shallow copy of entire array
const part = arr.slice(2, 5); // Copy elements [2, 3, 4]
arr.splice(2, 3, 'new'); // Mutate: remove 3 elements at index 2, insert 'new'

// Search/filter
arr.indexOf(value);     // O(n) linear search
arr.includes(value);    // O(n) linear search
arr.filter(fn);         // O(n) returns new array
arr.map(fn);            // O(n) returns new array
arr.reduce(fn, init);   // O(n) accumulate

// Sort (mutates)
arr.sort((a, b) => a - b); // O(n log n) comparison sort
arr.reverse(); // O(n) mutate in place

const str = "hello";
str[0] = 'H'; // Doesn't work! Strings are immutable

// Solution: convert to array, modify, convert back
const arr = str.split('');
arr[0] = 'H';
const result = arr.join('');

function createCounter() {
  const memo = {}; // Closure: memo persists between calls

  function fib(n) {
    if (n in memo) return memo[n]; // Check memo
    if (n <= 1) return n;
    memo[n] = fib(n - 1) + fib(n - 2); // Store result
    return memo[n];
  }

  return fib; // Return the function that closes over memo
}

const fib = createCounter();
console.log(fib(10)); // Uses memoization

typeof 5;          // "number"
typeof "hello";    // "string"
typeof {};         // "object" (beware: arrays, null, objects all "object")
typeof [];         // "object"
typeof null;       // "object" (historical bug!)

Array.isArray([]);  // true
Array.isArray({});  // false

// For null checks
if (value === null) { }
if (value == null) { } // Checks null OR undefined