Panda Guru LogoPanda
Guru

TikTok SWE Interview - Pass or Reject ?

Round 1

Questions: The interviewer asked about the Longest Increasing Subsequence.

The candidate mentioned a brute force approach involving sorting and iterating through the sequence to find the longest one. The interviewer prompted for performance details, leading to a discussion on time and space complexity.

Follow-up Question:

Candidate's Approach

The candidate proposed a hash set approach:

  • Add all elements to a set.
  • Iterate through the set and for each number, explore left and right to find the longest sequence.
  • Example sequence: (5, 2, 1, 8, 9, 4, 3, 7)
    • Starting at 5, the candidate would go left to find 1, then right to find the sequence 1-2-3-4-5.
  • To avoid revisiting elements, the candidate suggested using an extra visited set.
  • The candidate calculated the time complexity as O(n) and space complexity as O(n) for both sets.

The interviewer suggested an optimization hint:

  • Instead of going left every time, check if num - 1 exists to start finding the sequence, which could eliminate the need for the visited set.

The candidate struggled to fully grasp this hint under pressure but incorporated it into the final code, albeit still using the visited set unnecessarily. The candidate successfully wrote working code and ran test inputs provided by the interviewer.

Interviewer's Feedback

No feedback provided.