## Google Interview Question for Software Engineer / Developers

Country: India

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

We could use Inclusion–exclusion principle AND dynamic programming. The time complexity can be reduced to polynomial.

Firstly, Inclusion–exclusion principle:

Define F(s, p) to be the no. of expressions whose result are divisible by number p. For example, F("011", 2) = 6, F("011", 3) = 3.

Define F(s, {p, q}) to be the no. of expressions whose result are divisible by at least one of the digit prime in {p, q}.

Then, by Inclusion–exclusion principle, F(s, {p, q}) = F(s, p) + F(s, q) - F(s, p * q)

We have F(s, {2, 3, 5, 7}) = F(s, 2) + F(s, 3) + F(s, 5) + F(s, 7) - F(s, 2 * 3) - ... + F(s, 2 * 3 * 5) + ... - F(s, 2 * 3 * 5 * 7)

Now, we use dynamic programming to find F(s, p).

let s[i:]be the suffix string start at index i,
let n be the length of string s.
let num[i:j] be the number converted from substring s[i:j] inclusive.

Define R[i][j] be the no. of expressions which are formed from substring s[i:] and the remainder is j while mod p. (0 <= i < n, 0 <= j < p)
For example, s = "011", p = 2, R[1][0] is the no. of expressions formed from substring "11" and the remainder is 0 while they mod 2. R[1][0] = 2, since (1 + 1) % 2 = 0, (1 - 1) % 2 = 0, and R[1][1] = 1, since 11 % 2 = 1.

R[i][j] can be calculated from sub-problems R[k][l], where (num[i:k -1] + l) % p == j or (num[i: k - 1] - l) % p == j, for all k > i and k < n.

Then R[i][j] = Sum(R[k][(j - num[i:k - 1]) % p] +R[k][(num[i:k - 1] - j) % p], k = i + 1, ..., n - 1)

We get F(s, p) from R[0][0].
Here is code:

``````int F(const string& s, int p) {
int n = s.size(), R[n][p];
memset(R, 0, sizeof(R));

for (int i = n - 1; i >= 0; i--) {
int first = s[i] - '0';

for (int k = i + 1; k < n; k++) {
for (int j = 0; j < p; j++) {
// -1 % 2 = -1 replaced with (2 + -1 % 2) % 2 = 1
R[i][j] += R[k][(p + (j - first) % p) % p];
R[i][j] += R[k][(p + (first - j) % p) % p];
}

first = 10 * first + s[k] - '0';
}

R[i][first % p] += 1;
}

return R[0][0];
}

int walprimes(const string& s) {
return F(s, 2) + F(s, 3) + F(s, 5) + F(s, 7)
- F(s, 2 * 3) - F(s, 2 * 5) - F(s, 2 * 7) - F(s, 3 * 5) - F(s, 3 * 7) - F(s, 5 * 7)
+ F(s, 3 * 5 * 7) + F(s, 2 * 5 * 7) + F(s, 2 * 3 * 7) + F(s, 2 * 3 * 5)
- F(s, 2 * 3 * 5 * 7);
}``````

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

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

This is a really interesting solution. However, it seems that the inclusion-exclusion principle is actually causing you to do more work since you have to calculate F(s, {p, q}) many times. I suspect there's probably a way to use the dynamic programming and calculate whether the substring is a walprime in the inner loop. That would probably improve the performance by a constant multiple, especially since you'd get good cache performance on the inner loop.

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

Surely the search space for this problem will always be exponential no matter what you do? There are 3^(N-1) combinations for applying the operators, even if you were only solving the problem for those that factorise to a single prime so F runs in exponential time not polynomial time?

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

The time complexity of F(s, q) is obviously p * n^2. Since the primes set {2, 3, 5, 7} is unchanged, the whole time complexity is only related to the length of input string which can be considered as polynomial time.

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

Actually, you avoid Inclusion-Exclusion completely here, by using the dp state as
f(l,r,p,q,r,s) where p,q,r,s are the mod values take 2,3,5,7.
You need to find f(1,n,p,q,r,s) where p | q | r | s belongs to {0}.
for a given f(1,n,p,q,r,s) you can calculate it as matrix chain multiplication, by breaking into l,r;
f(L,R,p,q,r,s) = sum over( f(L,K,a,b,c,d)*f(K+1,R,e,f,c,d)) s.t ((a+e)%2 =p, (b+f)%3 = 0 etc.)

The total time complexity is O(N^3 * 2*3*5*7) since there are O(N^2*2*3*5*7) subproblems and each subproblem takes O(N) time to solve, if done in a bottom up way.

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

The optimal solution for this would be to solve by dynamics programming. I will solve it in a non-optimal way - by recursion. You can convert it to dynamic programming.

Start with a given number, split it by first char and rest and apply operator (+/- or none) between numbers and previously calculate sum and store output if wall prime

``````Helper Functions:
bool IsWallPrime(int num)	// checks if given number os wall prime
int CoverToInt(char* str, int len=strlen(str))	// converts len numbers of str into integer. Default value is whole strlen(str) i.e. whole string
To Invoke:
int ans = 0;
CheckPrime("12345", ans, 0);
print ans;``````

``````void CheckWallPrime(char* str, int& ans, int prevSum)
{
if(*str == '\0')
{
return ;
}

// For original "123", think that we are here with prevSum = 1 & str = "23"
int sum = prevSum + ConvertToInt(str);	// convert whole str to int (case 1 +23)
if(IsWallPrime(sum))
ans += 1;
sum = prevSum- ConvertToInt(str);	// convert whole str to int  : (case 1 - 23)
if(IsWallPrime(sum))
ans += 1;

int firstNumber = ConvertToInt(str, 1);	// split by first char and rest of string
// Apply +ve operator
CheckWallPrime(str+1, ans, prevSum + firstNumber); // (case 1+2 + rest of string "3")

// Apply -ve operator
CheckWallPrime(str+1, ans, prevSum - firstNumber); //  (case 1-2 + rest of string "3")

// Apply no operator:
CheckWallPrime(str+1, ans, prevSum*10 + firstNumber); //  (case 12 + rest of string "3")

}``````

I am not handling the case for the first character of string. This code applies operator to it which it shouldn't. e.g. for "123", it will consider +123, -123 and 123 (no operator) which is not correct. I am not handling that to avoid code looking obscure

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

Do you know what the time bound on this is? I'm a moron with time bounds, but it seems like for each digit you're executing the function three times on the remaining digits and so forth. Is that O(3^n)? Please don't ream me for suggesting the idiotic, I'm having a hard time with this one.

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

Yes, 3 recursive calls means each input is evaluated 3 times
In turn each nesting will also get called 3 times, resulting in 3 ^ N.

Intuitive way to think why would be thinking of a family tree, where each person as 3 kids.

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

Thanks -- I was just having a hard time believing I was analyzing tha right.

I think this can be done in 2^(2n) or less. If you're able to gauge it clearly would you look at my solution posted below and see if I got that bound estimate right? I have been thinking it might actually be 2^(n logn) since the length of the 2^n digit permutations range evenly from 1-n.

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

Below is my C++ solution. For each string of length n there are 3^(n-1) expressions.

\$ c++ wallprimes.cpp -o wallprimes
\$ ./wallprimes 2 011 12345
6
64

``````#include <iostream>
#include <string>
#include <cstddef>
#include <cstdlib>

int count = 0;

bool is_wallprime(int n)
{
return n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0;
}

void count_wallprimes(int result, std::string n, const std::string& str, size_t index)
{
if (index < str.length())
{
// first digit uses no operator
if (index > 0)
{
count_wallprimes(result + atoi(n.c_str()), std::string("+") + str[index], str, index + 1);
count_wallprimes(result + atoi(n.c_str()), std::string("-") + str[index], str, index + 1);
}
count_wallprimes(result, n + str[index], str, index + 1);
}
else
{
// add or subtract remaining digits
result += atoi(n.c_str());
if (is_wallprime(result))
count++;
}
}

int main(int argc, char** argv)
{
for (int i = 2; i < argc; i++)
{
count = 0;
int result = 0;
std::string n("0");
size_t index = 0;

count_wallprimes(result, n, argv[i], index);
std::cout << count << std::endl;
}
return 0;
}``````

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

``````Very Nice Code!
we have to just find all the combinations for Operators '+' & '-'  the indexes``````

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

Hey u mentioned that for an n digit number there can be 3N - 1 valid expressions which can be formed. I tried this with a 4 digit number and didn't find it to be working. I found more than 3N - 1 expression that is more than 11 expressions. M i correct or m i missing anything in it. These are the expressions which I found for a 4 digit number 2357
2 + 3 + 5 + 7
2 - 3 - 5 - 7
2 + 3 + 5 - 7
2 + 3 - 5 + 7
2 - 3 + 5 + 7
2 - 3 - 5 + 7
2 + 3 - 5 - 7
23 + 57
23 - 57
2 + 35 + 7
2 - 35 - 7
2 + 35 - 7
2 - 35 + 7
235 + 7
235 - 7
2 + 357
2 - 357
2357

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

A typo correction in the original question: There are 3 ^ (n-1) i.e. 3 raise to (n-1) such combinations (instead of 3n-1). Why? For n digits, you have n-1 'empty' spaces between consecutive numbers. Where you can decide to put 3 of possible options (+/- or none). So total combinations are 3*3*... (n-1) times

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

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

A typo correction in the original question: There are 3 ^ (n-1) i.e. 3 raise to (n-1) such combinations (instead of 3n-1)

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

Calculate possible set of possible sums, then count walprime

Let’s define dp as follows.
dp[i] is a set of possible number if we use i numbers.(dp[1] uses only input[0])
dp[0] should be only contain 0 because we don’t use any number.

Let’s define k as number of numbers we combine.
For example, if k = 3, we comine input[i - 0] and input[i-1] and input[i-2].
Also. let’s define numK as the combined number.
For example if k = 3, numK = input[i - 0]*100 + input[i-1]*10 + input[i-2]

We can build dp[i] for possible k using
//Calculate numK
//then
{{
for(int j:dp[i-k]){
}
}}

Then we can count walprimes in the set of dp[N+1].
*/

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

class Walprime {
public static void add(Map<Integer,Integer> map,int key,int value){
if(map.containsKey(key)){
map.put(key, value % 1000000007 + map.get(key) % 1000000007);
}else{
map.put(key, value % 1000000007);
}
}
public static int solve(String inputString) {
int N = inputString.length();
int M = 2*3*5*7;
int[] input = new int[N];
for(int i = 0; i < N;i++){
input[i] = Integer.parseInt(inputString.charAt(N - i - 1) + "");
}
Map<Integer,Integer>[] dp = new Map[N + 1];
for (int i = 0; i <= N; i++) {
dp[i] = new HashMap<Integer, Integer>();
}
dp[0].put(0, 1);
//dp[1].put(input[0], 1);
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= i; k++) {
int numK = 0;
for (int l = i; l > i - k; l--) {
numK = numK * 10 + input[l - 1];
numK %= M;
}
for (int j : dp[i - k].keySet()) {
}
}
}
for (int i : dp[N].keySet()) {
if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0 || i == 0)
}
return answer / 2; // dp[0] case will be double counted (+ and -). so we need to get half the answer
}

public static void main(String[] argv) throws IOException {
1);
// We don’t assume illegal input.
String[] inputs = new String[num];
for (int i = 0; i < num; i++) {
}
for (String input : inputs) {
System.out.println(solve(input));
}
}
}``````

11 1+1=2 :1
12 1+2=3 :1
13 1+3=4 1
14 1+5=5 1-4=-3 14: 3
21 2+1=3,21 :2

I couldn't estimate time complexity and space complexity.
This code works up to 20 digits.

# I believe 0 isn't prime number.. but the problem statements says so, I have written such code.

I would like to know the datasets also.

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

I did it in php because it's cheap and dirty. First calculates a possible permutation of the digits, and only at that point does it calculate the permutations of the +/-. That should save a lot of operations, since other solutions which calculate the permutations along with the +/- at the same time will be calculating the same digit permutation over and over again with different combinations of +/-.

This problem is NP and huge, yes? it seems like for each of the 2^n digit permutations there are 2^n permutations of +/- on the digits. At the risk of asking something really stupid, is that O(2^(2n)) bound?

It uses O(n) extra space though. There's commented code in there to return an answer array which would use much more, but this version just prints. I'm aware this doesn't fit the output requirements of the problem.

This algorithm works up to the max int, could be made to work for much larger numbers using GMP. But the universe might end before that completes.

``````<?php;

\$tests = array(
'12345',
'123412341234',
'3462',
);

function isWallPrime(\$int) {
if ((\$int % 2) == 0) return 2;
if ((\$int % 3) == 0) return 3;
if ((\$int % 5) == 0) return 5;
if ((\$int % 7) == 0) return 7;
}

function getWallPrimes(\$str) {
\$runningNumbers = array();
}

if (\$int == 0 ) {
return;
}

\$int10 = 10 * \$int;
\$rnLen = count(\$runningNumbers);
for (\$mod = 10 ; \$mod < \$int10 ; \$mod *= 10) {
\$runningNumbers[] = \$int % \$mod;
\$runningNumbers = array_slice(\$runningNumbers, 0, \$rnLen);
}
}

if (! isset(\$runningNumbers[\$index])) {
\$ret = isWallPrime(\$runningNum);
if (\$ret) {
echo 'Wallprime ', \$runningNum, "\t", 'divisible by ', \$ret, "\t", 'Permutation ', json_encode(array_reverse(\$runningAnswer)), "\n";
}
return;
}

\$newNum = \$runningNumbers[\$index];

}

//=======================================
//=======================================

echo "\n\n";
foreach (\$tests as \$str) {
\$ret = getWallPrimes(\$str);
echo "\n\n";
}

?>``````

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

BTW it also converts to int first which saves a hell of a lot of hidden cost in converting a string to an int over and over again.

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

Here's my (Java) solution. I didn't include the io part, just a method that calculates the number of walprimes for an array of digits.

``````public class Walprime {

public static int count(int[] ds, int acc, int i, char opi, int j) {
int a = 0;
for (int k = i; k <= j; k++) a = a * 10 + ds[k];
int accNew = opi == '+' ? acc + a : acc - a;
if (j == ds.length - 1) {
return isWalprime(accNew);
}
return count(ds, accNew, j+1, '+', j+1)
+ count(ds, accNew, j+1, '-', j+1)
+ count(ds, acc, i, opi, j+1);
}

public static int isWalprime (int n) {
return n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 ? 1 : 0;
}

public static int countWalPrime(int[] ds) {
return count(ds, 0, 0, '+', 0);
}
}``````

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

here is my java BFS solution

``````static int abs(int i){
return i<0?-i:i;
}

static boolean isWallprime(int n){
return (n%2==0)||(n%3==0)||(n%5==0)||(n%7==0);
}

static int bfs(String num){
int n = Integer.parseInt(num);
//		 state -->	i 	: split after digit i from the left
//					val : value of the exp. preceding i
//					prevSplit : position of the prev split

int i = 1, val = 0;
int ways = 0;
int curVal, val2, ssVal;
int prevSplit = 0;

// if lastsplit < 0  prev op was -
// if lastsplit > 0  prev op was +

if(isWallprime(n))
ways++;

while (!splitQ.isEmpty()){
i =  splitQ.poll();
val = valQ.poll();
prevSplit = prevSplitQ.poll();

// not to split
ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal = curVal*10 + Integer.parseInt(num.substring(i,i+1));
if (i<num.length()-1){

}

// operation split at i
val2 = Integer.parseInt(num.substring(i));
if(isWallprime(val+val2))
ways++;
//value between 2 splits
ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal+=Integer.parseInt(num.substring(i,i+1));

if (i<num.length()-1){
}

// trying subtraction
val2 = Integer.parseInt(num.substring(i));
if(isWallprime(val-val2))
ways++;

ssVal = Integer.parseInt(num.substring(abs(prevSplit),i));
curVal = (prevSplit>0)?val-ssVal:val+ssVal;
curVal-=Integer.parseInt(num.substring(i,i+1));
if (i<num.length()-1){
}

}
return ways;
}``````

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

I did it for only %5 and %7 .. but you should get the idea.

``````package com.intv.combinations;

public class PrintValidExpressions {

public static int expressionCount = 0;

/**
* Definition of a valid expression: any expression that evaluates to a number that is divisible by 5 or 7
*
* q. find all valid expressions given a string "s" by inserting - or + between the numbers.
*
* ex: 122 -> 1+2+2 = 5
*            12+2 = 14;
*
* @param args
*/
public static void main(String[] args) {

// Complexity:
// let k be the number of operators. O( (k+1)^(n-1)) .. so in this case for k = 2 (+,-) .. O(3 ^ n-1)
String numbers = "123";
System.out.println(validExpressions(numbers));
System.out.println(expressionCount);
}

public static int validExpressions(String numbers) {
return validExpressionHelper(numbers, "", "",0, 0);
}

public static int validExpressionHelper(String numbers, String operator, String expression, int result, int position) {

StringBuffer buffer = new StringBuffer(1024);

int count = 0;

for(int i = position ; i < numbers.length() ; i++) {

buffer.append(numbers.charAt(i));

int currentNumber = new Integer(buffer.toString()).intValue();
int currentResult = eval(currentNumber, result, operator);

if(i+1 == numbers.length()) {
boolean check = checkExpression(expression, currentNumber, currentResult);
if(check) return (count+1);
}

String plusExpr = expression + currentNumber + "+";
count += validExpressionHelper(numbers, "+" , plusExpr, currentResult, i+1);
String minExpr = expression + currentNumber + "-";
count += validExpressionHelper(numbers, "-" , minExpr,  currentResult , i+1);
}

return count;
}

private static boolean checkExpression(String expression, int currentNumber, int currentResult) {
// I am the last number in the expression
String currentExpression = expression + currentNumber;
System.out.println(currentExpression + " = " + currentResult );
expressionCount++;
return  (currentResult % 5 == 0 || currentResult % 7 == 0);
}

private static int eval(int currentNumber, int result, String prevOperator) {
if(prevOperator.isEmpty()) return currentNumber;
else if(prevOperator.equals("-")) {
return result - currentNumber;
} else { // assume for now it is +
return result + currentNumber;
}
}
}``````

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

is this similar to Karp-Robin algorithm ? this is used to check if the given string is substring of a bigger string and to compare it uses hash.
It looks like a integer varient of same problem. it takes O(n) time .

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.

### 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.

### 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.