Google Interview Question
Software DevelopersCountry: India
Interview Type: Written Test
void printCombos(string s1, string s2, string cur, set<string> & ans) {
if (s1 == "" && s2 == "") {
ans.insert(cur);
return;
}
if (s1 == "") {
ans.insert(cur + s2);
return;
}
if (s2 == "") {
ans.insert(cur + s1);
return;
}
for (int i = 0; i <= s2.size(); i++) {
string toAdd = s2.substr(0, i);
printCombos(s1.substr(1, s1.size()-1), s2.substr(i, s2.size()-i), cur + toAdd + s1[0], ans);
}
}
set<string> ans;
printCombos("hey", "sam", "", ans);
for (auto s : ans) cout << s << endl;
The question is somewhat similar to 'merging two sorted arrays' / just we need to take care of combinations.
Check out my implementation:
/*
* An attempt to solve CareerCup question
* Ref: https :// careercup.com/question?id=5663263489523712
*
* IdeOne: http :// ideone.com/84nDvP
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
public static void mergeStrings(String a, String b, int start, String str, List<String> result) {
int len = a.length() - start;
// System.out.println("start " + start + " / str = " + str);
if (len == 0) {
result.add(str);
return;
}
for (int i = 0; i < len; i++) {
String subA = a.substring(start, start+i+1);
String subB = b.substring(start, start+i+1);
mergeStrings(a, b, start+i+1, (str + subA + subB), result);
}
}
private static List<String> mergeStrings(String a, String b) {
if (a == null
|| b == null
|| a.length() != b.length()) {
String message = "Strings must be of equal length";
System.out.println(message);
// throw new IllegalArgumentException("Strings must be of equal length");
return null;
}
List<String> result = new ArrayList<String>();
mergeStrings(a, b, 0, "", result);
mergeStrings(b, a, 0, "", result);
return result;
}
public static void main (String[] args) throws java.lang.Exception
{
String a = "hey";
String b = "sam";
List<String> merged = mergeStrings(a, b);
System.out.println(merged);
// Output: [hseaym, hseyam, hesaym, heysam, shaemy, shamey, sahemy, samhey]
}
}
public static void possibleStringsUtil(String s1, int i, String s2, int j, List<String> wordList, String current) {
if(current.length() == s1.length() + s2.length()) {
wordList.add(current);
return;
}
if(i < s1.length())
possibleStringsUtil(s1, i+1, s2, j, wordList, current + s1.charAt(i));
if(j < s2.length())
possibleStringsUtil(s1, i, s2, j+1, wordList, current + s2.charAt(j));
}
public static List<String> possibleStrings(String s1, String s2) {
List<String> wordList = new ArrayList<String>();
possibleStringsUtil(s1, 0, s2, 0, wordList, "");
return wordList;
}
public class Solution {
public static void main(String[] args) {
Set<String> stringSet = new HashSet<String>();
getPermutationOfStringFiltered("heysam".toCharArray(), 0, "hey", "sam", stringSet);
List<String> strs = stringSet.stream().sorted().collect(Collectors.toList());
printSets(strs);
}
public static void getPermutationOfStringFiltered(char[] a, int i, String s1, String s2, Set<String> stringSet) {
if (i == a.length) {
String s = new String(a);
if (isValidString(s, s1.toCharArray()) && isValidString(s, s2.toCharArray())) {
stringSet.add(s);
}
} else if (i < a.length) {
for (int j = i; j < a.length; j++) {
swap(a, i, j);
getPermutationOfStringFiltered(a, i + 1, s1, s2, stringSet);
swap(a, i, j);
}
}
}
private static boolean isValidString(String string, char[] c) {
int index = -1;
int indexNext = -1;
for (int i = 0; i + 1 < c.length; i++) {
index = string.indexOf(c[i]);
indexNext = string.lastIndexOf(c[i + 1]);
if (index >= indexNext) {
return false;
}
}
return true;
}
private static void swapElements(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// generates:
/*
hesamy
hesaym
hesyam
heysam
hsaemy
hsaeym
hsamey
hseamy
hseaym
hseyam
sahemy
saheym
sahmey
samhey
shaemy
shaeym
shamey
sheamy
sheaym
sheyam
*/
In python:
def merge_strings(str_a, str_b):
result = []
first_a = [s for s in _get_all_comb_start_with_a(str_a, str_b)]
first_b = [s for s in _get_all_comb_start_with_a(str_b, str_a)]
result.extend(first_a)
result.extend(first_b)
return result
def _get_all_comb_start_with_a(str_a, str_b):
total_a = len(str_a)
total_b = len(str_b)
for qtd_slices_a in xrange(1, min(total_a, total_b + 1) + 1):
for slices_a in _get_all_possible_slices(str_a, qtd_slices_a):
for qtd_slices_b in xrange(max(1, qtd_slices_a - 1), min(qtd_slices_a, total_b) + 1):
for slices_b in _get_all_possible_slices(str_b, qtd_slices_b):
yield _combine_slices_start_with_a(slices_a, slices_b)
def _get_all_possible_slices(in_str, qtd_slices):
'''
'asdf', 1 -> 0
'asdf', 2 -> 0,1; 0,2; 0,3; 1,3; 2,3;
'asdf', 3 -> 0,1,2; 0,1,3; 0,2,3; 1,2,3;
'asdf', 4 -> 0,1,2,3
'''
first = 0
last = len(in_str)
pivots = [first] + [i for i in xrange(first + 1, qtd_slices)] + [last]
if len(pivots) <= 2:
yield _get_str_slices_from_pivots(in_str, pivots)
for piv_ndx in xrange(len(pivots) - 2, 0, -1):
start_val = pivots[piv_ndx]
end_val = pivots[piv_ndx + 1]
for ndx_val in xrange(start_val, end_val):
pivots[piv_ndx] = ndx_val
str_partial = _get_str_slices_from_pivots(in_str, pivots)
yield str_partial
def _get_str_slices_from_pivots(in_str, pivots):
partial = []
for i in xrange(len(pivots) - 1):
pair = (pivots[i], pivots[i+1])
partial.append(pair)
str_partial = [in_str[p[0]:p[1]] for p in partial]
return str_partial
def _combine_slices_start_with_a(slices_a, slices_b):
result = ''
len_a = len(slices_a)
len_b = len(slices_b)
for i in xrange(min(len_a, len_b)):
result += slices_a[i] + slices_b[i]
if len_a > len_b:
result += slices_a[-1]
return result
Test:
tst = [
('a', 'c', set(['ac', 'ca'])),
('abc', 'def', set(['dabecf', 'daefbc', 'adebfc', 'adefbc', 'deabfc', 'abdefc', 'adbecf', 'deafbc', 'dabefc', 'defabc', 'daebcf', 'deabcf', 'dabcef', 'abdcef', 'daebfc', 'adbefc', 'abdecf', 'adbcef', 'abcdef', 'adebcf'])),
('ab', 'cd', set(['abcd', 'cdab', 'acbd', 'cadb', 'acdb', 'cabd'])),
('ab', 'c', set(['abc', 'cab', 'acb'])),
]
for str_a, str_b, exp in tst:
res = set([ s for s in merge_strings(str_a, str_b)])
assert exp == res, '{}, {} -> {} != {}'.format(str_a, str_b, res, exp)
print '{}, {} -> {}'.format(str_a, str_b, res)
var answer = [];
var merge = function(s1, s2, curr) {
if(s1.length === 0 && s2.length === 0) {
answer.push(curr);
return
}
if(s1.length === 0) {
answer.push(curr + s2);
return ;
}
if(s2.length === 0) {
answer.push(curr + s1);
return ;
}
for(var i=0; i<=s2.length; i++) {
var toAdd = s2.substr(0,i);
merge(s1.substr(1, s1.length-1), s2.substr(i, s2.length-i), curr + toAdd + s1[0]);
}
}
merge("hey", "sam", "");
console.log(answer);
JavaScript, based on "anonymous" submission.
static List<String> combos(String a, String b){
int length = a.length() + b.length();
double total = Math.pow(2, length);
List<String> list = new ArrayList<>();
for(int i = 0; i < total; i++){
String s = "";
int ai = 0, bi = 0;
for(int j = 0; j < length; j++){
int ab = (i >> j) & 0x1;
if(ab == 0 && ai < a.length()){
s += a.charAt(ai++);
} else if(ab == 1 && bi < b.length()) {
s += b.charAt(bi++);
} else {
s = "";
break;
}
}
if (!s.equals("")) {
list.add(s);
}
}
return list;
}
Here is code to merge strings where order is same for both
public class MergeStringWithOrder {
public static void merge(String parent,String str1,String str2){
if (str1 == null || "".equals(str1)) {
System.out.println(parent+str2);
return;
} else if (str2==null || "".equals(str2)) {
System.out.println(parent+str1);
return;
}
merge(parent+str1.substring(0,1),str1.substring(1),str2);
merge(parent+str2.substring(0,1),str1,str2.substring(1));
}
public static void main(String a[]){
merge("","hey","sam");
}
}
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
String a="sam";
String b="hey";
StringBuilder out1=new StringBuilder();
out1.append(a);
generateSolUtil(out1,a.length(),b,0,0);
}
static void generateSolUtil(StringBuilder out1,int m,String b,int j,int start){
if(out1.length()==m+b.length()){
System.out.println(out1);
return;
}
else
for(int i=start;i<1+out1.length();i++){
out1.insert(i,b.charAt(j));
generateSolUtil(out1,m,b,j+1,i+1);
out1.deleteCharAt(i);
}
}
}
#include <iostream>
#include <string>
using namespace std;
void print_merge(string str1, string str2,
string out)
{
if (str1 == "") {
cout << out << str2 << endl;
return;
}
if (str2 == "") {
cout << out << str1 << endl;
return;
}
print_merge(str1.substr(1), str2, out + str1[0]);
print_merge(str1, str2.substr(1), out + str2[0]);
}
int main(void)
{
print_merge("hey", "sam", "");
return 0;
}
in c++
#include <iostream>
#include <string>
using namespace std;
void print_merge(string str1, string str2,
string out)
{
if (str1 == "") {
cout << out << str2 << endl;
return;
}
if (str2 == "") {
cout << out << str1 << endl;
return;
}
print_merge(str1.substr(1), str2, out + str1[0]);
print_merge(str1, str2.substr(1), out + str2[0]);
}
int main(void)
{
print_merge("hey", "sam", "");
return 0;
}
public class OrderedStringMerge {
public void merge(String f, String a, String b)
{
if (a.length()==0 || b.length()==0)
{
System.out.println(f+a+b);
return;
}
for (int i =0; i <= b.length(); i++)
merge(f+b.substring(0,i)+a.charAt(0),a.substring(1),b.substring(i));
}
public static void main(String argv[])
{
OrderedStringMerge osm = new OrderedStringMerge();
osm.merge("", "hey","Sam");
}
}
/* generates
heySam
heSyam
heSaym
heSamy
hSeyam
hSeaym
hSeamy
hSaeym
hSaemy
hSamey
Sheyam
Sheaym
Sheamy
Shaeym
Shaemy
Shamey
Saheym
Sahemy
Sahmey
Samhey
/*
import java.util.*;
public class mergeStr {
public static void main(String[] args) {
double startTime = System.currentTimeMillis();
String A = "Abdallah";
String B = "1234";
System.out.println(shuffleStr(A,B));
double stopTime = System.currentTimeMillis();
double elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
public static ArrayList <String> shuffleStr(String A, String B) {
ArrayList <String> strCombo = new ArrayList<String>();
int [] start = new int [B.length()+2]; //Inner indices are the locations of the B string chars
start[0] = -1; //Starting Index is predefined
start[start.length-1] = A.length() + B.length(); // Ending index is predefined.
strCombo = shuffleStr(strCombo, start, 1, 0, A.length(), A, B);
return strCombo;
}
public static ArrayList<String> shuffleStr(ArrayList<String> res, int [] start, int pos, int min, int max, String A, String B) {
//base case (add current shuffledStr)
if (pos == start.length-1) {
char [] addedStr = new char [A.length()+B.length()]; //
int locA = 0;
for (int i = 1; i < start.length; i++) { //Start directly from the inner
if (i != start.length-1) { addedStr[start[i]] = B.charAt(i-1); } //If still did not hit the outer index
//Fill in the String A (could be done using Strings). But, it is expensive to do substring
for (int j = start[i-1]+1; j < start[i]; j++) {
addedStr[j] = A.charAt(locA);
locA = locA + 1;
}
}
res.add(new String(addedStr)); //Add it .. Also could be done by appending a string: res = res + ....
return res;
}
//Recursion case
else {
for (int i = min; i <= max; i++) { //update char position of B, minimum location, max location
start[pos] = i;
res = shuffleStr(res, start, pos+1, i+1, max+1, A, B);
}
return res;
}
}
}
class Solution:
def merge(self, A, B):
if not A or not B:
return [A or B]
ret = []
for s in self.merge(A[1:], B):
ret.append(A[0] + s)
for s in self.merge(A, B[1:]):
ret.append(B[0] + s)
return ret
if __name__ == "__main__":
print(Solution().merge('hey', 'sam'))
# 20 results
# ['heysam', 'hesyam', 'hesaym', 'hesamy', 'hseyam', 'hseaym', 'hseamy',
# 'hsaeym', 'hsaemy', 'hsamey', 'sheyam', 'sheaym', 'sheamy', 'shaeym',
# 'shaemy', 'shamey', 'saheym', 'sahemy', 'sahmey', 'samhey']
/* ZoomBA.
Observe the problem can be solved fully declaratively.
Observe we can index the chars from the
1. first string as : 0,1,2,3,4...
2. second string as : -1,-2,-3,...
Now, join with condition:
all -ve should be sorted descending
all +ve should be sorted ascending .
then, map back to generate the merged string
*/
def merge_strings( s1, s2 ){
r1 = [ 0 : #|s1| ]
r2 = [ -1 : -#|s2| - 1: -1]
l = r1.list + r2.list
join_args = list( [0:#|l|] ) -> { l }
join ( @ARGS = join_args ) :: {
// must be unique
continue( #|set($.o)| != #|$.o| )
#(pos,neg) = partition( $.o ) :: { $.o >= 0 }
// sorted ascending? if previous > current then it is not
last = reduce( pos ) -> { break( $.p > $.o ){ null } ; $.o }
continue ( last == null )
// sorted descending? if previous < current then it is not
last = reduce( neg ) -> { break( $.p < $.o ){ null } ; $.o }
continue ( last == null )
// now map back the string as word
true } -> { fold( $.o , '' ) -> {
$.p += ( $.o >= 0 ? s1[ $.o ] : s2[ -$.o - 1] ) }
}
}
println( merge_strings( 'hey', 'sam' ) )
coded in c++
- whitehead June 10, 2016