Facebook Interview Question for SDE1s


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));
}

- Blackbird June 10, 2017 | Flag Reply
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))

- Fernando June 09, 2017 | Flag Reply
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) ✗

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