## Facebook Interview Question for Software Developers

• 6

Country: United States

Comment hidden because of low score. Click to expand.
6
of 8 vote

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

Typical Dynamic Programming

``````public void printSums(int c1, int c2, int c3) {

Set<Integer> sums = new HashSet<>();

for(int sum = 1; sum <= 1000; sum++) {

if(sums.contains(sum - c1) || sums.contains(sum - c2) || sums.contains(sum - c3)) {
System.out.println(sum);
}
}
}``````

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

``````def print_coins_sum(coins, limit)
one_coins = coins.map do |coin|
single_combinations(coin, limit)
end

two_coins = [two_combinations(one_coins[0], one_coins[1], limit), two_combinations(one_coins[0], one_coins[2], limit), two_combinations(one_coins[1], one_coins[2], limit)]

three_coins = two_combinations(two_combinations(one_coins[0], one_coins[1], limit), one_coins[2], limit)
[one_coins + two_coins + three_coins].flatten.uniq.sort
end

def two_combinations(set_one, set_two, limit)
set_one.map do |number|
set_two.map do |second_number|
sum = number + second_number
sum if sum <= limit
end
end.flatten.compact
end

def single_combinations(number, limit)
(1..(limit / number)).to_a.map { |time| number * time }
end

print_coins_sum [10, 15, 55], 1000``````

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

``````/**
* N -> coins.length = 3 = const
* M -> maxValue
* <p>
* time: O(N)
* space: O(1)
*/
private static final class PossibleValuesIterator implements Iterator<Integer> {

private final int[] coins;
private final int maxValue;

final Queue<Integer> minHeap = new PriorityQueue<>();

public PossibleValuesIterator(int[] coins, int maxValue) {

checkNotNull(coins);
checkArgument(maxValue >= 0);

this.coins = Arrays.copyOf(coins, coins.length);

for (int coin : coins) {
if (coin <= 0) {
throw new IllegalArgumentException("Invalid coin value: " + coin);
}
}

this.maxValue = maxValue;

for (int coin : coins) {
}
}

@Override
public boolean hasNext() {
return !minHeap.isEmpty();
}

@Override
public Integer next() {

int value = minHeap.poll();

assert value > 0 : "Negative or zero value detected: " + value;

for (int coin : coins) {

int possibleValue = value + coin;

if (possibleValue > 0 && possibleValue <= maxValue && !minHeap.contains(possibleValue)) {
}
}

return value;
}
}``````

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

x <- c()

for (i in seq(0,1000,15)){
for (j in seq(0,1000,25)){
for (k in seq(0,1000,55)) {
x <- c(x,ifelse (sum(i+j+k)<=1000,sum(i+j+k),0))
x <- unique(x)
}
}
}

sort(x)

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

``````public static void printSums(int[] coins){
boolean[] b = new boolean[1001];
b[0] = true;
Arrays.sort(coins);
for(int i = 0; i < coins.length; i++){
for(int j = coins[i]; j < b.length; j++){
if(b[j - coins[i]]){
b[j] = true;
}
}
}
for(int i = coins[0]; i < b.length; i++){
if(b[i]){
System.out.println(i);
}
}
}``````

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

Space O(n), Time O(n)

``````#!/bin/python
def print_combs(coins, max_num):
checker = [False] * (max_num + 1)
checker[coins[0]] = True
checker[coins[1]] = True
checker[coins[2]] = True
for n in xrange(max_num + 1):
if checker[n]:
print n
if (n + coins[0]) <= max_num:
checker[n + coins[0]] = True
if (n + coins[1]) <= max_num:
checker[n + coins[1]] = True
if (n + coins[2]) <= max_num:
checker[n + coins[2]] = True``````

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

``````#!/bin/python
#!/bin/python

def print_combs(coins, max_num):
checker = [False] * (max_num + 1)
checker[coins[0]] = True
checker[coins[1]] = True
checker[coins[2]] = True
for n in xrange(max_num + 1):
if checker[n]:
print n
if (n + coins[0]) <= max_num:
checker[n + coins[0]] = True
if (n + coins[1]) <= max_num:
checker[n + coins[1]] = True
if (n + coins[2]) <= max_num:
checker[n + coins[2]] = True``````

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

``````def makeChange(change,coins,memo,idx):
if idx >= len(coins):
return 0

if change == 0:
return 1

key = "%s,%s" % (change,coins[idx])
if key in memo:
return 1

ways=0
while change >= 0:
ways+=makeChange(change,coins,memo,idx+1)
change-=coins[idx]

if ways:

return ways

coins=[10,15,55]
coins.sort()
memo=set()
for i in xrange(min(coins),1001):
res=makeChange(i,coins,memo,0)
if res:
print  i``````

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

Not sure if I understood correctly, my implementation using a Sorted List / Max Heap

``````public static IEnumerable<int> Generate(int[] coins, int n)
{
var list = new List<int>();

if (coins == null || coins.Length == 0)
return list;

Array.Sort(coins);
if (n < coins[0])
return list;

var set = new SortedSet<int>();
int m = coins[0];

while (m < n)
{

foreach (var coin in coins)

m = set.First();
set.Remove(m);
}

return list;
}``````

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

``````import java.util.*;

public class CoinProblem {
public static void main(String[] args) {
List<Coin> coinList = new ArrayList<Coin>();
printCombs(coinList);
}
public static void printCombs(List<Coin> coinList) {
Map<Coin, Integer> map = new HashMap<Coin, Integer>();
for(Coin c: coinList){
Integer in = map.get(c);
if(in == null){
map.put(c, new Integer(1));
} else {
map.put(c, in + 1);
}
}
Set<Integer> result = new HashSet<Integer>();
List<Set<Integer>> list = new ArrayList<Set<Integer>>();
for(Coin c: map.keySet()){
}
// pick any Integer from each element to join or not join with any Integer from other Elements
for(int i=0; i< list.size(); i++){
Set<Integer> values = list.get(i);
if(result.isEmpty()){
} else {
Set<Integer> tmpRs = new HashSet<Integer>();
for(Integer value: values){
for(Integer rsi: result){
}
}
}
}
//sort result
List<Integer> listRs = new ArrayList<Integer>(result);
sort(listRs);
for(Integer rsInt: listRs){
System.out.println(rsInt);
}
}
public static void sort(List<Integer> listRs) {
//use any sort here, since its a small list for the examples, using insertion sort here:
for(int i= 1; i< listRs.size(); i++){
for(int j = 0; j< i; j++){
if(listRs.get(i) < listRs.get(j)){
Integer temp = listRs.get(i);
for(int k = i; k> j; k--){
listRs.set(k, listRs.get(k-1));
}
listRs.set(j, temp);
}
}
}
}
public static Set<Integer> findCombs(Coin c, Integer count) {
Set<Integer> set = new HashSet<Integer>();
if(count > 1){
Set<Integer> subSet= findCombs(c, count -1);
for(Integer i: subSet){
}
}
return set;
}
}

enum Coin{
Ten(10),Fifteen(15),FiveFive(55);
private int value;
Coin(int value){
this.value = value;
}
public int getValue(){
return value;
}
}``````

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

``````#include <iostream>
using namespace std;

#include "memory.h"

int main() {

int flag[1000];
memset(flag, 1000, 0);
int coins[] = {10, 13, 16, 55};
int max_num = 1000;

for(int j=1; j<200/coins[0]; j++)
{
if ((coins[0]*j) <= max_num)
flag[coins[0]*j] = 1;
}

flag[coins[0]] = 1;
flag[coins[1]] = 1;
flag[coins[2]] = 1;

for(int i=0; i<200; i++)
{
for(int k=1; k<4; k++)
{
for(int j=1; j<200/coins[k]; j++)
{
if(flag[i] == 1)
{
if ((coins[k]*j + i) <= max_num)
flag[j*coins[k] + i] = 1;
}
}
}
}

for(int i=0; i<200; i++)
{

if(flag[i])
cout << i << endl;
}

return 0;
}``````

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

``````#include <iostream>
using namespace std;

#include "memory.h"

int main() {

int flag[1000];
memset(flag, 1000, 0);
int coins[] = {10, 13, 16, 55};
int max_num = 1000;

for(int j=1; j<200/coins[0]; j++)
{
if ((coins[0]*j) <= max_num)
flag[coins[0]*j] = 1;
}

flag[coins[0]] = 1;
flag[coins[1]] = 1;
flag[coins[2]] = 1;

for(int i=0; i<200; i++)
{
for(int k=1; k<4; k++)
{
for(int j=1; j<200/coins[k]; j++)
{
if(flag[i] == 1)
{
if ((coins[k]*j + i) <= max_num)
flag[j*coins[k] + i] = 1;
}
}
}
}

for(int i=0; i<200; i++)
{

if(flag[i])
cout << i << endl;
}

return 0;
}``````

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

{{
x=0
while 0<=x<=len (list_counter) - 1:
for y in list_counter:
if y + list_counter[x] >1000 or y+list_counter[x] in list_counter: pass;
else: list_counter.append (y+ list_counter[x])
x+=1
}}}

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

Use dynamic programming with memoization. I believe this is O(maxValue), but others can confirm.

``````#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int, bool> cache;

bool exists(int value, vector<int> coins)
{
auto found = cache.find(value);

if (found != cache.end())
{
return (*found).second;
}
else if (value == 0)
{
return true;
}
else if (value < 0)
{
return false;
}

bool result = (exists(value - coins[0], coins)
|| exists(value - coins[1], coins)
|| exists(value - coins[2], coins));
cache[value] = result;
return result;
}

int main()
{
vector<int> coins = {10, 15, 55};

for (int i = 0; i < 1000; i++)
{
if (exists(i, coins))
{
cout << i << endl;
}
}

return 0;
}``````

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

Both of the following solutions should work. However, the second one is more robust.

``````class Problem
{

public static function combination(\$c1, \$c2, \$c3)
{
\$combined1 = \$c1 + \$c2;
\$combined2 = \$c1 + \$c3;
\$combined3 = \$c2 + \$c3;

\$data = [];
for(\$sum = 1; \$sum <= 1000; \$sum++){
if(\$sum % \$combined1 == 0 || \$sum % \$combined2 == 0 || \$sum % \$combined3 == 0){
\$data[] = \$sum;
}

}

return \$data;
}
}``````

The following solution will accept as many arguments as provided and will compute the combinations and returns the data.

``````class Problem
{

// Here you can pass as many arguments are you want. you can pass as little 2 and as many as you wish
public static function combination()
{
\$combos = self::getCombos(func_get_args());
\$totals = [];

for(\$total = 1; \$total <= 1000; \$total++)
{
foreach (\$combos as \$combo) {

if(\$total % \$combo == 0 ) {
\$totals[] = \$total;
break;
}
}
}

return \$totals;
}

// Find all possible combination
private static function getCombos(array \$values) : array
{
\$combos = [];
\$totalValues = count(\$values);

for (\$x = 0; \$x < \$totalValues; \$x++) {

for(\$y = 0; \$y < \$totalValues; \$y++) {

\$combo = \$values[\$x] + \$values[\$y];

if(\$x == \$y || in_array(\$combo, \$combos)) {
continue;
}

\$combos[] = \$combo;
}
}

return \$combos;
}
}``````

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

It seems like , you have to find the number from 10 to 1000 , which is divisible by given numbers (10,15,55).

There should be 2 loops ,
1- From 10 to 1000
2- To check for all coins
Break the inner loop on finding any suc number which is divisible by given coins.

for(int i=10;i<=1000;i++) {
for(int j = 0; j< coins.length;j++){
if(i%coins[j] == 0) {
System.out.println(i);
break;
}
}

}

Given n= 1000 and k = numbers of coins i.e 3
The time complexity of above code in worst case will be O(kn).

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

``````public static void main(String args[]) throws Exception {
printSums(10, 15, 55);
}

public static void printSums(int c1, int c2, int c3) {
BitSet bitSet=new BitSet(1000);
bitSet.set(0);
for (int sum = 1; sum <= 1000; sum++) {
if (bitSet.get(Math.abs(sum - c1)) || bitSet.get(Math.abs(sum - c2)) || bitSet.get(Math.abs(sum - c3))) {
System.out.println(sum);
bitSet.set(sum);
}
}
}``````

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

``````public static void main(String args[]) throws Exception {
printSums(10, 15, 55);
}

public static void printSums(int... c) {
BitSet bitSet = new BitSet(1000);
bitSet.set(0);
for (int sum = 1; sum <= 1000; sum++) {
if (ifSet(bitSet, c, sum)) {
System.out.println(sum);
bitSet.set(sum);
}
}
}

public static boolean ifSet(BitSet bitSet, int c[], int sum) {
for (int temp : c) {
if (bitSet.get(Math.abs(sum - temp)))
return true;
}
return false;
}``````

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.