Bit of a nitpick here.

“Your interviewer will probably ask about time complexity, seeing if you can reduce the time it takes to run your algorithm from say O(n log(n)) to O(n).”

O(n) time is linear time. O(n log(n)) is loglinear time. Linear time is slower than loglinear time. You want your algorithm to go the other way.