Google Interview Question
SDE-2sTeam: AdsWorld
Country: India
Interview Type: Phone Interview
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
}
}
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)
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)
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;
}
// 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;
}
}
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()
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;
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;
}
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;
}
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:
- nk June 09, 2017