Reverse a String using bits
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Question: Reverse a string in C using as little additional memory as possible.
Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.
Method 1 - Normal Reversal of String
void reverseString(char\* str) { int i, j; char temp; i\=j\=temp\=0; j\=strlen(str)\-1; for (i\=0; i<j; i++, j\-\-) { temp\=str\[i\]; str\[i\]\=str\[j\]; str\[j\]\=temp; } } Method 2 - Using xor to swap 2 characters
[Read More]Karp-Rabin algorithm
Posted on December 25, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Some points to note about this String matching algorithm:
uses an hashing function; preprocessing phase in O(m) time complexity and constant space; searching phase in O(m__n) time complexity; O(n_+_m) expected running time. Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string “window” looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used.
[Read More]Find first occurrence of a string in another
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Typical question for indexOf operation. Given two strings s1 and s2, find the first index of s2 in s1 in an efficient manner.
Solution: The problem has very typical solution, starting with each character in the source string start looking if the string being searched for, exists or not. However, the implementations may differ on the way they optimize. One good approach is to first look for the starting character of the string being searched for, in the string being searched.
[Read More]atoi() in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Write a function to convert an ASCII string to integer, similar to atoi() function of C++.
Solution: The solution is too simple, it’s simple checks for erroneous inputs that makes writing such a function fun.
public class AsciiToInteger { public static void main(String\[\] args) { AsciiToInteger instance \= new AsciiToInteger(); int x \= instance.atoi("-683"); System.out.println("Conversion is: " + x); } private int atoi(String number) { // check for NULL or empty if(number \=\= null || number.
[Read More]itoa() in Java
Posted on October 9, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: Write a function to convert an integer value to its ASCII equivalent and return as a character array, similar to itoa() function of C++.
Solution: The solution may seem tricky at first because the array is constructed left-to-right, whereas the number is read right-to-left. The easiest approach is to construct an array with digits from right-to-left and then reverse the array itself. The result being the number representation in character array.
[Read More]Find the smallest window in a string containing all characters of another string
Posted on September 30, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example
S = “ADOBECODEBANC”, T = “ABC”,
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
[Read More]Squeeze all multiple spaces in a string into one space
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
#include <stdio.h>
void trimspace(char \*dst) {
const char \*src = dst;
int tocopy = 1;
char c;
while((c = \*src++)) {
if(tocopy)
\*dst++ = c;
tocopy = (c != ' ') || (\*src != ' ');
}
\*dst = '\\0';
}
int main() {
char s\[64\];
scanf("%\[^\\n\]c", s);
trimspace(s);
printf("%s\\n", s);
}
To find the longest substring with unique characters in a given string
Posted on September 22, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
#include <stdio.h> #include <string.h> typedef struct { const char \*start; size\_t len; }Substring; Substring longestSubstring(const char \*s){ Substring ret = {s, 1}; Substring cur = {s, 1}; size\_t i, len = strlen(s); const char \*p = NULL; for(i = 1; i < len; ++i){ p = memchr(cur.start, s\[i\], cur.len); if(p){ if(cur.len > ret.len) ret = cur; cur.len -= (p - cur.start) + 1; cur.start = p + 1; } cur.len++; } if(cur.
[Read More]Reverse the words in a sentence in place
Posted on September 19, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given a sentence you have to reverse it word by word.
Example
That is, given a sentence like this :
I am a good boy
The in place reverse would be:
boy good a am I
Solutions Method1 - Reverse the sentence first and then words again
First reverse the whole string and then individually reverse the words
I am a good boy
<————->
yob doog a ma I
[Read More]Check if singly linked list is Palindrome
Posted on September 19, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
There are couple of solution to it :
Method 1 - Using the stack
A simple solution is to use a stack of list nodes. This mainly involves three steps.
Traverse the given list from head to tail and push every visited node to stack. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node. If all nodes matched, then return true, else false.
[Read More]