Amazon Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 5 vote

Its a variation of Dutch National Flag problem but with 3 way partitioning.
O(n) time complexity and not extrat space.
lower letter are first partition , space second and upper case third partition

Comment hidden because of low score. Click to expand.
2

Will it maintain order of the string ? I checked online but not sure if that actually maintains order .

Comment hidden because of low score. Click to expand.
2

It will not preserve the order..

Comment hidden because of low score. Click to expand.
1
of 1 vote

After this is done we need to regroup the 3 different groups in the order of the input array to keep the order.

Comment hidden because of low score. Click to expand.
0

How will you know what is the original order if you have just deleted it. You cannot use a different array than the one given as the input, so you no longer have your input array.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes it will not preserve the order..

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it will not maintain the order

Comment hidden because of low score. Click to expand.
0
of 0 vote

This should not be asked in an interview.

There is (IIRC) very very very tricky way to partition an array into two segments while maintaining order, in linear time, and with O(1) extra space.

You could do the above twice to solve this problem in the obvious way.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Cant we do this with Regular Expressions?

{{var str1 = str.match(/[a-z]+/gi);
var str2 = str.natch(/A-Z]+/gi);

var str3 = "";
str3 += str1.join(",");
str3+= " ";
str3+= str2.join(",");
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution to the problem.

``````public class AlphabetSorter {

public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";

for (int i = 0; i < input.length(); ++i) {

if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}

return lowers + spaces + uppers;
}

public static void main(String []args) {
String output = AlphabetSorter.sortString("a cBd LkmY");

System.out.println(output); //result: acdkm  BLY
}
}``````

Comment hidden because of low score. Click to expand.
0

you are using extra space with 3 string reference (lowers, psace, uppers) and many String instance

Comment hidden because of low score. Click to expand.
0

it can't be this easy buddy. no extra space plz. in place plz.

Comment hidden because of low score. Click to expand.
0

Dude.. Your code won't work for

``e cBAd LkmY``

because you are not sorting.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Used selection sort with a custom comparison logic which resides in the IsSpecialSmaller method.

These are my extension methods for the char.

``````public static class CharExtensions
{
public static bool IsSmall(this char c)
{
return c >= 97 && c <= 122;
}

public static bool IsSpace(this char c)
{
return c == 32;
}

public static bool IsUpper(this char c)
{
return c >= 65 && c <= 90;
}
}``````

And then the solution that uses these extension methods:

``````public static void Sort(char[] str)
{
for (int i = 0; i < str.Length; i++)
{
var minIndex = i;

for (int j = i + 1; j < str.Length; j++)
{
if (IsSpecialSmaller(str[j], str[minIndex]))
{
minIndex = j;
}
}

SwapChars(str, i, minIndex);
}
}

private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper() || a < b;
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return b.IsUpper() ? a < b : false;
}
}

private static void SwapChars(char[] str, int i, int j)
{
var tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}``````

Comment hidden because of low score. Click to expand.
0

I've noticed that the question is demanding that the original order among groups need to stay the same whereas my above code sorts them too. So the updated version of IsSpecialSmaller() method will avoid that.

``````private static bool IsSpecialSmaller(char a, char b)
{
if (a.IsSmall())
{
return b.IsSpace() || b.IsUpper();
}
else if (a.IsSpace())
{
return b.IsUpper();
}
else
{
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0

isn`t it O(n^2)?

Comment hidden because of low score. Click to expand.
0

Isn't this O(n^2)

Comment hidden because of low score. Click to expand.
0

It is indeed O(n^2) for runtime. Your comment made me realize O(n) is requested so mine wouldn't be the correct answer.

Comment hidden because of low score. Click to expand.
0

Isnt the complexity of this program O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

In java, a String is immutable. So it is at least required to create a char [] to manipulate a string right?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}

private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}

private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}

private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String arrange(String input) {
char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}

private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}

private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}

private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class ArrangeCharacters {

public static String arrange(String input) {
char []temp = input.toCharArray();
for (int i = 0; i < input.length(); i++) {
char ch = temp[i];
for (int j = i - 1; j >= 0 ; j--) {
if (isLowFollowLow(temp, i, j)) {
break;
} else if (isLowFollowsSpace(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isLowFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else if (isSpaceFollowUpp(temp, ch, j)) {
exchange(temp, j + 1, j);
} else {
break;
}
}
}
return new String(temp);
}

private static boolean isSpaceFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isSpaceChar(ch);
}

private static boolean isLowFollowUpp(char[] temp, char ch, int j) {
return Character.isUpperCase(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowsSpace(char[] temp, char ch, int j) {
return Character.isSpaceChar(temp[j]) && Character.isLowerCase(ch);
}

private static boolean isLowFollowLow(char[] temp, int i, int j) {
return Character.isLowerCase(temp[j]) && Character.isLowerCase(temp[i]);
}

private static void exchange(char[] temp, int i, int j) {
char ch = temp[i];
temp[i] = temp[j];
temp[j] = ch;
}``````

}

Comment hidden because of low score. Click to expand.
0

This is O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually, it is like a insertion sort. Compare each element i to 0 backwards.

Convert string to char array to each exchange and compare operation.

There are 3 conditions in which 2nd loops runs and exchange elements:
1) when in string Ul (U is upper case, l is lower case)
2) when Sl (s is space)
3) when US

Break condition is when : ll and above 3 condition not satisfied

This will give not exact o(n) but almost n as 2nd loops run only above 3 cases.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is easy. It can be done in two iterations of the array.
iteration 1)- start from the left side of the array find the first space. then find the small case letter after finding the space and swap. continue this till no small case letters found after space.

iterations 2) - Start from right side of the array but with capital case and spaces.

Now repeat again iteration 1) - After this entire array would be partitioned as small case, spaces and Upper case with maintaing the order.

Comment hidden because of low score. Click to expand.
0

Can you write the code for it?

Comment hidden because of low score. Click to expand.
0

How about cases that input does not have any space?

Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution is O(n) for swaps and O(n**2) on compares (and requires at least one space to do anything):

``````package me.arranger;

import java.util.ArrayList;

public class InplaceArranger
{
public static void Rearrange(char[ ] Letters)
{
LeftToRight(Letters);
RightToLeft(Letters);
LeftToRight(Letters);
}

private static void Swap(char[ ] Letters, int left, int right)
{
if ((left < Letters.length) && (right < Letters.length))
{
char hold = Letters[left];
Letters[left] = Letters[right];
Letters[right] = hold;
}
}

private static void LeftToRight(char[ ] Letters)
{
int iPos;

for (iPos = 0; iPos < Letters.length; iPos ++)
{
if (Letters[iPos] == ' ')
{
int iLower;
// Swap this space with the first lower-case character after it.
for (iLower = iPos + 1; ((iLower < Letters.length) && ( ! Character.isLowerCase(Letters[iLower]))); iLower ++)
;
if (iLower < Letters.length) Swap(Letters, iPos, iLower);
}
}
}

private static void RightToLeft(char[ ] Letters)
{
int iPos;

if (Letters.length == 0) return;
for (iPos = (Letters.length - 1); iPos >= 0; iPos --)
{
if (Letters[iPos] == ' ')
{
int iUpper;
// Swap this space with the first upper-case character before it.
for (iUpper = iPos - 1; ((iUpper >= 0) && ( ! Character.isUpperCase(Letters[iUpper]))); iUpper --)
;
if (iUpper >= 0) Swap(Letters, iUpper, iPos);
}
}
}

public static void main(String[] args)
{
String Text = "ab CDe fGHi JK lm";
char[ ] TextArray = Text.toCharArray( );

System.out.println(Text);
Rearrange(TextArray);
Text = new String(TextArray);
System.out.println(Text);
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

The problem states that the string will contain spaces. I think this is the correct solution. I don't think there is a possible solution without at least one space.

Comment hidden because of low score. Click to expand.
0

I don't think this is a correct algorithm. The existence of space is not a problem, we can solve it by metamorphosing-and-restoring method.
This algorithm claims iteration1->iteration2->iteration1.
Suppose we have a string 5ABcd, where 5 represents space.
Iteration 1: after the 1st swap, cAB5d; after the 2nd swap, cABd5.
Iteration 2: after the 1st swap, cA5dB; after the 2nd swap, c5AdB.
Iteration 1: after the 1st swap, cdA5B.
The result is incorrect. Of course we can perform iteration 2 again. But this is only for a simple example. For longer and more complex string, the repeat times will increase.

Actually, I suspect if there exists a O(n) time O(1) space algorithm

Comment hidden because of low score. Click to expand.
0

You are correct. The algorithm doesn't work correctly on this input set - good catch.

Comment hidden because of low score. Click to expand.
0
of 0 vote

But, Insertion sort is still not O(n)

Comment hidden because of low score. Click to expand.
0

For insertion sort you need extra memory.

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public class AlphabetSorter {

public static void sortString(String input) {

for (int i = 0; i < input.length(); ++i) {
if (Character.isLowerCase(input.charAt(i))) {
System.out.print(input.charAt(i));
}
}
for (int i = 0; i < input.length(); ++i) {
if (Character.isUpperCase(input.charAt(i))) {
System.out.print(input.charAt(i));
}
}
for (int i = 0; i < input.length(); ++i) {
if (input.charAt(i) == ' ') {
System.out.print(input.charAt(i));
}
}
}

public static void main(String []args) {
AlphabetSorter.sortString("a cBd LkmY");

}
}``````

Comment hidden because of low score. Click to expand.
0

I think you have not solved the problem, because you have not the string processed as required. In addition, using the output to print the char is a kind of needing extra memory.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
char *str          = "Got it Working Man";
char *temp_capital = (char*)malloc(sizeof(strlen(str)));
char *temp_small   = (char*)malloc(sizeof(strlen(str)));

int length_capital = 0;
int length_small = 0;

while(*str != '\0')
{
if(*str != ' ')
{
if( (*str >= 'A') && (*str <= 'Z') )
{
*temp_capital++ = *str;
length_capital++;
}
else if( (*str >= 'a') && (*str <= 'z') )
{
*temp_small++ = *str;
length_small++;
}

}
else
{
}
str++;
}
*temp_capital = '\0';
*temp_small++ = ' ';
*temp_small = '\0';

temp_capital = temp_capital - length_capital;
temp_small   = (temp_small  - (length_small+1));

printf(" The list of capital :%s \n", temp_capital );
printf(" The list of small :%s \n", temp_small );
printf("The concatenated string: %s", strcat(temp_small, temp_capital));
return 0;

}``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main()
{
char *str          = "Got it Working Man";
char *temp_capital = (char*)malloc(sizeof(strlen(str)));
char *temp_small   = (char*)malloc(sizeof(strlen(str)));

int length_capital = 0;
int length_small = 0;

while(*str != '\0')
{
if(*str != ' ')
{
if( (*str >= 'A') && (*str <= 'Z') )
{
*temp_capital++ = *str;
length_capital++;
}
else if( (*str >= 'a') && (*str <= 'z') )
{
*temp_small++ = *str;
length_small++;
}

}
else
{
}
str++;
}
*temp_capital = '\0';
*temp_small++ = ' ';
*temp_small = '\0';

temp_capital = temp_capital - length_capital;
temp_small   = (temp_small  - (length_small+1));

printf(" The list of capital :%s \n", temp_capital );
printf(" The list of small :%s \n", temp_small );
printf("The concatenated string: %s", strcat(temp_small, temp_capital));
return 0;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C# example

``````/// <summary>
/// Arrange String LowerCase Space Upper Case
/// </summary>
/// <param name="Input"></param>
/// <returns></returns>
public static string ArrangeStringLowSpaceUpper(string Input)
{
StringBuilder sb = new StringBuilder();
foreach (char c in Input)
{
if (Convert.ToInt32('a') <= Convert.ToInt32(c) && Convert.ToInt32('z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
sb.Append(' ');
foreach (char c in Input)
{
if (Convert.ToInt32('A') <= Convert.ToInt32(c) && Convert.ToInt32('Z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
return sb.ToString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/// <summary>
/// Arrange String LowerCase Space Upper Case
/// </summary>
/// <param name="Input"></param>
/// <returns></returns>
public static string ArrangeStringLowSpaceUpper(string Input)
{
StringBuilder sb = new StringBuilder();
foreach (char c in Input)
{
if (Convert.ToInt32('a') <= Convert.ToInt32(c) && Convert.ToInt32('z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
sb.Append(' ');
foreach (char c in Input)
{
if (Convert.ToInt32('A') <= Convert.ToInt32(c) && Convert.ToInt32('Z') >= Convert.ToInt32(c))
{
sb.Append(c);
}
}
return sb.ToString();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortChar {

public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();

String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
} else if (ascci >= 65 && ascci <= 90) {
} else if(ascci >= 97 && ascci <= 122) {
}
}

Collections.sort(uppercase);
Collections.sort(lower);

for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}

System.out.println(str);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortChar {

public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();

String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
} else if (ascci >= 65 && ascci <= 90) {
} else if(ascci >= 97 && ascci <= 122) {
}
}

Collections.sort(uppercase);
Collections.sort(lower);

for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}

System.out.println(str);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortChar {

public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();

String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
} else if (ascci >= 65 && ascci <= 90) {
} else if(ascci >= 97 && ascci <= 122) {
}
}

Collections.sort(uppercase);
Collections.sort(lower);

for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}

System.out.println(str);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortChar {

public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();

String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
} else if (ascci >= 65 && ascci <= 90) {
} else if(ascci >= 97 && ascci <= 122) {
}
}

Collections.sort(uppercase);
Collections.sort(lower);

for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}

System.out.println(str);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortChar {

public static void main(String[] args) {
List<Character> uppercase = new ArrayList<Character>();
List<Character> lower = new ArrayList<Character>();
List<Character> space = new ArrayList<Character>();

String s = "aG dYAb";
System.out.println(s);
String str = "";
for(int i=0 ;i <s.length() ; i ++) {
int ascci = (int)s.charAt(i);
if(ascci == 32) {
} else if (ascci >= 65 && ascci <= 90) {
} else if(ascci >= 97 && ascci <= 122) {
}
}

Collections.sort(uppercase);
Collections.sort(lower);

for(Character c : lower) {
str = str + c;
}
for(Character c : space) {
str = str + c;
}
for(Character c : uppercase) {
str = str + c;
}

System.out.println(str);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below code solve the problem in O(n)

``````package com.timepass.sortingx;

public class StringSort {
public static void threeWaySort(StringBuilder str){
int pos=0;

for (int i = pos; i < str.length(); i++) {
if(isLower(str.charAt(i))){
swap(str, pos++, i);
}
}

for (int i = pos; i < str.length(); i++) {
if(isSpace(str.charAt(i))){
swap(str, pos++, i);
}
}

for (int i = pos; i < str.length(); i++) {
if(isUpper(str.charAt(i))){
swap(str, pos++, i);
}
}
}

private static boolean isSpace(char ch){
return 32==ch;
}

private static boolean isUpper(char ch){
return ch>=65 && ch<=90;
}

private static boolean isLower(char ch){
return ch>=97 && ch<=122;
}

private static void swap(StringBuilder sb, int x, int y){
char y_char = sb.charAt(y);
sb.setCharAt(y, sb.charAt(x));
sb.setCharAt(x, y_char);
}

public static void main(String[] args) {
StringBuilder str = new StringBuilder("a cBd LkmY");
threeWaySort(str);
System.out.println(str);

}

}``````

Comment hidden because of low score. Click to expand.
0

You solved the problem in O(n) with no extra memory. However, you only keep the order of lower case letters. Imagine the bellow test case:
1. "aBDEFc"
You your program you will get:
After 1st loop (swap all lower case to begin):"acDEFB" (swipe 'c' with 'B')
No changes in spaces loop.
After 3rd loop, you will keep the same solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

As the problem states, this solution assumes that there is at least one space in the string.

public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}

public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;

for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space? If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;

for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution assumes that the string has at least one space.

{public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}

public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;

for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space? If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;

for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
Sort(charArray, 'A', 'Z', charArray.length - 1, -1, -1);
Sort(charArray, 'a', 'z', 0, charArray.length, 1);
System.out.print(charArray);
}

public static void Sort(char[] charArray, char lowerBound, char upperBound, int loopStartIndex, int loopEndIndex, int increment)
{
int firstSpaceIndex = -1;

for (int outer = loopStartIndex; outer != loopEndIndex; outer+=increment) {
if (charArray[outer] == ' ') {
// Is this the first space?  If so, make note of it.
if (-1 == firstSpaceIndex)
firstSpaceIndex = outer;
}
else if (charArray[outer] >= lowerBound && charArray[outer] <= upperBound && -1 != firstSpaceIndex) {
// If the current character is within bounds, swap it with the first space, and find the next space
charArray[firstSpaceIndex] = charArray[outer];
charArray[outer] = ' ';
int temp = firstSpaceIndex + increment;
firstSpaceIndex = -1;

for (int inner = temp; inner != outer+increment; inner+=increment) {
if (charArray[inner] == ' ') {
firstSpaceIndex = inner;
break;
}
}
}
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test
{

public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is simple way to do it:

``````public class Test
{

public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}
}

The sol will give proper answer in a simple way.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test
{

public static void main(String[] args)
{
String s = "a cBd LkmY";
StringBuilder lowerCase = new StringBuilder();
StringBuilder upperCase = new StringBuilder();
StringBuilder spaces = new StringBuilder();
char[] chars = s.toCharArray();
for (char x : chars)
{
if (Character.isLowerCase(x))
{
lowerCase.append(x);
}
else if (Character.isUpperCase(x))
{
upperCase.append(x);
}
else{
spaces.append(x);
}
}
String sortedWord = lowerCase.append(spaces.toString()).append(upperCase.toString()).toString();
System.out.println(sortedWord);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Durlav {

public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";

for (int i = 0; i < input.length(); ++i) {

if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}

return lowers + spaces + uppers;
}

public static void main(String []args) {
String output = Durlav.sortString("x gBd ADbmY");

System.out.println(output);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AlphabetSorter {

public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";

for (int i = 0; i < input.length(); ++i) {

if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}

return lowers + spaces + uppers;
}

public static void main(String []args) {
String output = AlphabetSorter.sortString("g cXSd FFGmY");

System.out.println(output);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AlphabetSorter {

public static String sortString(String input) {
String lowers = "";
String spaces = "";
String uppers = "";

for (int i = 0; i < input.length(); ++i) {

if (Character.isLowerCase(input.charAt(i))) {
lowers += input.charAt(i);
} else if (Character.isUpperCase(input.charAt(i))) {
uppers += input.charAt(i);
} else if (input.charAt(i) == ' ') {
spaces += input.charAt(i);
}
}

return lowers + spaces + uppers;
}

public static void main(String []args) {
String output = AlphabetSorter.sortString("a cBd LkmY");

System.out.println(output); //result: acdkm BLY
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
//char[] charArray = new char [] { 'c', 'A', 'B', 'd', ' '};
Sort(charArray);
System.out.print(charArray);
}

public static void Sort(char[]charArray) {
int writePos = charArray.length - 1;
// Search for capital letters in first pass
char lower = 'A';
char upper = 'Z';
for (int pass = 0; pass < 2; pass++)
{
// This character is in the correct place already
writePos--;
continue;
}
// Put the character in its correct place
// and shift the remaining characters left to fill
// in the gap
charArray[writePos--] = temp;
}
}
lower=upper=' '; // Search for spaces in second pass
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class SortNoExtraSpace {
public static void main(String[]args)
{
char[] charArray = new char [] { 'a', ' ', 'c', 'B', 'd', ' ', 'L', 'k', 'm', 'Y' };
//char[] charArray = new char [] { 'c', 'A', 'B', 'd', ' '};
Sort(charArray);
System.out.print(charArray);
}

public static void Sort(char[]charArray) {
int writePos = charArray.length - 1;
// Search for capital letters in first pass
char lower = 'A';
char upper = 'Z';
for (int pass = 0; pass < 2; pass++)
{
// This character is in the correct place already
writePos--;
continue;
}
// Put the character in its correct place
// and shift the remaining characters left to fill
// in the gap
charArray[writePos--] = temp;
}
}
lower=upper=' '; // Search for spaces in second pass
}
}``````

}

Comment hidden because of low score. Click to expand.
0

The algorithm works from the back of the string forwards, first placing the capital letters in their correct position, while shifting the string left. After the capital letters are placed, the algorithm does the same thing, placing the spaces in their correct position. Once the capital letters and spaces are positioned, the lowercase letters will automatically be in their correct places. I think this should still be O(N).

Comment hidden because of low score. Click to expand.
0

The space complexity is not constant. The difference between writePos and readPos might be O(n), hence the arraycopy method needs O(n) space. Moreover, you used arraycopy only for once within each scan, which probably "covers" some elements. I think to ensure no char/element is lost, one should use swap or copying twice.

Comment hidden because of low score. Click to expand.
0

The array copy uses the same array as the source and destination, so there is no additional space used. The copy shifts all elements left into the gap left over. The only question for me is the running time of the copy. The worst case scenario is presented when there is an equal number of spaces, followed by an equal number of uppercase letters, followed by an equal number of lowercase letters.

Comment hidden because of low score. Click to expand.
0

Do you mean that within each `if (charArray[readPos] >= lower && charArray[readPos] <= upper)` branch, the sub-array is only shifted by one unit? If so, then, true, only constant time is used. However, in the worst case, \Theta(n) elements will be shifted for \Theta(n) times. Hence the time complexity might be O(n^2). Anyway, the code above does not seem to be a worst case O(n) algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.sumit.crthcoin.chapter2;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SortAlphabets {

public static void main(String[] args) throws IOException {
List<Character> small = new ArrayList<Character>();
List<Character> large = new ArrayList<Character>();
for (int i=0;i<input.length();i++)
{
Character ch = input.charAt(i);
if(Character.isUpperCase(ch))
else if(Character.isLowerCase(ch))
}
Character[] upper = large.toArray(new Character[large.size()]);
Character[] lower = small.toArray(new Character[small.size()]);
StringBuilder sb1 = new StringBuilder(small.size());
for (Character ch : small)
sb1.append(ch);
String r1 = sb1.toString();
StringBuilder sb2 = new StringBuilder(large.size());
for(Character ch: large)
sb2.append(ch);
String r2 = sb2.toString();
char[] array1 = r1.toCharArray();
char[] array2 = r2.toCharArray();
Arrays.sort(array1);
Arrays.sort(array2);
String res = String.copyValueOf(array1) + " " + String.copyValueOf(array2);
System.out.println(res);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A variant of dutch national problem, however It doesn't seem that order can be maintained by O(n) complexity without any extra space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is not a clean one; but it works.

``````bool inrange(char a, char b, int& dir)
{
// check if b is in the range of a
// if a is CAPS, check if b is CAPS
dir = 0;

if ('A' <= a && a <= 'Z')
{
if (('A' <= b && b <= 'Z') || b == ' ')
{
return true;
}
else
{
if (b == ' ')
{
dir = 0;
return false;
}
else
{
dir = 0;
return false;
}
}
}
else if ('a' <= a && a <= 'z')
{
if ('a' <= b && b <= 'z')
{
return true;
}
else
{
if (b == ' ')
{
dir = 1;
return false;
}
else
{
dir = 1;
return false;
}
}
}
else if (a == ' ')
{
if (b == ' ')
{
return true;
}
else
{
if ('A' <= b && b <= 'Z')
{
dir = -1;
return false;
}
else if ('a' <= b && b <= 'z')
{
dir = 0;
return false;
}
}
}

return false;
}

void strmemove(char* dest, char* src, int size)
{
while(size)
{
*dest = *src;
dest--;
src--;
size--;
}
}

bool isSmall(char c)
{
return ('a' <= c )&& (c <= 'z');
}

bool isBig(char c)
{
return ('A' <= c )&& (c <= 'Z');
}

bool isSpace(char c)
{
return (' ' == c);
}

void encode(char str[])
{
int front = 1, back = 0;
int moveDir = 0;
unsigned long size = strlen(str);
int backSmall = 0, backSpace = 0;

printf("new string = %s, len=%zu\n", str, strlen(str));
while(back < size)
{
if (inrange(str[front], str[back], moveDir))
{
front++;
}
else
{

if (moveDir == -1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSpace);
str[backSpace] = temp;

front++;
back++;

backSpace++;
}
else if (moveDir == 1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSmall);
str[backSmall] = temp;

back++;
front++;

backSmall++;
backSpace++;
}
else
{
if (isSmall(str[back]))
{
backSmall++;
backSpace++;
}
if (isSpace(str[back]))
{
backSpace++;
}
back = front;
front++;
}
}
}

printf("new string = %s, len=%zu\n", str, strlen(str));
}

void encode_test()
{
char str[] = "aEBcfD Ah eK   ";
encode(str);

char str1[] = "EB D A K   ";
encode(str1);

char str2[] = "E a B b D d A a K k   b";
encode(str2);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is not a clean one; but it works.

``````bool inrange(char a, char b, int& dir)
{
// check if b is in the range of a
// if a is CAPS, check if b is CAPS
dir = 0;

if ('A' <= a && a <= 'Z')
{
if (('A' <= b && b <= 'Z') || b == ' ')
{
return true;
}
else
{
if (b == ' ')
{
dir = 0;
return false;
}
else
{
dir = 0;
return false;
}
}
}
else if ('a' <= a && a <= 'z')
{
if ('a' <= b && b <= 'z')
{
return true;
}
else
{
if (b == ' ')
{
dir = 1;
return false;
}
else
{
dir = 1;
return false;
}
}
}
else if (a == ' ')
{
if (b == ' ')
{
return true;
}
else
{
if ('A' <= b && b <= 'Z')
{
dir = -1;
return false;
}
else if ('a' <= b && b <= 'z')
{
dir = 0;
return false;
}
}
}

return false;
}

void strmemove(char* dest, char* src, int size)
{
while(size)
{
*dest = *src;
dest--;
src--;
size--;
}
}

bool isSmall(char c)
{
return ('a' <= c )&& (c <= 'z');
}

bool isBig(char c)
{
return ('A' <= c )&& (c <= 'Z');
}

bool isSpace(char c)
{
return (' ' == c);
}

void encode(char str[])
{
int front = 1, back = 0;
int moveDir = 0;
unsigned long size = strlen(str);
int backSmall = 0, backSpace = 0;

printf("new string = %s, len=%zu\n", str, strlen(str));
while(back < size)
{
if (inrange(str[front], str[back], moveDir))
{
front++;
}
else
{

if (moveDir == -1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSpace);
str[backSpace] = temp;

front++;
back++;

backSpace++;
}
else if (moveDir == 1)
{
char temp = str[front];
strmemove(&str[front], &str[front - 1], front - backSmall);
str[backSmall] = temp;

back++;
front++;

backSmall++;
backSpace++;
}
else
{
if (isSmall(str[back]))
{
backSmall++;
backSpace++;
}
if (isSpace(str[back]))
{
backSpace++;
}
back = front;
front++;
}
}
}

printf("new string = %s, len=%zu\n", str, strlen(str));
}

void encode_test()
{
char str[] = "aEBcfD Ah eK   ";
encode(str);

char str1[] = "EB D A K   ";
encode(str1);

char str2[] = "E a B b D d A a K k   b";
encode(str2);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can get there; but a clean code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.io.*;
class B{
void fun(StringBuffer s){
int l=s.length(),m=0,n=0,o=0,k;
int low[]=new int[l];
int up[]=new int[l];
int sp[]=new int[l];

for(int i=0;i<l;i++){
k=s.charAt(i);
if(k>=97 && k<=122){
low[m]=i;
m++;
}
else if(k==32){
sp[n]=i;
n++;
}
else if(k>=65 && k<=90){
up[o]=i;
o++;
}

}
for(int i=0;i<m;i++){
System.out.print(s.charAt(low[i]));
}
for(int i=0;i<n;i++){
System.out.print(s.charAt(sp[i]));
}
for(int i=0;i<o;i++){
System.out.print(s.charAt(up[i]));
}
System.out.println();

}
}
class A{
public static void main(String args[])throws IOException{
StringBuffer s1=new StringBuffer(s);
System.out.println(s1);
B b1=new B();
b1.fun(s1);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

#define CAPSL (1<<0)
#define SMALL (1<<1)
#define UNDERSCORE (1<<2)
#define SWAP(a, b) \
{ \
char c; \
c = *a; \
*a = *b; \
*b = c; \
}

char *start;

typedef enum ltype_ {
SMC = 0,
USC,
CAP,
} ltype;

ltype
gettype (char c)
{
if ((c >= 'a') && (c <= 'z')) return SMC;
if ((c >= 'A') && (c <= 'Z')) return CAP;
if (c == '_') return USC;
printf("Undefined type \n");
exit(1);
return SMC;
}

int
get_next_exp_flag (char c)
{
switch (gettype(c)) {
case SMC:
return (UNDERSCORE | CAPSL| SMALL);
case USC:
return (UNDERSCORE | CAPSL);
case CAP:
return CAPSL;
default:
printf("Fatal error \n");
exit(1);
}

}

int
get_current_flag (char c)
{
switch (gettype(c)) {
case SMC:
return (SMALL);
case USC:
return (UNDERSCORE);
case CAP:
return CAPSL;
default:
printf("Fatal error \n");
exit(1);
}
return -1;
}

#define EOLL '\0'
void
process_str( char *ptr)
{
int nef, cf;
char *save;

nef = get_next_exp_flag(*ptr);
ptr++;
while (*ptr != EOLL) {
cf = get_current_flag(*ptr);
save = ptr;
//printf("1. %c \n", *ptr);
while ((cf & nef) == 0) {
printf("Swap betw %c %c <%s>\n", *ptr, *(ptr-1), start);
getchar();
SWAP(ptr, (ptr-1));
if (ptr - 2 < start) {
break;
}
ptr -=2;// (??)
printf(" Now compare %c %c <%s>\n", *ptr, *(ptr+1), start);
getchar();
nef = get_next_exp_flag(*ptr);
ptr++;
cf = get_current_flag(*ptr);
}
ptr = save;
nef = get_next_exp_flag(*ptr);
printf("2. %c \n", *ptr);
ptr++;
}
}

int
main (int argc, char *argv[])
{
if (argc <= 1) return;
start = argv[1];
process_str(argv[1]);
printf("Final \n %s\n",start);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;
import java.util.Arrays;

public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{

}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;

}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);

}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}

}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;
import java.util.Arrays;

public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{

}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;

}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);

}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}

}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.lang.reflect.Array;
import java.util.Arrays;
public class Test1
{
static String str="Abxghfsg KHdsMhD";
public Test1()
{

}
public String sorting1(String str1)
{
char str[];
str=str1.toCharArray();
Arrays.sort(str);
String str2=new String(str);
System.out.println("Amresh "+str2);
return str2;
}
public void shortString(String str)
{
String lower="";
String upper="";
String spaces="";
int l=str.length();
for(int i=0;i<l;i++)
{
if(Character.isLowerCase(str.charAt(i)))
{
lower=lower+str.charAt(i);
}
else if (Character.isUpperCase(str.charAt(i))) {
upper=upper+str.charAt(i);
}
else if (str.charAt(i)==' ') {
spaces=spaces+str.charAt(i);
}}
String totstring=sorting1(lower)+spaces+sorting1(upper);
System.out.println("Total string "+totstring);
}
public static void main(String[] args) {
Test1 obj=new Test1();
obj.shortString(str);
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;
import java.util.*;

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

class Solution {

public static void main(String[] args){
String s = "a cBd LkmY";
Tough t = new Tough();
char[] arr = s.toCharArray();
t.sortArray(arr);

}

public void sortArray(char[] s){
int start = 0;
start = specialSort(s, start, s.length, 0);

start = specialSort(s, start + 1, s.length, 1);
specialSort(s, start+1, s.length, 2);
for(int i=0; i<s.length; i++){
System.out.print(s[i]);
}
}

public int specialSort(char[] s, int start, int length, int type){
int index = 0;
int lower = -1;
for(int i = start; i<length;i++){
char c = s[i];
boolean status = compare(type, c);
if(status && lower == -1){
index = i;
continue;
} else if(!status && lower == -1){
lower  = i;
continue;
} else{
if(lower >= 0 && status){
if(Math.abs(i - lower) == 1){
char temp = s[i];
s[i] = s[lower];
s[lower] = temp;
index = lower;
lower = i;
} else{
char temp = s[i];
for(int k=i-1; k>=lower; k--){
s[k+1] = s[k];
}
s[lower] = temp;
index = lower;
lower = lower + 1;
}
}

}
}
return index;
}

public boolean compare(int type, char a){
boolean status = false;
switch(type){
case 0: if(Character.isLowerCase(a))
status = true;
break;
case 1: if(a == ' ')
status = true;
break;
case 2: if(Character.isUpperCase(a))
status = true;
break;
}
return status;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

// C# CODE

string str = "aH JgUk OliTe ";

string lower = "", space = "", upper = "";

foreach (char s in str)
{
if (char.IsLower(s)) lower += s.ToString();
else if (char.IsUpper(s)) upper += s.ToString();
else space += s.ToString();
}

Console.Write(lower + space + upper);

Comment hidden because of low score. Click to expand.
0
of 0 vote

1] This C code is being tested in gcc.
The exact output is achieved using O(N2) and not by O(N).
In the following code, order of lower and upper case characters within the string is also maintained.
I/P: [ZtY cVj PkMl S]
O/P: [tcjkl ZYVPMS]
I have used a [char tmpchar variable] in my code for swapping.

2] #include<stdio.h>
#include<string.h>
int main()
{ char str[14]="ZtY cVj PkMl S";
lowspaceUpper(str);
}
lowspaceUpper(char *str)
{ int i,j,k;
char tmpchar;
printf("\nbefore sort:string=%s length=%d",str,strlen(str));

// Sorting Algorithm is used to swap characters according to the required sequence.

for(i=0;i<strlen(str);i++)
{
for(j=i+1;j<strlen(str);j++)
{
// the foll. conditions are used, if no swapping is required
if((str[i]==32 && str[j]==32))
continue;
else if((str[i]>=65 && str[i]<=90) && (str[j]>=65 && str[j]<=90))
continue;
else if((str[i]>=97 && str[i]<=122) && (str[j]>=97 && str[j]<=122))
continue;
else if(str[i]==32 && (str[j]>=65 && str[j]<=90))
continue;
else if((str[i]>=97 && str[i]<=122) && str[i]==32)
continue;
else if((str[i]>=97 && str[i]<=122) && (str[i]>=65 && str[i]<=90))
continue;
else{
if(str[i] >=65 && str[i] <=90) // foll condition is used if need to swap a Upper case with lower case or space
{
k=j;
tmpchar=str[k];

for(;k!=i;k--)
{
str[k]=str[k-1];
}
str[i]=tmpchar;
}else{ // foll condition is used if v need to swap a space with Upper case or Lower case
if(str[i]<str[j])
{
swap(&str[i],&str[j]);
}
}
}
}
printf("\niteration %d:string=%s",i,str);
}
printf("\nafter sort:string=%s length=%d",str,strlen(str));
printf("\n");
}
swap(char *ptr1,char *ptr2)
{
*ptr1 = (*ptr1) + (*ptr2); // x now becomes 15
*ptr2 = (*ptr1) - (*ptr2); // y becomes 10
*ptr1 = (*ptr1) - (*ptr2); // x becomes 5
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

void Swap(char *a, char *b)
{
char tmp = *a;
*a = *b;
*b = tmp;
}

char *Sort(char *str)
{
int i, j, l = strlen(str);
for(i=0; i< l ; i++)
for(j=i; j<l; j++)
if(str[i]>str[j])
Swap(str + i, str + j);
return str;
}
int main()
{
char str[]= "a cBd LkmY";
int i,l=0, u=0;
char Lower[8]= "", Upper[8]= "";

for(i=0; str[i]; i++)
if(islower(str[i]))
Lower[l++] = str[i];
else if(isupper(str[i]))
Upper[u++] = str[i];

printf("%s %s", Sort(Lower), Sort(Upper));
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

package prac;

import java.util.ArrayList;

public class SortChar {

public static void Rearrange(ArrayList<Character> textArray)
{
LeftToRight(textArray);
RightToLeft(textArray);

}

private static void LeftToRight(ArrayList<Character> textArray)
{
int iPos;

for (iPos = 0; iPos < textArray.size(); iPos ++)
{
if (textArray.get(iPos).equals(' '))
{
int iLower;
// Swap this space with the first lower-case character after it.
for (iLower = iPos + 1; (iLower < textArray.size()); iLower ++){
if(Character.isLowerCase(textArray.get(iLower))){
char temp= textArray.get(iLower);
textArray.remove(iLower);
iPos++;
}
}
}
}
}

private static void RightToLeft(ArrayList<Character> textArray)
{
int iPos;

if (textArray.size() == 0) return;
for (iPos = (textArray.size() - 1); iPos >= 0; iPos --)
{
if (textArray.get(iPos).equals( ' '))
{
int iUpper;
// Swap this space with the first lower-case character after it.
for (iUpper = iPos -1; (iUpper >=0); iUpper --){
if(Character.isUpperCase(textArray.get(iUpper))){
char temp= textArray.get(iUpper);
textArray.remove(iUpper);
iPos--;
}
}
}
}
}

public static void main(String[] args)
{
String Text = "ab CDe fGHi JK lm";
ArrayList<Character> TextArray = new ArrayList<Character>();
for (int a=0; a<Text.length();a++){
}
System.out.println(Text);
Rearrange(TextArray);
String t="";
for(int index=0; index< TextArray.size();index++){
t=t.concat(TextArray.get(index).toString());
}
System.out.println(t);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using Golang

``````package main

import "fmt"
import "unicode"

func sort(S *[]byte) {
marker := 0
//sort lower case
for index,value := range *S {
if unicode.IsLower(rune(value)) {
(*S)[index], (*S)[marker] = (*S)[marker], (*S)[index]
marker++
}
}
for i:=marker;i<len(*S);i++ {
if string((*S)[i])==" " {
(*S)[i], (*S)[marker] = (*S)[marker], (*S)[i]
marker++
}
}
}

func main() {
fmt.Println("Hello playground")
S := []byte("vHbR Tb TzzzA")
sort(&S)
fmt.Println(string(S))
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. First traverse the array to find the position of space as space position would be number of small characters +1.
2.now just again traverse the array and start from begining and pos[space+1]if find small char put before space.else put after space.
3.With this thier is no extra space an also in O(n).I hope you understand it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. First traverse the array to find the position of space as space position would be number of small characters +1.
2.now just again traverse the array and start from begining and pos[space+1]if find small char put before space.else put after space.
3.With this thier is no extra space an also in O(n).I hope you understand it.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.