Here is the algorithms question from my job interview:
A basketball league has 30 teams. Given a list of games where two teams play against one another, Write pseudocode to find 15 games in which all 30 teams play once. Calculate the time complexity of your algorithm (i.e. the big O notation), given n number of games in the list.
I have never felt less qualifed for a job in my life.
Other urls found in this thread:
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.
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
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
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
edit:
>n!/(r!(n-r)!)
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());
}
this seems correct to me
If I'm not mad, this is O(n) correct? Big O is something I've always had trouble with for some reason...
idk if you can assume its sorted thou
Does it matter if it's sorted? as long as you have no duplicates there won't be an issue.
yes its O(n/2) which simplifies to O(n)
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.
ah, thanks for clearing it up for me user. I was sick and missed the lectures on it.
What a dumb fucking question.
It's O(n).
True, I can't think of a good way to take care of that
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
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.
>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
>If so, that seems like a rather unsafe assumption.
That was the real test. Congratulations, you hired.
youtu.be
if you failed your second CS semester, why do you even apply for a job other than burger flipping ?
Are you OP?
each team is a vertex, each game an edge, and you have to find a k-matching.
Isn't it O(n^2) because you have to check that the teams are unique.
instead of hashmap, use inverted index. OrderedHashMap
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))
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.
Correct. This is a graph problem.
You do multiple pass-through.
It's not.
It seems the problem is called maximum matching.
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 Sup Forums.
The answer is maximum matching algorithm for general graphs.
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.
On average.
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)
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.
>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.
Pretty much the dumbest thing of 2017
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?
Sup Forums is kinda dumb.
>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.
This is a really simple graph problem
30 teams => 30 nodes
Every game in the list is an edge
Find the minimum spanning tree (kruskals, prims, etc), O(n), done
>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 Sup Forums is not the right place for CS discussion?
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.
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 Sup Forums. 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)))
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?
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))
So you really didn't know how to solve the problem.
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.
You sound like a fun guy to hang around.
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
Rip me in
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
>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.
If it's stupid but it works, it isn't stupid.
Honestly, I think that was smart.
# 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.
Oops, forget about the unused variable unmatchedTeams. And I accidentally put in a double else statement. Sorry, wrote this all on my phone.
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.
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
}
}
Oh, should probably add a check on the list length and do a continue if 15 at the beginning of the for loop.
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.
I guess it's getting late. I intended to empty the list somehow and try to start with the next but forgot.
>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).
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.
>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
>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.
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);
}
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.
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
This is a good lesson. Just because it looks fancy and nicely formatted doesn't mean it solves the problem correctly.
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).
> How did you reach that number?
Symmetry.
The algorithm is too much effort, I agree with 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.
>Symmetry.
Even then, won't it be 30*29/2=435.
>Even then, won't it be 30*29/2=435.
Bugger you're right, I was doing 30+29...+1, 30 too much :/
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).
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.
If it was anything like a regular season then it would just be the first 15 games.
list : result
list teamList
list initialList
result = parse ( initialList, result, teamList)
function parse (gameList, result, teamList) : list
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)
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.
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.
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.
But you're generating your own list of games instead of picking from the set of matches that you're provided
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.
So basically generate a graph, teams are verticies and games are edges, and find mst?
C++ doesnt work with infinite lists
where can i learn more about this max matching algorithm?