The role came from a TikTok HR reach-out. There was no HR call, they only asked about my sponsorship situation over email and then scheduled a 1-hour phone interview.
The interview was on HackerRank. I started with a self-introduction, then a behavioral question: tell me about a challenge.
After that came a LeetCode problem, Possible Bipartition:
Split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Given the integer n and the array dislikes where dislikes[i] = [a_i, b_i] indicates that the person labeled a_i does not like the person labeled b_i, return true if it is possible to split everyone into two groups in this way.
I had never seen this problem and had never practiced graph coloring, so I had no idea where to start. With some hints from the interviewer, my solution was:
- Build a map where the key is a person's label and the value is the people they have a dislike relationship with, recorded in both directions.
- Use two HashSets to represent the two groups.
- Iterate over the map. If the current person has not been assigned to a group yet, put them in the first group by default.
- Check all of their neighbors. If a neighbor is already in the same group as them, return
false. Otherwise put the neighbor in the other group. - If the iteration ends with no conflict, return
true.
Oh, and there were no provided test cases. I had to compile the code and write my own test cases by hand. I used the two given examples, wrote the test cases in the main function and printed the answers.
The interviewer kept stressing that my solution needed to be optimized. I was mostly thinking about time and space complexity, but it already felt like O(n + m) and I wasn't sure what else to optimize.
Only later, when I went back to LeetCode, did I realize it needed BFS/DFS...
Hope this write-up helps everyone. Good luck with your interviews, and I hope you all land the offers you want soon!
Discussion
Loading comments…