Facebook Interview Question for Software Developers


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<>();
        sums.add(0);

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

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

- aonecoding January 27, 2017 | Flag Reply
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

- Infamous January 27, 2017 | Flag Reply
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) {
                minHeap.add(coin);
            }
        }

        @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)) {
                    minHeap.add(possibleValue);
                }
            }

            return value;
        }
    }

- m@}{ January 27, 2017 | Flag Reply
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)

- akshay January 27, 2017 | Flag Reply
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);
		}
	}
}

- divm01986 January 29, 2017 | Flag Reply
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

- Anonymous January 30, 2017 | Flag Reply
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

- Ulises January 30, 2017 | Flag Reply
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:
        memo.add(key)

    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

- taylorleebiz January 31, 2017 | Flag Reply
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)
	{
		list.Add(m);
		
		foreach (var coin in coins)
			set.Add(m + coin);
		
		m = set.First();
		set.Remove(m);
	}
	
	return list;
}

- hnatsu January 31, 2017 | Flag Reply
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>();
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Ten);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.Fifteen);
		coinList.add(Coin.FiveFive);
		coinList.add(Coin.Ten);
		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()){
			list.add(findCombs(c, map.get(c)));
		}
		// 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()){
				result.addAll(values);
			} else {
				Set<Integer> tmpRs = new HashSet<Integer>();
				for(Integer value: values){
					for(Integer rsi: result){
						tmpRs.add(rsi + value);
					}
				}
				result.addAll(tmpRs);
			}
		}
		//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>();
		set.add(c.getValue());
		if(count > 1){
			Set<Integer> subSet= findCombs(c, count -1);
			for(Integer i: subSet){
				set.add(c.getValue() + i);
			}
		}
		return set;
	}
}


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

- Mei Li February 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

#include "memory.h"

int main() {
	// your code goes here
	
	    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;
}

- Prabh February 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

#include "memory.h"

int main() {
	// your code goes here
	
	    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;
}

- nprabhanjan February 20, 2017 | Flag Reply
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
}}}

- Lorenzo February 25, 2017 | Flag Reply
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;
}

- LittleEwokGunda July 23, 2017 | Flag Reply
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;
	    }
    }

- Anonymous June 07, 2019 | Flag Reply
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).

- azambhrgn January 27, 2017 | Flag Reply
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);
			}
		}
	}

- koustav.adorable July 23, 2017 | Flag Reply
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;
	}

- koustav.adorable July 23, 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