Lesson 2: Programs 6-10: Sequences, Anagrams and Counting

How to use this lesson. Read the question and try it yourself for ten minutes before you read the approach. In a real interview, say your idea out loud, mention the edge cases (empty input, one item, duplicates, negative numbers), then code, then test with an example.

Problem 6: Fibonacci Numbers

Question. Return the n-th Fibonacci number, where F(0)=0, F(1)=1 and each next number is the sum of the previous two.

Examples.

• n = 10 → 55
• n = 0 → 0

Approach. The naive recursive version recomputes the same values again and again and takes exponential time. Keep just the last two numbers in a loop, or cache results in a Map (memoization).

function fib(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

function fibMemo(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, value);
  return value;
}

console.log(Array.from({ length: 11 }, (_, i) => fib(i)));
console.log(fib(50), fibMemo(50), fib(78));

Output:

[
   0, 1,  1,  2,  3,
   5, 8, 13, 21, 34,
  55
]
12586269025 12586269025 8944394323791464

Complexity. The loop is O(n) time and O(1) space. The memoized version is O(n) time and O(n) space.

Follow-up an interviewer may ask. Can you do better than O(n)? (Matrix exponentiation or fast doubling gives O(log n).) And what happens after F(78)? (Numbers pass the safe integer limit; use BigInt.)

Problem 7: Check for Anagrams

Question. Two words are anagrams if they contain the same letters in a different order. Return true if so, ignoring case.

Examples.

• "listen", "silent" → true
• "abc", "abd" → false

Approach. If the lengths differ they cannot be anagrams. Otherwise compare the sorted letters (O(n log n)), or count letters in an object or Map (O(n)): add one for each letter of the first word and subtract one for each letter of the second; every count must end at zero.

function isAnagram(a, b) {
  a = a.toLowerCase();
  b = b.toLowerCase();
  if (a.length !== b.length) return false;
  const counts = new Map();
  for (const ch of a) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (const ch of b) {
    if (!counts.get(ch)) return false;
    counts.set(ch, counts.get(ch) - 1);
  }
  return true;
}

const isAnagramSorted = (a, b) => [...a.toLowerCase()].sort().join("") === [...b.toLowerCase()].sort().join("");

for (const [x, y] of [["listen", "silent"], ["Hello", "Olelh"], ["abc", "abd"], ["aab", "abb"], ["", ""]]) {
  console.log(JSON.stringify(x), JSON.stringify(y), isAnagram(x, y), isAnagramSorted(x, y));
}

Output:

"listen" "silent" true true
"Hello" "Olelh" true true
"abc" "abd" false false
"aab" "abb" false false
"" "" true true

Complexity. Counting is O(n) time and O(k) space (k = number of distinct letters). Sorting is O(n log n).

Follow-up an interviewer may ask. How would you group a list of words into anagram families? (Use the sorted letters as a Map key.)

Problem 8: Count Character Frequency

Question. Return how many times each character appears in a string.

Examples.

• "mississippi" → { m: 1, i: 4, s: 4, p: 2 }

Approach. Walk through the string once, adding one to an entry for each character. A Map keeps insertion order and works for any key; a plain object also works for characters. reduce gives a compact version.

function charFrequency(s) {
  const counts = {};
  for (const ch of s) counts[ch] = (counts[ch] || 0) + 1;
  return counts;
}

console.log(charFrequency("mississippi"));
console.log(charFrequency(""));
const counts = [..."mississippi"].reduce((m, ch) => m.set(ch, (m.get(ch) ?? 0) + 1), new Map());
console.log(counts);
console.log([...counts].sort((a, b) => b[1] - a[1])[0]);

Output:

{ m: 1, i: 4, s: 4, p: 2 }
{}
Map(4) { 'm' => 1, 'i' => 4, 's' => 4, 'p' => 2 }
[ 'i', 4 ]

Complexity. O(n) time, O(k) space for k distinct characters.

Follow-up an interviewer may ask. How would you find the most frequent character? (Sort the entries by count, or track the maximum while counting.)

Problem 9: First Non-Repeating Character

Question. Return the first character in a string that appears only once, or null if there is none.

Examples.

• "swiss" → "w"
• "aabb" → null

Approach. Two passes: first count every character, then scan the string again in order and return the first whose count is 1. Scanning the original string (not the Map) is what keeps the order right.

function firstUnique(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) ?? 0) + 1);
  for (const ch of s) {
    if (counts.get(ch) === 1) return ch;
  }
  return null;
}

for (const text of ["swiss", "aabb", "leetcode", "", "z"]) {
  console.log(JSON.stringify(text), "->", firstUnique(text));
}

Output:

"swiss" -> w
"aabb" -> null
"leetcode" -> l
"" -> null
"z" -> z

Complexity. O(n) time, O(k) space.

Follow-up an interviewer may ask. What if the text is a stream and you cannot read it twice? (Keep the counts plus an ordered structure of the characters seen once.)

Problem 10: Remove Duplicates and Keep the Order

Question. Return an array with the repeated items removed, keeping the first occurrence of each in the original order.

Examples.

• [3, 1, 3, 2, 1] → [3, 1, 2]

Approach. A Set remembers what you have seen. In fact [...new Set(items)] already keeps the first occurrences in order, because a Set preserves insertion order. For objects, remember a key (such as an id) instead of the object itself.

function uniqueInOrder(items) {
  const seen = new Set();
  const result = [];
  for (const item of items) {
    if (!seen.has(item)) {
      seen.add(item);
      result.push(item);
    }
  }
  return result;
}

console.log(uniqueInOrder([3, 1, 3, 2, 1]));
console.log(uniqueInOrder([..."banana"]));
console.log(uniqueInOrder([]));
console.log([...new Set([3, 1, 3, 2, 1])]);
const users = [{ id: 1, n: "a" }, { id: 2, n: "b" }, { id: 1, n: "c" }];
console.log([...new Map(users.map((u) => [u.id, u])).values()].map((u) => u.n));

Output:

[ 3, 1, 2 ]
[ 'b', 'a', 'n' ]
[]
[ 3, 1, 2 ]
[ 'c', 'b' ]

Complexity. O(n) time, O(n) space.

Follow-up an interviewer may ask. How do you remove duplicate objects by a field? (Key a Map by that field: the last duplicate wins; check has first to keep the first.)