DFS (Depth First Search) on tree or graph
Posted on January 1, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Consider this tree (which is a graph without a cycle) :
Now DFS means traversing to the depth…and then going up, so here DFS traversal will result in 5 2 -4 3 21 19 25. We can use non recursive as well recursive approach to solve this problem.
A depth first search (DFS) through a tree starts at the root and goes straight down a single branch until a leaf is reached.
[Read More]BFS (Breadth first search ) OR Level Order Traversal on tree
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Algorithm
Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and then visit i.e. mark the vertex as visited and process all of v’s neighbors. Now that we’ve visited and processed all of v’s neighbors, we need to visit and process all of v’s neighbors neighbors Example
So consider the tree:
[Read More]Check if 2 strings are rotated versions of each other
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Given two string s1 and s2 how will you check if s1 is a rotated version of s2 ?
OR
Assume you have a method isSubstring() which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring.ie: ‘waterbottle’ is a rotation of ‘erbottlewat’
[Read More]Syntax highlighter for blogs
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Escape all % characters in a string; % is the escape character
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Example :
Input : India has GDP of 10% in 2009
Output : Input has GDP of 10%% in 2009
It is usually not be possible to do this in-place since the original unescaped string may not have enough space in the array to store the additional escape characters. But if we create a new array, O(n) algo is possible, though space complexity will increase.
String escapePercent(String input) { StringBuilder sb = new StringBuilder(); char\[\] str = input.
[Read More]Remove whitespace from a string in-place, in linear time
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Should not there be a \o in the end to terminate t… Neha - Oct 2, 2013Should not there be a \o in the end to terminate the string??
Yes this is a ‘\0’ terminated string only. We are moving ahead only when we find a white space (when we say):
while (str[ahead] == ' ‘) ahead++;
Rest all the characters except the space are copied as is, which also includes ‘\0’ and hence string is ‘\0’ .
[Read More]Remove whitespace from a string in-place, in linear time
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
void removeWhitespace(char\* str) {
int current \= 0;
int ahead \= 0;
while (str\[ahead\] !\= '\\0') {
while (str\[ahead\] \=\= ' ') ahead++;
str\[current\] \= str\[ahead\];
current++;
ahead++;
}
}
Implementing strcpy
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
char *strcpy ( char *dest, const char *src );
strcpy is short for string copy, which means it copies the entire contents of src into dest. The contents of dest after strcpy will be exactly the same as src such that strcmp ( dest, src ) will return 0.
size\_t strlen ( const char \*s ); ```strlen will return the length of a string, minus the termating character ('\\0'). The size\_t is nothing to worry about.
[Read More]Implementing strcat
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
char \*strcat ( char \*dest, const char \*src );
```strcat is short for string concatenate, which means to add to the end, or append. It adds the second string to the first string. It returns a pointer to the concatenated string. Beware this function, it assumes that dest is large enough to hold the entire contents of src as well as its own contents.
Implementing strcmp
Posted on December 31, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
int strcmp ( const char \*s1, const char \*s2 );
```strcmp will accept two strings. It will return an integer. This integer will either be:
Negative if s1 is less than s2.
Zero if s1 and s2 are equal.
Positive if s1 is greater than s2.