String Problem

https://www.interviewbit.com/courses/programming/topics/strings/ and https://leetcode.com/tag/string/ and https://github.com/mariusneo/string-interview-questions and  https://github.com/mission-peace/interview/wiki/String

  1. Check if string follows order of characters defined by a pattern or not – simple problem but what we need to keep in mind that we can use in-built python methods like `find` and `rfind` rather than writing everything from scratch.
  2. Calculate sum of all numbers present in a string – again using the build in python function.
  3. Lower case to upper case – An interesting fact . The ASCII table is constructed in such way that the binary representation of lowercase letters is almost identical of binary representation of uppercase letters. The only difference is the sixth bit, setted only for lowercase letters. What that elegant function does is unset the bit of index 5 of in[i], consequently, making that character lowercase.Example: Character ‘A’ is integer 65 = (0100 0001)2, while character ‘a’ is integer = 97 = (0110 0001)2.

    Read this.In python u can do it in a single line like –
                         chr( ord(‘z’) – 32)

  4. Check if a sentence is palindrome or not –
    Start from both end of the sentence and keep comparing each word.
     Java Code
    Good to Know –

    char[] chars = string.replaceAll(" ", "").toLowerCase().toCharArray();

    The replaceAll() method creates another copy of the string. Then, toLowerCase() creates another copy of the string. Finally, toCharArray() creates yet another copy in a character array of the resulting string. Of course, with the exception of the final result, the rest will get garbage collected. But each of the copies in an additional O(n) time.

  5.  Write a function to find the longest common prefix string amongst an array of strings.
    1. Word by Word Matching   
    2. Character by Character Matching
    3. Divide and Conquer 
    4. Binary Search
  6. Length of last word – Code
    Just start from the end.

Easy Section – 

  1. Given two binary strings, return their sum (also a binary string). Code
  2. Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.  Code
  3. Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.Example:
    Input: s = “abcdefg”, k = 2
    Output: “bacdfeg”Code
  4. Given a word, you need to judge whether the usage of capitals in it is right or not.
    We define the usage of capitals in a word to be right when one of the following cases holds:
    All letters in this word are capitals, like “USA”.
    All letters in this word are not capitals, like “leetcode”.
    Only the first letter in this word is capital if it has more than one letter, like “Google”.
    Otherwise, we define that this word doesn’t use capitals in a right way.
    One way is to count the total of capital and small letters.
    If capital == length, fine.
    If only 1 capital, and only first character is capital fine. Else False.
    If  small == length, then fine.
    Other way is the logic here.
  5. Converting Roman Numerals to Decimal lying between 1 to 3999
    Split the Roman Numeral string into Roman Symbols (character).
    Convert each  symbol of Roman Numerals into the value it represents.
    Take symbol one by one from starting from index 0:

    • If current value of symbol is greater than or equal to the value of next symbol, then add this value to the running total.
    • else subtract this value by adding the value of next symbol to the running total.
  6. Write a function to find the longest common prefix string amongst an array of strings.
  7. Write a function to find the longest common prefix string amongst an array of strings. – KMP ALGO
  8. Write a function to find the longest common prefix string amongst an array of strings.
  9. Check valid parentheses in a string. – also a stack question
  10. Reverse words in a given string – StackOverfFlow
    string[] words =  "This is interview question".split(" ");
    string rev = "";
    for(int i = words.length - 1; i >= 0 ; i--)
    {
       rev += words[i] + " ";
    }
    // rev = "question interview is This "
    
    // can also use StringBuilder:
    StringBuilder revb = new StringBuilder;
    for(int i = words.length - 1; i >= 0 ; i--)
    {
       revb.Append(words[i]);
       revb.Append(" ");
    }
    // revb.toString() = "question interview is This "
  11. Run length encoding. Interesting Read on Wiki.
  12. Unique Word Abbreviation. An abbreviation of a word follows the form . Below are some examples of word abbreviations: …..
    Code . Code. Here it’s important to note that the same word may appear twice in the dict.
    There are only 2 conditions we return true for isUnique(“word”)
    1. The abbr does not appear in the dict.
    2. The abbr is in the dict && the word appears one and only once in the dict.
  13. Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases
  14. Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
    One way we can think of is to use the number at front. e.g. abcdef, we can store 6abcdef.  However, what if the string also starts from numbers, e.g. 123abc. In this case, what we stored is 6123abc, which is wrong. Therefore, we need to use another divider to divide the length of the string with the string itself. In this solution, we just use ‘#’.
  15. Design a algorithm to point all permutation of a string, assume all the character are unique same as C11_4
  16. Write a method to transfrom a string to int.
  17. Recursive function to do substring search
  18. Longest Common Prefix | Set 4 (Binary Search) Given a set of strings, find the longest common prefix. GFGGFG
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s