Google Interview Question for Software Engineers


Country: United States




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

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    long factorial(long n){
        long fact = 1;
        for (long i = 1; i<= n; ++i)
            fact *= i;
        return fact;
    }

    void DFS(const string &s1, int m, int i,
    const string&s2, int n, int j,
    string path,vector<string> &ret){
        if(i==m &&j==n)  {
            ret.push_back(path);
            return;
        }
        if(i < m)  DFS(s1, m, i+1, s2, n, j, path+s1, ret);
        if(j < n)  DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);
    }

    vector<string> combineTowStrings(const string &s1,const string &s2) {
        int m =s1.length(), n = s2.length();
        long count =factorial(m+n)/factorial(n)/factorial(m);
        cout <<"count:" << count << endl;
        vector<string> ret;
        DFS(s1, m, 0, s2,n, 0, "", ret);
        return ret;
    }

    int main() {
        vector<string> ret = combineTowStrings("AB","CDF");
        cout <<ret.size() << endl;
        for(string &s: ret)  cout << s << endl;
        return 0;

}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.

All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

- aonecoding4 January 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class Main {

    public static void main(String[] args) {
        String s1 = "main"; //"abc";
        String s2 = "view"; //"de";

        List<String> res = new ArrayList<>();
        mergeStrings(s1, s2, 0, 0, "", res);

        System.out.println("Number of combinations: " + res.size());
        for (String s : res) {
            System.out.println(s);
        }
    }

    private static void mergeStrings(String s1, String s2, int pos1, int pos2, String curr, List<String> res) {
        if (pos1 == s1.length()) {
            res.add(curr + s2.substring(pos2));
            return;
        }

        if (pos2 == s2.length()) {
            res.add(curr + s1.substring(pos1));
            return;
        }
        mergeStrings(s1, s2, pos1 + 1, pos2, curr + s1.charAt(pos1), res);
        mergeStrings(s1, s2, pos1, pos2+1, curr + s2.charAt(pos2), res);
    }
}

- mykolaba February 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is anagram once two strings are concatenated.
So, simply add two strings and run anagram algorithm.
The complexity is (m +n) !

package algorithm;

import static java.lang.System.out;

public class Anagram {
public void anagram(String prefix, String word) {
if (word.length() <= 1) {
out.println(prefix + word);
return;
}

for (int i = 0; i < word.length(); i++) {
String before = word.substring(0, i); // letters before cur
String cur = word.substring(i, i + 1);
String after = word.substring(i + 1); // letters after cur
anagram(prefix + cur, before + after);
}
}

public static void main(String[] args) {
Anagram anagram = new Anagram();
String s1 = "...";
String s2 = "......";
anagram.anagram("", s1+s2);
}
}

- Anonymous February 02, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't agree. The question states you need to maintain the sequence of characters, so it is not simple anagram.

- WMT February 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(m+n)! , but since the order of elements in string 1 n 2 should remain same. No of ways : (m+n)!/(m!xn!)

- anshuk2305 February 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

from collections import deque
import math
s1 = 'abc'
s2 = '12'

def string_combine(s1, s2):
    s1 = deque(s1)
    s2 = deque(s2)
    s = deque()
    __str_combine(s1, s2, s)

def __str_combine(s1, s2, s):
    if len(s1) == 0 and len(s2) == 0:
        print(s)
    else:
        if len(s1) > 0:
            s.append(s1.popleft())
            __str_combine(s1, s2, s)
            s1.appendleft(s.pop())
        if len(s2) > 0:
            s.append(s2.popleft())
            __str_combine(s1, s2, s)
            s2.appendleft(s.pop())


def string_combination_count(s1, s2):
    # think m+n as slots 
    # and choosing positions for chars in min length string without order in those slots
    m = len(s1)
    n = len(s2)
    to_choose = min(m,n)
    slots = m+n
    return int(math.factorial(slots) / (math.factorial(to_choose) * math.factorial(slots - to_choose)))

string_combine(s1, s2)
print(string_combination_count(s1, s2))

- foobar February 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

here is a simple solution

package main

import (
	"bytes"
	"fmt"
)

func mergeStrings(s1, s2 string) string {
	var merged bytes.Buffer
	var i, j int
	for i < len(s1) && j < len(s2) {
		//fmt.Printf("i and j are %d, %d \n", i, j)
		if s1[i] < s2[j] {
			merged.WriteString(string(s1[i]))
			i += 1
		} else if s1[i] > s2[j] {
			merged.WriteString(string(s2[j]))
			j += 1
		} else {
			merged.WriteString(string(s1[i]))
			i += 1
			j += 1
		}
	}

	if i < len(s1) {
		for i < len(s1) {
			merged.WriteString(string(s1[i]))
			i += 1
		}
	}

	if j < len(s2) {
		for j < len(s2) {
			merged.WriteString(string(s2[j]))
			j += 1
		}
	}

	return merged.String()
}

func main() {
	str1 := "ace"
	str2 := "bdf"
	merged := mergeStrings(str1, str2)
	fmt.Printf("Merged str is %s", merged)
}

- logiclogy February 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main

import (
	"bytes"
	"fmt"
)

func mergeStrings(s1, s2 string) string {
	var merged bytes.Buffer
	var i, j int
	for i < len(s1) && j < len(s2) {
		//fmt.Printf("i and j are %d, %d \n", i, j)
		if s1[i] < s2[j] {
			merged.WriteString(string(s1[i]))
			i += 1
		} else if s1[i] > s2[j] {
			merged.WriteString(string(s2[j]))
			j += 1
		} else {
			merged.WriteString(string(s1[i]))
			i += 1
			j += 1
		}
	}

	if i < len(s1) {
		for i < len(s1) {
			merged.WriteString(string(s1[i]))
			i += 1
		}
	}

	if j < len(s2) {
		for j < len(s2) {
			merged.WriteString(string(s2[j]))
			j += 1
		}
	}

	return merged.String()
}

func main() {
	str1 := "ace"
	str2 := "bdf"
	merged := mergeStrings(str1, str2)
	fmt.Printf("Merged str is %s", merged)
}

- Anonymous February 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef map<__int64, vector<std::string>> _subset_map;
void getMerges(const std::string& a, const std::string&b, const std::string& prefix, _subset_map& subsets, vector<std::string>& ret)
{
	if (a.size() == 0 && b.size() == 0)
	{
		ret.push_back(prefix);
		return;
	}
	__int64 key = a.size();
	key = (key << 32) | b.size();
	_subset_map::const_iterator f = subsets.find(key);
	const vector<std::string>* sub_vector;
	if (f == subsets.end())
	{
		vector<std::string>& sub = subsets[key];
		if(a.size()>0)
			getMerges(a.substr(1), b, std::string(1, a[0]), subsets, sub);
		if (b.size()>0)
			getMerges(a, b.substr(1), std::string(1, b[0]), subsets, sub);
		sub_vector = &sub;
	}
	else
	{
		sub_vector = &(f->second);
	}
	for (int i = 0, n = sub_vector->size(); i<n; i++)
		ret.push_back(prefix + sub_vector->at(i));
}
void getMerges(const std::string& a, const std::string& b, vector<std::string>& ret)
{
	_subset_map subsets;
	getMerges(a, b, "", subsets, ret);
}

- lesit.jae February 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can simply reduce the problem to combinatorics solution.

e.g., how many ways a I can arrange m red and n blue balls.
Answer is (m+n)!/m!*n!

- MJShop February 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {

public static void main(String[] args) {
String s1 = "main"; //"abc";
String s2 = "view"; //"de";

List<String> res = new ArrayList<>();
mergeStrings(s1, s2, 0, 0, "", res);

System.out.println("Number of combinations: " + res.size());
for (String s : res) {
System.out.println(s);
}
}

private static void mergeStrings(String s1, String s2, int pos1, int pos2, String curr, List<String> res) {
if (pos1 == s1.length()) {
res.add(curr + s2.substring(pos2));
return;
}

if (pos2 == s2.length()) {
res.add(curr + s1.substring(pos1));
return;
}
mergeStrings(s1, s2, pos1 + 1, pos2, curr + s1.charAt(pos1), res);
mergeStrings(s1, s2, pos1, pos2+1, curr + s2.charAt(pos2), res);
}
}

- mykolaba February 13, 2019 | 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