Arrays, Strings & Hashing

Arrays, strings, and hashing turn up in every Cisco coding round, and they take up more of the loop than any other cluster. When a screen gives you one medium problem, this is the bucket it most often comes from. When the online assessment pairs a couple of coding tasks with its block of fundamentals questions, the coding half usually lives here too. Learn to move quickly and cleanly through this material and you have covered the largest slice of what the loop actually asks.

The good news is that the bar is honest and reachable. These problems sit in the easy-to-medium band, the grade goes to a correct, tested solution, and a flash of insight is beside the point, and Cisco tends to let you run your code. Two ideas carry almost everything here. The first is hashing: a dictionary that answers "have I seen this, and where" in constant time, which collapses a nested-loop scan into a single pass. The second is that a string is just an array of characters you walk with pointers or a window. Once those two habits are automatic, most of this cluster is pattern recognition.

The Cisco angle

The forgiving medium bar is a real feature of this loop, and it changes how you should spend the interview. Cisco is not running a FAANG-style gauntlet where only the elegant one-liner survives. Reports keep saying the DSA is less brutal than candidates brace for, and that partial credit is real. A working solution that handles the corners beats a clever fragment that misreads an edge. So get a correct version on the board first, name its time and space cost without being asked, then reach for the optimization. A calm, tested solution is exactly the signal a company hiring people to maintain systems for years is listening for.

Why this cluster carries the loop

Two forces put this cluster on top. The first is simple volume: across the problems Cisco is known to reach for, arrays outnumber every other tag, with strings and hash usage close behind. Longest Palindromic Substring shows up as the single most recurring string problem, and the matrix-walk family (rotate, spiral, traverse) recurs too. Interval merges and top-K-by-frequency counts recur, and so do deduplication and the plain reverse-and-parse tasks. If you get to drill only one area, this is the rational bet.

The second force is that hashing quietly powers the rest. A frequency map is a hash map. Grouping anagrams is a hash map keyed on a signature. Deduplicating device names is a hash map remembering what it has seen. Even the sliding window leans on a map to track what sits inside the current span. Master the dictionary and you have not learned one trick. You have learned the tool that half of these problems are secretly built on.

• Hash map: Membership and pairing in O(1). Two Sum, plus seen-before and deduplication checks, all rest on asking "is this value here, and where" in constant time. The dictionary is the single most useful data structure in this cluster.
• Frequency map: Counting and grouping. Group Anagrams and Top K Frequent, plus majority-element questions, all reduce to tallying occurrences, then reading the tally. A counter turns "how many of each" into one pass.
• Two pointers: Scanning ends or a center. Palindromes expand outward from a center, sorted-pair searches close in from both ends, and in-place reversals swap toward the middle. One index in, one index out.
• Sliding window: A Premium question. Longest substring without a repeat, smallest window covering a target, longest run under a constraint: grow the window on the right, shrink it on the left, track the best.

The toolkit

Four templates cover almost everything in this cluster. Drill each until the skeleton runs on autopilot, because when your fingers know the shape, your head is free for the wrinkle the problem wraps around it. Each template below maps straight onto one of the practice problems that follow.

A hash map for O(1) lookup

The most common upgrade in this whole cluster is trading a nested loop for a dictionary. Whenever a brute force says "for each element, scan the rest to find its partner," a hash map remembers what you have already passed so the partner is one constant-time question away. You go from O(n squared) to O(n) by spending a little memory. This is the Two Sum move. Once you see it, you will spot it everywhere.

def two_sum(nums, target):        # the archetypal O(1)-lookup problem
    seen = {}                     # value -> the index we saw it at
    for i, x in enumerate(nums):
        need = target - x         # the partner that would complete the pair
        if need in seen:          # O(1) membership check, the whole point
            return [seen[need], i]
        seen[x] = i               # record this value before moving on
    return []

Record the value only after you check for its partner, so a single element never pairs with itself. The same skeleton answers a family of questions: swap the dictionary for a set when you only need "have I seen this," and you have deduplication and cycle-of-values checks for free.

A frequency map for counting

When the question is about how often things occur, tally first and answer second. A frequency map counts every item in one pass, and then grouping, most-frequent, and "do these two match" questions are a short step away. Python hands you a counter, but building one by hand is three lines. Know it cold.

def frequency_map(items):
    counts = {}                   # item -> how many times it appears
    for x in items:
        counts[x] = counts.get(x, 0) + 1
    return counts
# top-k by frequency once the tally exists:
# sorted(counts, key=counts.get, reverse=True)[:k]
# a shared signature groups items: sorted(word) keys all its anagrams

Two strings are anagrams exactly when their letter tallies match. Any canonical fingerprint of the tally, the sorted string or a 26-slot count, becomes a dictionary key that collects every anagram under it. That is the whole engine behind Group Anagrams.

Two pointers

Two pointers come in two flavors, and both matter here. On a sorted array you walk one index up from the left and one down from the right, closing in until they meet. For palindromes you do the opposite: start at a center and widen two indices outward while the characters on each side match. Either way you get a linear scan. No extra memory needed.

def is_palindrome(s):             # opposite-ends two pointers
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
def widest_around(s, left, right):   # center-out two pointers
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1                    # widen while both ends still match
        right += 1
    return s[left + 1:right]          # step back to the last matching pair

The center-out version is the key to Longest Palindromic Substring. Every palindrome has a center: a single character for odd lengths, or a gap between two characters for even lengths. Try every center and expand from each, and you find the longest one in a clean quadratic scan.

A sliding window

A sliding window is the tool for "the best contiguous stretch that obeys a rule." Grow the window by advancing the right edge one step at a time, and when the rule breaks, pull the left edge forward until it holds again. A map tracks what currently sits inside the window so the shrink knows how far to move. Every index enters and leaves at most once, so the whole scan is linear.

def longest_clean_run(s):         # longest span with no repeated character
    last = {}                     # char -> the last index we saw it at
    left = 0                      # left edge of the current window
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1   # jump the left edge past the earlier copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

The Cisco angle

Reach for a dictionary by reflex, because hashing here is exactly how the network itself finds things. A switch does not scan a list to decide where a frame goes; it hashes the destination address into a MAC table and reads the answer in one lookup. ARP caches and flow tables lean on the same constant-time lookup you are building on the whiteboard, and so do routing structures. So when you replace a nested scan with a hash map, you are reaching for the exact instinct the systems Cisco ships are built around. Say it out loud: "I will keep a map so the lookup is O(1), the way a forwarding table does." That shows you know why the tool exists as well as how to type it.

Asked at Cisco

Four problems, one per template. Two Sum is the hash-map lookup in its purest form. Group Anagrams keys a dictionary on a frequency signature. Longest Palindromic Substring expands two pointers out from every center. Longest Substring Without Repeating Characters slides a window and remembers the last place it saw each character. Build each base version, clear the corners, then let the walkthrough carry the follow-up Cisco tends to bolt on.

The Cisco angle

Read the string problems as parsing problems, because that framing is the day job at a networking company. A config file, a routing-table dump, a packet header, an IP address written as text: an engineer here spends real time slicing strings into meaningful fields, then checking and normalizing them. Longest Palindromic Substring is a scan-and-compare over characters. Group Anagrams normalizes tokens to a canonical form so equivalent ones collapse together. Both use the muscle you'd use to parse a line of configuration into structure. When a string problem shows up, treat it as the parsing task it resembles, and the careful, corner-aware handling that reads as competence comes naturally.

1

The Complement Lookup: Two Sum

EasyCommonly asked

Problem

You're given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.

Return the two indices in any order. This is the classic Two Sum, the problem most often used to check whether you reach for a hash map instead of a nested loop.

Input: nums = [2,7,11,15], target = 9

Output: [0, 1]

nums[0] + nums[1] = 2 + 7 = 9, so the answer is the pair of indices 0 and 1.

Input: nums = [3,2,4], target = 6

Output: [1, 2]

nums[1] + nums[2] = 2 + 4 = 6. The pair 3 + 3 is not available because there is only one 3.

Input: nums = [3,3], target = 6

Output: [0, 1]

The two separate 3s at indices 0 and 1 sum to 6. Two copies of the same value at different indices are allowed.

How this uses the pattern

This is the hash-map lookup. Walk the array once, and for each value compute the complement target minus value. If the complement is already in your map, you have the pair; otherwise record the current value with its index and move on.

The Complement Lookup: Two Sum

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[2,7,11,15],9]Expected: [0, 1]

Input: [[3,2,4],6]Expected: [1, 2]

Input: [[3,3],6]Expected: [0, 1]

Input: [[-1,-2,-3,-4,-5],-8]Expected: [2, 4]

Input: [[0,4,3,0],0]Expected: [0, 3]

Need a hint? (3 available)

The Cisco angle

Two Sum is the purest test of the single reflex this whole cluster rewards: seeing a nested scan and replacing it with a dictionary. The brute force pairs every element with every other for O(n squared). The hash map remembers what it has passed, so the partner is one constant-time question away. That drops it to O(n). The tell interviewers watch for is whether you record each value after checking for its complement rather than before, which is what stops a lone element from pairing with itself. Get the one-pass version out cleanly and you have shown the instinct the rest of the cluster keeps asking for.

Take it further

Suppose the array arrives already sorted and the interviewer wants it solved in O(1) extra space, no hash map allowed. Switch to opposite-ends two pointers. Start one index at the front and one at the back. The sorted order tells you which way to step: move the front up when the sum is too small, the back down when it's too big. It is the same pairing idea with a pointer walk instead of a dictionary.

Show solution & walkthrough

2

Bucketing by Signature: Group Anagrams

MediumSometimes asked

Problem

You're given an array of strings strs. Group together the strings that are anagrams of one another, meaning each uses the same letters the same number of times, just in a different order. Return the groups.

The groups may be returned in any order, and the strings within a group may be in any order. This is the classic Group Anagrams, a frequency-signature grouping problem.

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["ate","eat","tea"],["bat"],["nat","tan"]]

eat, tea, and ate share the letters a-e-t; tan and nat share a-n-t; bat stands alone. Three groups.

Input: strs = ["cat","act","dog","god","tac"]

Output: [["act","cat","tac"],["dog","god"]]

cat, act, and tac are all the letters a-c-t; dog and god share d-g-o. Two groups.

Input: strs = [""]

Output: [[""]]

A single empty string forms one group by itself.

How this uses the pattern

This is a frequency-map grouping. Give every string a canonical signature that all its anagrams share (the sorted letters work), and use that signature as a dictionary key. Every string lands in the bucket for its signature, and the buckets are the groups.

Bucketing by Signature: Group Anagrams

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [["eat","tea","tan","ate","nat","bat"]]Expected: [["ate","eat","tea"],["bat"],["nat","tan"]]

Input: [["cat","act","dog","god","tac"]]Expected: [["act","cat","tac"],["dog","god"]]

Input: [["abc","bca","cab","xyz","zyx"]]Expected: [["abc","bca","cab"],["xyz","zyx"]]

Input: [[""]]Expected: [[""]]

Input: [["a"]]Expected: [["a"]]

Need a hint? (3 available)

The Cisco angle

Group Anagrams is the frequency-signature idea in the open: two strings belong together exactly when their letter tallies match, so you need a canonical form that collapses every anagram onto one key. Sorting a string's letters is the quickest such form to reach for, and the dictionary does the rest, one bucket per signature. Fluency here means seeing that "same letters" means "same key." You never compare strings to each other at all; you drop each into the bucket its signature names. It is the normalize-then-group shape behind deduping identifiers and folding equivalent tokens together.

Take it further

The strings can be long, and sorting each one to build its key costs a log factor per string. Drop it: instead of the sorted string, use a 26-slot count of each letter as the key, which is built in one linear pass over the word. The grouping is identical, but the per-string key work falls from sorting to counting, which matters when the words are long and the alphabet is small and fixed.

Show solution & walkthrough

3

Reading a Field Both Ways: Longest Palindromic Substring

MediumSignature problem

Problem

You're given a string s. Return the longest contiguous substring of s that reads the same forward and backward. If several substrings tie for the longest, returning any one of them is fine.

This is Longest Palindromic Substring, the string problem that recurs most often in a Cisco loop. A single character counts as a palindrome, so the answer is never empty for a non-empty input.

Input: s = "babad"

Output: "bab"

Both "bab" and "aba" are valid longest palindromes of length 3; returning either is accepted.

Input: s = "cbbd"

Output: "bb"

The even-length center between the two b's expands to "bb", the longest palindrome here.

Input: s = "a"

Output: "a"

A single character is a palindrome of length 1.

How this uses the pattern

This is center-out two pointers. Every palindrome has a center, one character for odd lengths or a gap between two for even lengths. Try all 2n-1 centers, expand outward while both sides match, and keep the longest span you find.

Reading a Field Both Ways: Longest Palindromic Substring

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: ["babad"]Expected: "bab"

Input: ["cbbd"]Expected: "bb"

Input: ["a"]Expected: "a"

Input: ["ac"]Expected: "a"

Input: ["racecar"]Expected: "racecar"

Input: ["forgeeksskeegfor"]Expected: "geeksskeeg"

Need a hint? (3 available)

The Cisco angle

Longest Palindromic Substring is the string problem Cisco reaches for most, and the clean solution is the expand-around-center two-pointer walk rather than anything exotic. A palindrome is defined by its center, so you don't search substrings. You grow outward from each of the 2n-1 possible centers and let the matching characters tell you how far the palindrome reaches. The one wrinkle worth naming out loud is handling even-length palindromes, which sit between two characters, alongside the odd-length ones centered on a single character. Miss the even case and half the answers slip through.

Take it further

Instead of the longest palindrome, count how many palindromic substrings s contains in total, where different start or end positions count as different substrings. The expand step is doing the counting already: every time the two pointers widen and still match, that is one more palindrome centered there. So keep the same 2n-1 centers, and instead of tracking the widest span, add one to a running total on each successful expansion.

Show solution & walkthrough

4

The Longest Clean Window: Longest Substring Without Repeating Characters

MediumCommonly asked

Problem

You're given a string s. Return the length of the longest contiguous substring that contains no repeated character.

This is Longest Substring Without Repeating Characters, the canonical sliding-window problem. The substring must be contiguous, so it is a window over s, not an arbitrary subsequence.

Input: s = "abcabcbb"

Output: 3

The longest clean window is "abc", of length 3. Every longer window repeats a character.

Input: s = "bbbbb"

Output: 1

Every character is the same, so the longest window without a repeat is a single "b".

Input: s = "pwwkew"

Output: 3

The window "wke" has length 3. Note "pwke" is not contiguous, so it does not count.

How this uses the pattern

This is a sliding window with a last-seen map. Advance the right edge one character at a time; when the new character repeats one already inside the window, jump the left edge just past that earlier copy. Track the widest window along the way.

The Longest Clean Window: Longest Substring Without Repeating Characters

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: ["abcabcbb"]Expected: 3

Input: ["bbbbb"]Expected: 1

Input: ["pwwkew"]Expected: 3

Input: [""]Expected: 0

Input: ["dvdf"]Expected: 3

Input: ["abba"]Expected: 2

Need a hint? (3 available)

The Cisco angle

Longest Substring Without Repeating Characters is the sliding window in its textbook form, and the clean version leans on a map from each character to the last index it appeared. Growing the right edge is easy. The hard part is how far to jump the left edge when a repeat appears: just past the earlier copy of the repeated character. The corner that separates a correct solution from a nearly-correct one is guarding that jump so a stale index from outside the current window never drags the left edge backward. Get that guard right and the scan stays linear and honest.

Take it further

Generalize the rule: return the length of the longest substring that contains at most k distinct characters, for a given k. The window structure is unchanged, but the shrink condition moves from "no character repeats" to "no more than k distinct characters are inside." Keep a count of each character in the window, and pull the left edge forward while the number of distinct characters exceeds k. The original problem is essentially the case where every character in the window must be distinct.

Show solution & walkthrough

The Cisco angle

Step back and the four problems collapse into a single habit: read the shape, then reach for the matching template. A pairing search is a hash lookup. A grouping-by-sameness is a frequency signature keyed into a dictionary. A symmetry question is two pointers growing from a center. A best-contiguous-run question is a sliding window. None of that is memorization for its own sake. It is the same set of moves the systems here run on, from the forwarding table that hashes an address to the parsing that turns a config line into structure. The bar rewards a clean, tested first pass over a fragile trick. Name the template, write it carefully, then state its cost, and you clear this cluster comfortably.