Here is the algorithms question from my job interview: A basketball

bump for curiosity. I remember something like this in my discrete mathematics class in a previous semester but with baseball teams. Im looking through my notes/quizzes for it now.

dude you dont need to know shit like this IRL

Can someone smart tell me what the question is asking and how to solve it. I mean in 15 games all teams would have played once, A1 vs B1.

>>58843075
i dont know how to solve it, but i'm assuming the list isn't ordered to be neat and tidy like that. i.e. in 15 games, some teams play more than once, and others play 0 times.

Using hash map, iterate through the list and for each game, check if neither teams are in your map and if not, add it to the map. Increment counter each time. O(N) worst case.

Sophomore, I don't know shit

>>58843045
Ok, so maybe this is a permutation problem, and for that i believe the formula is
>n/(n!(n-r)!)

n would be the 30 teams and r would be the 15 games, but maybe im pulling this out of my ass, someone call me out if so

>>58843191
Correct.

well if theres 30 teams, then each team will play all 29 other teams

put the teams in an array, loop through it and print out 1 vs 30, 2 vs 29, 3, vs 28, 4 vs 27, etc

thats my guess. probably way wrong tho

>>58843215
edit:
>n!/(r!(n-r)!)

>>58843225

did this just for fun

var teams = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30];

while (!teams[0] =="")
{
    console.log("" + teams.shift() + " played " + teams.pop());
}

>>58843225
this seems correct to me

>>58843564
If I'm not mad, this is O(n) correct? Big O is something I've always had trouble with for some reason...

>>58843677
idk if you can assume its sorted thou

>>58843845
Does it matter if it's sorted? as long as you have no duplicates there won't be an issue.

>>58843842
yes its O(n/2) which simplifies to O(n)

>>58843191
Doesn't necessarily work. For example, imagine that you started with a game in which teams 1 and 2 played (t1 and t2) and continued onward finding match ups for all all teams up through t28. That would leave t29 and t30 unmatched so far. Now imagine there was no match for t29 vs t30. Your algorithm would conclude that there is no solution. However, imagine that there was a match for t1 vs t29 and t2 vs t30. In that case, you would need to discard that first match and pick those other two matches to get a valid solution. You can't just assume that iterating through the list once that you're going to be able to find a correct solution.

>>58843881
ah, thanks for clearing it up for me anon. I was sick and missed the lectures on it.

>>58842945
What a dumb fucking question.
It's O(n).

>>58843892
True, I can't think of a good way to take care of that

>>58843859
yeah but your kinda dodging the question you need to pick your 15 games from a list not just create your own one from an array

It's a minimum matching problem if I'm not mistaken

void findGames(int[] arr)
for(int i=0; i<15; i++){
    setGame(arr[i], arr[i+15]);
}

O(n) complexity. Isn't this all there is to it if there are only 30 teams?

>>58844716
Are you assuming that team 0 plays team 15, team 1 plays team 16, et cetera? If so, that seems like a rather unsafe assumption.

>>58842945
>basketball
I'm transnigger and this question has triggered me. This is a violation if my rights and I am literally shaking.

You'll be hearing from my ACLU lawyers soon, you while male

>>58845831
>If so, that seems like a rather unsafe assumption.
That was the real test. Congratulations, you hired.
https://youtu.be/BdEvuQE6t5c?t=90

>>58842945
if you failed your second CS semester, why do you even apply for a job other than burger flipping ?

>>58845921
Are you OP?

each team is a vertex, each game an edge, and you have to find a k-matching.

>>58843842
Isn't it O(n^2) because you have to check that the teams are unique.

>>58843892
>>58844184

instead of hashmap, use inverted index. OrderedHashMap<Team, List<Tuple<Team, Team>>>

build inverted index in O(n) time, where n in number of games, maintain sorting in List by the sum of length of each teams respective games list asc. Maintain OrderedHashMap ordering by length of respective list asc. Go thru orderedhashmap, pop the first off the list, remove game from other teams list, if it is of length 0, then pop second item off of the list, etc. if you popped a full list then no solution.

O(n + m*max(number of games per team))

>>58842945
Have you never taken a discrete maths class in your life? This is why retards need CS majors, they can't be trusted to learn what they need on their on, even though the information is out there.

>>58846112
Correct. This is a graph problem.

>>58844184
You do multiple pass-through.

>>58843224
It's not.

It seems the problem is called maximum matching.

>>58842945
Create an empty set representing teams
Create a map where key is the game and the value is an array containing the teams who played
Create a map where the key is the team and the value is an array of games
Create a sorted array of keys representing teams by value size (number of games played)
For each entry in your sorted array of keys (ascending order), look up the games they played in
Create a sorted array of games by number of games the opposing team has played
iterating over the array in ascending order...
Add current team and opposing team to set.
remove current and opposing team from maps
If set has size == 30 you have the correct answer
if not done processing
recursively something something

I give up. I have actual projects I was going to work on. Fuck you /g/.

The answer is maximum matching algorithm for general graphs.

>>58842945

It's going to be O(1). If the teams in the list are randomly distributed then for large n you will have early termination at a point in the list independent of n.

>>58848528

On average.

>>58848528
That sounds like BS.

Create a map: team -> games played

Go through list and increment games played for each game (O(n))

Check that there is a feasible solution, all teams have non-zero vals (O(n))

Attempt to remove every game from list (can remove if number can be reduced by 1 and not be zero for both teams). Again linear.

It's O(n)

>>58848615

If the first 30 games in the list are just what you need, trying to apply an algorithm over the entire list would be silly.

An iterative algorithms which searches for a solution by looking at one extra game at a time is obviously possible.

It will obviously terminate at an average number of games smaller than n if the teams are randomly distributed for n tending to infinity.

You could of course say that the teams are non randomly distributed and there is a single unique solution in the list regardless of n. So you on average have to look at a fixed percentage of n. But that should really have been said in the problem statement then, a random distribution is the most natural to assume.

>>58848799

>It will obviously terminate at an average number of games smaller than n if the teams are randomly distributed for n tending to infinity.

I should say :

It will obviously terminate at a fixed average number of games if the teams are randomly distributed for n tending to infinity.

Game 01: Team 01 vs Team 02
Game 02: Team 03 vs Team 04
Game 03: Team 05 vs Team 06
Game 04: Team 07 vs Team 08
Game 05: Team 09 vs Team 10
Game 06: Team 11 vs Team 12
Game 07: Team 13 vs Team 14
Game 08: Team 15 vs Team 16
Game 09: Team 17 vs Team 18
Game 10: Team 19 vs Team 20
Game 11: Team 21 vs Team 22
Game 12: Team 23 vs Team 24
Game 13: Team 25 vs Team 26
Game 14: Team 27 vs Team 28
Game 15: Team 29 vs Team 30

15 games, 30 teams. took me O(2 minutes) to type this.

computer science "degrees" do law like a real alpha.

>>58848841
Pretty much the dumbest thing of 2017

>>58848799
That sounds like total BS. Your argument is based on gut feeling.

> An iterative algorithms which searches for a solution by looking at one extra game at a time is obviously possible.

And what's the algorithm?

/g/ is kinda dumb.

>>58848779
>Check that there is a feasible solution, all teams have non-zero vals (O(n))
Just because all teams played more than 1 games, doesn't mean there's a solution. How dumb are you? In any case, we can assume there's a such solution 15 games that pair 30 teams perfectly.

>Attempt to remove every game from list (can remove if number can be reduced by 1 and not be zero for both teams). Again linear.
Again, super dumb. Assume there is a unique solution, a set of 15 games. With your way, you can accidentally remove one of the games from the unique solution and get no solution.

>>58849099
>Find the minimum spanning tree (kruskals, prims, etc), O(n), done
Do you even know what a minimum spanning tree is?
30 teams, 15 matches. 15 disconnected edges.
It's a maximum matching problem.

Can we just take this moment to remind ourselves that /g/ is not the right place for CS discussion?

>>58842945
is there any optimization to be had by looking at teams that have played less matches than teams who have played a lot?

Also if any team has played every other team theres no point in searching for a match that fits within the constraints ), since you could probably leave them to the end and find a trivial solution for them. In essence they end up behaving like free variables/parametric solution.

>>58849212
And? So what's your solution? Assuming no optimization, there's no such team that played everyone.
Or you don't know what you're talking about and just want to sound smart on /g/. Get a life.

(let* ((league (iota 30 1)) (schedule (map (lambda (z) (map (lambda (y) (cons z y)) (remove (lambda (x) (= x z)) league))) league))) (map (lambda (k) (list-ref (list-ref schedule k) k)) (iota (/ (length league) 2) 0 2)))

>>58849243

No need to be so fucking aggressive you psycho.

I was legitimately asking a question that maybe someone with more experience in the field could offer some insight about. Why are you so angry at someone for taking part in the discussion on a Mongolian Underwater Basket Weaving forum anyways kid?

>>58849287
output is:

((1 . 2) (3 . 4) (5 . 6) (7 . 8) (9 . 10) (11 . 12) (13 . 14) (15 . 16) (17 . 18) (19 . 20) (21 . 22) (23 . 24) (25 . 26) (27 . 28) (29 . 30))

>>58849292
So you really didn't know how to solve the problem.

>>58849287
>>58849295
Oh, I thought it said "GIVE a list where two teams play each other" and thought it wanted all possibilities first, then provide a list of games from that list.

I'm drunk

games = given_list
count = 0
while count happened_games is not 30 {
    team_a = games[count][0]
    team_b = games[count][1]
    if team_a and team_b not a key in happened_games  {
        happened_games[team_a] = count
        happened_games[team_b] = count
    }
    count++

    if count gt games {
        instructions not clear, dick stuck in printer
    }
}

complexity I guess is O(n+1) at worst, with ideally O(15) being the best case scenario.

>>58849311
You sound like a fun guy to hang around.

>>58849332
Omg, just admit you don't understand the problem. No need for personal attacks.

I wrote a program once for a mini4wd tournament of 10+ people that play against each other 3 at a time for 5 manches.
It shuffled the player array and split it in groups of 3, iterated like 100000 times, giving points to each combination to find the best outcome (each player playing against different people/lanes as much as possible).

I'm a bad programmer

>>58843892
Rip me in
>>58849324

Well maybe when checking for keys if either already existed you could handle it in an else statement, but Im going to sleep. Someone make a real solution

>>58848799
>If the first 30 games in the list are just what you need, trying to apply an algorithm over the entire list would be silly.
That's a big IF.
>An iterative algorithms which searches for a solution by looking at one extra game at a time is obviously possible.
Like having a window scanning for 15 matches? Like [0..14],[1..15],... That is stupid. Or you meant increasing the window size? [0..14]->[0..15]->...That's basically the original problem.
>It will obviously terminate at an average number of games smaller than n if the teams are randomly distributed for n tending to infinity.
That's a non-answer.

>>58849361
If it's stupid but it works, it isn't stupid.
Honestly, I think that was smart.

>>58842945
# gamesList = list of games
# unmatchedTeams = initial list of 30 teams
# listOfGames = empty list
# for x = 0; x < gamesList.length;x++{
# for i = x; i < gamesList.length; i++{
# if gamesList[i] teams don't match any teams in listOfGames
# add gamesList[i] to listOfGames
# if listOfGames.length == 15
# break
# }
# if listOfGames.length == 15
# break
# else
# else listOfGames.empty()
#}

I'm guessing O(n^2), because the 3rd loop that checks whether the teams have already been added only gets as big as 14 teams.

>>58849522
Oops, forget about the unused variable unmatchedTeams. And I accidentally put in a double else statement. Sorry, wrote this all on my phone.

>>58849522
>>58849539
Suppose there is an unique solution, a set of 15 matches that include all 30 teams. By your method, you'll always include the first match. If the first match is not part of the unique solution, your program will iterate through all the matches without giving a solution.

>>58849565
Oh, OK lets try this

 
finalist = empty
listOfGames = gameslist

findfifteenunique(gameslist, finalist)

void findfifteenunique(* inputlist, * fillinglist){
for item on inputlist{
    if item is on fillinglist
        Continue 
    for game on fillinglist{
        if any team on item matches any team on game
            continue 2 // continues on outer continue
    }
   fillinglist.add(item)
   if fillinglist.length == 15
       return
   findfifteenunique(inputlist,filinglist
} 

} 

>>58849698
Oh, should probably add a check on the list length and do a continue if 15 at the beginning of the for loop.

>>58849698
Dafuq is
>continue 2 // continues on outer continue

Anyways, same thing, by default your code will try to include the first match. If the unique solution doesn't include the first match, your code will not work. Let's be generous, even if there's multiple solution, it's always possible none of them include the first match.

The standard answer to the problem is maximum matching algorithm for general graph.

>>58849728
I guess it's getting late. I intended to empty the list somehow and try to start with the next but forgot.

>>58849728
>The standard answer to the problem is maximum matching algorithm for general graph.
It's O(V^2 E), since V, the number of teams, is 15 and everyone on this thread takes E, number of matches as N. It's O(N).

>>58849378

It's not such a big if, there are only 465 possible matches after all. Early termination as n becomes large becomes rather likely.

That said, it was kind of silly of me to assume average big-O. Cause why the hell would you make life hard on yourself? They don't specify and worst case big-O is probably easier to calculate. Best case even easier, but I don't think they'll appreciate the assumption.

>>58842945
>Listofteams[]
>Listofgames[]
>Pick à game, remove the two team from the listofteam, pick another game, if the teams aren't on the listofteams pick another game
Eventually remove the games with the teams already picked on listofgames[] so you browse it faster and have less cases to test

>>58849865
>465 possible matches
How did you reach that number?
Isn't it 30*29 = 870 possible pairings.
>Early termination as n becomes large becomes rather likely.
You kept saying that, but what kind of algorithm are you suggesting?
And the interview also asked the time complexity.

>>58842945

function checkbool(tbool, nteams){
  for(iter = 1:nteams){
    if(tbool[iter]) return true;
    }
  return false;
  }
    

function scanlist(list, nteams){
  var teambool[1 : nteams] = false;
  var cont = true;
  var listi = 0;
  var listpicks = [];
  while( cont ){
    var nofind = false;
    while(!nofind){
    var tempi = list[listi];
    var tA = teambool[tempi.teamA] == false;
    var tB = teambool[tempi.teamB] == false;
    nofind = (tA + tB) == 2;
    listi += !nofind;
    }
    teambool[tempi.teamA] = true;
    teambool[tempi.teamB] = true;
    listpicks.push(list[listi]);
    cont = checkbool(teambool, nteams);
  }

>>58849882
You may pick the wrong game.
If for example the correct answer is match 2-16.
Your suggested solution will pick match 1 and has no way to arrive to the real solution, which is match 2,3,4,...,16.

>>58849906
OP problem just talk about finding 15 games, they never talk about an order or a specific game. They just want all the teams with a game

>>58849904
This is a good lesson. Just because it looks fancy and nicely formatted doesn't mean it solves the problem correctly.

>>58849925
There is a list of games.
Let the list of matches be: (3,7),(1,2),(3,4),(5,6),...,(29,30),...
As you can see, a possible solution is match 2-16.
With your method you will include match (3,7) which is not part of the real solution.

It's a graph problem.
Maximum matching on a general graph.
Complexity is O(number of total matches).

>>58849893

> How did you reach that number?

Symmetry.

The algorithm is too much effort, I agree with >>58849766 though. It's going to be O(n). Like the possible matches, the possible set of 15 matches is also bounded (large but bounded). So in the worst case end you will just be doing an O(1) match against each new entry to see if it completes a possible set of matches, so O(n) worst case.

>>58849972
>Symmetry.
Even then, won't it be 30*29/2=435.

>>58849990

>Even then, won't it be 30*29/2=435.

Bugger you're right, I was doing 30+29...+1, 30 too much :/

>>58849972
I think your intuition is correct. The randomized algorithm to solve matching problem is O(V^2.4). From wikipedia. Since V is fixed, 30, it's O(1).

>>58842945
Pretty cool, what kind of job asks you this stuff?
Has to be better than some nu-male cumsucking webdev bs.

I would rather actually code it in some easy ass language such as C# and then put it in pseudocode.

>>58842945
If it was anything like a regular season then it would just be the first 15 games.

>>58842945

list <game> : result
list <team> teamList
list <game> initialList

result = parse ( initialList, result, teamList)

function parse (gameList, result, teamList) : list<game>
    if size of result is 15
        return result
    else
        for game in gamelist
            if (game.teamA not in teamList) and (game.teamB not in teamList)
                add teamA to teamList
                add teamB to teamList
                add game to result
                remove game from gameList
                return parse ( gameList, result, teamList)
            end if
    end if
end function

time complexity should be O(n)

>>58851204
What ignorance. OP and a lot of people here had difficulties solving the problem. And you share a trival shit code thinking you solved the problem.

>>58851264
what's wrong with my trivial shit code ?

Let the number of matches/edges as N.
Then building the graph would be O(N).
Solving maximum matching problem would be O(1) to O(N) depending on implementation. Because number of teams/vertices are fixed at 15.
Randomized algorithms will also give O(1).
All from wikipedia. I'm not even a CS guy.

>>58851273
There's a certain combination(s) of match pairs that solves OP's problem. You just add any match that have new teams. There is no guarantee you will arrive at the correct combination. For example the first match pair you chose may not be part of the solution.

Everyone had submitted similar solution before on this thread. Yours however is the one with the most amateurish feel. Overly complicated for a simple idea.

>>58843564
But you're generating your own list of games instead of picking from the set of matches that you're provided

>>58843215
you have to find games not the number of games.

Permutations allow repeated items (pair of teams) so combination would be better, but you are using the combination formula so your intuition isn't bad. For this you have to create pairs of teams as a item. So the items would explote combinational too.

>>58851516
So basically generate a graph, teams are verticies and games are edges, and find mst?

C++ doesnt work with infinite lists

>>58849963
>>58849728
where can i learn more about this max matching algorithm?

>>58851758
Not MST as in minimum spanning tree. That one is for connected edges. Here we wants unique disconnected edges and vertices. We call it matching.

>>58851811
Dunno, I just reiterate what Wikipedia says.

>>58851601
Permutation doesn't allow repetition you dumb fuck

In python:


f = open("input", "r").readlines()

games = [(int(x.split(",")[0]),int(x.split(",")[1])) for x in f]
count = max([max(x) for x in games]) + 1
done = False

def dfs (stack, games):
global done
if (not done):
overlap = games
for prev in stack:
overlap = overlap & m[prev]

for game in games:
overlapThis = overlap & m[game]

stack.append(game)

if (len(overlapThis) == 0 and len(stack) == count / 2):
print stack
done = True

dfs (stack, overlapThis)
stack.pop()

def noTouch(game):
res = set([])
for g in games:
touch = False
for team in g:
if (team in game):
touch = True
break
if (not touch):
res.add(g)
return res

m = {}
for game in games:
m[game] = noTouch(game)

s = []
dfs(s, set(games))


input file:
0,1
2,3
x,y

>>58853127
Oops, tabs did not carry over.

>>58853127
>>58853136
What's with people not commenting their most likely wrong solution? Is it arrogance?