Google Interview Question for Software Developers


Country: India
Interview Type: Written Test




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

coded 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;
}

- whitehead June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

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;

- Anonymous May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#Coded in Python

a='hey'
b='sam'
import random
ans=['']*720
for i in range(720):
    aa=0
    bb=0
    temp=''
    while aa<len(a) or bb<len(b):
        r=random.randint(0,1)
        if r==0:
            temp+=a[aa:aa+1]
            aa+=1
            print(temp)
        else:
            temp+=b[bb:bb+1]
            bb+=1
            print(temp)
    ans[i]=temp
    
set(ans)

- Krishna Vijaywargiy May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]
	}
}

- Ameya Naik May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- SK May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
*/

- guilhebl May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- gustavo.andriotti May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- email@genesis.re May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python:

def merge_strings(s1, s2):
	def rec(a, b, i):
		if len(a) == 0 or i >= len(b):
			return [b + a]
		else:
			return rec(a[1:], b[:i] + a[0] + b[i:], i+1) + rec(a, b, i+1)
	return rec(s1, s2, 0)

- Amitai May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Rohit May 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
    }


}

- akshay May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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);
	        }
	}
}

- Hamender May 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- whitehead June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- whitehead June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
/*

- Robert July 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}
	}
}

- AbdallahCh89 July 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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']

- akak18183 September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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' ) )

- NoOne November 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def merge(s1, s2, out):
    if s1 == "":
        print out+s2
        return
    
    if s2 == "":
        print out+s1
        return
    
    merge(s1[1:], s2, out+s1[0])
    merge(s1, s2[1:], out+s2[0])

merge("hey", "sam", "")

- Nitish Garg January 16, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More