Facebook Interview Question
SDE1sCountry: United States
#include<iostream>
using namespace std;
int getNextPrime(int n)
{
int c=2;
for(int i=n+1; ;i++)
{
for(int j=2;j<i;j++)
{
if(i%j==0)
c++;
if(c>3)
{
break;
}
}
if(c==2)
{
return i;
}
c=2;
}
}
int main()
{
int n;
int t=2;
int a[100],i=0;
cin >>n;
while(n!=0)
{
if(n%t==0)
{
n=n/t;
a[i]=t;
i++;
}
else
{
t=getNextPrime(t);
}
}
for(int j=0;j<=i;j++)
{
cout << a[j]<<"*";
}
}
Solution in python. Cost O(nLogn).
Log n is the cost of computing the number of 3 at a given number (we divide the number by 10 each time) and we perform this operation n times.
def numof3(n):
total = 0
while (n > 10):
if (n % 10) == 3: total += 1
n /= 10
if n == 3: total += 1
return total
def count3(n):
total = 0
for x in xrange(1, n+1):
total += numof3(x)
return total
for every number from 1 to N count number of digits = K
implementation in Scala:
object NumKCount {
def main(args: Array[String]): Unit = {
println(countK(30,3))
}
def countKDigit(n:Int, k:Int):Int = {
var num = n
var count = 0
while (num > 10) {
val digit = num % 10
if (digit == k) {count += 1}
num = num / 10
}
if (num == k) {count += 1}
count
}
def countK(n:Int, k:Int):Int = {
1.to(n).foldLeft(0)((acc, x) => acc + countKDigit(x, k))
}
}
def countOccurences(x, y):
q = Queue.Queue(x);
q.put(y);
count = 0;
visited = [];
while not q.empty():
item = q.get();
count = count + str(item).count(str(y));
for i in range(0, 10):
temp = str(item) + str(i);
if int(temp) <= x and temp not in visited:
q.put(temp);
visited.append(temp);
for i in range(1, 10):
temp = str(i) + str(item);
if int(temp) <= x and temp not in visited:
q.put(temp);
visited.append(temp);
print count;
countOccurences(40,4);
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 15, 2017