## geekofthegeeks

BAN USER- 0of 0 votes

AnswersGiven an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.

- geekofthegeeks in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven a binary tree, find the largest subtree having atleast two other duplicate subtrees .

- geekofthegeeks in United States| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 0of 0 votes

AnswersGiven the following decoder, write the encoder. (The encoder should be written to compress whenever possible):

- geekofthegeeks in United States

p14a8xkpq -> p14akkkkkkkkpq

(8xk gets decoded to kkkkkkkk. The only other requirement is that encodings be unambiguous)

Note that the String can have any possible ascii character| Report Duplicate | Flag | PURGE

Google Software Engineer Algorithm - 4of 4 votes

AnswersGiven an array of pairs of the form <a, b>. We have to find a sub-array such that the 1st element in the pairs are in increasing order and the sum of 2nd element of the pairs in the sub-array is maximum possible

- geekofthegeeks in United States| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - 2of 2 votes

AnswersEngineers at Google have decided to call any integer (+ve, -ve or 0) that is divisible by at least one of the single digit primes (2, 3, 5, 7) as Walprimes. Thus -21, -30, 0, 5, 14 etc are Walprimes, while -121, 1, 143 etc. are not Walprimes.

- geekofthegeeks in India

Now, consider a n-digit integer d1d2d3..dn. Between any 2 consecutive digits you can place either a (+) sign, a (-) sign or nothing. So, there are 3n-1 different expressions that can be formed from it. Some of the expressions so formed may evaluate to a Walprime. For example, consider the 6 digit integer 123456: 1 + 234 - 5 + 6 = 236, which is a Walprime, but 123 + 4 - 56 = 71, which is not a Walprime.

Your task is to write a program to find the no. of expressions (out of the possible 3n-1 expressions) that evaluate to a Walprime, for a given input. Note that leading zeroes are valid. For example, if the input is 1202004, it can be split as 12 + 020 - 04 etc. Also, the input itself can contain leading zeroes.

Input format: (Read from stdin)

The first line of input contains a single integer 'T' denoting the no. of test cases.

Each of the following 'T' lines contain a single string 's' (of length 'n') denoting an input for which you need to find the no. of valid expressions evaluating to a Walprime.

Output format: (Write to stdout)

Output exactly 'T' integers (one per line), where the ith line denotes the no. of valid expressions that evaluate to a Walprime for the ith input string. Since the output can be large, print all the quantities modulo 1000000007.

Sample testcase:

Input:

2

011

12345

Output:

6

64

Explanation:

For the first test case, s = "011". There are 32 = 9 valid expressions that can be formed from this string, namely {0+11, 0-11, 0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1, 011} . Out of these 9 expressions, only the following 6 of them evaluate to a Walprime: {0+1+1, 0+1-1, 0-1+1, 0-1-1, 01+1, 01-1}.

Constraints:

There are 3 data sets.

For the first data set (5 points) -

1

For the second data set (10 points) -

1

For the third data set (15 points) -

1| Report Duplicate | Flag | PURGE

Google Software Engineer / Developer Algorithm - -5of 5 votes

AnswerWhy do you think the company has been named so?

- geekofthegeeks in United States| Report Duplicate | Flag | PURGE

Tribal Fusion Software Engineer / Developer - 0of 0 votes

AnswersDetermine the 10 most frequent words given a terabyte of strings.

- geekofthegeeks in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer / Developer Algorithm

I retract what I said. It will be your first guess.

- geekofthegeeks May 22, 2016find the largest subtree that has atleast two other duplicate subtrees. So definitely not your second guess. Not the first either as the duplicate subtress may not necessarily be rooted at the left and right child (but can be a subtree of them as well)

- geekofthegeeks May 22, 2016for following example of apple,bc, plent ,

answer will be:

abcplenplet

No to both

- geekofthegeeks November 16, 2013**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

for encoded string 81xx, the decoded string can be either 8x or xxxxx..xxxxx (81xs), hence the encoding is ambiguous

- geekofthegeeks May 28, 2016