Facebook Interview Question
Software DevelopersCountry: United States
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
/**
* 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;
}
}
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);
}
}
}
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
#!/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
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
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;
}
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;
}
}
#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;
}
#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;
}
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;
}
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;
}
}
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).
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);
}
}
}
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;
}
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
- aonecoding January 27, 2017