Interview - Oracle

Question

In the game, the only points that can be made are 2,3,4,5,6,7,8, and they can be made as many times as you like.

What is the total number of combinations a team can play, and a team can reach 50 points.

an example of 8,8,8,8,8,8,8,2 8,8,8,8,8,4,4,2,2 is given. etc...

Answer 1

The problem can be solved using dynamic programming with two parameters:

• i is the index to which we examined
• s is the total score.

f(i, s) will contain the total number of ways to achieve the score s .

Let score[] be a list of unique positive ratings that can be made.

Composition for DP solution:

 f(0, s) = 1, for all s divisible to score[0] f(0, s) = 0, otherwise f(i + 1, s) = Sum [for k = 0 .. floor(s/score[i + 1])] f(i, s - score[i + 1] * k) 

Answer 2

This seems like a coin change issue. I wrote Python code a while ago.

Edited solution:

 from collections import defaultdict my_dicto = defaultdict(dict) def row_analysis(v, my_dicto, coins): temp = 0 for coin in coins: if v >= coin: if v - coin == 0: # changed from if v - coin in (0, 1): temp += 1 my_dicto[coin][v] = temp else: temp += my_dicto[coin][v - coin] my_dicto[coin][v] = temp else: my_dicto[coin][v] = temp return my_dicto def get_combs(coins, value): ''' Returns answer for coin change type problems. Coins are assumed to be sorted. Example: >>> get_combs([1,2,3,5,10,15,20], 50) 2955 ''' dicto = defaultdict(dict) for v in xrange(value + 1): dicto = row_analysis(v, dicto, coins) return dicto[coins[-1]][value] 

In your case:

 >>> get_combs([2,3,4,5,6,7,8], 50) 3095 

Answer 3

This is like visiting a decision tree with 7 branches.

Code:

 class WinScore{ static final int totalScore=50; static final int[] list={2,3,4,5,6,7,8}; public static int methodNum=0; static void visitTree( int achieved , int index){ if (achieved >= totalScore ){ return; } for ( int i=index; i< list.length; i++ ){ if ( achieved + list[i] == totalScore ) { methodNum++; }else if ( achieved + list[i] < totalScore ){ visitTree( achieved + list[i], i ); } } } public static void main( String[] args ){ visitTree(0, 0); System.out.println("number of methods are:" + methodNum ); } } output: number of methods are:3095 

Answer 4

Just stumbled upon this question - here is a C # variation that allows you to explore different combinations:

 static class SlotIterator { public static IEnumerable<string> Discover(this int[] set, int maxScore) { var st = new Stack<Slot>(); var combinations = 0; set = set.OrderBy(c => c).ToArray(); st.Push(new Slot(0, 0, set.Length)); while (st.Count > 0) { var m = st.Pop(); for (var i = m.Index; i < set.Length; i++) { if (m.Counter + set[i] < maxScore) { st.Push(m.Clone(m.Counter + set[i], i)); } else if (m.Counter + set[i] == maxScore) { m.SetSlot(i); yield return m.Slots.PrintSlots(set, ++combinations, maxScore); } } } } public static string PrintSlots(this int[] slots, int[] set, int numVariation, int maxScore) { var sb = new StringBuilder(); var accumulate = 0; for (var j = 0; j < slots.Length; j++) { if (slots[j] <= 0) { continue; } var plus = "+"; for (var k = 0; k < slots[j]; k++) { accumulate += set[j]; if (accumulate == maxScore) plus = ""; sb.AppendFormat("{0}{1}", set[j], plus); } } sb.AppendFormat("={0} - Variation nr. {1}", accumulate, numVariation); return sb.ToString(); } } public class Slot { public Slot(int counter, int index, int countSlots) { this.Slots = new int[countSlots]; this.Counter = counter; this.Index = index; } public void SetSlot(int index) { this.Slots[index]++; } public Slot Clone(int newval, int index) { var s = new Slot(newval, index, this.Slots.Length); this.Slots.CopyTo(s.Slots, 0); s.SetSlot(index); return s; } public int[] Slots { get; private set; } public int Counter { get; set; } public int Index { get; set; } } 

Example:

  static void Main(string[] args) { using (var sw = new StreamWriter(@"c:\test\comb50.txt")) { foreach (var s in new[] { 2, 3, 4, 5, 6, 7, 8 }.Discover(50)) { sw.WriteLine(s); } } } 

Sets 3095 combinations.