Google Interview Question for Software Developers


Country: United States




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

A solution that saves state.

public class NumberProblem
{
    // for length two, we know the answer.

    private int[][] lengthTwoResults = 
        {{ 4,5,6,7,8,9 },
        { 5,6,7,8,9},
        { 6,7,8,9 },
        { 7,8,9 },
        { 0,8,9 },
        { 0,1,9 },
        { 0,1,2 },
        { 0,1,2,3 },
        { 0,1,2,3,4 },
        { 0,1,2,3,4,5 }
        };

    private int[][] countState; // Store state.
    
    public void main(String args[])
    {
        int count = 0;
        int n = 5;
        countState = new int[n-1][];
        for (int i = 0; i < n-1; i++)
        {
        	// Set up matrix
            countState[i] = new int[10];
        }
        // Loop through possible start numbers (1-9).  So number starting with 0 not allowed.
        for (int i = 1; i < 9; i++)
        {
            count += getCount(i, n-1);
        }
        System.out.println("Count is " + count);
    }

    /**
	* Recursively go through possible numbers after a prefix.
	**/
    public int getCount(int prefixNumber, int n)
    {
        /* Bottom layer of recursion.  We’ve got one more number to go.  
         * Check the above array. */
        if (n == 1)
        {
            return lengthTwoResults[prefixNumber].length;
        }
		// Check to see if we’ve calculated this result before.
		if (countState[n-1][prefixNumber] != 0)
		{
		    // If so, return it.
		    return countState[n-1][prefixNumber];
		}
		int count = 0;
		// Else, loop through all of the possible next-numbers.
        for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
        {
            // Have we calculated those results before?
            if (countState[n-2][nextPossibleNumber] != 0)
            {
                // Yes, just add to count.
                count += countState[n-2][nextPossibleNumber];
            } else {
                int subCount = getCount(nextPossibleNumber, n-1);
                // Save result in matrix for next time.
                countState[n-2][nextPossibleNumber] = subCount;
                count += subCount;
            }
                
        }
        // Save result of this value of n and prefix for next time.
        countState[n-1][prefixNumber] = count;
        return count;
    }
}

- Andy August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good idea to store the states! One small nit:
The for loop can be cleaner as follows:

for (int nextPossibleNumber: lengthTwoResults[prefixNumber])
        {
            // Have we calculated those results before?
            count += getCount(nextPossibleNumber, n-1);  
        }

I thing all the things you tried to do in the for loop is already done before.

- wwu August 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

// Original method that is called 
int countNumbers(int N)
{
    int result[N];  // this works in latest C standard (or malloc/new)
    
    int count=0;  // passed by referenced into helper
    
    countNumbersHelper(result, 0, N, count);

    return count;
}
    

int countNumbersHelper(int result[], int posToFill, int N, int &count)
{
    // if we have filled N digits into result, then up the count...	
    if(posToFill = N) {
        count++;
	return;
    }
    
    // if the result array still needs a digit to be filled into 'posToFille'
    //   ... try all possible digits 
    for( int i=0; i < 10; i++)
    {
        if(posToFill == 0 && i==0) continue;  // first digit has to be non-zero
        
        //skip if distance to prev. digit < 4
        if( posToFill > 0 && abs(result[posToFill-1] , i ) < 4 ) continue; 
        
        // Try filling digit 'i' into result and recurse to fill remaining result[ ]
        result[posToFill]=i;
        countNumbersHelper(result, posToFill+1, N, count);
    }
}

- RecruitingForSandvineCanada August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice logic.

#include <stdio.h>
int out[100];
int count;
void foo(int *out, int pos_to_fil, int size)
{
        if (pos_to_fil == size) {
                count++;
                return;
        }
        int i;
        for (i=0;i<=9;i++) {
                if (pos_to_fil == 0 && i == 0)
                        continue;
                if (pos_to_fil >0 && abs(out[pos_to_fil-1] -i) < 4)
                        continue;
                out[pos_to_fil] = i;
                foo(out, pos_to_fil + 1, size);
        }
}

int main(void) {
        foo(out, 0, 3);
        printf("count %d\n", count);
        return 0;
}

- variksla August 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

someone please explain what is the question saying, did not get it

- jigili August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

how many possible number your can get where each digit of the possible number is four bigger/smaller than the next digit
if n =3
then 159 is one possible number because the second digit i.e 5 is bigger than 1 by four and also 9 is bigger than second digit i.e 5 by 4.

other possible numbers could be 151,161,171,181,191,162,173 etc

- inadram August 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

someone please explain the question, I really do not get what it says

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

public class CountNumbersNSmallerGreaterThanPrevAfter {
    final static int[][] A = {
        {},                 // 0
        {5, 6, 7, 8, 9},    // 1
        {6, 7, 8, 9},       // 2
        {7, 8, 9},          // 3
        {8, 9},             // 4
        {1, 9},             // 5
        {1, 2},             // 6
        {1, 2, 3},          // 7
        {1, 2, 3, 4},       // 8
        {1, 2, 3, 4, 5},    // 9
    };

    public static void main(String[] args) {
        countNumbers("", 0, 5);
    }

    static int count = 0;
    static void countNumbers(String prefix, int index, int n) {
        if (index == 0) {
            for (int i = 1; i <= 9; i++) {
                countNumbers(prefix + i, index + 1, n);
            }
        } else {
            if (index == n) {
                System.out.println(prefix);
                count++;
            } else {
                int prev = prefix.charAt(index - 1) - '0';
                for (int k : A[prev]) {
                    countNumbers(prefix + k, index + 1, n);
                }
            }
        }
    }
}

- onurraktas August 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Dyanmic programming.
If you know that you have N_{1,n} number finishing with 1 of length n ... N_{9,n} numbers finishing with 9 of length n, then for instance
N_{2,n+1} = N_{6,n}+N_{7,n}+N_{8,n} + N_{9,n}

public class countNumbers {

	public static void main(String[] args) {

		int n   = 5;
		int res = howMany( n );
		System.out.println( res );
	}
	
	static int howMany( int n ){
		int[][] tabRes = new int[n][9];
		for( int i = 0 ; i < 9 ; i++) tabRes[0][i] = 1;		
		for( int i = 1 ; i < n ; i++){
			for( int j = 0 ; j < 4 ; j++ ){
				tabRes[ i ][ j ]     = sumArray( tabRes , i - 1, 4 + j  , 8 );
				tabRes[ i ][ 8 - j ] = sumArray( tabRes , i - 1, 0  , 4-j);
			}
			tabRes[ i ][ 4 ] = tabRes[ i - 1][ 0 ] + tabRes[ i - 1][ 8 ];
		}
		return sumArray( tabRes  , n-1 , 0 , 8 );
	}
	
	static int sumArray( int[][] array , int idxRow , int first , int last ){
		int res = 0;
		for( int i = first; i<= last ; i++){
			res += array[ idxRow ][ i ];
		}
		return res ;
	}

}

- antoinedematteo August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution if we already calculate all number of length (n-1) ending with 0-9.

long improvedCount (int n) {
    long arr[10], tmp[10], tot=0;
    int i, j, k;
    arr[0] = 0; // First number cannot be 0
    tmp[0] = 0;
    for (i =1; i<10; i++) {
        arr[i] = 1; //all elements can occur 1 time in  number of length 1
        tmp[i] = 0;
    }

    for (i=1; i<n; i++) {
        for (j=0; j<10; j++) {
            for (k=0;k<10; k++) {
                if (ABS(k-j) >=4)
                    tmp[j] +=  arr[k];
            }
        }
        for (j=0; j<10; j++) {
            arr[j] = tmp[j];
            tmp[j] = 0;
        }
    }

    tot = 0;
    for (i=0; i<10; i++) {
        tot += arr[i];
    }

    return (tot);
}

- Anonymous August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution if we already calculate all number of length (n-1) ending with 0-9.

long improvedCount (int n) {
    long arr[10], tmp[10], tot=0;
    int i, j, k;
    arr[0] = 0; // First number cannot be 0
    tmp[0] = 0;
    for (i =1; i<10; i++) {
        arr[i] = 1; //all elements can occur 1 time in  number of length 1
        tmp[i] = 0;
    }

    for (i=1; i<n; i++) {
        for (j=0; j<10; j++) {
            for (k=0;k<10; k++) {
                if (ABS(k-j) >=4)
                    tmp[j] +=  arr[k];
            }
        }
        for (j=0; j<10; j++) {
            arr[j] = tmp[j];
            tmp[j] = 0;
        }
    }

    tot = 0;
    for (i=0; i<10; i++) {
        tot += arr[i];
    }

    return (tot);
}

- Anonymous August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we find all possible combination of number ending 0-9 with n-1 length, then we can calculate all possible combinations of bumber ending 0-9 with n length

long improvedCount (int n) {
    long arr[10], tmp[10], tot=0;
    int i, j, k;
    arr[0] = 0; // First number cannot be 0
    tmp[0] = 0;
    for (i =1; i<10; i++) {
        arr[i] = 1; //all elements can occur 1 time in  number of length 1
        tmp[i] = 0;
    }

    for (i=1; i<n; i++) {
        for (j=0; j<10; j++) {
            for (k=0;k<10; k++) {
                if (ABS(k-j) >=4)
                    tmp[j] +=  arr[k];
            }
        }
        for (j=0; j<10; j++) {
            arr[j] = tmp[j];
            tmp[j] = 0;
        }
    }

    tot = 0;
    for (i=0; i<10; i++) {
        tot += arr[i];
    }

    return (tot);
}

- Harish August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we find all possible combination of number ending 0-9 with n-1 length, then we can calculate all possible combinations of bumber ending 0-9 with n length

long improvedCount (int n) {
    long arr[10], tmp[10], tot=0;
    int i, j, k;
    arr[0] = 0; // First number cannot be 0
    tmp[0] = 0;
    for (i =1; i<10; i++) {
        arr[i] = 1; //all elements can occur 1 time in  number of length 1
        tmp[i] = 0;
    }

    for (i=1; i<n; i++) {
        for (j=0; j<10; j++) {
            for (k=0;k<10; k++) {
                if (ABS(k-j) >=4)
                    tmp[j] +=  arr[k];
            }
        }
        for (j=0; j<10; j++) {
            arr[j] = tmp[j];
            tmp[j] = 0;
        }
    }

    tot = 0;
    for (i=0; i<10; i++) {
        tot += arr[i];
    }

    return (tot);
}

- Harish August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the question a bit more? not completely get it.

- Anonymous August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you please explain the question a bit more, not completely get it

- rbk August 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my native language is not english, I dont quite get the questions, could some one rephrase it for me please. Thanks.

- David Chan August 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getAllNum (int n, int length) {
	// cout << n << endl;
	if (length == 1) {
		return 1;
	}
	int combination = 0;
	for (int i = 0; i <= (n-4); i ++) {
		combination += getAllNum(i, length-1);
	}
	for (int i = 9; i >= (n+4); i--) {
		combination += getAllNum(i, length-1);
	}
	return combination;
}

int generateDigit(int length) {
	int total = 0;

	for (int i = 1; i < 10; i ++) {
		total += getAllNum(i, length);
	}

	return total;

}

- DoDoMastery August 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using recursion

public class FourDifference {
    public int find(int length) {
        int count = 0;
        for (int i = 1; i <= 9; i++) {
            count += generateNumber(length, 0, i, 0, 0);
        }
        return count;
    }

    private int generateNumber(int length, int index, int currentNumber, int nextNumber, int count) {
        if (length == index + 1 || nextNumber < 0 || nextNumber > 9) return count;

        if (isNextBiggerByFour(currentNumber, nextNumber) || iSNextSmallerByFour(currentNumber, nextNumber)) {
            if (length == index + 2) count += 1;
            count = generateNumber(length, index + 1, nextNumber, 0, count);
        }
        return generateNumber(length, index, currentNumber, nextNumber + 1, count);
    }


    private boolean isNextBiggerByFour(int currentDigit, int nextDigit) {
        return (nextDigit - currentDigit >= 4);
    }

    private boolean iSNextSmallerByFour(int currentDigit, int nextDigit) {
        return (currentDigit - nextDigit >= 4);
    }
}

source - git.io/vOArQ
test - git.io/vOAom

- inadram August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using dynamic programming approach, while also saving ALL the numbers that are found following the above constraints:

def solution(distance, digits):
    """Find how many numbers of length n are there such that each digit in such a number
    is at least k smaller/greater than the number before and after it.

    e.g. If (n == digits == 5) and (k == distance == 4), then, the numbers "39518" and "15951"
         are both part of the solution set.

    """
    n = digits
    k = distance

    if (n < 2):
        raise ValueError('# of digits must be 2 or above!')
    if (distance >= 10):
        raise ValueError('Distance must be between 0 and 9!')

    # Using a dynamic programming approach:
    # let dp be a two-dimensional array following this property:
    # dpk[n][p] = the set of numbers with `n` digits and prefix number `p` that satisfy the above constraint
    #             for a constant `k`.
    dpk = {}

    # we can construct the solution set for n = 2
    for i in range(10):         # i is the digit in the tens position
        dpk[(2, i)] = set()     # initialize dpk[2][i] to empty
        for j in range(10):     # j is the digit in the ones position
            if abs(i - j) < k:
                continue
            # add all possible two-digit numbers "ij" such that i and j are k distance apart
            dpk[(2, i)].add('{:d}{:d}'.format(i, j))

    # we now have the base dpk[2][i] for all 1-digit prefixes filled in

    # now, iteratively build our solution from n = 3 onward
    # here, for 3 <= n <= digits:
    #
    #       dpk[n][p] = Union{ {"pD" for all D in dpk[n-1][i] } for all i such that |i - p| >= k
    #
    for n in range(3, n+1):
        for p in range(10):                     # build a solution for all prefixes in [0,9]
            build = set()
            dpk[(n,p)] = build
            for i in range(10):                 # find all possible suffixes with a given prefix
                if abs(i - p) < k:
                    continue
                suffixes = dpk[ ((n-1),i) ]
                for suffix in suffixes:
                    build.add('{:d}{:s}'.format(p, suffix))

    return dpk


if __name__ == '__main__':
    distance = 4
    digits = 5

    print 'Problem parameters . . .'
    print '# of digits: {:d}'.format(digits)
    print 'Distance between digits: {:d}'.format(distance)

    dpk = solution(distance, digits)
    
    # from the above, only collect dpk[n] where n == digits
    keys = [(n, p) for (n, p) in dpk if (n == digits and p != 0)]
    # ignoring prefix '0', collect all numbers from each prefix
    sol_numbers = set()
    for key in keys:
        subset = dpk[key]
        for n in subset:
            sol_numbers.add(int(n))

    print
    print 'Solution . . .'
    #print sol_numbers
    print 'There are {:d} such numbers.'.format(len(sol_numbers))


##
## Output:
##
## $ python numdistance.py
## Problem parameters . . .
## # of digits: 5
## Distance between digits: 4
## 
## Solution . . .
## There are 3224 such numbers.
##

- Santoso.Wijaya August 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getCount(int N) {
  if (N <= 0) { return 0; }
  if (N == 1) { return 10; }
  int count1[10] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
  int count2[10] = { };
  int *pPrevCounts = &count1[0];
  int *pCounts = &count2[0];
  for (int iDigit = 1; iDigit < N; ++iDigit) {
    if (iDigit % 2) {
      pPrevCounts = &count1[0];
      pCounts = &count2[0];
    } else {
      pPrevCounts = &count2[0];
      pCounts = &count1[0];
    }
    for (int i = 0; i <= 9; ++i) {
      for (int j = i - 4; j >= 0; --j) {
        pCounts[j] += pPrevCounts[i];
      }
      for (int j = i + 4; j <= 9; ++j) {
        pCounts[j] += pPrevCounts[i];
      }
    }
  }
  int result = 0;
  for (int i = 0; i <= 9; ++i) {
    result += pCounts[i];
  }
  return result;
}

int main() {
  int N = 2;
  cout << getCount(N) << endl;
  cout << countNumbers(N) << endl;
  return 0;
}

- AL August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

int numnum( int n )
{
if ( n <= 1 ) return 0;
int len = 10;
vector< vector<int> > dp( 2, vector<int>( 10, 0 ) );
int pre = 0, cur = 1;
//init
for ( int i = 1; i < len; ++i )
dp[cur][i] = 1;

//dp[cur][i] = { count(nums)| nums are which end with i}

for ( int k = 2; k <= n; ++k ) {
swap( pre, cur );
for ( int i = 0; i < len; ++i ) {
for ( int j = 0; j <= i - 4; ++j ) {
dp[cur][j] += dp[pre][i];
}
for ( int j = i + 4; j < len; ++j ) {
dp[cur][j] += dp[pre][i];
}
}
}
int sum = 0;
for ( int i = 0; i < len; ++i ) {
// cout << dp[cur][i] << " ";
sum += dp[cur][i];
}
cout << endl << " total: " << sum << endl;
}

}}

- rockrock August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int numnum( int n )
{
	if ( n <= 1 ) return 0;
	int len = 10;
	vector< vector<int> > dp( 2, vector<int>( 10, 0 ) );
	int pre = 0, cur = 1;
	//init
	for ( int i = 1; i < len; ++i )
		dp[cur][i] = 1;

	//dp[cur][i] = { count(nums)| nums are which end with i}

	for ( int k = 2; k <= n; ++k ) {
		swap( pre, cur );
		for ( int i = 0; i < len; ++i ) {			
			for ( int j = 0; j <= i - 4; ++j ) {
				dp[cur][j] +=  dp[pre][i];
			}
			for ( int j = i + 4; j < len; ++j ) {
				dp[cur][j] += dp[pre][i];
			}
		}
	}
	int sum = 0;
	for ( int i = 0; i < len; ++i ) {
		// cout << dp[cur][i] << " ";
		sum += dp[cur][i];
	}
	cout << endl << " total: " << sum << endl;
}

- rockrock August 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] map = {0, 5, 4, 3, 2, 2, 2, 3, 4, 5 };

int[][] ranges = new int[][]
{
    new int[] { 5, 6, 7, 8, 9 },
    new int[] { 6, 7, 8, 9 },
    new int[] { 7, 8, 9 },
    new int[] { 8, 9 },
    new int[] { 9, 1 },
    new int[] { 1, 2 },
    new int[] { 1, 2, 3 },
    new int[] { 1, 2, 3, 4 },
    new int[] { 1, 2, 3, 4, 5 }
};

public int NumberCombinations(int n)
{
    if (n == 1)
        return 9;
    else if (n == 0)
        return 0;
    else if (n < 0)
        return -1;

    int total = 0;

    for (int i = 1; i <= 4; i++)
    {
        total += NumberCombinations(n - 1, i);
    }

    total *= 2;

    total += NumberCombinations(n - 1, 5);

    return total;
}


private int NumberCombinations(int n, int value)
{
    if (n == 1)
        return map[value];

    int total = 0;
    int[] a = ranges[value - 1];

    for (int i = 0; i < a.Length; i++)
        total += NumberCombinations(n - 1, a[i]);

    return total;
}

- hnatsu August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can be solved without using the ranges array is pretty much the same

private int NumberCombinations(int n, int value)
{
    if (n == 1)
        return map[value];

    int total = 0;
    int m = value - 4;
    for (int i = 1; i <= m; i++)
        total += NumberCombinations(n - 1, i);

    m = value + 4;
    for (int i = 9; i >= m; i--)
        total += NumberCombinations(n - 1, i);

    return total;
}

- hnatsu August 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fill the table f[][], so that f[n][a] indicates how many integers of length n that start with digit 'a' satisfy the property.
To calculate f[n][a], sum f[n-1][b] for the allowed values of b.

def count(N):
	next_number = {i:[j for j in range(10) if abs(i-j) > 3] for i in range(10)}
	f = [[0] * 10  for i in range(N)]
	for i in range(10): f[0][i] = 1
	for j in range(1, N):
		for i in range(10):
			f[j][i] = sum([f[j-1][k] for k in next_number[i]])
	return sum(f[N-1][j] for j in range(1,10))

- ojy August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fill the table f[][], so that f[n][a] indicates how many integers of length n that start with digit 'a' satisfy the property.
To calculate f[n][a], sum f[n-1][b] for the allowed values of b.

def count(N):
	next_number = {i:[j for j in range(10) if abs(i-j) > 3] for i in range(10)}
	f = [[0] * 10  for i in range(N)]
	for i in range(10): f[0][i] = 1
	for j in range(1, N):
		for i in range(10):
			f[j][i] = sum([f[j-1][k] for k in next_number[i]])
	return sum(f[N-1][j] for j in range(1,10))

- ojy August 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question is similar to the famous "Box Stacking" problem.

int numNumbers4Apart(int N, int previous, int index,
                     vector<vector<int>>& numbersAtIndex) {
    if(index == N) return 1;
    if(previous >= 0 && numbersAtIndex[index][previous] != -1)
        return numbersAtIndex[index][previous];
    int ways = 0;
    for(int i=0; i<10; ++i) {
        if(promising(i, previous)) {
            ways += numNumbers4Apart(N, i, index+1, numbersAtIndex);
        }
    }
    
    if(previous >= 0) {
        numbersAtIndex[index][previous] = ways;
    }
    
    return ways;
    
}

    int N = 5;
    vector<vector<int> > numbersAtIndex(N, vector<int>(10, -1));
    cout << numNumbers4Apart(N, -3, 0, numbersAtIndex) << endl;

- Josh August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Apparently you can't edit your solution...I forgot the 'promising' function

bool promising(int candidate, int previous) {
return abs(candidate - previous) >= 4;
}

- Josh August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic Programming:
Time Complexity O(100*N) = O(N)
Space Complexity O(20) = O(1)

//Mehrdad AP



int solve(int N)
{
	vector<int> dpCur(10,0),dpPrev(10,0);

	dpPrev[0]=0;
	for (int i=1;i<10;i++)
		dpPrev[i]=1;

	for (int i=1;i<N;i++){
		for (int j=0;j<10;j++)
			for (int k=0;k<10;k++)
				if (abs(j-k)>=4)
					dpCur[j]+=dpPrev[k];

		dpPrev=dpCur;
	}

	int ans=0;
	for (int i=0;i<10;i++)
		ans+=dpPrev[i];

	return ans;
}

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

Nice idea using the state logic . Here is my implementation

446 void num_problem_util(char A[][6], int i, int c, int n, char *path, int k, int l) {
447     int j;
448 
449     if(k==n) {
450         //we print only at the leaves
451         printf("%s ", path);
452         return;;
453     }
454 
455     for(j=0;j<c;j++) {
456         if(A[i][j] != 'x') {
457             path[l] = A[i][j];
458             num_problem_util(A, A[i][j]-'0', c, n, path, k+1, l+1);
459         }
460     }
461 }
462 void number_problem() {
463    //maintain the state information, ie for each digit we store the number of permissible next digits
464    char state[][6] = { {'4', '5', '6', '7', '8', '9'},   // digit 0
465                       {'5', '6', '7', '8', '9', 'x'},    // digit 1
466                       {'6', '7', '8', '9', 'x', 'x'},    
467                       {'7', '8', '9', 'x', 'x', 'x'},
468                       {'0', '8', '9', 'x', 'x', 'x'},
469                       {'0', '1', '9', 'x', 'x', 'x'},
470                       {'0', '1', '2', 'x', 'x', 'x'},
471                       {'0', '1', '2', '3', 'x', 'x'},
472                       {'0', '1', '2', '3', '4', 'x'},
473                       {'0', '1', '2', '3', '4', '5'} }; // digit 9
474 
475    /*
476     * now we create a path array array to store all the valid combination of the arrays
477     * the length of the array will be 6 ( max number of column in state array)
478     */
479    
480    char *path = (char*)malloc(sizeof(char)*6);
481    int n;
482    printf("Enter length of digits\n");
483    scanf("%d", &n);
484    
485    num_problem_util(state, 1, 6, n, path, 0, 0);
486 }

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

We can use DP to solve this problem. Define dp[i][j] is the anwer for the first i numbers and the ith number is j, then we have dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][j - 4]

int solve(int n) {

	vector<vector<int> > dp(n, vector<int>(10, 0));
	dp[0][0] = 0;
	for (int i = 1; i < 10; ++i)
		dp[0][i] = 1;

	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 10; ++j) {
			for (int k = 0; k <= j -4; ++k) {
				dp[i][j] += dp[i][k];
			}
		}
	}

	int ans = 0;
	for (int j = 0; j < 10; ++j)
		ans += dp[n - 1][j];

	return ans;
}

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

O(n*k^2) time and O(k) memory where n is the length of the number and k is the size of the digit set. Since k is constant and equal to 10 it is O(n) time and O(1) space.

public static int calcNumberOfNumbers2(int n) {
        if (n==1) { 
            return 9;
        }
        int[] a = new int[10];
        for (int i = 0 ; i < 10; i++) {
            a[i] = 1;
        }
        int[] b = new int[10];
        
        for (int i = 1 ; i < n; i++) {
            b[0] = b[4] + a[5] + a[6] + a[7] + a[8] + a[9];
            b[1] = a[5] + a[6] + a[7] + a[8] + a[9];
            b[2] = a[6] + a[7] + a[8] + a[9];
            b[3] = a[7] + a[8] + a[9];
            b[4] = a[0] + a[8] + a[9];
            b[5] = a[0] + a[1] + a[9];
            b[6] = a[0] + a[1] + a[2];
            b[7] = a[0] + a[1] + a[2] + a[3];
            b[8] = a[0] + a[1] + a[2] + a[3] + a[4];
            b[9] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5];
            a= b;
        }
        return b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + b[7] + b[8] + b[9];
    }

- yaronbic October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

From the simple recurrence relation we can derive a O(1) time and space solution...

First number must not be 0.
So for f(0) = 9.
Looking at 0-9 the only ones that add 2 are going to be 4 and 5 since 4->(0, 8) and 5->(1, 9).
We also know that it'll only add it every other digit since it needs to go from 4->0->4, 4->8->4 or 5->1->5, 5->9->5.
Every layer though, 0->4, 8->4, and 9->5, 1->5. So again we get 2 extra..
f(1) = 11 => {15, 26, 37, 40, 48, 51, 59, 62, 73, 84, 95}
f(2) = 13 => {151, 159, 262, 374, 404, 484, 515, 595, 626, 737, 840, 848, 951, 959}
...
So 9 + 2*length-1

int countNumsDist4(int length) {
		return 9 + 2*(length - 1);
	}

- math.derp October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int countNdigitValues(int n)
{
	if(n<=1)
	{
		return 0;
	}
	int[] ends=new int[10];//store cumulative counts on the number of 2 digit values that end with 0-i(where i>=0 && i<=9)
	int[] begins=new int[10];//store cumulative counts on the number of 2 digit values that begin with 0-9 (where i>=0 && i<=9)
	
	for(int i=0;i<ends.length;i++)
	{
		int digits=countDigitsLess(i)+countDigitsGreater(i);
		ends[i]=ends[i-1]+digits;
		begins[i]=begins[i-1]+digits;	
		
	}
	for(int i=3;i<=n;i++)
	{
		int[] endsUpdate=new int[10];//stores how many i digit values end with each digit using counts for i-1 digits
		int[] beginsUpdate=new int[10];//stores how many i digit values begin with each digit using counts for i-1 digits
		for(int j=0;j<9;j++)
		{
			if(j+4<=9)
			{
				endsUpdate[j]=ends[9]+ends[j+4-1];
				beginsUpdate[j]=begins[9]+begins[j+4-1];
			}
			if(j-4>=0)
			{
				endsUpdate[j]+=ends[j-4];
				beginsUpdate[j]+=begins[j-4];
			}
		}
		ends=endsUpdate;
		begins=beginsUpdate;
	
	}
	return ends[ends.length-1]+begins[begins.length-1];


}
//Time complexity is O(N), space is O(1)


//Count the number of digits 4 or more units less than k.
private int countDigitsLess(int k)
{
	if(k>=4)
	{
		return(k-4+1);
	}

	return 0;
}

//Count the number of digits 4 or more units greater then k.

private int countDigitsGreater(int k)
{
	if(k<=5)
	{
		return(9-(k+4)+1)
	}
	return 0;
}

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

I was thinking more of a recursive solution:

public class CountOfNumsWithDigitsSeperatedByFour {
    public static void main(String[] args)
    {
        System.out.println(CountOfNums(5));
    }
    
    static int CountOfNums(int size)
    {
        int count = 0;
        for(int i = 1; i <= 9; i++)
        {
            count += CountOfNumsStartingWith(i, size-1, i+"");
        }
        
        return count;
    }
    
    static int CountOfNumsStartingWith(int i, int size, String s)
    {
        if (size == 0)
        {
            System.out.println(s);
            return 1;
        }
        
        int count = 0;
        for(int k = i+4; k <= i+9; k++)
        {
            if (IsSafe(k))
            {
                count += CountOfNumsStartingWith(k, size-1, s+k);
            }
        }
        
        for(int k = i-4; k >= i-9; k--)
        {
            if (IsSafe(k))
            {
                count += CountOfNumsStartingWith(k, size-1, s+k);
            }
        }
        
        return count;
    }
    
    static boolean IsSafe(int num)
    {
        return num >= 0 && num <= 9;
    }
}

- Anon April 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class plus4combin {
public static void main(String args[])
{
int array[]=new int[5];
for(int i=1;i<10;i++)
{
	array[0]=i;
method(array,1);	
}
}

private static void method(int[] array,int index) {
	// TODO Auto-generated method stub
	if(index==array.length)
		{
		for(int ch:array)
			System.out.print(ch);
		System.out.println();
		}
	else if(index<array.length)
	{
		for(int k=4;k<10;k++)
		{
			if(array[index-1]+k < 10)
		{array[index]=array[index-1]+k;
		method(array,index+1);
		}
		
		if(array[index-1]-k>0)
			{
			array[index]=array[index-1]-k;
			method(array,index+1);
			}
		}
	}
	
}


}

- Bharaneedharan Dhanaraj August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Example in Node.js:

var out = [];
var n = 5;
var result = 0
function combine(start) {
    if (out.length == n) {
        console.log(out.join(""));
        result++;
        return;
    }
    
    for (var i = 1; i < 10; i++) {
        if (Math.abs(out[out.length-1]-i)<4)
            continue;
        out.push(i);
        combine(i+1);
        out.pop();
    }
}

combine(0);

console.log("Number of possibilities for n = 5: " + result); // 1454

- brazilcoder August 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't seem correct. 3224 looks as a right answer here. The solution doesn't consider 0 at all, does it?

- Alex M. October 29, 2015 | 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