Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
just two steps：
1，reverse the sentence
2, reverse every word in the sentence
code:
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
void swap(char *a, char *b)
{
if(*a == *b)
return;
(*a)^=(*b);
(*b)^=(*a);
(*a)^=(*b);
return;
}
void reverse(char *arry, int len)
{
for(int i = 0; i < (len>>1); i++)
swap(arry+i, arry+len-1-i);
return;
}
void rev_sentence(char *arry, int len)
{
reverse(arry, len);
int start = 0;
int sum = 0;
for(int i = 0; i<len; i++)
{
if(arry[i] != ' ')
sum++;
else
{
reverse(arry+start, sum);
start += sum + 1;
sum = 0;
}
}
reverse(arry+start, sum);
printf("%s\n", arry);
return;
}
int main()
{
char ar[50] = "reverse the word";
rev_sentence(ar, strlen(ar));
return 0;
}
1) reverse whole string
2) reverse each word
public static void revWord(char[] a) {
// reverse whole
revWord(a, 0, a.length);
int st = -1;
int end = -1;
for (int i = 0; i < a.length; i++) {
if (st == -1 && a[i] != ' ') {
st = i;
}
if (end == -1 && a[i] == ' ' ) {
end = i;
}
if(i == a.length-1){
end=i+1;
}
if (st != -1 && end != -1) {
revWord(a, st, end );
st = -1;
end = -1;
}
}
}
public static void revWord(char[] a, int s, int l) {
int mid = (l - s) / 2;
l--;
for (int i = 0; i < mid; i++, l--) {
char t = a[s+i];
a[s+i] = a[l];
a[l] = t;
}
}
Split on white space and then iterate to half the length of the sentence switching every position
public String wordReverse(String sent){
String[] words = sent.split("\\s+");
String temp;
for(int i = 0; i < (words.length/2); i++){
temp = words[i];
words[i] = words[words.length-1-i];
words[words.length-1-i] = temp
}
String newString = "";
for(String s : words){
newString += (s + " ");
}
return newString.trim();
}
Solution using recursive approach without modifying the original content.
#include <stdio.h>
void reverseTheWord(char *sentence, int len)
{
if( *sentence )
{
int i=0;
for(i; sentence[i] != ' '; i++);
reverseTheWord(sentence+i+1, len);
sentence[i] = '\0';
printf("%s ", sentence);
if(i != len ) //for make the string as before because i entered '\0' inplace of ' '(space).
sentence[i] = ' ';
}
}
int main()
{
char sentence[] = "reverse the word of this sentence";
int len = sizeof(sentence)/sizeof(sentence[0]);
reverseTheWord(sentence, len);
printf("\n%s ", sentence);
return 0;
}
o/p:- h+t+t+p://ideone.com/1zE3rK#view_edit_box
#include <iostream>
using namespace std;
// REVERSING THE WORDS IN A SENTENCE
void ReverseString( char* string, unsigned start, unsigned end ) {
for( unsigned i = start, j = end; i < j; ++i, --j ) {
char temp = *(string + i);
*(string + i) = *(string + j);
*(string + j) = temp;
}
}
void ReverseSentence( char* sentence ) {
if( !sentence )
return;
// Subtract 1 to account for null terminator
int sentenceLen = strlen(sentence);
ReverseString(sentence, 0, sentenceLen - 1);
// Find the indices of each word
unsigned start = 0, end = 0;
for( unsigned i = 0; i <= sentenceLen; ++i ) {
if( sentence[ i ] == ' ' || sentence[ i ] == '\0' ) {
end = i - 1;
ReverseString(sentence, start, end);
start = i + 1;
}
}
}
int main(int argc, char *argv[]) {
char sentence[] = "Reverse the words in this sentence";
ReverseSentence(sentence);
printf(sentence);
}
public class Reverse {
public static void main(String ars[]){
String str="Reverse the word please";
char res[]=str.toCharArray();
String add="";
//ArrayList arr=new ArrayList();
ArrayList arr=new ArrayList();
ArrayList<String> result=new ArrayList<String>();
for(int i=0;i<res.length;i++){
if(res[i]==' '){
arr.add(i);
}
}
arr.add(res.length);
int start=0,end=0;
for(int i=0;i<4;i++){
end=(Integer) arr.get(i);
result.add(str.substring(start, end));
result.add(" ");
start=end+1;
}
for(int i=result.size()-1;i>=0;i--){
System.out.print(result.get(i));
}
}
}
void print(char* str,int i,int chkpoint){
for (int j=i;j<=chkpoint;j++){
// printf("%s","here");
printf("%c",str[j]);
}
}
int main(){
char* str = "I am going to office";
printf("%d",strlen(str));
int len = strlen(str);
int chkpoint=len-1;
for (int i=len-1;i>=0;--i){
if (str[i]==' ' or i==0)
{
print(str,i,chkpoint);
chkpoint =i;
}
}
getchar();
return 0;
}
public void reverseSentence(String insentence) {
char[] sentence = insentence.toCharArray();
int[] blankposlist = new int[100];
displayArray(sentence);
int k = 0;
blankposlist[k++] = -1;
// storing the position of blank space in the input string.
for (int i = 0; i < sentence.length; i++) {
if (sentence[i] == ' ') {
blankposlist[k++] = i;
}
}
blankposlist[k] = sentence.length;
// reverse the input string
reverseString(sentence, 0, sentence.length - 1);
// Reverse each word
for (int m = 0; m < sentence.length;) {
int reverselen = blankposlist[k] - blankposlist[k - 1] - 1;
reverseString(sentence, m, m + reverselen - 1);
m = m + reverselen + 1;
k--;
}
displayArray(sentence);
}
public void reverseString(char[] inarray, int start, int end) {
char ch;
for (int i = 0; i <= (end - start) / 2; i++) {
ch = inarray[start + i];
inarray[start + i] = inarray[end - i];
inarray[end - i] = ch;
}
}
void displayArray(char[] inarray) {
System.out.println("\n---- Displaying array ---");
for (char element : inarray) {
System.out.print(element);
}
#include <stdio.h>
#include <string.h>
int main() {
int len, read_head, word_read_head, write_head, word_len;
char string[100], rev_string[100];
scanf("%[^\n]s", string);
len = strlen(string);
word_len = 0;
write_head = 0;
read_head = len - 1;
for (; read_head >= 0; read_head--) {
if (string[read_head] == ' ' || read_head == 0) {
if (read_head == 0) {
word_read_head = read_head;
word_len++;
}
else
word_read_head = read_head + 1;
for(; word_len > 0; word_len--)
rev_string[write_head++] = string[word_read_head++];
rev_string[write_head++] = ' ';
word_len = 0;
}
else
word_len++;
}
rev_string[write_head] = '\0';
printf("%s\n", rev_string);
return 0;
}
public static void reverse(char[] input, int startIndex, int endindex)
{
int _index = startIndex;
int _i = 0;
while (_index < startIndex + (endindex - startIndex)/2 )
{
if (input[_index] != input[endindex - 1 - _i])
{
char _temp = input[_index];
input[_index] = input[endindex - 1 - _i];
input[endindex - 1 - _i] = _temp;
}
_index++;
_i++;
}
}
/*Cases: input -> null or empty
* my name is ruchir nishkam -> nishkam ruchir is name my
* ruchirnishkam -> ruchirnishkam
* my name is ruchir nishkam -> nishkam ruchir is name my
*/
public static char[] ReverseString(string input)
{
if (string.IsNullOrEmpty(input))
throw new NullReferenceException();
char _separator = ' ';
int _index = 0;
bool _hasSpace = false;
while (_index < input.Length)
{
if (input[_index] == _separator)
{
_hasSpace = true;
break;
}
_index++;
}
char[] inputArray = input.ToCharArray();
if (_hasSpace)
{
reverse(inputArray, 0, input.Length);
int _startIndex = 0;
_index = 0;
while (_index < inputArray.Length)
{
if (inputArray[_index] == _separator)
{
reverse(inputArray, _startIndex, _index);
_startIndex = _index + 1;
}
_index++;
}
reverse(inputArray, _startIndex, _index);
}
return inputArray;
}
public static String revWordsOpt(String str)
{
String s[] =str.split(" ");
StringBuffer temp =new StringBuffer();
for (int i=s.length-1;i>=0;i--)
{
if (s[i].trim().length()>0)
temp.append(s[i]).append(" ");
}
if (temp.length()>1)
temp.setLength(temp.length()-1);
return temp.toString();
}
1. divide the string into a sequence of words
- Anonymous April 09, 20132. push into a stack and pop all words from the stack