## Google Interview Question for SDE-2s

• 0

Country: India
Interview Type: Phone Interview

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

Wow interesting question, okay so lets start with a bit of math before coding,Imagine the number 897 and digit 6:
1) From 0 - 9 every digit comes once
2) From 0 - 99 every digit comes 20 times except 0 which comes 10 times
3) Now count(897, 6) = count(0-799, 6) + count(800-897, 6)
count(0-799, 6) = count(99, digit) * 8 + 100 since 6 <= 7 otherwise 0
count(800-897) = count(97, 6) + 6 == 8 ? 98 : 0
Once you get the formulae right its very simple dynamic programming with memorization:

``````public class DigitOccurence {
public int getOccurence(int number, int digit) {
number = Math.abs(number);
if(digit < 0 || digit > 9) {
return 0;
}

Map<Integer, Integer> cache = new HashMap<>();
return this.getOccurence(number, digit, cache);
}

private int getOccurence(int number, int digit, Map<Integer, Integer> cache) {
// Every digit appears once from 0 - 9
if(number < 10) {
return 1;
}
// Every digit appears 20 times from 0 - 99 except 0 which appears 10 times
else if(number < 100) {
return digit == 0 ? 10 : 20;
}
return cache.get(number);
}

int numDigits = this.getNumDigits(number);
int msd = this.getMostSygnificantDigit(number);
int numButMsd = number - msd * Math.pow(10, numDigits - 1); // get 98 out of 898
/**
Here is the magic:
=> C(898, digit) = C(0-799, digit) + C(800-898, digit) //  msd is 8, numButMsd is 98
=> C(799, digit) = C(99, digit) * 8 + (digit < 8) ? 100 : 0
=> C(800-898, digit) = C(98, digit) + (digit == 8) ? 99 : 0;
=> C(898, digit) = (C(799, digit) = C(99, digit) * 8 + (digit <= 6) ? 100 : 0)
+ (C(98, digit) + (digit == 8) ? 99 : 0);
*/
int occurence = (msd * this.getOccurence(Math.pow(10, numDigits - 1) - 1, digit, cache) + (digit < msd) ? Math.pow(10, msd - 1) : 0)
+ (this.getOccurence(numButMsd, digit, cache) + digit == msd ? numButMsd + 1 : 0);
cache.put(number, occurence);
return occurence;
}

private int getNumDigits(int number) {
int count = 0;
while(number > 0) {
count++;
number = number / 10;
}
return count;
}

private int getMostSygnificantDigit(int number) {
if(number == 0) {
return 0;
}
int numDigits = this.getNumDigits(number);
return number / Math.pow(10, number - 1);
}
}``````

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

In Scala:

``````object CheckNumber {

def main(args: Array[String]): Unit = {
println(checkNum(25,2))
}

def checkNum(x:Int, y:Int):Int = {
var count = 0

def countFreq(n:Int) = {
var num = n
while (num > 0) {
if (num % 10 == y) count += 1
num = num / 10
}
}

1.to(x).foreach(n => countFreq(n))
count
}

}``````

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

``````int numOcurrences(int x, int y)
{
int occur(0);
while (x > 0) {
int val = x;
while (val > 0) {
occur += (val - (val/10)*10 == y) ? 1:0;
val = val / 10;
}
--x;
}
return occur;
}``````

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

In scala:

``````def getOccurance(start: Int, end: Int): List[Int] = {
if (start > end)
getOccurance(end, start)
else {
var result = for (i <- start to end; if (i.toString().contains(start.toString()))) yield i
result.toList
}
}``````

then using REPL
println(getOccurance(2, 25)) //> List(2, 12, 20, 21, 22, 23, 24, 25)
println(getOccurance(25, 2)) //> List(2, 12, 20, 21, 22, 23, 24, 25)

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

In scala:

``````def getOccurance(start: Int, end: Int): List[Int] = {
if (start > end)
getOccurance(end, start)
else {
var result = for (i <- start to end; if (i.toString().contains(start.toString()))) yield i
result.toList
}
}``````

println(getOccurance(2, 25)) //> List(2, 12, 20, 21, 22, 23, 24, 25)
println(getOccurance(25, 2)) //> List(2, 12, 20, 21, 22, 23, 24, 25)

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

This is ok with any x less than 100 but let say x= 222 the code doesn't solve this, Am I wrong?

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

Time: O(log x).
Space: O(1).

``````int DigitCount(int x, int y) {
int count = 0;
for (int place_value = 1; place_value <= x; place_value *= 10) {
int digit = (x / place_value) % 10;
int left = x % place_value;
int right = x / (place_value * 10);
if (digit < y) {
count += right * place_value;
} else if (digit > y) {
count += (right + 1) * place_value;
} else {
count += right * place_value + 1 + left;
}
}
return count;
}``````

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

``````// package whatever; // don't place package name!

import java.io.*;
import java.lang.*;
import java.util.*;

class myCode
{
public static void main (String[] args) throws java.lang.Exception
{

System.out.println(findnumOfDigit(28,2));

}

public static int findnumOfDigit(int num,int target_digit){
int current = num;
int divide = 1;
int res = 0;
while(current!=0){
int r = current%10;
if(r>target_digit){
res += (current/10+1)*divide;
}else if(r==target_digit){
res += (current/10)*divide+num%divide+1;
}else{
res += (current/10)*divide;
}
divide *= 10;
current /= 10;
}

return res;
}
}``````

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

/* Assuming range(x) is 2 digits number and y is single digit number. */

int getOccurances(int x, int y)
{
int count = 0;
if(x>0 && y>0 && x>y)
{
for(int i=1;i<=x;i++)
{
if(i%10 == y)
{
count++;
}
if(i/10 == y)
{
count++;
}
}
}
return count;
}

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

/* Assuming the range (x) is 2 digits number and y is single digit number. */

``````int getOccurances(int x, int y)
{
int count = 0;
if(x>0 && y>0 && x>y)
{
for(int i=1;i<=x;i++)
{
if(i%10 == y)
{
count++;
}
if(i/10 == y)
{
count++;
}
}
}
return count;
}``````

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

``````def count_ocurrences(x: int, y: int) -> int:
"""Count the number of digit 'y' in the numbers of range [0, 'x']
>>> get_ocurrences(25, 2)
9
>>>
"""
assert 0 <= y < 10
count = 0
for i in range(x + 1):
n = i
while n > 0:
if n % 10 == y: count += 1
n /= 10
return count

if __name__ == '__main__':
import doctest
doctest.testmod()``````

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

``````import Queue

def countOccurences(x, y):
q = Queue.Queue(x);
q.put(y);
count = 0;
while not q.empty():
item = q.get();
count = count + str(item).count('2');
for i in range(0, 10):
temp = str(item) + str(i);
if int(temp) <= x :
q.put(temp);
for i in range(1, 10):
temp = str(i) + str(item);
if int(temp) <= x and i != y:
q.put(temp);
print count;``````

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

This is how you do it in ZoomBA:

``````def count_digit( num_range, digit ){
sd = (str(digit))[0]
sum ( [0:num_range +1] ) -> {
sum( str(\$.o).value ) -> { sd == \$.o ? 1 : 0 }
}
}
println( count_digit(25,2) )``````

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

``````public int getOccurence(int x, int y) {
int count = 0;
int itr = y;

while(itr <= x) {
if(itr % 10 == y) {
count++;
}
if(itr != 0 && itr/10 == y) {
count++;
itr++;
} else if(itr/10 == y-1) {
itr = itr + (10 - y);
} else {
itr += 10;
}

}
return count;
}``````

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

``````public int getOccurence(int x, int y) {
int count = 0;
int itr = y;
while(itr <= x) {
if(itr % 10 == y) {count++;}
if(itr != 0 && itr/10 == y) {	count++;
itr++;
} else if(itr/10 == y-1) {itr = itr + (10 - y); }
else {itr += 10;	}
}
return count;
}``````

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

``````public int getOccurence(int x, int y) {
int count = 0;
int itr = y;

while(itr <= x) {
if(itr % 10 == y) {
count++;
}
if(itr != 0 && itr/10 == y) {
count++;
itr++;
} else if(itr/10 == y-1) {
itr = itr + (10 - y);
} else {
itr += 10;
}

}
return count;
}``````

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

in C

``````int getOcurrence(int x, int y)
{
int ret = 0;
int i = 0;
int j = 0;
char temp[3];

for ( i = 0; i <= x; i++)
{
sprintf(temp, "%d", i);
for (j = 0; j < 2; j++)
{
if (temp[j] == '2')
{
++ret;
}
}
}

return ret;
}

int main(void)
{

printf("Number of = %d\n", getOcurrence(25, 2));
return 0;
}``````

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

In C

``````int getOcurrence(int x, int y)
{
int ret = 0;
int i = 0;
int j = 0;
char temp[3];

for ( i = 0; i <= x; i++)
{
sprintf(temp, "%d", i);
for (j = 0; j < 2; j++)
{
if (temp[j] == '2')
{
++ret;
}
}
}

return ret;
}

int main(void)
{

printf("Number of = %d\n", getOcurrence(25, 2));
return 0;
}``````

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

``````int numOcurrences(int x, int y)
{
int occur(0);
while (x > 0) {
int val = x;
while (val > 0) {
occur += (val - (val/10)*10 == y) ? 1:0;
val = val / 10;
}
--x;
}
return occur;
}``````

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

int numOcurrences(int x, int y)
{
int occur(0);
while (x > 0) {
int val = x;
while (val > 0) {
occur += (val - (val/10)*10 == y) ? 1:0;
val = val / 10;
}
--x;
}
return occur;
}

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.