unknown Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
I didn't check your code, but some optimizations are possible like somehow, keep track of solved sub-problems as they'll surely be repeated in future recursions. Also, perhaps its not necessary to actually populate whole graph, instead just recurse through one path until we get final score and then, during unwinding store results in some map of pair(score) and a string(possible path). Then, during backtracking, we don't have to recurse again for a sub-problem for which a solution is already saved in that map. Also, we don't again recurse for a sub-problem whose reverse pair is already saved in map as key but we'll take care while printing the value(string).
If a graph based solution is not required, one could use a simple iterative solution. Given final result "a : b", there are (a+b)!/a!/b! distinct permutations. We can generate them e.g. like
def print_standings(a, b):
for n in range(2**(a+b)):
l = [(n>>x)&1 for x in range(a+b)]
if sum(l) == a :
i = 0; j = 0;
print('{i} - {j}'.format(**locals()))
for y in l:
if y :
i += 1
else :
j += 1
print('{i} - {j}'.format(**locals()))
print('')
// ZoomBA : Showcasing the recursion. Minimal, and effective.
def traverse(path, destination){
current = (path.split("#"))[-1]
if ( current == destination ){
println ( path.replace('#', '->') )
return
}
#(l,r) = current.split(':')
#(L,R) = destination.split(':')
if ( int(l) > int(L) || int(r) > int(R) ){ return }
// notice conformance : left casting of integer from string
traverse ( str('%s#%s:%s' , path , l , 1 + r ) , destination )
traverse ( str('%s#%s:%s' , path , 1 + l , r ) , destination )
}
traverse ( '0:0' , '2:2' )
c# implementation.
using System;
using System.Collections.Generic;
namespace ScoreCombinations {
class Program {
private static void CreateNode( Node prevNode, int i = 0, int j = 0 ) {
Node node;
if ( i + 1 <= a ) {
node = new Node { i = i+1, j = j, Parent = prevNode };
AddToList(node);
CreateNode( node, i+1, j );
}
if ( j + 1 <= b ) {
node = new Node { i = i, j = j+1, Parent = prevNode };
AddToList( node );
CreateNode( node, i, j+1 );
}
}
private static void PrintPath() {
foreach ( var node in list ) {
Stack<Node> stack = new Stack<Node>();
Node currNode = node;
while ( currNode != null ) {
stack.Push( currNode );
currNode = currNode.Parent;
}
while ( stack.Count > 0 ) {
var elm = stack.Pop();
Console.Write( $"({elm.i},{elm.j}) " );
}
Console.WriteLine("\n-------------------");
}
}
private static void AddToList( Node node ) {
if ( node.i == a && node.j == b ) {
list.Add( node );
}
}
static void Main(string[] args) {
SetScore( 2, 3 );
CreateNode( new Node {i = 0, j = 0, Parent = null} );
PrintPath();
Console.ReadLine();
}
private static int a;
private static int b;
static List<Node> list = new List<Node>();
private static void SetScore( int a1, int b1 ) {
a = a1;
b = b1;
}
class Node {
public int i;
public int j;
public Node Parent;
}
}
}
c++, Binomial Coefficient, O(n*m)
int casesOfSoccerScore(int a, int b) {
int i, j, ret;
vector<int> even, odd;
if (a < b) {
i = a;
a = b;
b = i;
}
even.assign(a + 1, 1);
odd.assign(a + 1, 1);
for (i = 1; i <= b; i++) {
if (i % 2 == 0) {
for (j = 1; j <= a; j++) {
even[j] = even[j - 1] + odd[j];
}
} else {
for (j = 1; j <= a; j++) {
odd[j] = odd[j - 1] + even[j];
}
}
}
if (b % 2 == 0) {
ret = even[a];
} else {
ret = odd[a];
}
return ret;
}
Java solution
(String parsing of score can be avoided by using some form of tuple to represent it)
public static void printAllScorePossibilities(int t1, int t2) {
Queue<List<String>> q = new LinkedList<List<String>>();
Stack<String> initialPath = new Stack<String>();
initialPath.add("0-0");
q.add(initialPath);
while (!q.isEmpty()) {
List<String> tmpPath = q.poll();
String lastNode = tmpPath.get(tmpPath.size() - 1);
if (lastNode.equals(t1 + "-" + t2)) {
System.out.println(tmpPath);
}
String[] s = lastNode.split("-");
int t1Curr = Integer.parseInt(s[0]);
int t2Curr = Integer.parseInt(s[1]);
if (t1Curr < t1) {
List<String> newPath = new ArrayList<String>(tmpPath);
newPath.add((t1Curr+1)+"-"+t2Curr);
q.add(newPath);
}
if (t2Curr < t2) {
List<String> newPath = new ArrayList<String>(tmpPath);
newPath.add(t1Curr+"-"+(t2Curr+1));
q.add(newPath);
}
}
}
public static void main(String[] args) {
printAllScorePossibilities(3,2);
}
Prints:
[0-0, 1-0, 2-0, 3-0, 3-1, 3-2]
[0-0, 1-0, 2-0, 2-1, 3-1, 3-2]
[0-0, 1-0, 2-0, 2-1, 2-2, 3-2]
[0-0, 1-0, 1-1, 2-1, 3-1, 3-2]
[0-0, 1-0, 1-1, 2-1, 2-2, 3-2]
[0-0, 1-0, 1-1, 1-2, 2-2, 3-2]
[0-0, 0-1, 1-1, 2-1, 3-1, 3-2]
[0-0, 0-1, 1-1, 2-1, 2-2, 3-2]
[0-0, 0-1, 1-1, 1-2, 2-2, 3-2]
[0-0, 0-1, 0-2, 1-2, 2-2, 3-2]
Here approach is to use recursion to explore (i+1,j) and (i,j+1) branches and finally prints the path.
package com.explorescrorepossibilities;
public class ScorePossibilities {
static int iFinal=2, jFinal=3;
public static void main(String[] args) {
System.out.println("Final Score :" + iFinal + "-" + jFinal);
System.out.println("Score Possibilities :");
findScorePossibilities();
}
private static void findScorePossibilities(){
findScorePossibilities(0,0,"[");
}
private static void findScorePossibilities(int iNext, int jNext,String pathSoFar) {
if(iNext<iFinal){
findScorePossibilities(iNext+1,jNext, pathSoFar+iNext+"-"+jNext+",");
}
if(jNext<jFinal){
findScorePossibilities(iNext,jNext+1, pathSoFar+iNext+"-"+jNext+",");
}
if(iNext==iFinal && jNext==jFinal){
System.out.println(pathSoFar+iNext+"-"+jNext+"]");
}
}
}
Prints:
Final Score :2-3
Score Possibilities :
[0-0,1-0,2-0,2-1,2-2,2-3]
[0-0,1-0,1-1,2-1,2-2,2-3]
[0-0,1-0,1-1,1-2,2-2,2-3]
[0-0,1-0,1-1,1-2,1-3,2-3]
[0-0,0-1,1-1,2-1,2-2,2-3]
[0-0,0-1,1-1,1-2,2-2,2-3]
[0-0,0-1,1-1,1-2,1-3,2-3]
[0-0,0-1,0-2,1-2,2-2,2-3]
[0-0,0-1,0-2,1-2,1-3,2-3]
[0-0,0-1,0-2,0-3,1-3,2-3]
THe problem is basically what are the different ways we can reach a particular score starting from (0, 0). From each node of a graph, there are only 2 possible paths. e.g for a score node (i, j) the possible pathsa re (i+1, j) or (i, j+1).
We can create the graph recursively first and then run a DFS to find all the paths.
In python:
In the graph creation part, I look for whether (i+1, j) and (i, j+1) are valid and if so, recursively call the same function to populate the graph. Once the score value goes above either i, j or both, the recursion will return.
In the case of the printing, we need to keep track of the path for each node as a string. And append to it as we progress down the tree graph. When we hit a node which has an empty list, then we print out the full path at that point and return. Then the backtracking will take the next potential path and reach the final node again printing out that path as well.
$ python get_score_combination.py
- haroud December 02, 2015{(0, 0): [(1, 0), (0, 1)],
(0, 1): [(1, 1), (0, 2)],
(0, 2): [(1, 2), (0, 3)],
(0, 3): [(1, 3)],
(1, 0): [(2, 0), (1, 1)],
(1, 1): [(2, 1), (1, 2)],
(1, 2): [(2, 2), (1, 3)],
(1, 3): [(2, 3)],
(2, 0): [(2, 1)],
(2, 1): [(2, 2)],
(2, 2): [(2, 3)],
(2, 3): []}
(0, 0),(1, 0),(2, 0),(2, 1),(2, 2),(2, 3)
(0, 0),(1, 0),(1, 1),(2, 1),(2, 2),(2, 3)
(0, 0),(1, 0),(1, 1),(1, 2),(2, 2),(2, 3)
(0, 0),(1, 0),(1, 1),(1, 2),(1, 3),(2, 3)
(0, 0),(0, 1),(1, 1),(2, 1),(2, 2),(2, 3)
(0, 0),(0, 1),(1, 1),(1, 2),(2, 2),(2, 3)
(0, 0),(0, 1),(1, 1),(1, 2),(1, 3),(2, 3)
(0, 0),(0, 1),(0, 2),(1, 2),(2, 2),(2, 3)
(0, 0),(0, 1),(0, 2),(1, 2),(1, 3),(2, 3)
(0, 0),(0, 1),(0, 2),(0, 3),(1, 3),(2, 3)