Microsoft Interview Question
Software Engineer / DevelopersCountry: Europe
Interview Type: Phone Interview
O(n) -
public static void main(String[] args) {
String str = "the brown fox ran fast";
reverse(str);
}
public static void reverse(String str){
int n = str.length()-1;
char[] carr = str.toCharArray();
Stack<String> stack = new Stack<String>();
String temp = "";
while(n >= 0){
if(carr[n] == ' '){
stack.push(temp);
temp = "";
}else{
temp += carr[n];
}
n--;
}
stack.push(temp);
while(!stack.isEmpty()){
System.out.print(stack.pop() + " ");
}
}
The solution I proposed in C#:
public static void Main(String[] args){
string sentence= "the brown fox ran fast";
string [] words=sentence.Split(' ');
sentence="";
for(int i=0;i<words.Length;i++)
{
sentence+=ReverseWord(words[i]);
if(i!=words.Length-1) sentence+=" ";
}
Console.WriteLine(sentence);
}
public static string ReverseWord(string word)
{
string output="";
for(int i=0;i<word.Length;i++)
{
output+=word[word.Length-i-1];
}
return output;
}
The solution I proposed in C#:
public static void Main(String[] args){
string sentence= "the brown fox ran fast";
string [] words=sentence.Split(' ');
sentence="";
for(int i=0;i<words.Length;i++)
{
sentence+=ReverseWord(words[i]);
if(i!=words.Length-1) sentence+=" ";
}
Console.WriteLine(sentence);
}
public static string ReverseWord(string word)
{
string output="";
for(int i=0;i<word.Length;i++)
{
output+=word[word.Length-i-1];
}
return output;
}
The solution I proposed in C#:
public static void Main(String[] args){
string sentence= "the brown fox ran fast";
string [] words=sentence.Split(' ');
sentence="";
for(int i=0;i<words.Length;i++)
{
sentence+=ReverseWord(words[i]);
if(i!=words.Length-1) sentence+=" ";
}
Console.WriteLine(sentence);
}
public static string ReverseWord(string word)
{
string output="";
for(int i=0;i<word.Length;i++)
{
output+=word[word.Length-i-1];
}
return output;
}
My solution in Java:
static String reverseAnyWords(String initialString) {
StringBuilder reversedString = new StringBuilder();
StringBuilder word = new StringBuilder();
for(int ii = 0; ii < initialString.length(); ii++) { // O(N)
if (!Character.isSpaceChar(initialString.charAt(ii))) { // O(1)
word.append(initialString.charAt(ii));
}
else {
if (word.length() != 0) {
reversedString.append(word.reverse());
word.delete(0, word.length());
}
reversedString.append(initialString.charAt(ii));
}
}
// Last piece
if (word.length() != 0) {
reversedString.append(word.reverse());
word.delete(0, word.length());
}
return reversedString.toString();
}
function reverStringWords($str){
$input_array = explode(' ', $str);
foreach($input_array as $index => $word){
$characters = str_split($word);
$limit = floor(count($characters) / 2);
for($i = 0; $i < $limit; $i++){
$new_index = count($characters) - $i -1;
// Swap.
$tmp = $characters[$i];
$characters[$i] = $characters[$new_index];
$characters[$new_index] = $tmp;
}
$input_array[$index] = implode('', $characters);
}
print_r(implode(' ', $input_array));
}
reverStringWords('Hello World!');
public static void main(String[] args) {
Stack<Character> stack = new Stack<Character>();
String s = new String("the brown fox ran fast");
char[] chararr = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(char c : chararr) {
if(c != ' ') {
stack.push(c);
} else {
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
sb.append(' ');
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
System.out.print(sb);
}
public static void main(String[] args) {
Stack<Character> stack = new Stack<Character>();
String s = new String("the brown fox ran fast");
char[] chararr = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(char c : chararr) {
if(c != ' ') {
stack.push(c);
} else {
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
sb.append(' ');
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
System.out.print(sb);
}
public static void main(String[] args){
Stack<Character> stack = new Stack<Character>();
String s = new String("the brown fox ran fast");
char[] chararr = s.toCharArray();
StringBuffer sb = new StringBuffer();
for(char c : chararr) {
if(c != ' ') {
stack.push(c);
} else {
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
sb.append(' ');
}
}
while(!stack.isEmpty()) {
sb.append(stack.pop().toString());
}
System.out.print(sb);
}
public static void main(String a[])
{
String string="The brown fox ran fast abc 12345 .\\nys>{}?[[]";
StringTokenizer strs = new StringTokenizer(string," ");
List<String> stringList =new ArrayList<>();
String strintToPrint="";
while (strs.hasMoreElements())
{
stringList.add(strs.nextToken());
}
Collections.reverse(stringList);
for(String str : stringList){
strintToPrint+=new StringBuilder().append(str).reverse().toString()+" ";
}
System.out.println(strintToPrint.trim());
}
xpublic static void main(String a[])
{
String string="The brown fox ran fast abc 12345 .\\nys>{}?[[]";
StringTokenizer strs = new StringTokenizer(string," ");
List<String> stringList =new ArrayList<>();
String strintToPrint="";
while (strs.hasMoreElements())
{
stringList.add(strs.nextToken());
}
Collections.reverse(stringList);
for(String str : stringList){
strintToPrint+=new StringBuilder().append(str).reverse().toString()+" ";
}
System.out.println(strintToPrint.trim());
}
public static void main(String a[])
{
String string="The brown fox ran fast abc 12345";
StringTokenizer strs = new StringTokenizer(string," ");
List<String> stringList =new ArrayList<>();
String strintToPrint="";
while (strs.hasMoreElements())
{
stringList.add(strs.nextToken());
}
Collections.reverse(stringList);
for(String str : stringList){
strintToPrint+=new StringBuilder().append(str).reverse().toString()+" ";
}
System.out.println(strintToPrint.trim());
}
String string="The brown fox ran fast abc 12345 .\\nys>{}?[[]";
StringTokenizer strs = new StringTokenizer(string," ");
List<String> stringList =new ArrayList<>();
String strintToPrint="";
while (strs.hasMoreElements())
{
stringList.add(strs.nextToken());
}
Collections.reverse(stringList);
for(String str : stringList){
strintToPrint+=new StringBuilder().append(str).reverse().toString()+" ";
}
System.out.println(strintToPrint.trim());
C# implementation. Complexity O(n):
static string Transform(string str) {
var sb = new StringBuilder(str.Length);
var cursor = 0;
for (var i = 0; i < str.Length; i++) {
if (char.IsLetter(str[i])) {
sb.Insert(cursor, str[i]);
}
else {
sb.Append(str[i]);
cursor = i + 1;
}
}
return sb.ToString();
}
steps
- Anonymous November 02, 20171> reverse your string
2> swap first word with last word increment start and decrement end