In this session, we will be covering a few string based questions. These questions are deceptively simple, but have quite a few ways to throw you off!

Strings Questions:

  1. isAnagram: Given two strings, check if they are anagrams are not.
    boolean isAnagram(String word1, String word2)
  2. FirstUniqueLetter: Given a string, print the first unique (non-repeated) letter in it.
    char firstUniqueLetter(String word)
  3. Rearrangements: Given a string, print all the rearrangements of letters, keeping the vowels together.
    void printArrangementsVowelsTogether(String word)
    Note: If the question were, keep the consonants together is that the same?
  4. Given a string that contains only series of letters a or b. Write a function to compress the sequence of strings by encoding repetitions.
    baaaaaab => ba6b (b followed by a 6 times, followed by b).
    Also write a function to decompress the string
    ba6b => baaaaaab.
  5. Given a string write a program to find the longest palindrome in a string?
    Easy: O(n2) time & O(1) space, Hard: O(n) time & O(1) space.
  6. You are given a list of words that are in MixedCaseClassNameNotation, representing all the token names in your project. Write a function that accepts the “search keyword” and returns a list of tokens that match the search keyword. Capital letters are matched different from

    Search => List
    A => [full list]
    Asp => [“AspectCloneMapperAdapter”, “AspectDecoratorFactory”]
    AspD => [“AspectDecoratorFactory”]
    AA => [“AbstractAdapterInfoPrototype”, “AnnotationAdapterComparator”]

Solution Discussion:

Q1. isAnagram:

Clarifying questions:

  • What is the character set? only letters, a-z, ascii or UTF-8?
  • Are they only lower case characters? What if capitalization:

Solution Approaches: Should take about 2 minutes to narrow down to the algorithm and 5 minutes to implement it.

Good approaches:

  • Sort both words and compare. Works, but most interviewers will forbid you from modifying the string.
  • Char counting?

Bad approaches:

  • How about using a Set? Terrible idea. Set can only tell you if a letter is there or not.

Q2. FirstUniqueLetter:

Solution approaches:

  • HashMap + Priority Queue
    • Maintained in the ordered by insertion
  •  ArrayLisT
    • Deletion of element in the queue
  •  LinkedHashMap
    • Insertion complexity is not constant
    • FindFirstUniqueLetterAtAnyPoint Query is O(n)
  • Set for counting
    • Histogram for every subject
    • Queue of unique elements
    • First element in the queue is the result
    • If the element is new, the element will not be evicted from the queue.
      • New Front of the Queue may be dirty — evict it if so.

Q3: Rearrangements:

  • Find all the arrangements among vowels
  • Use each arrangement as a chunk and find all arrangements
  • What if vowels were duplicated?
  • Why is it a bad idea to use a set? Generating all useless combinations