String are set of characters stored together at consecutive memory locations.
Let us now look at some basic knowledge you should have about arrays and strings.
Let us start with a question.
1) Implement an algorithm to determine if a string has all uniques characters. What if you cannot use additional data structures ?
A) We need to identify if a character is repeated or not. How would you say that the below string has repeated characters
"Hello how are you"
You remember in your mind that there are letters 'l', 'o' and 'e', while reading rest of the string you check if it is among the letters you already read. You need to tell the computer to do the same thing in a code.
To remember a character's occurrence in most efficient way, we create an array of 256 integers elements and initialize them to 0. While traversing or reading the string we increment the value at the ascii value of a character. For example when we see the letter 'l' which has an ascii value of 108 we increment the value at index 108. When done if we have any value greater than 1 we have repeated characters. Below is the code for the same
http://codepad.org/eeXC8Vk2
You can edit and play around with the code.
2) Implement a function void reverse(char *str) in C or C++ which reverses a NULL terminated string.
A) Let us first implement in a brute force way, i.e. by copying into another temporary string
http://codepad.org/lpj4h65V
But the above code does not show that you are a wise programmer. Let us now improve the algorithm.
Improvement in any algorithm is done in two ways either by saving time or space.
Since we are only traversing the string once, which cannot be avoided the only other saving is in space. We are creating another temporary string to copy the contents into, can we do it without it ?
Yes we can.
For example assuming the string is "Hello". To reverse that string I need to swap the characters in the beginning of the string with their counter parts from the end.
H <-> o
e <-> l
Do we still need the extra string to store ? Not really. See the code below
http://codepad.org/SlntaXd8
3) Given two strings write a function to decide if one is a permutation of the other.
A) Permutation of any sting is nothing but rearrangement of a give set of elements. cab is a permutation of abc. We discussed in question 1 about how to remember characters. We can apply the same technique here.
Please try it yourself. If you still need help let me know.
4) Given two strings find if one is found in another and return the staring index of the matched string.
If not found in the main string it should return -1.
pattern(abcdefgh, %ef%) should return 4.
pattern(abc def gh, %cb%) should return -1.
The percentile(%) symbol represents a wild card. If I say c% the main string should start with c, if I say %g, the main string should end with g.
A) We are searching for a string within a string.
When we find the first matched character, remember the index of the main string and continue to match all the characters of the pattern string, if we find any mismatch we continue to find the first character of the pattern string in the main string again till we exhaust the main string.
Find the complete code in the link below.
http://codepad.org/YXmHgHP1
There are several boarder and special cases being covered in the above code
First
Need less to say if there is nothing to operate on return -1.
Second
If the first character of the pattern string is not % and the first character is not equal to the first character of the main string return -1.
Third
The most important among all the cases is if the pattern length is greater than the original string, we cannot find the pattern anyway.
Fourth
If the last character is not % and is also not equal to the last character of the main string you should return -1.
Fifth
We are done with the border cases. We need to decide the index to which we will compare .i.e as discussed above if we do not have % at the beginning of the pattern string we start comparison from index 0, but if we do, we compare from index 1.
Sixth
As discussed above same holds good for the last character of the pattern string if it is % we compare till last but one character, but if it is not we compare till last character.
The final for loop begins after all the above cases
We start comparing each and every character in the main string with the first character of the pattern string. When a match is found, remember the index and start comparing the rest of the characters. If we find a mismatch with any one character break and start over again comparing the first character of patter string.
Still have questions ? Let me know.
5) Give a string identify the longest palindrome string and its starting index if present.
A) What is a palindrome string ?
Any string which is equivalent to its reversed string is a palindrome string. For example
abbbcbbba is a palindrome string
cbc is a palindrome string
aa is a palindrome string
Here is the code to identify the biggest palindrome
Brute force method
http://codepad.org/s289SAle
Again a similar logic as pattern matching with a little modification.
Look for a repeated character and verify that all the characters in between satisfy the palindrome condition for which I used the verifyPalindrome function in the code above. If the verifyPalindrome returns a positive integer ensure that it is the maximum of all the ones found before that. If you need the last of all the similar sized palindromes make the maximum check condition from greater than to greater than or equal.
The computational complexity of this method is O(N^3) which is very expensive.
Can we do better ?
Yes we can using dynamic programming.
We can store the information of all the substrings using a two dimensional boolean matrix, where each index holds the start and end of a palindrome string.
http://codepad.org/gMvqD3a5
In the above code we are first setting all the single characters as Palindrome in dynamicMemory, then all the 2 character sub strings if they are same.
We then check all the other sub stings with length 3 or greater.
Computational complexity of this approach is O(N) which is far better than the brute force method above.
6) Given a string print all the combinations of the same.
A) Combinations of any set of elements(in this case a set of characters) is nothing but the different ways you can select some or all the elements in the set.
For a string "abc" with n=3 elements, there are (2^n) - 1 = 7 you can select the characters i.e you can select a, b, c, ab, ac, bc, abc
How do we do that programmatically ?
There is a very easy way to do that. Let the number of elements in the set represent bits in a binary number i.e for 3 elements we have three bits, lets write all the numbers starting from 1.
abc
-001 : c
-010 : b
-011 : bc
-100 : a
-101 : ac
-110 : ab
-111 : abc
Each bit with a 1 represents the corresponding elements selection. This can also be extended for selecting 1, 2 or 3 at a time by counting the number of 1's in that number.
http://codepad.org/YO0oQ8mC
7) Give a string print all the permutations of the same
A) Permutation of a given set of numbers is nothing but the number of ways we can arrange them, unlike combinations the order of elements is considered in permutations that is ab is different than ba.
In a given string "abc" the following are the permutations
abc
acb
bac
bca
cab
cba
If you observe the first character is same in every pair of sets and the rest are swapped.
Here is how you can do it programmatically.
http://codepad.org/NV8KEMBS
8) Given a 2-D array rotate it clockwise by 90degrees
A) Visualize the 2-D array and rotate it by 90degrees clock wise. See each and every element it just moved from place A to place B.
This happens layer by layer. Look at the top layer the first row now is right most column. We can do that by copying the whole row into an array and continue the same with each row and column. This requires O(N) space.
Can we do better ? Yes we can we can rather copy element by element.
This method is essentially the same as copying array, but we have a loop which does the work for us.
So the following array
1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7
Should look like
4 3 2 1 5 4 3 2 6 5 4 3 7 6 5 4
Here is the code for the same :
http://codepad.org/ECvVgNQP
No comments:
Post a Comment