Strings
String problems are main topics in interview and for interview purpose you must have idea about few known algorithm for search/matching pattern, string reverse and other basic problems.
Here are the few links which can guide you on this area :
Advanced String Searching Boyer-Moore-Horspool Algorithms : https://www.youtube.com/watch?v=QDZpzctPf10 String problems with solutions http://www.geeksforgeeks.org/category/c-strings/
Problem 1:
|
/// <summary> /// Determine if a string has all unique characters. /// </summary>
public static bool IsUniqueCharacter(string str) { bool[] uniqueChar = new bool[256]; for (int i=0; i < str.Length; i++) { int charValue = (int) str[i]; if (uniqueChar[charValue]) return false; uniqueChar[charValue] = true; } return true; }
|
Problem 2
|
/// <summary> /// Reverse a string /// </summary> /// <param name="str"></param> /// <returns></returns> public static string ReverseString(string str) { var newStr = str.ToCharArray(); for (int i = 0; i < newStr.Length / 2; i++) { char temp = newStr[i]; newStr[i] = newStr[newStr.Length - i - 1]; newStr[newStr.Length - i - 1] = temp; //Other Solution using XOR bit operator /* newStr[i] ^= newStr[newStr.Length - i - 1]; newStr[newStr.Length - i - 1] ^= newStr[i]; newStr[i] ^= newStr[newStr.Length - i - 1]; */ } return new string(newStr); }
|
Problem 3
|
/// <summary> /// Given two strings. Write a method to decide if one is permutation (Anagram) of others /// 1- Please check with interviewer if anagram comparison is case sensitive i.e. is "God" an anagram of "dog" ? /// 2- Simple Solution : Sort both string and compare. (This is not optimal solution) /// 3- Best Solution : Count how many times each character appears, then compare two arrays. /// </summary> /// <param name="str1"></param> /// <param name="str2"></param> /// <returns></returns> public static bool IsAnagram(string str1, string str2) { if (str1.Length != str2.Length) return false; int[] letters = new int[256]; for (int i = 0; i < str1.Length; i++) { int charValue = (int)str1[i]; letters[charValue]++; } for (int i = 0; i < str2.Length; i++) { int charValue = (int)str2[i]; if (--letters[charValue] < 0) return false; } return true; }
|
Problem 4 :
|
/// <summary> /// Implement a method to perform basic string compression using the counts of repeated characters. /// for ex: the string aabcccccaaa would become a2b1c5a3. /// if the compressed string would not become smaller than the original string, method should return original string. /// </summary> /// <param name="str"></param> /// <returns></returns> public static string Encrypt(string str) { char key = str[0]; int count = 1; StringBuilder builder = new StringBuilder(); for (int i = 1; i < str.Length; i++) { if (str[i] == key) { count++; } else { builder.Append(key.ToString() + count.ToString()); key = str[i]; count = 1; } } builder.Append(key.ToString() + count); // if compressed string larger than the original return original if (builder.ToString().Length > str.Length) return str; return builder.ToString(); }
|
Problem 5:
|
/// <summary> /// Remove duplicates characters from string /// </summary> /// <param name="input"></param> /// <returns></returns> public static string RemoveDuplicates(string input) { char[] str = input.ToCharArray(); if (string.IsNullOrEmpty(input)) return string.Empty; if (input.Length < 2) return input; int tail = 1; // number of unique char in the array // start at 2nd char and go till the end of the array. for (int i = 1; i < str.Length; i++) { int j; // for every char in outer loop check if that char is already seen. for (j = 0; j < tail; j++) { if (str[i] == str[j]) break; // break if we find duplicate. } // if j reachs tail..we did not break, which implies this char at pos i // is not a duplicate. So we need to add it our "unique char list" // we add it to the end, that is at pos tail. if (j == tail) { str[tail] = str[i]; tail++; } } return new string(str).Substring(0,tail); // Get only tail count character from string. }
|
Problem 6
|
/// <summary> /// Boyer Moore Algorithm to search a pattern in string /// </summary> public static void SearchString() { string text = "WE HOLD THESE TRUTHS TO BE SELF-EVIDENT"; string pattern = "TRUTH"; int _defaultValue = pattern.Length; var _distnaces = new Dictionary<char, int>(); // Create bad match Table for (int i = 0; i < pattern.Length - 1; i++) { if (_distnaces.ContainsKey(pattern[i])) { _distnaces[pattern[i]] = pattern.Length - i - 1; } else { _distnaces.Add(pattern[i], pattern.Length - i - 1); } } int k = pattern.Length - 1; int j = 1; int currentPosition = _defaultValue - j; while (j <= pattern.Length && currentPosition <= text.Length - Pattern.Length) { // Match last character, if found then match second last and so on if (pattern[_defaultValue - j] == text[k]) { k--; j++; } else { // if mismatch then check if charcater exist in Table then get shift value otherwise shift by pattern length int shiftValue = pattern.Length; if (_distnaces.ContainsKey(text[k])) { shiftValue = _distnaces[text[k]]; } k = currentPosition + shiftValue; currentPosition = k; j = 1; } } if(j == pattern.Length + 1) Console.WriteLine("Matched"); else Console.WriteLine("Not Matched"); }
|
Problem 7
|
/// <summary> /// You are given a string. You have to eliminate the pairs (two same chars adjacent to each other). /// eg. input string RGBBGBGR –> RGGBGR–> RBGR (output) /// </summary> /// <returns></returns> public static void RemoveAdjacentPair() { var str = "RGBBGBGR".ToCharArray(); int i, j=0; for (i = 1; i < str.Length; i++) { while ((str[i] == str[j]) && j >= 0) { i++; j--; } str[++j] = str[i]; } var newStr = new string(str).Substring(0, j+1); Console.WriteLine(newStr); }
|
Problem 8
|
/// <summary> /// The worst case complexity of Naive algorithm is O(m(n-m+1)) or O(mn) /// Best Case O(n) if value does not exists or O(m) if value exists. /// Brute Force Search Algo /// </summary> public static void PatternSearchNaive() { string text = "THIS IS A TEST TEXT"; string pattern = "TEST"; int textLength = text.Length; int patLength = pattern.Length; int j; for (int i = 0; i <= textLength - patLength; i++) { for (j = 0; j < patLength; j++) { if (text[i + j] != pattern[j]) break; } if (j == patLength) { Console.WriteLine("Pattern Found at Index {0}", i); } } }
|
/// <summary> /// /// </summary> /// <param name="args"></param> private static void ReverseString(string[] args) { string strSupplied = "how are you"; string strWord = null; string strResult = null; for (int i = strSupplied.Length - 1; i >= 0; i--) { if (strSupplied[i].ToString() != " ") strWord = strSupplied[i] + strWord; else { strResult = strResult + " " + strWord; strWord = ""; } } strResult = strResult + " " + strWord; Console.Write(strResult.ToString()); Console.ReadKey(); }
|
No comments:
Post a Comment