## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

Here is a five line code solution for the problem:

``````void printAll(string st) {
cout << st[0] << st.size()-2 << st[st.size()-1] << endl;
for(int i=st.size()-3; i>=1; i--) {
for(int k=0; k<=st.size()-2-i; k++)
cout << st.substr(0,k+1) << i << st.substr(i+k+1) << endl;
}
cout << st << endl;
}``````

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

``````public class I18N {

public static void main(String[] args) {
String in = "careercup";
int count = 7;

char[] input = in.toCharArray();
String s = ""+input[0];
String e = ""+ input[input.length-1];

System.out.println(s+""+count+e);
int i =0;
while(count > 1  && i < input.length) {
--count;
System.out.println(s+input[i+1]+""+count+""+e);
System.out.println(s+""+count+input[(i+1)+count]+e);
s = s +input[i+1];
i++;

}
}

}``````

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

``````public static void main(String[] args) {
String in = "careercup";
int count = 7;

char[] input = in.toCharArray();
String s = ""+input[0];
String e = ""+ input[input.length-1];

System.out.println(s+""+count+e);
int i =0;
while(count > 1  && i < input.length) {
--count;
System.out.println(s+input[i+1]+""+count+""+e);
System.out.println(s+""+count+input[(i+1)+count]+e);
s = s +input[i+1];
i++;

}
}``````

Do you see any problem in my code ?. I could do it in one loop.

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

Guru, problem of your code is you don't cover: ca2ercup

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

Here is a five line solution:

``````void printAll(string st) {
cout << st[0] << st.size()-2 << st[st.size()-1] << endl;
for(int i=st.size()-3; i>=1; i--) {
for(int k=0; k<=st.size()-2-i; k++)
cout << st.substr(0,k+1) << i << st.substr(i+k+1) << endl;
}
cout << st << endl;
}``````

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

And use an unordered_map to prevent dupes from being printed.

e.g., if input was "aaa," this would print a1a twice.

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

len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)

str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));

printf("%c",str1[l]);
}

if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);

}
}

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

``````public static void generateCombination(int startIndex, String inputString, int endIndex,boolean isFirst){

if(isFirst) // First Time called with generateCombination(1,input,input.length()-1, true);
{
}

String startString = inputString.substring(0,startIndex);
String middleString = inputString.substring(startIndex, endIndex);
String endString = inputString.substring(endIndex, inputString.length());

String rightShift = null;
String leftShift = null;

for (int inputCounter = middleString.length(); inputCounter > 0; inputCounter--) {

if(middleString.length()==inputCounter)
{
}
else
{
rightShift = middleString.substring(0, middleString.length()-inputCounter);

leftShift = middleString.substring(inputCounter,middleString.length());

if(endIndex-startIndex>=2)
{
generateCombination(++startIndex, inputString, --endIndex, false);
}
}
}
}``````

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

``````public static void main(String[] args) {

String s = "careercup";

generateAll18(s, 1, s.length() - 1);
}

public static void generateAll18(String s, int i, int j) {

if (i >= j) {

return;
}

String s1, s2, s3;

s1 = s.substring(0, i + 1)+(j- i - 1)+""+s.substring(j, s.length());
s2 = s.substring(0, i)+(j - i)+""+s.substring(j, s.length());
s3 = s.substring(0, i+1)+(j - i)+""+s.substring(j + 1, s.length());
System.out.println(s1);
System.out.println(s2);
System.out.println(s3);

generateAll18(s, i+ 1, j-1);
generateAll18(s, i + 1, j);
generateAll18(s, i, j - 1);
}``````

Modify this by adding a hashtable to remove duplicates

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

This problem becomes simple once you break it down into processing the word layer by layer.

Maintain a prefix and suffix that start as the first and last letters of the input word.
Maintain pointers to left and right indices indicating the range of the word currently being processed.
For each "layer", we want to compute the left + sizeof(remainder to right), sizeof(remainder to left) + right, and sizeof(entire layer), then sandwich these three into the prefix and suffix computed so far, then update the prefix and suffix.

Pseudocode:

``````while (left < right) {
results.add(prefix + a[left] + (right - left - 1) + suffix);
results.add(prefix + (right - left - 1) + a[right] + suffix);
results.add(prefix + (right - left) + suffix);
prefix = prefix + a[left];
suffix = a[right] + suffix;
}

// It is important to identify the last layer, which is when the layer's size is 3 or 2.
// For the 2 case, left and right cross over.
// For the 3 case, left and right hit the same character, which is handled below
if (left == right) {
prefix = prefix + a[left];
}

// Finally, add the original word into the result

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

Here is a five line solution:

``````void printAll(string st) {
cout << st[0] << st.size()-2 << st[st.size()-1] << endl;
for(int i=st.size()-3; i>=1; i--) {
for(int k=0; k<=st.size()-2-i; k++)
cout << st.substr(0,k+1) << i << st.substr(i+k+1) << endl;
}
cout << st << endl;
}``````

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

Please find the recursive solution and possibly handling all cases where the number in mid is not a single digit.

``````public class GenerateI18NCombination {

private Set<String> set = new HashSet<String>();

private void recurse(String arr, String strSoFar) {
if (arr.length() > 0) {
String replace = replaceNumber(strSoFar, arr.length(), arr.charAt(0), true);
if (!set.contains(replace)) {
String s = arr.substring(1);
recurse(s, replace);
}
replace = replaceNumber(strSoFar, arr.length(), arr.charAt(arr.length() - 1), false);
if (!set.contains(replace)) {
String s = arr.substring(0, arr.length()-1);
recurse(s, replace);
}
} else {
}
}

private String replaceNumber(String str, int length, char ch, boolean isInFront) {
String[] arr = str.split("\\d");
if (length - 1 == 0) {
return arr[0] + ch + arr[1];
} else {
if (isInFront) {
return arr[0] + ch + (length - 1) + arr[1];
} else {
return arr[0] + (length - 1) + ch + arr[1];
}
}
}

public static void main(String[] args) {
GenerateI18NCombination obj = new GenerateI18NCombination();
obj.recurse("AREERCU", "C7P");
List<String> sortedList = new ArrayList<String>(obj.set);
Collections.sort(sortedList);
System.out.println(sortedList);
}

}``````

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

``````public static void generateCombination(int startIndex, String inputString, int endIndex,boolean isFirst){

if(isFirst) // First Time called with generateCombination(1,input,input.length()-1, true);
{
}

String startString = inputString.substring(0,startIndex);
String middleString = inputString.substring(startIndex, endIndex);
String endString = inputString.substring(endIndex, inputString.length());

String rightShift = null;
String leftShift = null;

for (int inputCounter = middleString.length(); inputCounter > 0; inputCounter--) {

if(middleString.length()==inputCounter)
{
}
else
{
rightShift = middleString.substring(0, middleString.length()-inputCounter);

leftShift = middleString.substring(inputCounter,middleString.length());

if(endIndex-startIndex>=2)
{
generateCombination(++startIndex, inputString, --endIndex, false);
}
}
}
}``````

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);

len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)

str1[j]=str[j];

str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));

printf("%c",str1[l]);
}

if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);

}

}

return 0;

}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)

str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));

printf("%c",str1[l]);
}

if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);

}
}
return 0;
}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);
len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)
str1[j]=str[j];
str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));
printf("%c",str1[l]);
}
if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);
}
}
return 0;
}

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

``````public static void gen(String s){
if (s == null) return;

for(int len = s.length()-2; len > 0; --len){
for(int i = 1, j = i+len; j < s.length(); ++i, ++j){
System.out.print(s.substring(0,i));
System.out.print(len);
System.out.println(s.substring(j));
}
}

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

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

My solution in simple words:
2. Iterate through position 1 through (word.length - chunk) and take out the chunk and replace it with the size of the chunk
3. Increment chunk and go to step 3 again until chunk is word.length - 2

Code:

``````public List<String> i18n(String word){
List<String> ret = new ArrayList<String>();
for(int chunk = 1; chunk <= word.length - 2; chunk++){
for(int i = 1; i < word.length - chunk; i++){
String s = word.substring(0, i) + chunk + word.substring(i + chunk);
}
}
return ret;
}``````

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

Here is my solution in Python.

``````def make_all_str(input_str):
result = []
for l in range(1, len(input_str)):
for start in range(0, len(input_str) - l + 1):
# result.append(input_str[:i] + str(len) + input_str[(start + len):]
res_str = input_str[:start] + str(l) + input_str[(start + l):]
result.append(res_str)
# end loop
# end loop
result.append(str(len(input_str)))
return result

def do_the_thing(input_str):
return map(lambda str: input_str[0] + str + input_str[-1], make_all_str(input_str[1:-1]))

print(do_the_thing("internationalization"))``````

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

``````def make_all_str(input_str):
result = []
for l in range(1, len(input_str)):
for start in range(0, len(input_str) - l + 1):
# result.append(input_str[:i] + str(len) + input_str[(start + len):]
res_str = input_str[:start] + str(l) + input_str[(start + l):]
result.append(res_str)
# end loop
# end loop
result.append(str(len(input_str)))
return result

def do_the_thing(input_str):
return map(lambda str: input_str[0] + str + input_str[-1], make_all_str(input_str[1:-1]))

print(do_the_thing("internationalization"))``````

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

Here is the working java code.

``````public class GetAllStrings
{
public static void main(String agrs[])
{
GetAllStrings("careercup");
}

private static void GetAllStrings(String iInputString)
{
for(int i=1; i<=(iInputString.length()-2); i++)
{
for(int j=1; j+i<=(iInputString.length()-1); j++)
{
System.out.print( iInputString.substring(0, j) );
System.out.print( i );
System.out.print( iInputString.substring(j+i, iInputString.length()  ) );
System.out.print( "\n" );
}
}
}
}``````

I believe the total number of possible combinations would be 1+2+.....+(n-2) where n is the length of the string.

Sample output of above program is like
==============================
c1reercup
ca1eercup
car1ercup
care1rcup
caree1cup
career1up
careerc1p
c2eercup
ca2ercup
car2rcup
care2cup
caree2up
career2p
c3ercup
ca3rcup
car3cup
care3up
caree3p
c4rcup
ca4cup
car4up
care4p
c5cup
ca5up
car5p
c6up
ca6p
c7p

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

``````void gen_i18n(const std::string& s)
{
auto len = s.length();
for (auto i = len - 2; i >= 1; --i)
{
for (auto p = 1; p + i <= len - 1; ++p)
{
std::ostringstream oss;
oss << s.substr(0, p);
oss << i;
oss << s.substr(p + i, len - (p + i));
std::cout << oss.str() << std::endl;
}
}
std::cout << s << std::endl;
}``````

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

``````public static void stringManip(String inputLine){
int i,j;
int n = inputLine.length();
System.out.println(inputLine);
for(j=n;j>1;j--){
for(i =1;i<inputLine.length()-1 && (inputLine.substring(i,j-1).length() !=0);i++){
System.out.println(inputLine.substring(0,i)+""+inputLine.substring(i,j-1).length()+""+inputLine.substring(j-1));
}//end of i
}//end of j
}``````

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

``````public static void stringManip(String inputLine){
int i,j;
int n = inputLine.length();
System.out.println(inputLine);
for(j=n;j>1;j--){
for(i =1;i<inputLine.length()-1 && (inputLine.substring(i,j-1).length() !=0);i++){
System.out.println(inputLine.substring(0,i)+""+inputLine.substring(i,j-1).length()+""+inputLine.substring(j-1));
}//end of i
}//end of j
}``````

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

This is a lovely question that check your understanding for String processing. This is my working Java code.

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

public class i18nGenerator {

public static List<String> generate(String input) {
int workAreaLength = input.length() - 2;
List<String> output = new ArrayList<String>();

if (input.length() <= 2) {
return output;
}

for (int i = 1; i <= workAreaLength; ++i) {
int startFrom = 1;
int windowLength = i;

while ((startFrom + windowLength) <= input.length() - 1) {
String sub1 = input.substring(0, startFrom);
String sub2 = input.substring(startFrom + windowLength);

++startFrom;
}
}

return output;
}

public static void main(String []args) {
List<String> output = generate("careercup");

for (String s : output) {
System.out.println(s);
}

}
}``````

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

``F(ANB) = {print(ANB); if(N>0) {F(ACN-1B), F(AN-1DB), F(ACN-2DB)}}``

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

``````public void printI18NStrings(String s) {
int n = s.length() - 1;

while(n > 0) {
genStrings(s, n);
n--;
}
}

private void genStrings(String s, int n) {

int idx = 1;
String prefix = null;
String suffix = null;

while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}``````

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

``````public void printI18NStrings(String s) {
int n = s.length() - 1;

while(n > 0) {
genStrings(s, n);
n--;
}
}

private void genStrings(String s, int n) {

int idx = 1;
String prefix = null;
String suffix = null;

while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}``````

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

``````public void printI18NStrings(String s) {
int n = s.length() - 1;

while(n > 0) {
genStrings(s, n);
n--;
}
}

private void genStrings(String s, int n) {

int idx = 1;
String prefix = null;
String suffix = null;

while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}``````

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

``````public void printI18NStrings(String s) {
int n = s.length() - 1;

while(n > 0) {
genStrings(s, n);
n--;
}
}

private void genStrings(String s, int n) {

int idx = 1;
String prefix = null;
String suffix = null;

while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}``````

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

``````public void printI18NStrings(String s) {
int n = s.length() - 1;

while(n > 0) {
genStrings(s, n);
n--;
}
}

private void genStrings(String s, int n) {

int idx = 1;
String prefix = null;
String suffix = null;

while(idx + n < s.length() ) {
prefix = s.substring(0, idx);
suffix = s.substring(idx +n);
System.out.println(prefix + n + suffix);
idx++;
}
}``````

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

``````import (
"fmt"
"strconv"
)

func i18n(word string) []string {
// Map to store the result
// This avoids duplicates
m := make(map[string]struct{})
for i, j := len(word)-2, 1; i > 0; i, j = i-1, j+1 {
for k := 1; k <= j; k++  {
w := word[:k] + strconv.Itoa(i) + word[i+k:]
m[w] = struct{}{}
}
}
m[word] = struct{}{}
// Extract the keys from the map
result := make([]string, len(m))
i := 0
for k := range m {
result[i] = k
i += 1
}
return result
}``````

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

``````private static void Printi8n(string input)
{
if (string.IsNullOrEmpty(input))
return;

int length = input.Length;
for (int i = 1; i < length; i++)
{
int substrLen = input.Substring(i, length - i - 1).Length;
string result = input.Substring(0, i) + (substrLen > 0 ? substrLen.ToString() : "") + input[length - 1];
Console.WriteLine(result);
}
}``````

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

Here is a simple C# function to do this:

``````private static void Printi8n(string input)
{
if (string.IsNullOrEmpty(input))
return;

int length = input.Length;
for (int i = 1; i < length; i++)
{
int substrLen = input.Substring(i, length - i - 1).Length;
string result = input.Substring(0, i) + (substrLen > 0 ? substrLen.ToString() : "") + input[length - 1];
Console.WriteLine(result);
}
}``````

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

``````public static void i18n(String input) {

if(input == null || input.length() < 3) {
print("Input error.");
return;
}
int ipLen = input.length();
StringBuffer buff = new StringBuffer(input);
for(int i = 1; i < ipLen - 1; i++) {
//print("replace length = " + i);
for(int k = 1; k < ipLen - i; k++) {
//print("inner loop: k = " + k);
replace(buff, k, i);
buff.setLength(0);
buff.append(input);
}
}
}

private static void replace(StringBuffer buff, int start, int len) {
buff.replace(start, start + len, String.valueOf(len));
print(buff.toString());
}

public static void print(String msg) {
if(msg != null)
System.out.println(msg);
}``````

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

I looked at this problem like a simple but unreliable string compression. Basically, each compressible word is divided into 3 parts:
2. The body, aka the number
3. The footer
So this solution finds what I called the middle word and then finds all substrings of that middle word possible. And then for each of those, builds a possible result.

``````var simplifyWord = function(word){
var middleWord = word.substring(1, word.length-1);
var max = middleWord.length;
var possibleCompressions = [];

// Check if length is > 3
if(word.length < 3)
return possibleCompressions;

for(var i = 0; i < middleWord.length; i++){
var sub = "";
for(var k = 0; k < max; k++){
sub += middleWord[i+k];
var currentWordFooter = word.substring(currentWordHeader.length + sub.length);
}
max--;
}
return possibleCompressions;
}``````

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

``````package crackingCode;

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

public class I18N {

public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}

private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();

for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
}
}

for (String s : strings) {
int numberString = subStringLength - s.length();

for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);

}
}

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

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

package crackingCode;

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

public class I18N {

public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}

private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();

for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
}
}

for (String s : strings) {
int numberString = subStringLength - s.length();

for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);

}
}

System.out.println(newStrings);
}
}

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

``````package crackingCode;

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

public class I18N {

public static void main(String args[]) {
String x = "careercup";
generateAllPossibleString(x);
}

private static void generateAllPossibleString(String x) {
// All the Strings
List<String> strings = new ArrayList<String>();
List<String> newStrings = new ArrayList<String>();
String subString = x.substring(1, x.length());
int subStringLength = subString.length();

for (int i = 0; i < subString.length(); i++) {
StringBuffer start = new StringBuffer();
start.append(subString.charAt(i));
for (int j = i + 1; j < subString.length(); j++) {
start.append(subString.charAt(j));
}
}

for (String s : strings) {
int numberString = subStringLength - s.length();

for (int p = 0; p < s.length(); p++) {
String newString = x.charAt(0) + s.substring(0, p)
+ numberString + s.substring(p, s.length() - 1)
+ x.charAt(x.length() - 1);

}
}

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

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

``````/* C implementation */

void print_i18n(char *str)
{
if (!str) return;

/* minimum three character string is required */
int l = strlen(str);
if (l < 3) {
return;
}

char out[16];

/*
* Two chars are consumed by first and last positions which are
* fixed, so started with l - 2 to 1
*
* In inner loop start placing 'n' as character to each possible
* position. i.e. length of prefix (before number) + characters
* consumed by n are within limit (p + n < l)
*
* Then -
*  - copy prefix (first p characters)
*  - Append number
*  - copy suffix after skipping n characters
*/
for (int n = l - 2; n > 0; n--) {
for (int p = 1; p + n < l; ++p) {
strncpy(out, str, p);
out[p] = '0' + n;
strcpy(out + p + 1, str + p + n);
printf("%s\n", out);
}
}
}``````

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

``````public class Main {

public static void main(String[] args) {
// input
String input =  "LavenderFarms";

// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);

for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+  ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);

Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}``````

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

``````public class Main {

public static void main(String[] args) {
// input
String input =  "LavenderFarms";

// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);

for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+  ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);

Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}``````

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

``````public class Main {

public static void main(String[] args) {
// input
String input =  "LavenderFarms";

// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);

for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+  ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);

Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}``````

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

``````public class Main {

public static void main(String[] args) {
// input
String input =  "LavenderFarms";

// for all the char in the input, except the start and end, we will look up input char and
// append it to the result
StringBuilder result_sb = new StringBuilder();
int Factor = input.length() - 2;
result_sb.append(input.toCharArray()[0]);

for(int i=1; i < input.length(); i++){
System.out.println(result_sb.toString()
+  ( Factor > 0 ? Integer.toString(Factor) : "" )
+ input.toCharArray()[input.length() - 1]);

Factor -- ;
result_sb.append(input.toCharArray()[i]);
}
}
}``````

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

I am not clear about the question, actually answer. The combination of output is confusing. Can you provide full set of output for a simple example say "Google"

Will all these be part of the output?
g1ogle
go1gle
goo1le
goog1e

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

``````private void printCombination(String inputStr){
int length = inputStr.length();
int startCharCount = 2;
while(startCharCount < inputStr.length()){
Map<Integer, Integer> numberMap = getSumCombination(startCharCount++);
for(Integer key : numberMap.keySet()){
String str1 = inputStr.substring(0, key);
String str2 = inputStr.substring(inputStr.length()-numberMap.get(key), inputStr.length());
int count = inputStr.length()-(str1.length()+str2.length());
System.out.println(""+str1+"-"+count+"-"+str2);

}
}
}
/**
*
* @param startCharCount
* @return
*/
private Map getSumCombination(int startCharCount) {
int i=1;
int j=startCharCount-1;
Map numberMap = new HashMap();
numberMap.put(i, j);
while(j > 1){
numberMap.put(++i, --j);
}
return numberMap;
}``````

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

``````private void printCombination(String inputStr){
int length = inputStr.length();
int startCharCount = 2;
while(startCharCount < inputStr.length()){
Map<Integer, Integer> numberMap = getSumCombination(startCharCount++);
for(Integer key : numberMap.keySet()){
String str1 = inputStr.substring(0, key);
String str2 = inputStr.substring(inputStr.length()-numberMap.get(key), inputStr.length());
int count = inputStr.length()-(str1.length()+str2.length());
System.out.println(""+str1+"-"+count+"-"+str2);

}
}
}
/**
*
* @param startCharCount
* @return
*/
private Map getSumCombination(int startCharCount) {
int i=1;
int j=startCharCount-1;
Map numberMap = new HashMap();
numberMap.put(i, j);
while(j > 1){
numberMap.put(++i, --j);
}
return numberMap;
}``````

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

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

void print(char[],int);

int main()
{
char a[100],ch;
int i=0,l,len_a,j,no,b;
while((ch=getchar())!='\n')
a[i++]=ch;
a[i]='\0';
print(a,strlen(a));
}

void print(char a[],int size)
{
int b,no,i,j,l;
l=size-2;
no=1;
while(l)
{
b=no;
j=0;
while(b)
{
for(i=0;i<=j;i++)
printf("%c ",a[i]);
printf("%d ",l);
for(i=l+j+1;i<size;i++)
printf("%c ",a[i]);
printf("\n");
b--;
j++;
}
no++;
l--;
}
}

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

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

public class prog3 {
//List<String> s2 = new ArrayList<String>();
public static void main(String[] args) {
String s = "careercup";

generate_set1(s, 1, s.length());
generate_set2(s,1,s.length());

}

public static void generate_set2(String s,int i,int j)
{
if(i>=j)
{
return;
}
else
{
for(i=1;i<s.length();i++)
{
if(j-(i+2)>0)
{
String s1 =s.substring(0,i)+(j-(i+2))+s.substring(s.length()-2);
System.out.println(s1);

}

else
{
String s1 = s.substring(0,i)+s.substring(s.length()-1);
System.out.println(s1);
}
}
}
}

public static void generate_set1(String s, int i, int j) {

if (i >= j) {

return;
} else {
for (i = 1; i < s.length(); i++) {
if (j - (i + 1) > 0) {
String s1 = s.substring(0, i) + (j - (i + 1)) + s.substring(s.length() - 1);
System.out.println(s1);
} else {
String s1 = s.substring(0, i) + s.substring(s.length() - 1);
System.out.println(s1);
}
}

}

}
}``````

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

void print(char a[],int size)
{
int b,no,i,j,l;
l=size-2;
no=1;
while(l)
{
b=no;
j=0;
while(b)
{
for(i=0;i<=j;i++)
printf("%c ",a[i]);
printf("%d ",l);
for(i=l+j+1;i<size;i++)
printf("%c ",a[i]);
printf("\n");
b--;
j++;
}
no++;
l--;
}
}

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

Hi I like a lot of the solutions already proposed, the idea with this one is to cache the already used strings so no need to reuse the SubString method repeatedly.

``````public List<string> CreateIstrings(string s)
{
List<string> result = new List<string>();

if (s == null || s.Length <= 2)
return result;

int index = 1;
int n = s.Length - 2;
string[] list1 = new string[n];
string[] list2 = new string[n];
string a = new string(s[0], 1);
string b = new string(s[s.Length - 1], 1);

for (int i = n; i >= 1; i--)
{
list1[index - 1] = a;
list2[n - index] = b;

for (int j = 0, k = n - index; j < index; j++, k++)

a += s[index];
b = s[s.Length - 1 - index] + b;
index++;
}

return result;
}``````

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

``````public class I18n{

public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;

for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}``````

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

``````public class I18n{

public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;

for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}``````

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

``````public class I18n{

public static void main(String[] args){
String local = "careercup";
int strLen = local.length();
int delta = 0;

for(int i=1; i<strLen; i++){
delta = strLen-i-1;
for(int j=delta; j>0 ; j--){
System.out.println(local.substring(0,i)+j+local.substring(j+i, strLen));
}
}
}
}``````

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

C++ code

``````#include <iostream>
#include <string>
using namespace std;
void print_all(const string begin, const string  middle, const string end) {
if(middle.length()==0)
cout<<begin<<end<<endl;
else {
for(int i=middle.length();i>0;i--)
cout<<begin<<i<<middle.substr(i,middle.length()-i)<<end<<endl;
print_all(begin+middle.front(),middle.substr(1,middle.length()-1),end);
}
}
int main() {
print_all("i","nternationalizatio","n");
}``````

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

``````#include<iostream>
#include<string>
using namespace std;

void function(string str, int count)
{
if(count<0)
return;
else if(count==0)
return;
else
{
int len = str.length();
for(int i=0;i<len-1-count;i++)
{
cout<<str[0];
for(int j=0;j<i;j++)
cout<<str[1+j];
cout<<count;
for(int j=count+1+i;j<len-1;j++)
cout<<str[j];
cout<<str[len-1];
cout<<" ";
}
cout<<endl<<endl;
if(count>=0)
function(str, count-1);
}
}

int main()
{
string str = "careercup";

function(str, str.length()-2);

system("PAUSE");
return 0;
}``````

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

``````public List<String> solve(String input) {
List<String> res = new ArrayList<String>();

int n = input.length();

for (int i = 1; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
String s = input.substring(0, i) + String.valueOf(j - i) + input.substring(j);
}
}

return res;
}``````

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

``````void printPermutations(string str, int head, int gap) {
for (int i = 0; i < head;i++) {
cout << str[i];
}
cout << gap;
for (int i = head + gap; i < str.size(); i++) {
cout << str[i];
}
cout << "\n";
}

void getPermutations(string str, int gap) {

int tail = gap;
while (tail < str.size() - 1) {
tail++;
}
}

void i18n(string str) {
for (int i = str.size() - 2; i > 0; i--;) {
getPermutations(str, i);
}
}``````

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

``````594 void print_i18n(char *S, int i, int j, int n) {
595
596     int k=0;
597
598     while(k<=i){
599         printf("%c", S[k]);
600         k++;
601     }
602     printf("%d", j-(i+1));
603     while(j<=n){
604         printf("%c", S[j]);
605         j++;
606     }
607     printf("\n");
608 }
609
610 void i18n(char *S, int i, int j, int n) {
611
612     if(j-i == 1)
613         return;
614
615     print_i18n(S, i, j, n);
616
617     i18n(S, i+1, j, n);
618     i18n(S, i, j-1, n);
619``````

}

call this function like this : i18n(S, 0, n-1, n-1);
where n is length of the string

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

``````function abbreviations(\$s){
\$middle = substr(\$s, 1, strlen(\$s) - 2);
for(\$i=1; \$i<strlen(\$s)-2; \$i++){
echo \$s[0] . substr(\$middle, 0, \$i) . (strlen(\$s)-2 - \$i) . \$s[strlen(\$s)-1] . '<br/>';
echo \$s[0] . (strlen(\$s)-2 - \$i) . substr(\$middle, strlen(\$s)-2 - \$i, \$i) . \$s[strlen(\$s)-1] . '<br/>';
}
echo \$s[0] . ( strlen(\$s) - 2) . \$s[strlen(\$s)-1];
}``````

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[10],str1[19];
int len,i,j,k,l;
printf(" enter the string:=>");
scanf("%s",str);

len=strlen(str);
for(i=0;i<len-1;i++)
{
for(j=0;j<=i;j++)

str1[j]=str[j];

str1[j]=str[len-1];
str1[++j]='\0';
printf("\n");
for(l=0;l<i+2;l++)
{
if(l==i+1)
printf("%d",len-(i+2));

printf("%c",str1[l]);
}

if(i>0)
{
int m,len2;
len2=len-2;
printf("\n");
for(m=0;m<i;m++)
{
printf("%c",str[m]);
}
printf("%d",len-(i+2));
for(j=0;j<2;j++)
printf("%c",str[len2++]);

}

}

return 0;

}

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

Not sure if somebody has already suggested this approach, we can easily solve this by recursion.

We also need to maintain a hash table to eliminate duplicates

The pseudo code would be as follows

``````generatei18n(str, sPos, ePos){
i  = (ePos - sPos) - 1
if( i <= 0) return
rs = str.subString(0,sPos)+ i + str.subString(ePos);
generatei18n(str, sPos+1, ePos)
generatei18n(str, sPos, ePos-1)

}``````

The time complexity would be !n.

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.