Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
19
of 21 vote

I think the key of this problem is to determine the initial first number and the second number. once it's decided, other numbers are automatically generated.

Below code is not optimized, but should work.

/// <summary>
        /// what about:
        ///     1. all zero - 00000
        ///     2. starting with zero - 0112
        ///     3. zero in the middle
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        static bool IsAggregatedNumber(string text)
        {
            for (var i = 1; i <= text.Length / 2; i++)
            {
                for (var j = 1; j <= text.Length / 2; j++)
                {
                    if (Match(i, j, text))
                    {
                        return true;
                    }
                }
            }

            return false;
        }

        static bool Match(int i, int j, string text)
        {
            var first = text.Substring(0, i);
            var second = text.Substring(i, j);
            var buffer = new StringBuilder();
            buffer.Append(first);
            buffer.Append(second);
            while (buffer.Length < text.Length)
            {
                var third = (Int32.Parse(first) + Int32.Parse(second)).ToString();
                buffer.Append(third);
                first = second;
                second = third;
            }

            return buffer.Length == text.Length && buffer.ToString() == text;
        }

- shawn November 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

your code works fine

- greenrise123 November 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Modified the code a wee bit in java. works for the test cases in the problem

static boolean isAggregatedNumber(String text) {
		int length = text.length() / 2;
		for(int i = 1; i <= length; i++) {
			for(int j = 2; j <= length; j++) {
				if(Match(i,j,text)) {
					return true;
				}
			}
		}
		return false;
	}

	static boolean Match(int i, int j, String text) {
		String first = text.substring(0, i);
		String second = text.substring(i, i*2);
		StringBuilder buffer = new StringBuilder(first);
		buffer.append(second);
		while(buffer.length() < text.length()) {
			Integer x  = (Integer.parseInt(first) + Integer.parseInt(second));
			String third =  x.toString();
			buffer.append(third);
			first = second;
			second = third;
			}
		if(text.equals(buffer.toString())) 
			return true;
		return false;				
	}

- PAN November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think for the sake of the problem, it is better to assume that the second number is greater than the first.

- John November 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work. check the case 1121325

- Anonymous December 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous it works for this case.
it will pass when in match function 1 , 12 will go as the substrings.
so it will become 11213 then 12+13 will happen i.e 1121325.
The solution is absolutely correct

- Geek January 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@PAN, you modified version has some issues I think:

In the first method named isAggregatedNumber:

// issue in this line with initialization of 'j'
	for(int j = 2; j <= length; j++) {

/* This can be corrected in either of the two ways: */
// (1) If we allow for 23225 as valid, for ex: 23+2=25, 
// where first=23, second=2, and third=25. Do: j=1 (as done by shawn),
	for(int j=1; j <= length; j++) {

// (2) If (1) is not allowed and only proper Fibonacci pattern is allowed, 
// like 232447 as valid, for ex: 23+24=47, 
// where first=23, second=24, and third=47. Do: j=i,
	for(int j = i; j <= length; j++) {

In the second method named Match:

// issue in this line with the 2nd parameter of substring()
	String second = text.substring(i, i*2);

	// this can be corrected this way
	String second = text.substring(i, j);

I think shawn's proposed method is doing fine.

- Anonymous March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shawns solution will return true for any number with even digits, one check to see if any addition is happening needs to be done

- notadev January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you can skip this check and loops for some cases if you don't let i and j iterate further than textlength / 3 because one addition result needs at least 1/3 of the textlength in space. Not thoroughly checked though.

- BigB May 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good job shawn! Here's a working python solution:

def find_aggregated_number(A):
    for i in range(1,int(len(A)/2)):
        for j in range(i+1,int(len(A)*2/3)+1):
            if(check_aggregate(i,j,A)):
                return True
    return False

def check_aggregate(i,j,A):
    result = A[0:i] + A[i:j]
    first = int(A[0:i])
    second = int(A[i:j])
    
    while(len(A) > len(result)):
        third = first + second
        result = result + str(third)
        first = second
        second = third 
    return (len(result)==len(A)) and (result == A)

for A in ["112358","122436","1299111210","112112224"]:
    if (find_aggregated_number(A)):
        print("{} is an aggregated number".format(A))
    else:
        print("{} is not an aggregated number".format(A))

- bluepulse5577 September 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

enum {
FALSE,
TRUE
};
/*
 * Pass 12345 as array, index = 2, size = 2 
 * result of this function would be 34.
 * Pass 12345 as array, index = 2, size = 3 
 * result of this function would be 345.
 * Pass 12345 as array, index = 1, size = 3 
 * result of this function would be 234.
 */
int make (int *A, int index, int n)
{
        // n is the size
	int iterator = index + size - 1;
	int sum = 0;
	while (iterator >= index)
	{
		sum = sum * 10 + A[iterator];
		iterator--;
	}
        return sum;
}
int is_Aggregated(int *Array, int size)
{
	int factor = 1;							
        // used to move the indexes through the locations.
	int i = 0, j, k;
	
	while (i < n)
	{
		j = i + factor;
		k = j + factor;
		if (k >= n )
		{
			break;
		}
		if(make(A,i,factor) + make(A,j,factor) != 
                   make (A,k,factor))
		{
			i = 0;
			factor++;
		} else {
			if ( k + factor == n){
			/*
			 * The last position is matched, therefore 
                         * the array is a aggregate;
			 */
			 return TRUE;
			}
		    i = i + factor;
		}

	}
	return FALSE;
}

example 1
pass a: 0 1 1 2 3 5 8
        i j k
pass b: 0 1 1 2 3 5 8
          i j k
pass c: 0 1 1 2 3 5 8
            i j k    
pass d: 0 1 1 2 3 5 8
              i j k
pass e: 0 1 1 2 3 5 8
                i j k      ==> true

Example 2

pass a: 1 2 3 4 4 6 8 0
        i j k
pass b: 1 2 3 4 4 6 8 0
          i j k            ==> i = 0, factor = 2
pass c: 1 2 3 4 4 6 8 0
        i   j   k
pass d: 1 2 3 4 4 6 8 0
            i   j   k      ==> true
		
Example 3
pass a: 1 2 3 4 5 6 5 7 9
        i j k
pass b: 1 2 3 4 5 6 5 7 9
          i j k            ==> i = 0, factor = 2
pass c: 1 2 3 4 5 6 5 7 9
        i   j   k          ==> i = 0, factor = 3
pass d: 1 2 3 4 5 6 5 7 9
        i     j     k          ==> true

---
A mistake is a crash course in learning.
Please comment on its correctness.
---

- code_monkey November 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is a linear solution!!

- code_monkey November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Mistakes
Alg related:
1) After factor variable increases, i should start from 0 instead it starts from factor position. The problem line is "i = i + factor;"
2) make method does not return the sum variable.
Syntax related:
3) function header should be
int is_Aggregated(int *A, int n)
4) There should be a ; in line i = 0

Cheers! :)

- VladP November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

why do you assume that the two numbers that are to be summed have same number of digits?

you program doesn't solve 132411235: 1234+1=1235

- nikhil simha November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@VladP :
Corrected. Thanks :)

- code_monkey November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you check for 1235813 - in this case all your assumptions are valid ( like second is > first number etc).
Your input works only if A is given as { 1,2,3,5,8,13} but not
{ 1,2,3,5,8,1,3}. Correct me if I mistook. If you say you need to input the array as in the second case, you are back to the same problem, how will u partition the array to 13 or 1,3.

- sivabasava February 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Agreeing to nikhil simha,

Assuming that the two numbers that are to be summed have same number of digits does not make up for satisfactory solution.

Solution proposed fails to solve example like:
1299111210, because 12+99=111, 99+111=210
1100101, because 1+100=101

- Anonymous March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code doesn't even compile, and after fixing it, it doesn't solve the following inputs:
1100101
12344680
1299111210

- mytestaccount2 October 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I did it recursively in Python:

def isAgg(n, path=[]):
    #if the input is an integer change it into a string
    n=str(n)
    
    #if 1+1=2 in 112358
    if len(path)==3 and sum(path[:2]) == path[2]:
        #if a+b=c and there is nothing left, return True         
        if len(n)==0:
            #print path, n
            return True
        #if a+b=c and there is leftover
        else:
            #print path, n
            path.pop(0)
            return True and isAgg(n, list(path) )
    #if the sum of first two numbers is not the third number, discard the current path
    elif len(path)>3:
        return False 

    #for check all possible permutations: 112358 -> isAgg(1, 12358), isAgg(11, 2358), isAgg(112, 358),...   
    out=False
    for i in range(1, len(n)+1):
        out |= isAgg(n[i:], path + [int(n[:i])])
    return out

print isAgg(112112224)

- softbass November 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think dynamic programming should be used here. I figured out a recurrence relation to solve this in O(n^5). Does anyone have a better idea?

- Epic_coder November 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

One of the other answers mentions it: the key is to determine the initial first and second numbers, then rest is easy to verify.

There are Theta(n^2) possibilities for the first and second, and O(n) time to verify for each such possiblilty, so there is an O(n^3) algorithm.

- Anonymous November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't be the case- consider 1125126 - 1 + 125 = 126 but 1+1 could look like they are a good pick for aggregation

- gizmo November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gizmo: What part of "there are theta(n^2) possibilities" didn't you understand?

1,1 is one possibility, but fails when you reach 5. So you try another one...

- Anonymous November 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Since the constraint is not specified, I will assume the number of digits is ~20. The question asks to divide the number into several parts, so a n-digit number can be divided at at most n-points ( between every two adjacent digits and minus point before first digit ). Hence, use backtrack to iterate through all 2^n possibilities and check for the condition.

Complexity should be O(2^n) and number for index i to index j can be pre-calculated

- tungnk1993 November 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Python version

# -*- coding: utf-8 -*-
"""
Created on Sun Nov 25 19:45:26 2012

@author: qzhang
"""
DEBUG = 0

def IsAggregatedNumber(number):
    global DEBUG
    num_str = str(number)
    length = len(num_str)
    if DEBUG == 1:
        print "length is",length
    for i in range(1,length/2+1):
        for j in range(1,length/2+1):
            if match(i,j,num_str):
                return True
    
    return False
    
    
def match(i,j,num_str):
    global DEBUG
    first = num_str[:i]
    second = num_str[i:i+j]
    buff = ""
    buff =buff +first
    buff =buff +second
    
    while len(buff) < len(num_str):
        if DEBUG ==1:
            print "first ", first
            print "second ", second
        third = str(int(first) + int(second))
        if DEBUG ==1:
            print "third ", third
        buff =buff +third
        first = second
        second = third
    
    if(cmp(buff,num_str) == 0):
        return True
    else:
        return False
        
    
if __name__ == "__main__":
    print IsAggregatedNumber(112358)
    print IsAggregatedNumber(1224)
    print IsAggregatedNumber(1299111210)
    print IsAggregatedNumber(112112224)

- John November 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution in Java. Also created an amount of unit tests.
Also works for very big numbers (see last Unit Test), using BigInteger.

import java.math.BigInteger;

public class AggregatedNumber {
	public boolean testNumber(String number) {
		if (number.length() <= 2) {
			return true;
		}

		// Find j: the position of the second pointer
		for(int j = 1; j < number.length() - 1; j++) {
			String number1String = number.substring(0, j);
			if (number1String.length() > 1 && number1String.charAt(0) == '0') {
				// A non-zero number should not start with a zero
				continue;
			}
			BigInteger number1 = new BigInteger(number1String);

			// Find jLength: The length of the second value
			for(int jLength = j; jLength < number.length() - j; jLength++) {
				String number2String = number.substring(j, j + jLength);
				if (number2String.length() > 1 && number2String.charAt(0) == '0') {
					// A non-zero number should not start with a zero
					continue;
				}
				BigInteger startTwo = new BigInteger(number2String);

				// Check if the combination {j, jLength} results in an aggregated number
				if (check(number1, startTwo, number.substring(number1String.length() + number2String.length()))) {
					return true;
				}
			}
		}
		
		// We did not find any valid combination of {j, jLength}: return false
		return false;
	}

	private boolean check(BigInteger number1, BigInteger startTwo, String numberSubstring) {
		if (numberSubstring.isEmpty()) {
			// We are finished
			return true;
		}

		// What do we expect next? The previous two numbers added
		BigInteger expected = number1.add(startTwo);
		String expectedString = expected + "";
		if (!numberSubstring.startsWith(expectedString)) {
			// The next number was not found: the sequence is not an aggregated number
			return false;
		}

		// Do recursion on the rest of the string
		String newNumberSubstring = numberSubstring.substring(expectedString.length());
		return check(startTwo, number1.add(startTwo), newNumberSubstring);
	}
}

-------------------------------------------------

import static org.junit.Assert.*;

import org.junit.Test;

public class IsAggregatedNumberTest {
	private AggregatedNumber numberChecker = new AggregatedNumber();

	@Test
	public void testFibSimple() {
		boolean test = numberChecker.testNumber("112");
		assertTrue(test);
	}

	@Test
	public void testLengthTwo() {
		boolean test = numberChecker.testNumber("11");
		assertTrue(test);
	}

	@Test
	public void testFibMediumPrependNine() {
		boolean test = numberChecker.testNumber("911235813");
		assertFalse(test);
	}

	@Test
	public void testSkip() {
		boolean test = numberChecker.testNumber("1012");
		assertFalse(test);
	}

	@Test
	public void testZero() {
		boolean test = numberChecker.testNumber("000");
		assertTrue(test);
	}

	@Test
	public void testFibZeroes() {
		boolean test = numberChecker.testNumber("00000000000");
		assertTrue(test);
	}

	@Test
	public void testZeroTwo() {
		boolean test = numberChecker.testNumber("022461016264268110178");
		assertTrue(test);
	}

	@Test
	public void testZeroTwenty() {
		boolean test = numberChecker.testNumber("02020406010016026042068011001780");
		assertTrue(test);
	}

	@Test
	public void testFibMedium() {
		boolean test = numberChecker.testNumber("11235813");
		assertTrue(test);
	}

	@Test
	public void testFibWrong() {
		boolean test = numberChecker.testNumber("113");
		assertFalse(test);
	}

	@Test
	public void testFibDoubleDigits() {
		boolean test = numberChecker.testNumber("122436");
		assertTrue(test);
	}

	@Test
	public void testFibDoubleDigits2() {
		boolean test = numberChecker.testNumber("1299111210");
		assertTrue(test);
	}

	@Test
	public void testFibTripleDigits() {
		boolean test = numberChecker.testNumber("112112224");
		assertTrue(test);
	}

	@Test
	public void testFibSingleDoubleDigits() {
		boolean test = numberChecker.testNumber("11011213253");
		assertTrue(test);
	}

	@Test
	public void testFibNonGreedy() {
		boolean test = numberChecker.testNumber("1125126");
		assertTrue(test);
	}

	@Test
	public void testFibWrong2() {
		boolean test = numberChecker.testNumber("11251265");
		assertFalse(test);
	}

	@Test
	public void testMediumInitials() {
		boolean test = numberChecker.testNumber("100000100000200000");
		assertTrue(test);
	}

	@Test
	public void testFibLong() {
		boolean test = numberChecker.testNumber("011235813213455891442333776109871597258441816765");
		assertTrue(test);
	}

	@Test
	public void testFibHuge() {
		boolean test = numberChecker.testNumber("0112358132134558914423337761098715972584418167651094617711286574636875025121393196418317811");
		assertTrue(test);
	}
	
	@Test
	public void testGigangtic() {
		boolean test = numberChecker.testNumber("011235813213455891442333776109871597258441816765109461771128657463687502512139319641831781151422983204013462692178309352457857028879227465149303522415781739088169632459861023341551655801412679142964334944377014087331134903170183631190329712150734807526976777874204912586269025203650110743295128009953316291173862675712721395838624452258514337173654352961625912867298799567220260411548008755920250473078196140527395378816557470319842106102098577231716768017756527777890035288449455702128537272346024814111766903046099419039249070913530806152117012949845401187926480651553304939313049695449286572111485077978050341645462290670755279397008847578944394323791464");
		assertTrue(test);
	}
}

- A V March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

enum XYZPhase {xx,yy,zz};

bool IsAggregatedNumberAux(
	long long AggregatedX,
	long long AggregatedY,
	long long AggregatedZ,
	XYZPhase Phase,
	long long NumToCheck,
	int AggregatedLength
	)

{
	AggregatedLength++;
	if (NumToCheck==0) {
		return false;
	}	
	if (Phase==xx) {
		if (AggregatedX + AggregatedY == AggregatedZ)
		{
			if (NumToCheck<10) { //we checked the last digit
				return true;
			}
			AggregatedZ=AggregatedY;
			AggregatedY=AggregatedX;
			return (IsAggregatedNumberAux(
				0,
				AggregatedY,
				AggregatedZ,
				xx,
				NumToCheck,
				0
				));
		}
		return (IsAggregatedNumberAux(
			AggregatedX+(NumToCheck%10)*AggregatedLength,
			AggregatedY,
			AggregatedZ,
			xx,
			NumToCheck/10,
			AggregatedLength
			));
	}
	if (Phase==yy) {
		if ((IsAggregatedNumberAux(
			AggregatedX,
			AggregatedY+(NumToCheck%10)*AggregatedLength,
			AggregatedZ,
			yy,
			NumToCheck/10,
			AggregatedLength
			)))
		{
			return true;
		}
		return IsAggregatedNumberAux(
			AggregatedX,
			AggregatedY+(NumToCheck%10)*AggregatedLength,
			AggregatedZ,
			xx,
			NumToCheck/10,
			0
			);
	}

	//phase == zz
	if ((IsAggregatedNumberAux(
		AggregatedX,
		AggregatedY,
		AggregatedZ+(NumToCheck%10)*AggregatedLength,
		zz,
		NumToCheck/10,
		AggregatedLength
		)))
	{
		return true;
	}
	return IsAggregatedNumberAux(
		AggregatedX,
		AggregatedY,
		AggregatedZ+(NumToCheck%10)*AggregatedLength,
		yy,
		NumToCheck/10,
		0
		);
}

bool IsAggregatedNumber(long long NumToCheck)
{
	return (IsAggregatedNumberAux(
		0,
		0,
		0,
		zz,
		NumToCheck,
		0
		));
}

- Ben November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isAggregatedNumberSequence(String numberSequenceStr) {
		int isize = 1;
		for(int i = 0; i + isize < numberSequenceStr.length(); isize++) {
			int jsize = 1;
			for(int j = i + isize; j + jsize < numberSequenceStr.length(); jsize++) {
				int inti = Integer.parseInt(numberSequenceStr.substring(i, i + isize));
				int intj = Integer.parseInt(numberSequenceStr.substring(j, j + jsize));
				if (isAggregateNumber(inti, intj, numberSequenceStr.substring(j + jsize, numberSequenceStr.length()))) {
					return true;
				}
			}
		}
		return false;
	}
	
	private static boolean isAggregateNumber(int prev, int current, String str) {
		if(str.length() == 0) {
			return true;
		}
		int next = prev + current;
		if(str.startsWith(next + "")) {
			return isAggregateNumber(current, next, str.replaceFirst(next + "", ""));
		}
		return false;
	}

	public static void main(String[] args) {
		System.out.println(isAggregatedNumberSequence("123"));
		System.out.println(isAggregatedNumberSequence("11111111112"));
		System.out.println(isAggregatedNumberSequence("000"));
		System.out.println(isAggregatedNumberSequence("11235813"));
		System.out.println(isAggregatedNumberSequence("112112224"));
		System.out.println(isAggregatedNumberSequence("124"));
		
	}

- zanyaziz November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- :D November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think that we can identify whether the number can be decompose into 3 numbers a,b,c such that a+b = c first. And then if any subset of the number can be decomposed, we then propagate to the end of the number. It will take O(n^3)

- binhngoc17 November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A working solution in ruby. Like many people comment in here, the key is to get the first 2 elements. Given that, you just need to perform checks on the remaining elements. It requires a lot of switching between integers and strings.

# Gets the size of the biggest chunk of numbers you can take
# and iterates from 1 to that, taking the first 2 numbers
# and performing the check with that
def aggregated_check(number)
  biggest_chunk_size = number.to_s.split('').count/3
  return false if biggest_chunk_size < 1

  1.upto(biggest_chunk_size) do |chunk_size|
    split_number = spaces_on(number, chunk_size)

    next unless split_number.select { |number| number.size != chunk_size }.empty?

    return true if is_aggregate?(split_number)
  end
  
  false
end

# Returns an array with the number divided in X intervals
def spaces_on(number, interval)
  number.to_s.gsub(/.{#{interval}}/, '\& ').split  
end

# Takes first and second numbers and adds them, saves the result in "sum"
# then takes "sum.digits" characters from the string, if that is different to sum
# just returns false. If its true, then first becomes second, second becomes sum. 
def is_aggregate?(split_number)
  first = split_number.shift.to_i
  second = split_number.shift.to_i
  number = split_number.join

  loop do 
    sum            = first + second
    sum_digits     = sum.to_s.size
    return true if number[sum_digits - 1].nil?
    possible_match = number[0..sum_digits - 1].to_i
    return false if sum != possible_match

    number = number[sum_digits..number.size]
    first  = second
    second = sum
  end

end

- Daniel November 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The working code is here

int main(void) {

char Str[]="112112224";
AgreegatedFunction(Str);
}
void AgreegatedFunction(char *inputstr)
{


int NoofDigits = 1,resultdigits;
int stridx=0;
char operand[10],val[10];
int operand1,operand2;
int i,result;
int valid= 0;
while(*(inputstr+stridx) != '\0')
{
// get operand 1
if(!valid)
{
for( i=0;i<NoofDigits && *(inputstr+stridx) != '\0';i++, stridx++)
operand[i]=*(inputstr+stridx);


operand[i]='\0';
operand1 = atoi(operand);


// get operand 2
for( i=0;i<NoofDigits && *(inputstr+stridx) != '\0';i++, stridx++)
operand[i]=*(inputstr+stridx);

operand[i]='\0';
operand2 = atoi(operand);
}

resultdigits = Noofdigitsforresult(operand1+operand2);
// get result
for( i=0;i< resultdigits && *(inputstr+stridx) != '\0';i++, stridx++)
val[i]=*(inputstr+stridx);

val[i]='\0';
result = atoi(val);

if((operand1 + operand2) != result )
{
NoofDigits++;
valid = 0;
if( stridx < strlen(inputstr))
{
stridx = 0;
}
}
else
{
printf("operand one %d operand two %d result %d\n",operand1,operand2,result);
valid = 1;
operand1 = operand2;
operand2 = result;

}

}
if(valid)
printf(" it is a aggregated number");
else
printf(" it is not a aggregated number");
}

int Noofdigitsforresult(int result)
{
int noofdigits = 1;

while(result > 9)
{
result = result /10;
noofdigits++;
}
printf("No.of digits %d",noofdigits);
return noofdigits;
}

- ganl November 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_digits(n):
    if n == 0:
        return [0]
    digits = []
    while n > 0:
        digits.insert(0, n % 10)
        n = n // 10
    return digits

def make_number(digits):
    n = 0
    for digit in digits:
        n *= 10
        n += digit
    return n

def get_aggregates(n):
    """Get the aggregate factoring of n, that is split n into
    a list of numbers so that each number is the sum of two previous ones,
    and all numbers concatted together form n. Return empty list if no such
    grouping exists.

    >>> get_aggregates(112358)
    [1, 1, 2, 3, 5, 8]
    >>> get_aggregates(122436)
    [12, 24, 36]
    >>> get_aggregates(1299111210)
    [12, 99, 111, 210]
    >>> get_aggregates(112112224)
    [112, 112, 224]

    The elements don't have to be nondecreasing:
    >>> get_aggregates(10112)
    [1, 0, 1, 1, 2]
    >>> get_aggregates(1211314)
    [12, 1, 13, 14]
    >>> get_aggregates(12112133)
    [121, 12, 133]

    The list must be at least 3 members long:
    >>> get_aggregates(1)
    []
    >>> get_aggregates(137)
    []
    >>> get_aggregates(1125)
    []
    """

    def make_aggregate(first, second, rest):
        aggregate = [first, second]
        prev = first
        cur = second

        while len(rest) > 0:
            nextt = prev + cur
            digits = get_digits(nextt)
            if rest[:len(digits)] == digits:
                aggregate.append(nextt)
                prev = cur
                cur = nextt
                rest = rest[len(digits):]
            else:
                return None
        return aggregate

    digits = get_digits(n)
    for first_length in range(1, len(digits)):
        for second_length in range(first_length + 1, len(digits)):
            first = make_number(digits[:first_length])
            second = make_number(digits[first_length:second_length])
            rest = digits[second_length:]
            aggr = make_aggregate(first, second, rest)
            if aggr:
                return aggr
    return []

def is_aggregate(n):
    return get_aggregates(n) is not None

if __name__ == "__main__":
    import doctest
    doctest.testmod()

- Anonymous November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We figure out first and second numbers, build aggregated number, and check if it is the given number. If it is not, take another digit to rebuild second number and repeat the process. This needs to continue for first number too if the built aggregated number is not the given one. Worst Case Scenario [for example 1123581323] : O(N^3) and Best Case Scenario [for example 1123581321]: O(N)

public boolean isAggregate(int input) {
		String s = String.valueOf(input);
		if (s.length() < 3) {
			return false;
		}
		for (int i = 1; i <= s.length() - 2; i++) {
			for (int j = 1; i + j <= s.length() - 1; j++) {
				int number1 = Integer.parseInt(s.substring(0, i));
				int number2 = Integer.parseInt(s.substring(i, i + j));
				int number3 = number1 + number2;
				int num2Size = String.valueOf(number2).length();
				int num3Size = String.valueOf(number3).length();
				double d1 = Math.pow(10, num2Size + num3Size) * number1;
				double d2 = Math.pow(10, num3Size) * number2;
				double d3 = number3;
				int result = (int) (d1 + d2 + d3);
				while (String.valueOf(result).length() < s.length()) {
					int temp = number2 + number3;
					int size = String.valueOf(temp).length();
					double dd1 = Math.pow(10, size) * result;
					if (dd1 > Integer.MAX_VALUE) {
						break;
					}
					result = (int) (dd1 + temp);
					number2 = number3;
					number3 = temp;
				}
				if (result == input) {
					return true;
				}
			}
		}
		return false;
	}

- Sam November 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each possible pair of start numbers validate if the number string is same is sequence created by using them as seed values. If any such pair is found then true else false.

static bool CheckIfAggregate(string num)
            {
                int index1 = 0;
                int index2 = 1;

                while (index1 < num.Length-2)
                {
                    index2 = index1+1;
                    var num1 = int.Parse(num.Substring(0, index1+1));
                    while(index2 < num.Length-1)
                    {
                        var num2 = int.Parse(num.Substring(index1+1, index2-index1));
                        if(IsSequencePresent(num.Substring(index2+1), num1, num2))
                        {
                            return true;
                        }
                        index2++;
                    }
                    index1++;
                }
                return false;
            }

            static bool IsSequencePresent(string num, int num1, int num2)
            {
                if (String.IsNullOrEmpty(num))
                {
                    return false;
                }

                while (String.IsNullOrEmpty(num) == false)
                {
                    if (!num.StartsWith((num1 + num2).ToString()))
                    {
                        return false;
                    }
                    var temp = num1+num2;
                    num1 = num2;
                    num2 = temp;
                    num = num.Substring(temp.ToString().Length);
                }

                return true;
            }

- TestedCode November 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like this. Idea is to scan from right to left. First look for the right most digit to see if it is sum of any two numbers on the left. if it is, recursively do the same thing for the rest of the number on left. if it also returns true then it's aggregated. if the recursive call returns false, then you look for the right most two digits and recursive again.. you do it until n/2 digits on the right, if you can't find it, return false.
there are two recursive calls one dividing the number to left and right parts and second one is to look for the permutations of n*2 digits to see if any of permutations' sum gives the summation for the right most n digits..

#include<vector>
#include <iostream>
using namespace std;


bool isAggregated(int number);

void parseArrayForTwoValues(std::vector<int>& arr, int index, int& left, int& right)
{
	left = 0;
	right = 0;
	int current = 0;
	int base = 1;
	while(current < index)
	{
		int valueToAdd = arr[current];
		left *= base;
		left += valueToAdd;
		base *= 10;
		current ++;
	}

	base =1;
	while(current < (int)arr.size())
	{
		int valueToAdd = arr[current];
		right *= base;
		right += valueToAdd;
		base *=10;
		current ++;
	}
}

bool sumExists(int searchForValue ,std::vector<int> arr, int index)
{
	if (index == arr.size())
		return false;

	for (int i = 0; i < arr.size(); i++)
	{
		int left = 0, right = 0;
		parseArrayForTwoValues(arr, index, left, right);
		if ((left + right ) == searchForValue)
			return true;
		if( sumExists(searchForValue, arr, index+1))
			return true;
		arr.erase(arr.begin());
		if (sumExists(searchForValue, arr, 1))
			return true;
	}
}


int digitLength(int number)
{
	int size = 0;
	if (!number) return 1;
	while(number)
	{
		number /=10;
		size++;
	}
	return size;
}

int extractSubnumberOnRight(int number, int skipFromRight, int numDigits)
{
	while (skipFromRight != 0)
	{
		// reduce the number
		number /= 10;
		skipFromRight--;
	}
	if (numDigits == -1)
		return number;
	int mod = 10;
	while(numDigits > 1)
	{
		mod *= 10;
		numDigits--;
	}
	return number % mod;
}

std::vector<int> numberToArray(int number)
{
	std::vector<int> result;
	if (!number)
	{
		result.push_back(0);
		return result;
	}
	while(number)
	{
		int val = number%10;
		result.insert(result.begin(), val);
		number/=10;
	}
	return result;
}

bool isAggregatedHelper(int number, int numOfDigitsToCheckOnRight)
{
	if (numOfDigitsToCheckOnRight > digitLength(number)/2)
		return false;

	int lookForSum = extractSubnumberOnRight(number, 0, numOfDigitsToCheckOnRight);
	int lookIn     = extractSubnumberOnRight(number, numOfDigitsToCheckOnRight, 2* numOfDigitsToCheckOnRight);
	int restOfNumber = extractSubnumberOnRight(number, numOfDigitsToCheckOnRight*3, -1);

	std::vector<int> arr = numberToArray(lookIn);
	bool sumFound = sumExists(lookForSum, arr, 1);
	if (sumFound)
	{
		if (digitLength(lookForSum)+digitLength(lookIn) == digitLength(number))
			return true;
		if (isAggregated(restOfNumber))
			return true;
	}
	return isAggregatedHelper(number, numOfDigitsToCheckOnRight+1);
}

bool isAggregated(int number)
{
	return isAggregatedHelper(number, 1);
}

int _tmain(int argc, _TCHAR* argv[])
{
	bool result = isAggregated(112112224);
	cout << result << endl;
	return 0;
}

- noname November 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool is_aggnum(int num)
{
        char s[256];
        char tmp1[256], tmp2[256], tmp3[256];
        snprintf(s, 256, "%d", num);

        size_t len = strlen(s);
        for (int i = 1; i < (len+1)/2; i++) {
                strncpy(tmp1, s, i); 
                tmp1[i] = 0;
                int a = atoi(tmp1);
                for (int j = 1; j < (len+1)/2; j++) {
                        strncpy(tmp2, s+i, j); 
                        tmp2[j] = 0;
                        int b = atoi(tmp2);
                        int c = a + b;
    
                        snprintf(tmp3, 256, "%d", c); 
                        int x = strlen(tmp3);
                        //printf("%s %s %s\n", tmp1, tmp2, tmp3);
                        if (strncmp(s+i+j, tmp3, x) == 0) {
                                if (len == i + j + x)
                                        return true;
                                if (is_aggnum(atoi(s+i)))
                                        return true;
                        }   
                }   
        }   
        return false;
}

- Anonymous December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*********************************************************************
* we will name a number "aggregated number" if this number has the following
* attribute: just like the Fibonacci numbers 1,1,2,3,5,8,13.....
*
* the digits in the number can divided into several parts, and the later part
* is the sum of the former parts.
*
* like 112358, because 1+1=2, 1+2=3, 2+3=5, 3+5=8 122436, because 12+24=36
* 1299111210, because 12+99=111, 99+111=210 112112224, because 112+112=224 so
* can you provide a function to check whether this number is aggregated number
* or not?
*
*********************************************************************/

public class AggregatedNumberProblem {
	
	public boolean isAggregated(int number){
		String str = String.valueOf(number);
		boolean status = false;
		for(int length1=1;length1 < ((str.length()/2)+1);length1++){
			for(int length2=1;length2<=((str.length()/2)+1);length2++){
				System.out.println("first"+str.substring(0,length1));
				System.out.println("second"+str.substring(length1,length1+length2));
				System.out.println("rest"+str.substring(length1+length2));
				if( isMatch(str.substring(0,length1),str.substring(length1,length1+length2),str.substring(length1+length2))==true){
					status = true;
				}
			}
		}
		System.out.println("status is"+status);
		
		return status;
	}
	
	public boolean isMatch(String str1,String str2,String str3){
		if(str3.equals("")){return true;}
		System.out.println("first"+str1);
		System.out.println("second"+str2);
		System.out.println("rest"+str3);
		int a = Integer.parseInt(str1);
		int b = Integer.parseInt(str2);
		int c = a+b;
		String temp = String.valueOf(c);
		if(temp.length() > str3.length()){
			return false;
		}
		String third = str3.substring(0,temp.length());
		int match = Integer.parseInt(third);
		if(match == a+b){
			return isMatch(str2,third,str3.substring(third.length()));
		}
		return false;
	}

	public static void main(String args[]){
		AggregatedNumberProblem anp = new AggregatedNumberProblem();
		anp.isAggregated(12113);
	}
}

- Daman December 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I write a code in Java and pass all the cases appeared in this post. Let me know if it has any problem:

public boolean ST(String s){
for(int first = 1; first <= s.length()/2; first++){
for(int second = first+1; second <= (s.length()-first)/2 + first; second++){
if(CK(s.substring(0,first), s.substring(first, second), s.substring(second))){
return true;
}
}
}
return false;
}

public boolean CK(String s1, String s2, String rest){
int i1 = Integer.parseInt(s1);
int i2 = Integer.parseInt(s2);
String sum = (i1 + i2) + "";
if(sum.length() > rest.length()){
return false;
}
if(sum.equalsIgnoreCase(rest.substring(0, sum.length()))){
if(sum.length() == rest.length()){
return true;
}
return CK(s2, sum, rest.substring(sum.length()));
}
return false;
}

- genie@brandeis.edu January 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

122122244112
122+122=244 and 1+1=2 does not pass.

- FriendlyMan January 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool IsAgggregated(string num)
        {
            if (num.Length < 3)
                return false;

            //We just need to find out if the string is an aggregate for all combinations of first 2 numbers
            for (int i = 0; i <= num.Length - 3; i++)
            {
                string numA = num.Substring(0, i + 1);
                for (int j = i + 1; j <= num.Length - 2; j++)
                {
                    string numB = num.Substring(i+1, j-i);
                    if(AggTest(numA, numB, num.Substring(numA.Length + numB.Length)))
                        return true;
                }
            }
            return false;
        }
        public static bool AggTest(string a, string b, string number)
        {
            int numA = int.Parse(a);
            int numB = int.Parse(b);
            int sum = numA + numB;

            if(sum == int.Parse(number))
                return true;

            if(number.StartsWith(sum.ToString()))
            {
                return AggTest(numB.ToString(), sum.ToString(), number.Substring(sum.ToString().Length));
            }
            
            return false;
        }

- BP January 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a working python solution using Shawn's logic:

def find_aggregated_number(A):
    for i in range(1,int(len(A)/2)):
        for j in range(i+1,int(len(A)*2/3)+1):
            if(check_aggregate(i,j,A)):
                return True
    return False

def check_aggregate(i,j,A):
    result = A[0:i] + A[i:j]
    first = int(A[0:i])
    second = int(A[i:j])
    
    while(len(A) > len(result)):
        third = first + second
        result = result + str(third)
        first = second
        second = third 
    return (len(result)==len(A)) and (result == A)

for A in ["112358","122436","1299111210","112112224"]:
    if (find_aggregated_number(A)):
        print("{} is an aggregated number".format(A))
    else:
        print("{} is not an aggregated number".format(A))

- bluepulse5577 September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def is_aggregated(number):
    num = str(number)

    for i in range(1, len(num) - 1):
        summand1 = int(num[:i])

        for j in range(i + 1, len(num)):
            summand2 = int(num[i:j])
            sum = summand1 + summand2;
            pos = j

            while num.startswith(str(sum), pos):
                pos += len(str(sum))
                summand1, summand2 = summand2, sum
                sum = summand1 + summand2

            if pos == len(num):
                return True

    return False

- jgriesser March 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean isAggregatedNumber(int n){
		boolean result = false;
		String num = (n+"");
		int len = num.length();
		if(len<2){return true;}
		int x, y;
		for(int i=1; i<len; i++){
			for(int j=i+1; j<len; j++){				
				x = Integer.parseInt(num.substring(0,i));
				y = Integer.parseInt(num.substring(i,j));
				int s = x+y; String ss = (s+"");
				if(j+ss.length()<=len && ss.equalsIgnoreCase(num.substring(j, j+ss.length()))){
					if(j+ss.length()==len) return true;					
					return isAggregatedNumber(Integer.parseInt(num.substring(i)));
				}				
			}
		}
		return result;
	}

- Andi November 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code works fine for most numbers but fails for numbers like 112233 because you did not handle the logic for the cases where the first three digits agree the requirement and the rest dosenot but the number as a whole does...
how ever i modified your code to make it work let me know if there are any special cases that the following code wont work for.....

package interviews;

public class AggNum {
	public boolean isAggregatedNumber(int n){
		boolean result = false;
		String num = (n+"");
		int len = num.length();
		if(len<2){return true;}
		int x, y;
		int length=1;
		for(int i=length; i<len; i++){
			
			for(int j=i+length; j<len; j++){				
				x = Integer.parseInt(num.substring(0,i));
				y = Integer.parseInt(num.substring(i,j));
				int s = x+y; String ss = (s+"");
				System.out.println("num = "+num+" i = "+i+" j = "+j+" x = "+x+" y = "+y+" s = "+s);
				
				if(j+ss.length()<=len && ss.equalsIgnoreCase(num.substring(j, j+ss.length()))){
					if(j+ss.length()==len) return true;					
					if(isAggregatedNumber(Integer.parseInt(num.substring(i))))
					{
						return true;
					}
					else
					{
						length++;
					}
				}				
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		int n = 114228342;
		
		AggNum a = new AggNum();
		System.out.print(a.isAggregatedNumber(n));

	}

}

- rajesh November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi rajesh,
nice logic but it may fail for the this case
10111 -> 10+1->11

- raj November 19, 2012 | Flag


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