Xerox Interview Questions, Process, and Tips

Round: Technical Interview
Experience: I got stuck in the question as I wasn't able to approach this question. The interviewer helped me out by giving me the following two clues.
1. Two properties of MST : Cycle Property and Min-Cut Property.
2. 4 cases : (modified edge in old MST)*(weight increased or decreased) -> I eliminated two cases as it would return the old MST. Only 10 and 01 need to be considered.
Tips: Requires Graph Theory(Min Spanning Tree algorithm, Min Spanning Tree properties etc.)

Round: Technical Interview
Experience: I had no idea to approach this problem.
I decided to first come up with an algorithm to obtain the maximal transitive sub-tournament given a tournament.
The interviewer then told me to see if I can upper bound the minimum out-degree in a tournament.
After this, the solution was to upper bound the minimum size of the transitive sub-tournament.
HINT : Use the fact that a tournament contains N_choose_2 number of edges for part II.
Tips: Requires very little graph theory. More thinking based, proof oriented. I had to prove every claim I made.

Skills: Graph Theory, Logical And Structured Thinking, Proving Abilitites
College Name: IIT Madras