## unknown Interview Question for Software Engineers

• 2

Country: United States
Interview Type: Phone Interview

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

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.

``````def create_score_graph(current_score, final_score, graph):
(I, J) = final_score
(i, j) = current_score
if i < I:
if (i+1, j) not in graph[(i, j)]:
graph[(i, j)].append((i+1, j))
if (i+1, j) not in graph.keys():
graph[(i+1, j)] = []
create_score_graph((i+1, j), final_score, graph)
if j < J:
if (i, j+1) not in graph[(i, j)]:
graph[(i, j)].append((i, j+1))
if (i, j+1) not in graph.keys():
graph[(i, j+1)] = []
create_score_graph((i, j+1), final_score, graph)

def print_all_scores(graph, current_score, pstr):
(i, j) = current_score
mystr = pstr[:]
if not mystr:
mystr += "(%s, %s)" % (i, j)
else:
mystr += ",(%s, %s)" % (i, j)
if not graph[current_score]:
print mystr
else:
for score in graph[current_score]:
print_all_scores(graph, score, mystr)

graph = {(0,0): []}
final_score = (2, 3)
start_score = (0, 0)
create_score_graph(start_score, final_score, graph)
import pprint
pp = pprint.PrettyPrinter()
pp.pprint(graph)
# graph should have all possible path to final score
print_all_scores(graph, start_score, "")``````

\$ python get_score_combination.py
{(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)

Comment hidden because of low score. Click to expand.
2

the graph is really just a nxm matrix :)

Comment hidden because of low score. Click to expand.
2

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).

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

Quick thought: We may be able to do BFS instead of DFS and accumulate the paths to each node (while adding the current node). At the final node, add the node to each of the accumulated paths and print out.
All the paths are of equal length in this problem.

someone: good point.

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

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('')``````

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

I dont think just printing the possible combinations is sufficient. Each intermediate score can ben reached via different paths, and this only prints each one once.

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

``````// 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' )``````

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

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 };
CreateNode( node, i+1, j );
}
if ( j + 1 <= b ) {
node = new Node { i = i, j = j+1, Parent = prevNode };
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 ) {
}
}

static void Main(string[] args) {

SetScore( 2, 3 );
CreateNode( new Node {i = 0, j = 0, Parent = null} );
PrintPath();
}

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;
}
}
}``````

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

complexity: O(m+n), where m - total number of nodes, n - number of leaf nodes.
Roughly O(m).

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

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;
}``````

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

The task requires "print all the possible ways", but this solution only counts the number of all possible ways.

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

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) {
Stack<String> initialPath = new Stack<String>();

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);
int t2Curr = Integer.parseInt(s);
if (t1Curr < t1) {
List<String> newPath = new ArrayList<String>(tmpPath);
}
if (t2Curr < t2) {
List<String> newPath = new ArrayList<String>(tmpPath);
}
}
}

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]``````

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

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]``````

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.