Amazon Interview Question Computer Scientists
Country: India
Interview Type: In-Person
public class ExpandString
{
public static void expand(String str)
{
if (str == null)
throw new IllegalArgumentException();
String[] fields = str.split(",");
for (String field : fields)
{
if (field.matches(".*\\.\\..*"))
{
String [] ranges = field.split("\\.\\.");
int start = Integer.valueOf(ranges[0]);
int end = Integer.valueOf(ranges[1]);
for (int i = start; i <= end; i++)
{
System.out.print(i+",");
}
}
else
{
System.out.print(field+",");
}
}
}
public static void main (String [] args)
{
if (args.length != 1)
{
throw new IllegalArgumentException();
}
ExpandString.expand(args[0]);
}
}
Java code
public static void main(String[] args){
String x = "1..5,8,11..14,18,20,26..29";
String y = "1,2,3,4,5,8,11,12,13,14,18,20,26,27,28,29";
extend(x,y);
}
static void extend(String x,String y){
String[] target=y.split(",");
ArrayList<Integer> source=new ArrayList<>();
String[] tmp=x.split("\\.\\.");
for(int i=0;i<tmp.length;i++){
String[] tmp2=tmp[i].split(",");
for(int j=0;j<tmp2.length;j++){
source.add(Integer.valueOf(tmp2[j]));
}
}
for(String s:target){
if(!source.contains(Integer.valueOf(s)))
source.add(Integer.valueOf(s));
}
Collections.sort(source);
for(Integer i:source){
System.out.print(i+",");
}
}
public static void expandString2(String x){
StringTokenizer st = new StringTokenizer(x, ",");
int tokenCounter = 0;
while(st.hasMoreTokens()){
String token = st.nextToken();
if(tokenCounter != 0){
System.out.print(",");
}
int index = token.indexOf("..");
tokenCounter++;
if(index != -1){
int min = Integer.parseInt(token.substring(0,index));
int max = Integer.parseInt(token.substring((index + 2), token.length()));
for(int i=min; i<=max; i++){
System.out.print(i);
if(i != max){
System.out.print(",");
}
}
}
else{
System.out.print(token);
}
}
}
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class StringSplit {
public static void main(String []args)
{
String source="1..5,8,11..14,18,20,26..29";
String splitData[]=source.split(",");
for(int i=0;i<splitData.length;i++)
{
if(splitData[i].contains(".."))
{
String tar[]=splitData[i].split("\\.\\.");
int start=Integer.parseInt(tar[0]);
int end=Integer.parseInt(tar[tar.length-1]);
for(int index=start;index<=end;index++)
System.out.print(index+" ");
}
else
System.out.print(splitData[i]+" ");
}
}
}
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class StringSplit {
public static void main(String []args)
{
String source="1..5,8,11..14,18,20,26..29";
String splitData[]=source.split(",");
for(int i=0;i<splitData.length;i++)
{
if(splitData[i].contains(".."))
{
String tar[]=splitData[i].split("\\.\\.");
int start=Integer.parseInt(tar[0]);
int end=Integer.parseInt(tar[tar.length-1]);
for(int index=start;index<=end;index++)
System.out.print(index+" ");
}
else
System.out.print(splitData[i]+" ");
}
}
}
I am not sure if this is the best approach. Here's a simple java code for this problem.
public class StringExpansion {
public static void main(String[] args) {
String str = "1..5,8,11..14,18,20,26..29";
System.out.println(conversion(str));
}
public static String conversion(String str) {
String[] arr = str.split(",");
StringBuilder sb = new StringBuilder();
for(int i = 0; i < arr.length; ++i) {
if(arr[i].contains("..")) {
arr[i] = getNumberString(arr[i]);
}
sb.append(arr[i]);
if(i != arr.length -1) {
sb.append(",");
}
}
return sb.toString();
}
private static String getNumberString(String str) {
String[] nums = str.split("\\.\\.");
int start = Integer.parseInt(nums[0]);
int end = Integer.parseInt(nums[1]);
StringBuilder sb = new StringBuilder();
while(start < end) {
sb.append(start);
sb.append(",");
start++;
}
sb.append(end);
return sb.toString();
}
}
void expandNumbersDriver()
{
char * x = "1..5,8,11..14,18,20,26..29";
char charArray[300];
for (unsigned int i = 0; i < 300; i++)
{
if (i < strlen(x))
{
charArray[i] = x[i];
}
else
{
charArray[i] = '\0';
}
}
cout << "Input : " << endl << charArray << endl;
expandCharArray(charArray, 0, 0);
cout << "Output : " << endl << charArray << endl;
}
void expandCharArray(char * inputStr, unsigned int readPos, unsigned int writePos)
{
char curChar = inputStr[readPos];
if (curChar == '\0')
{
inputStr[writePos] = '\0';
return;
}
if (isdigit(curChar) || curChar == ',')
{
expandCharArray(inputStr, readPos + 1, writePos + 1);
inputStr[writePos] = curChar;
}
else
{
// Get Left Number
int leftSide = (int) readPos;
leftSide--;
while (leftSide >= 0 && isdigit(inputStr[leftSide]))
{
leftSide--;
}
leftSide++;
int size1 = (readPos - 1) - leftSide + 1;
char * tempArray = new char[size1 + 1];
for (int i = 0; i < size1; i++)
{
tempArray[i] = inputStr[leftSide + i];
}
tempArray[size1] = '\0';
int number1 = atoi(tempArray);
delete[] tempArray;
// Get right Number
int rightSide = (int)readPos + 2;
while (rightSide < strlen(inputStr) && isdigit(inputStr[rightSide]))
{
rightSide++;
}
rightSide--;
int size2 = rightSide - (readPos + 2) + 1;
tempArray = new char[size2 + 1];
for (int i = 0; i < size2; i++)
{
tempArray[i] = inputStr[readPos + 2 + i];
}
tempArray[size2] = '\0';
int number2 = atoi(tempArray);
delete[] tempArray;
// Get Expanion Size
int sizeNeeded = 1; // initial comma
char tempCharArray[300];
for (int i = number1 + 1; i < number2; i++)
{
_itoa_s(i, tempCharArray, 300,10);
sizeNeeded += strlen(tempCharArray) + 1;
}
// Expand Now
expandCharArray(inputStr, readPos + 2, writePos+sizeNeeded);
tempArray = new char[sizeNeeded];
unsigned int tempArrayPos = 0;
tempArray[tempArrayPos] = ',';
tempArrayPos++;
for (int i = number1 + 1; i < number2; i++)
{
_itoa_s(i, tempCharArray, 300, 10);
for (int j = 0; j < strlen(tempCharArray); j++)
{
tempArray[tempArrayPos] = tempCharArray[j];
tempArrayPos++;
}
tempArray[tempArrayPos] = ',';
tempArrayPos++;
}
for (int i = 0; i < sizeNeeded; i++)
{
inputStr[writePos + i] = tempArray[i];
}
delete[] tempArray;
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void print_series(int start, int end){
printf("%d",start);
for(int i = start+1; i <= end ; i++){
printf(",%d",i);
}
}
void main(int argc, char** argv){
printf("%s\n",argv[1]);
char* arg = argv[1];
int i =0;
int num = 0;
int start, end ;
printf("\n");
int substitute = 0;
int dots = 0;
for(; i<strlen(arg); i++){
switch(*(arg+i)) {
case '.':
dots ++;
if(dots == 1)
start = num;
num = 0;
break;
case ',':
if(dots == 2){
print_series(start, end);
printf(",");
dots = 0;
num=0;
} else {
printf("%d,", num);
num = 0;
}
break;
default:
num = num * 10 + (*(arg+i) - '0');
if(dots == 2){
end = num;
}
}
}
if(dots == 2){
print_series(start, end);
} else {
printf("%d", num);
}
printf("\n");
}
#include<stdio.h>
#include<string.h>
int main(){
char str[]="1..5,8,11..14,18,20,26..29";
char str1[50];
int i=0,j=0,count=0,flag=0,a,b;
int sz=strlen(str)+1;
while(i!=sz){
if(str[i]=='.'){
count++;
if(count==1){
if(str[i-3]==','||(i-3)==-1){
a=(str[i-2]-'0')*10+(str[i-1]-'0');
}
else
a=str[i-1]-'0';
printf("\na=%d",a);
}
if(count==2){
if(str[i+3]==','||(i+3)==(sz-1)){
b=(str[i+1]-'0')*10+(str[i+2]-'0');
i++;
}
else
b=str[i+1]-'0';
printf("\nb=%d",b);
}
i++;
continue;
}
if(str[i]==','){
str1[j]=',';
i++;j++;
continue;
}
if(count==2){
while(b>a){
a=a+1;
str1[j]=',';
str1[++j]=a/10 + '0';
str1[++j]=a%10 + '0';
j++;
}
count=0;
}
else{
str1[j++]=str[i];
}
i++;
}
printf("\ngiven string = %s\nexpended str : %s\n",str,str1);
return 0;
}
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
void expandToken(char *token){
int len = strlen(token);
double exp=0;
int startNum=0, endNum =0;
int number =0 ;
//cout<<"Token=["<<token<<"] its leng=["<<len<<"]"<<endl;
for(int i=0;i<len;i++){
if(i!=len-1 && *(token+i) == '.' && *(token+i+1) == '.'){
for(int j=i-1;j>=0;j--){
int dg = *(token+j)-'0';
number+= (int)(pow(10,exp++))*dg;
}
startNum = number;
number = 0;
exp = 0;
for(int j=len-1;j>=i+2;j--){
int dg = *(token+j)-'0';
number += (int)(pow(10,exp++))*dg;
}
endNum = number;
cout<<",";
for(int cnt=startNum+1;cnt<=endNum;cnt++){
cout<<cnt;
if(cnt!=endNum)
cout<<",";
}
return;
}
else{
cout<<*(token+i);
}
}
}
void expandNos(char *str){
char *p = strtok(str, ",");
while (p) {
expandToken(p);
p = strtok(NULL, ",");
if(p){
cout<<",";
}
}
cout<<endl;
}
int main(){
char str[]="5,8,11..14,15..17,18,20,26..29,40..50";
cout<<"Input=["<<str<<"]"<<endl;
expandNos(str);
return 0;
Quick implementation with C++ using cstrings on a machine that does not support itoa.
Use strtok twice: first to divide the input with delimiter "," and then with delimiter "..".
{
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <cstdlib>
using namespace std;
void unroll (char * string, char * newstring);
int main(int argc, char ** argv) {
char string [] = "1..5,8,11..14,18,20,26..29";
char * newstring = new char [strlen(string)*100];
printf ("%s \n", string);
unroll (string, newstring);
printf ("%s \n", newstring);
}
void unroll (char *string, char * newstring) {
//edge cases
if (string == NULL) {
printf ("string is empty");
return;
}
if (strlen(string) == 1) {
newstring[0] = string[0];
return;
}
//divide into tokens and store them in array chunks
char * token;
char * temptoken;
char * nbr1 = new char [5];
char * nbr2 = new char [5];
int count = 0;
char * pos = new char [5];
token = strtok (string, ",");
char * * chunks = new char * [20];
while (token != NULL) {
chunks [count] = new char [strlen(token)];
strcpy (chunks[count], token);
token = strtok (NULL, ",");
count++;
}
//read each item in chunk and extract the numbers
int items = 0;
char tempnbr [3];
for (int i=0; i < count; i++) {
nbr1 = strtok(chunks[i],"..");
nbr2 = strtok(NULL, "..");
strcat (newstring,nbr1);
if (nbr2 != NULL) {
for (int j = atoi(nbr1)+1; j <=atoi(nbr2);j++) {
strcat (newstring, ",");
sprintf (tempnbr, "%d", j);
strcat (newstring, tempnbr);
}
}
//to make sure the semi-colon doesn't appear at the end
if (i != count-1){
strcat (newstring, ",");
}
}
}}
Here is a Java Solution
//string x = "1..5,8,11..14,18,20,26..29"
//string y = "1,2,3,4,5,8,11,12,13,14,18,20,26,27,28,29"
public static String expandStr(String s) {
String[] tokens = s.split(",");
StringBuilder buff = new StringBuilder();
boolean isFirst = true;
for (int i = 0; i < tokens.length; i++) {
String s1 = tokens[i];
int start = 0, end = 0;
int ix = s1.indexOf("..");
if (ix > 0) {
start = Integer.parseInt(s1.substring(0, ix));
end = Integer.parseInt(s1.substring(ix + "..".length())) + 1;
} else {
start = Integer.parseInt(s1);
end = start + 1;
}
for (int j = start; j < end; j++) {
if (!isFirst) {
buff.append(",");
} else {
isFirst = false;
}
buff.append(j);
}
}
return buff.toString();
}
Simplifed Java Solution with for each loop
//string x = "1..5,8,11..14,18,20,26..29"
//string y = "1,2,3,4,5,8,11,12,13,14,18,20,26,27,28,29"
public static String expandStr(String s) {
String[] tokens = s.split(",");
StringBuilder buff = new StringBuilder();
boolean isFirst = true;
for (String s1 : tokens) {
int start = 0, end = 0;
int ix = s1.indexOf("..");
if (ix > 0) {
start = Integer.parseInt(s1.substring(0, ix));
end = Integer.parseInt(s1.substring(ix + "..".length())) + 1;
} else {
start = Integer.parseInt(s1);
end = start + 1;
}
for (int j = start; j < end; j++) {
if (!isFirst) {
buff.append(",");
} else {
isFirst = false;
}
buff.append(j);
}
}
return buff.toString();
}
package expandString;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class ExpandString {
public static void main(String[] args) {
String x = "1..5,8,11..15,18,22..25";
Stack<Integer> stack = new Stack<Integer>();
Matcher matcher = Pattern.compile("\\d+").matcher(x);
while (matcher.find()) {
System.out.println(matcher.group());
stack.push(Integer.parseInt(matcher.group()));
}
StringBuffer buffer = new StringBuffer();
int j = 0;
for (int i = 0; i < x.length(); i++) {
char ch = x.charAt(i);
if (ch == ',') {
buffer.append(stack.get(j) + ",");
j++;
} else if (ch == '.' && x.charAt(i + 1) == '.') {
i++;
int present = stack.get(j);
int next = stack.get(j + 1);
while (present != next) {
buffer.append(present + ",");
present++;
}
j++;
}
}
buffer.append(stack.get(j));
System.out.println(buffer.toString());
}
}
public static void expand(String s) {
String p = s;
String[] array = p.split("\\..");
String k = "";
for (int i = 0; i < array.length; i++) {
if (i != array.length - 1) {
String[] array1 = array[i].split(",");
String[] array2 = array[i + 1].split(",");
int a = Integer.parseInt(array1[array1.length - 1]);
int b = Integer.parseInt(array2[0]);
for (int j = a + 1; j < b; j++) {
array[i] = array[i] + "," + j;
}
}
if (k != "")
k = k + "," + array[i];
else
k = k + array[i];
}
System.out.println(k);
}
private static string ExpandString(string sequence)
{
StringBuilder builder = new StringBuilder();
int init, end, iLoc = 0;
string[] strLst = sequence.Split(new char[] { ',' });
foreach (string s in strLst)
{
if (s.Contains(".."))
{
iLoc = s.IndexOf("..");
init = Convert.ToInt32(s.Substring(0, iLoc)); // Initial range
end = Convert.ToInt32(s.Substring(iLoc + 2, s.Length - iLoc - 2)); // 2nd period @ p[i+1]
for (int j = init; j <= end; j++)
builder.Append(j + ",");
}
else
builder.Append(s + ",");
}
// Remove last ','
if (builder[builder.Length -1] > 0)
builder = builder.Remove(builder.Length - 1, 1);
return builder.ToString();
}
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
using namespace std;
string expandString(string input)
{
int strLen = input.size();
stringstream expandedStr;
int index = 0;
while(index < strLen)
{
//Find regions to be expanded
if(input[index] == '.' && input[index + 1] == '.')
{
int startIndex = index;
int endIndex = index;
int from = 0;
int to = 0;
while(startIndex != -1 && input[startIndex] != ',')
startIndex--;
while(endIndex != strLen && input[endIndex] != ',')
endIndex++;
int nrDigits = index - startIndex - 1;
for(int i = 0; i < nrDigits; i++)
{
from += (input[index - i- 1]-48)*pow(10,i);
}
nrDigits = endIndex - index - 2;
for(int i = 0; i < nrDigits; i++)
{
to += (input[endIndex - i- 1]-48)*pow(10,i);
}
for(int i = from+1; i < to; i++)
{
expandedStr << ",";
expandedStr << i;
}
expandedStr << ",";
index = index+2;
}
expandedStr << input[index];
index++;
}
return expandedStr.str();
}
int main(int argc, char *argv[])
{
string x = "1..5,8,11..14,18,20,26..29";
cout << expandString(x) << endl;
return 0;
}
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
using namespace std;
string expandString(string input)
{
int strLen = input.size();
stringstream expandedStr;
int index = 0;
while(index < strLen)
{
//Find regions to be expanded
if(input[index] == '.' && input[index + 1] == '.')
{
int startIndex = index;
int endIndex = index;
int from = 0;
int to = 0;
while(startIndex != -1 && input[startIndex] != ',')
startIndex--;
while(endIndex != strLen && input[endIndex] != ',')
endIndex++;
int nrDigits = index - startIndex - 1;
for(int i = 0; i < nrDigits; i++)
{
from += (input[index - i- 1]-48)*pow(10,i);
}
nrDigits = endIndex - index - 2;
for(int i = 0; i < nrDigits; i++)
{
to += (input[endIndex - i- 1]-48)*pow(10,i);
}
for(int i = from+1; i < to; i++)
{
expandedStr << ",";
expandedStr << i;
}
expandedStr << ",";
index = index+2;
}
expandedStr << input[index];
index++;
}
return expandedStr.str();
}
int main(int argc, char *argv[])
{
string x = "1..5,8,11..14,18,20,26..29";
cout << expandString(x) << endl;
return 0;
}
void expandString(NSMutableString *xString) {
NSInteger count = [xString replaceOccurrencesOfString:@".."
withString:@",..,"
options:NSCaseInsensitiveSearch
range:NSMakeRange(0, xString.length)];
NSMutableArray *subStrings = [xString componentsSeparatedByString:@","].mutableCopy;
while ([subStrings containsObject:@".."]) {
NSUInteger dotIndex = [subStrings indexOfObject:@".."];
NSUInteger firstIndex = dotIndex - 1;
NSUInteger lastIndex = dotIndex + 1;
NSUInteger firstNum = [subStrings[firstIndex] integerValue];
NSUInteger lastNum = [subStrings[lastIndex] integerValue];
for (NSInteger i = firstNum +1 ; i < lastNum; i++) {
[subStrings insertObject:[@(i) stringValue] atIndex:dotIndex];
dotIndex++;
}
[subStrings removeObjectAtIndex:dotIndex];
}
NSLog(@"%@",[subStrings componentsJoinedByString:@","]);
}
i did not tested the below code , just tried to give simple algorithm
improvements to do : do with out array size var xlen
- vijay September 17, 2014string x = "1..5,8,11..14,18,20,26..29" int xlen = x.size(); int i = 0; while(i < xlen) { if(i+3 < xlen && (x[i+1] == '.' && x[i+2] == '.')) { int temp = x[i]; //take temp var to not to modify array x while(tem <= x[3]) printf(" %d", temp++); i += 3; //finished one }else { printf(" %d", x[i]); i++; } if(x[i] == ',') i++; }