Hashing

- Fundamentals -

First Non-Repeating Char

1. Given a string 's', Design an algorithm that return the first character that appears only once in the string when reading from left to right.

If no such character exists, the algo should return '-1'.

  • parameters - (String s)
  • output - index or -1 as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String "aabcd" "aabbccddeeff" "aaaaaa"
Output 2 (index of 'b') -1 (all characters repeat) -1 (all same letters)
Explanation The first non-repeating character is 'b' at index 2. Every character repeats, so there is no unique character. All characters are the same, so there is no unique character.

All Pair Sum

2. Given an array of integers 'A', Design an algorithm that returns all unique pairs in array whose sum equals target.

If no valid pairs exist, return an empty list [].

  • parameters - (integer array A), (target t)
  • output - pairs as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String [1, 2, 3, 4], 5 [1, 1, 1, 1, 1, 1, 1, 1], 2 [], 5
Output [[1, 4], [2, 3]] [[1, 1]] []
Explanation Two distinct pairs (1+4 and 2+3) add up to 5. Many duplicate numbers, but only one unique pair (1+1). No elements in the array, so no pairs exist.

Group Anagrams

3. Given an array of strings, Design an algorithm that groups all anagrams together.

Two words are anagrams if they contain the same characters in the same frequency, but in any order.

The algo should return a list of lists where each sublist contains anagrams.

  • parameters - (Array of strings)
  • output - list of lists as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String ["bat", "tab", "cat"] ["aaaaaaaaaa", "aaaaaaaabc", "bcaaaaaaa", "cbaaaaaaa"] ["", "", ""] (empty strings)
Output [["bat", "tab"], ["cat"]] [["aaaaaaaaaa"], ["aaaaaaaabc"], ["bcaaaaaaa"], ["cbaaaaaaa"]] [["", "", ""]]
Explanation The words quickly form small groups, leading to a fast execution. All words have almost identical character distributions, requiring deeper comparison. The function must handle empty strings gracefully without errors.

Substring without repeats

4. Given a string 's', Design an algorithm that returns the longest contiguous substring that does not contain duplicate characters.

  • parameters - (String s)
  • output - Substring as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Input String "abcdef" "aaaaaaa" "" (empty string) or "a" (single character)
Output "abcdef" "a" "" (for empty input) or "a" (single character)
Explanation No duplicate characters → entire string is the result. All characters are the same → longest substring is a single character. Handles edge cases: empty string, single character, string with only unique chars.

Design HashMap

5. Design a hash map (dictionary-like data structure) that allows users to store key-value pairs efficiently.

    The implementation must include the following functionalities:

  • insert (put) : Adds a key-value pair, replacing existing values if the key already exsits.
  • retrieve (get): Returns the value for a given key, or '-1' if the key is not present.
  • delete (remove): Removes a key-value pair if it exists.

The put, get, and remove operations should run in average-case O(1) time complexity.

The implementation should efficiently handle hash collisions using chaining (linked lists) or open addressing (probing techniques). and support dynamic resizing when the load factor crosses a threshold.

Parameter \ Case Best Case Worst Case Edge Case
Parameters Small number of unique keys Large number of keys, many collisions Empty hash map, key does not exist
Output Fast O(1) insert/retrieve/delete High collision rate leads to O(N) retrieval Returns -1 when key is missing
Explanation Minimal collisions, direct access Many keys map to the same index, requiring linked list traversal or probing Ensures correctness for missing keys

Isomorphic Strings

6. Design an algorithm that returns '1' if given two strings 's' and 't' are isomorphic else return '0'.

Two strings are isomorphic if each character in the first string can be mapped uniquely to a character in the second string while preserving the order.

  • Each character from string 1 must map to exactly one character in string 2.
  • No two characters in string 1 should map to the same character in string 2.
  • The length of both strings must be same.
  • parameters - (String s), (String t)
  • output - 1 or 0 as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Parameters "abc", "xyz" "aaaa", "bcda" "a", "b"
Output 1 0 1
Explanation Every character has a unique mapping. 'a' maps to different characters ('a' → 'b', 'a' → 'c'). Single-character strings are always isomorphic.

- Intermediate Problems -

Longest Sequence

1. Design an algorithm that returns the longest sequence of consecutive numbers in increasing order that occur in a unsorted array of integers.

  • A consecutive sequence consists of numbers that appear in sequence (e.g. [1,2,3,4], [10,11,12,13])
  • The numbers in the array may not be distinct (Duplicates should be ignored)
  • The sequence does not have to be contiguous in the array
  • In case of multiple sequences with same longest length, return the one that starts with the smallest number
  • parameters - (Integer Array A)
  • output - sequence as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Parameters [1,2,3,4,5,6] [100, 4, 200, 1, 3, 2, 101, 102, 103, 104] [1,1,1,1], [10,9,8,7,6,5,4,3,2,1]
Output [1,2,3,4,5,6] [1,2,3,4] (or any valid sequence) [1], [1,2,3,4,5,6,7,8,9,10]
Explanation The array is already sorted in increasing order, so the longest sequence is obvious. The numbers are randomly placed, requiring extra work to find [1,2,3,4]. A case with all identical numbers OR a fully descending order where the longest sequence is 1.

Substring with chars

2. Given two strings 's' and 'p', Design an algorithm that returns the shortest contiguous substring of 's' that contains all characters of p with their exact frequency.

If no such substring exists, return an empty string.

If multiple substrings of same length exist, return the leftmost one.

  • parameters - (String s), (String p)
  • output - Substring as per above problem statement
Parameter \ Case Best Case Worst Case Edge Case
Parameters s = "abcdefgh", p = "abc" s = "aaaaaaaabcaaaaaa", p = "abc" s = "abc", p = "abcd"
Output "abc" "abc" "" (empty string)
Explanation The first three characters already contain all of p, so the substring is found instantly. The required substring appears near the middle, meaning the entire string must be searched. Since p contains a character not in s, it's impossible to find a valid substring.