## Facebook Interview Question for SDE1s

• 0

Country: United States

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

If you remove all the 9s from a sequence of numbers in base 10, then you end up with a sequence in base 9.

So all we have to do is convert n in base 10, to base 9 and return that.

``````int nthNumber(int n) {
return Integer.valueOf(Integer.toString(n, 9));
}``````

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

Cost O(nlogn). The operation of computing if a number contains a 9 is logarithmic as we check each digit we perform this operation n times.
Solution in Python:

``````def contains9(n):
while (n > 10):
if (n % 10) == 9: return True
n /= 10
if n == 9: return True
return False

def filter9(n):
return filter(lambda x: not contains9(x),
xrange(1, n+1))``````

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

Caching will definitely help. Here is how to do it in ZoomBA:

``````removed_9 = seq ( 0 ) ->{
next = \$.p[-1] + 1
while ( '9' @ str(next) ){ next += 1 }
next //return
}
def newNumber(inx){
if ( inx <= 0 ) return ''
while ( inx  >= size ( removed_9.history ) ){
removed_9.next
}
removed_9.history[inx]
}
println( newNumber(1) )
println( newNumber(8) )
println( newNumber(9) )
println( removed_9.history )``````

The result:

``````➜  zoomba99 git:(master) ✗ zmb tmp.zm
1
8
10
[ 0,1,2,3,4,5,6,7,8,10 ]
➜  zoomba99 git:(master) ✗``````

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

1) Just iterate through numbers and ignore number with digit 9 in them like the solutions above which takes nLogN time
2) We can make the above logic fast by not considering any number to the right of 9 for eg if we are at 19876 then o point going to 19877 as 9 is at position 3 so instead jump directly to 20000 or in case of 1888 jump to 2000, this will be faster but still nlogn
3) We can do this in linear time O(N) in best case scenario by:
Lets say countOccurenceOf9(n) returns number of times 9 appears until n then n th number = n + countOccurenceOf9(n) but there must be numbers contains 9 between n and n + countOccurenceOf9(n) so then we find find how many times 9 appeared between n and n + countOccurenceOf9(n) and skip by that amount and repeat

``````public class Solution {
public int getNthNumber(int number, int digit) {
if(digit < 0 || digit > 9) {
return -1;
}
DigitOccurence digitOccurence = new DigitOccurence();
int n = number;
int numOfDigits = digitOccurence.getOccurence(n, digit);
int numToSkip = numOfDigits;
while(numToSkip != 0) {
int newN = n + numToSkip; // but there might be digits between n and n+numOfDigits so we need to skip them too
int t = digitOccurence.getOccurence(newN, digit);
numToSkip = t - numOfDigits;
numOfDigits = t;
n = newN;
}
return this.getNumberAfterRemovinDigit(n, digit);
}

private int getNumberAfterRemovinDigit(int n, int digit) {
if(result == -1) {
return n;
}
int numberWithDigitsWipedOutAfterPosition = n / Math.pow(10, result);
numberWithDigitsWipedOutAfterPosition = n * Math.pow(10, result); // Change 19899 into 19000
return numberWithDigitsWipedOutAfterPosition + Math.pow(10, result); // 19000 + 1000 = 20000 as we need to remove 9 from number
}

private int getMostSygnificantDigitPosition(int n, int digit) {
int position = 0;
int result = -1;
while(n > 0) {
if(n % 10 == digit) {
result = position;
}
position++;
n = n / 10;
}
return result;
}

/********************************** Code below is to find number of occurences of digit d until number n****/
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 19 (conting 22 as one occurence in this case) times from 0 - 99 except 0 which appears 10 times
else if(number < 100) {
return digit == 0 ? 10 : 19;
}
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

``````public static void removenine()
{
for(int count=1; count<=100; count++)
{
String numberAsString = Integer.toString(count);
if (numberAsString.contains("9"));

else
{
System.out.println(numberAsString);
}

}
}``````

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.