Google Interview Question for SDE-2s


Team: AdsWorld
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;
    }
    else if(cache.hasKey(number)) {
      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);
  }
}

- nk June 09, 2017 | Flag Reply
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    
  }
  
}

- guilhebl June 06, 2017 | Flag Reply
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;
}

- aliasgarg June 08, 2017 | Flag Reply
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)

- Eko Harmawan Susilo June 08, 2017 | Flag Reply
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)

- eko.harmawan.susilo June 08, 2017 | Flag Reply
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?

- Hamada.G.Ibrahim June 09, 2017 | Flag Reply
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;
}

- Anonymous June 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain the mental model plz?

- Manju February 24, 2020 | Flag
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;
    }
}

- tiandiao123 September 07, 2017 | Flag Reply
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;
}

- Abhishek Chavan April 08, 2018 | Flag Reply
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;
}

- Abhishek Chavan April 08, 2018 | Flag Reply
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()

- python April 10, 2018 | Flag Reply
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;

- koustav.adorable June 06, 2017 | Flag Reply
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) )

- NoOne June 06, 2017 | Flag Reply
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;
	}

- ganu June 06, 2017 | Flag Reply
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;
	}

- ganu June 06, 2017 | Flag Reply
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;
	}

- Ganu June 06, 2017 | Flag Reply
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;
}

- Gustavo Camacho June 06, 2017 | Flag Reply
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;
}

- Gustavo Camacho June 06, 2017 | Flag Reply
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;
}

- Aliasgar Gangardiwala June 08, 2017 | Flag Reply
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;
}

- Aliasgar Gangardiwala June 08, 2017 | Flag Reply


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