Facebook Interview Question
void reverseWords( char str[] ){
int start = 0, end = 0, length;
length = strlen(str);
/* Reverse entire string */
reverseString(str, start, length - 1);
while( end < length ){
if( str[end] != ' ' ){ /* Skip non-word characters */
/* Save position of beginning of word */
start = end;
/* Scan to next non-word character */
while( end < length && str[end] != ' ' )
end++;
/* Back up to end of word */
end--;
/* Reverse word */
reverseString( str, start, end );
}
end++; /* Advance to next token */
}
}
void reverseString( char str[], int start, int end ){
char temp;
while( end > start ){
/* Exchange characters */
temp = str[start];
str[start] = str[end];
str[end] = temp;
/* Move indices towards middle */
start++; end--;
}
}
const char CHAR_SPACE = ' ';
const char STR_END = '\0';
char * reverse_word(char * start, char * end);
char * get_wstart(char * linePos);
char * get_wend(char * linePos); // first char cannot be space
int main(void)
{
char line[] = "hello world";
char * wstart = NULL, * wend = NULL;
char * in = NULL;
printf("line: %s\n", line);
for(in = line; (wstart = get_wstart(in)) != NULL; in = wend + 1) {
wend = get_wend(wstart);
reverse_word(wstart, wend);
}
printf("reversed line: %s.\n", line);
return 0;
}
char * get_wstart(char * linePos)
{
if(linePos == NULL || *linePos == STR_END) return NULL;
// skip over spaces
for(; *linePos == CHAR_SPACE; linePos++) ;
if(*linePos == STR_END) return NULL;
else return linePos;
}
char * get_wend(char * linePos)
{
if(linePos == NULL) return NULL;
for(; *linePos != CHAR_SPACE && *linePos != STR_END; linePos++) ;
return linePos - 1;
}
char * reverse_word(char * start, char * end)
{
char * retval = start;
char tmpChar;
while(start < end) {
tmpChar = *start;
*start = *end;
*end = tmpChar;
start++;
end--;
}
return retval;
}
public class ReverseWords {
public ReverseWords() {
}
public String reverseString(String str) {
StringBuffer reversedStr = new StringBuffer();
int length = str.length();
for(int i = length-1; i >= 0; i--) {
reversedStr.append(str.charAt(i));
}
return reversedStr.toString();
}
public String reverseWord(String str) {
String word;
StringBuffer reversedStr = new StringBuffer();
int length = str.length();
int i, j;
for(i = 0, j = 0; i < length; i++) {
if(str.charAt(i) == ' ') {
word = str.substring(j, i);
j = i+1;
reversedStr.append(reverseString(word));
reversedStr.append(" ");
}
}
word = str.substring(j, i);
reversedStr.append(reverseString(word));
return reversedStr.toString();
}
public static void main(String[] args) {
ReverseWords rw = new ReverseWords();
String str = rw.reverseString("hello world!");
System.out.println(str);
str = rw.reverseWord("hello world!");
System.out.println(str);
}
}
I tried to make an efficient C version:
void ReverseString(char *sBegin, char *sEnd)
{
char *savedBegin = sBegin;
int n = (sEnd - sBegin + 1) / 2;
char t;
while (sBegin < savedBegin + n)
{
t = *sBegin;
*sBegin = *sEnd;
*sEnd = t;
sBegin++;
sEnd--;
}
}
void ReverseWords(char *s)
{
char *b = NULL;
char *e = s;
bool done = false;
while (true)
{
// Let b find next non-space or null after e
b = e;
while (*b != 0 && *b == ' ')
{
b++;
}
// Let e find next space or null after b
e = b;
while (*e != 0 && *e != ' ')
{
e++;
}
done = *b == 0 || e == b;
if (done)
{
return;
}
ReverseString(b, e - 1);
}
}
<pre lang="java" line="1" title="CodeMonkey49435" class="run-this">def revStr(iStr):
size = len(iStr)
loop = int(math.floor(size/2))
iStr = list(iStr)
for i in range(loop):
tmp = iStr[i]
iStr[i] = iStr[size-1-i]
iStr[size-1-i] = tmp
rStr = ''
for i in iStr:
rStr += i
return rStr
def revLine(line):
wList = line.split()
rLine = ''
for i in wList:
rLine = rLine + revStr(i)+' '
return rLine
</pre><pre title="CodeMonkey49435" input="yes">
</pre>
void reverseStr(char* str, int i, int j)
{
while (i < j)
{
str[i] ^= str[j];
str[j] ^= str[i];
str[i++] ^= str[j--];
}
}
void reverseLine(char* str, int size)
{
int i = 0;
int j = 0;
reverseStr(str, 0, size - 1);
while (true)
{
if (str[j] == ' ' || str[j] == '\t' || str[j] == 0)
{
reverseStr(str, i, j - 1);
if (str[j] == 0) return;
i = j + 1;
}
j++;
}
}
Java Code
public static void main(String[] args){
String s="this is a test hey ho";
String[] tmp=s.split(" ");
for(int i=0;i<tmp.length;i++){
System.out.println(reverseOneLine(tmp[i]));
}
}
static String reverseOneLine(String s){
char[] c=s.toCharArray();
char[] r=new char[s.length()];
for(int i=0;i<c.length;i++){
r[i]=c[c.length-1-i];
}
return String.valueOf(r);
}
Java code without using String.split()
public static void main(String[] args) {
String rev = "esrever hcae drow NI siht enil";
String orig = "reverse each word IN this line";
assert rev.equals(reverse(orig));
}
private static String reverse(String str) {
if (str == null) {
throw new IllegalArgumentException();
}
if (str.trim().isEmpty()) {
return str;
}
StringBuilder sb = new StringBuilder();
int ws = -1; // word start index
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
if (ws != -1) {
sb.append(revWord(str.substring(ws, i)));
}
sb.append(' ');
ws = -1;
} else {
if (ws == -1) {
ws = i;
}
}
}
if (ws >= 0) {
sb.append(revWord(str.substring(ws, str.length())));
}
return sb.toString();
}
private static String revWord(String str) {
StringBuilder sb = new StringBuilder();
for (int i = str.length() - 1; i >= 0; i--) {
sb.append(str.charAt(i));
}
return sb.toString();
}
public static String reverseOnlyWords(String str) {
if (str == null) {
return str;
}
String result = "";
String wordToBeReversed = "";
int count = 0;
for (int i = 0; i < str.length(); i++) {
System.out.println("current ch: " + str.charAt(i));
if (str.charAt(i) == ' ') {
// now reverse the word
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
// add the space after reverse the word
result = result + str.charAt(i);
//reset
count = 0;
wordToBeReversed = "";
} else {
wordToBeReversed = wordToBeReversed + str.charAt(i);
count++;
}
}
// for left over on the buffer to be copied
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
return result;
}
public static String reverse(String original) {
String reverseWord = "";
for (int i = original.length()-1; i >= 0; i--) {
reverseWord = reverseWord + original.charAt(i);
}
return reverseWord;
}
public static String reverseOnlyWords(String str) {
if (str == null) {
return str;
}
String result = "";
String wordToBeReversed = "";
int count = 0;
for (int i = 0; i < str.length(); i++) {
System.out.println("current ch: " + str.charAt(i));
if (str.charAt(i) == ' ') {
// now reverse the word
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
// add the space after reverse the word
result = result + str.charAt(i);
//reset
count = 0;
wordToBeReversed = "";
} else {
wordToBeReversed = wordToBeReversed + str.charAt(i);
count++;
}
}
// for left over on the buffer to be copied
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
return result;
}
public static String reverse(String original) {
String reverseWord = "";
for (int i = original.length()-1; i >= 0; i--) {
reverseWord = reverseWord + original.charAt(i);
}
return reverseWord;
}
public static String reverseOnlyWords(String str) {
if (str == null) {
return str;
}
String result = "";
String wordToBeReversed = "";
int count = 0;
for (int i = 0; i < str.length(); i++) {
System.out.println("current ch: " + str.charAt(i));
if (str.charAt(i) == ' ') {
// now reverse the word
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
// add the space after reverse the word
result = result + str.charAt(i);
//reset
count = 0;
wordToBeReversed = "";
} else {
wordToBeReversed = wordToBeReversed + str.charAt(i);
count++;
}
}
// for left over on the buffer to be copied
if (count > 0) {
result = result + reverse(wordToBeReversed);
}
return result;
}
public static String reverse(String original) {
String reverseWord = "";
for (int i = original.length()-1; i >= 0; i--) {
reverseWord = reverseWord + original.charAt(i);
}
return reverseWord;
}
void ReverseString(char* src, int beginIndex, int endIndex) {
- LayingOffMS February 28, 2009if (src==NULL || (beginIndex >= endIndex)) {
return;
}
int b = beginIndex; int e = endIndex;
while ( b <= e) {
char tmp = src[b];
src[b] = src[e];
src[e] = tmp;
}
}
void ReverseWordsInALine(char* src) {
if (src==NULL || strlen(src) <= 1)
return;
}
int i=0;
int j=i+1;
while (j <= strlen(src)-1) {
while(src[i])==' ') {
i++;
}
while(src[j]!==' '&& src[j]!='\0') {
j++;
}
ReverseString(src, i, j-1);
}
}