Interview Q&A / Data Structures & Algorithms

1. How do you check if a string of brackets is valid (balanced parentheses)?

   Scan the string with a stack. Push every opening bracket. For every closing bracket, the stack must be non-empty and its top must be the matching opening bracket, which you then pop. The string is valid only if the stack is empty at the end. O(n) time, O(n) space.

   BeginnerIn-depthCoding3 min read
2. How do you find the longest substring without repeating characters?

   Use a sliding window. Expand the right end one character at a time and remember the last index where each character was seen. If the new character already appears inside the window, move the left end just past its previous position. Track the largest window size. This is O(n) time.

   AdvancedIn-depthCoding4 min read
3. How do you check if a string is a palindrome, ignoring spaces, punctuation and case?

   Use two pointers from both ends. Skip characters that are not letters or digits, compare the rest in lowercase, and move inward. If any pair differs, it is not a palindrome.

   BeginnerQuick answerCoding1 min read
4. How do you check if one string is a rotation of another?

   They must have the same length, and the second string must appear inside the first string written twice. For example, "waterbottle" doubled contains "erbottlewat".

   BeginnerQuick answerCoding1 min read
5. How do you check whether two strings are anagrams of each other?

   Two strings are anagrams if they have the same letters with the same counts. Count the characters of the first string, subtract using the second, and check that every count ends at zero.

   BeginnerQuick answerCoding1 min read
6. How do you find the first non-repeating character in a string?

   Count how often each character appears in one pass, then scan again and return the first character whose count is 1.

   BeginnerQuick answerCoding1 min read
7. How do you find the longest common prefix among an array of strings?

   Take the first string as the candidate prefix and shorten it until every other string starts with it. Return what is left, which may be an empty string.

   BeginnerQuick answerCoding1 min read
8. How do you reverse the order of words in a sentence, ignoring extra spaces?

   Trim the string, split on one or more whitespace characters, reverse the array of words, and join with a single space.

   BeginnerQuick answerCoding1 min read
9. How do you find the longest palindromic substring in a string?

   Every palindrome has a centre. Try each index as an odd-length centre and each gap between letters as an even-length centre, expand outward while the ends match, and keep the longest.

   IntermediateQuick answerCoding1 min read
10. How do you generate all valid combinations of n pairs of parentheses?

    Build the string character by character. You may add an opening bracket while fewer than n have been used, and a closing bracket only when it would not exceed the number of openings. A string of length 2n is valid.

    IntermediateQuick answerCoding1 min read
11. How do you group anagrams together from a list of words?

    Anagrams share the same sorted letters, so use the sorted word as a hash map key and collect each word under its key. The map values are the groups.

    IntermediateQuick answerCoding1 min read