Let me begin with a disclaimer. I am NOT a recruiter, and NOT an official interviewer. However, I have interviewed numerous times (over a 100 in total) as an interviewee and an interviewer in real-life situations and mock interview settings. My observations here are empirical and based on my personal experiences, being on both sides of the table.

There are a few areas that a candidate needs to focus on:

- Structure (this post)
- Knowledge
	- Algorithms 
	- Datastructures
- Coding Practice (leetcode and similar platforms)
- Interviewing Skill (mock interview)
	- pramp.com, interviewing.io, etc.

I find that a lot of candidates lack a structure for approaching problems and so their outcomes are highly variant. With a proper structure this variability is drastically reduced. In my humble opinion, this is where books such as Cracking the Coding Interview are truly helpful. The author has laid down a structure for approaching coding questions. The items in the structure serve both as a guide to facilitate the coding interview conversation and also to arrive at a solution.

Additionally, they are milestones for signals that the interviewers score the candidate on. The structure is time tested, is not something novel, and works well for shared coding sessions, even in a non-interview professional / work setting.

Here, I shall use a problem that I solved (non-optimally) using this technique in order to demonstrate that even though the solution is not optimal, the walkthrough allows the interviewee to demonstrate their analysis, depth of understanding and appreciation of the problem. The problem is Student Attendance Record II.

This is a hard level problem on leetcode and I got a time limit exceeded.

• Listen

  • Repeat the question in your own words. Ask a few clarifying questions. Structure as input and output. Write this in the shared codepad. Writing it down crystallizes the requirements in my mind:

  Requirements:
  	Input: a positive integer representing the number of attendance days. 
  		Value is >= 1 and <= 100,000
  	
  	Output: Number of possible rewardable student records modulo 10**9 + 7.
  	
  	Note: 
  		Only a single "A" allowed in a studend attendance record (SAR)
  		Not more than 2 consecutive Ls in a SAR

• Examples

  • Even if the interviewer has given you examples, come up with your own. Think null, empty, negative, zeros, and really large inputs. Write down a few examples:

  n == 0? (not a valid input)
  n == 100,000 (largest possible value of n)

• Bruteforce

  • How would one attempt to solve this problem by exhaustively checking every available option
  • Write a simple pseudocode
  • At this stage one must define variable names, and function names, so that we can communicate precisely with the interviewer, without any ambiguity

  - I am thinking of counting the number of SARs as we are building SARs
  - At each index of the final string we have a choice of A, L, or P
  - If there is an A already, I cannot add any more As
  - If the last two attendances are Ls then the current one cannot be an L
  
  - Therefore, the function needs to track number of As encountered already
  - function needs to capture the last two records (so we can preemptively avoid 3 Ls in a row)
  - Therefore the parameters are:
  	- index (in a rewardable SAR)
  	- count of As in the current SAR
  	- last_two characters of SAR
  		
  So a recursive approach (pseudocode)
  recfn(index, a_count, last_two)
  	#returns the number of ways of constructing a rewardable student attendance record (SAR)
  	# currently at index, already encountered a_count As, current last two characters: last_two
  	#
  	
  	if index == n - 1
  		return 1 #count 1 successful atendance record, AR
  	
  	#now how do I transition to the next indices?
  	
  	#if 0 As encountered then add an A and continue to next index otherwise 0
  	#call this count1
  	
  	#if last two chars are NOT Ls, then add an L and continue
  	#call this count2
  	
  	#add a P and continue
  	#call this count3
  	
  	#return the sum of count1, count2, count3
  • Remember to mention time and space complexities
    • There are n choices for index. 2 choices for a_count (0 or 1). Eight (8) choices for last_two characters 3 x 3 - 1 (AA is NOT allowed as a valid rewardable student attendance record). Therefore space complexity: O(n*2*8) = O(n)
    • At each index we are evaluating three separate computations count1, count2, count3 each of which is a recursive call. Therefore, the time complexity becomes: O(3**n)

• Optimize

  • This is the tricky part that requires knowledge of algorithms and data structures. Specific algoithmic patterns and templates: BFS, DFS, Backtracking etc. Specific data structures: Heaps, Lists, Dictionaries, Tries etc.
  • An optimization that I arrived at here was to memoize (remember the past evaluations of the recursive function). This affects the computational graph in that repeated calculations will be memorized. So, our algoithm has, now, a time complexity of : O(n*2*8) = O(n). This is possible because index can occupy at most n different values. a_count, 2 different values and finally last_two, 8 different choices. However, it appears that this algorithm encounters a TLE in leetcode because even though this approach is asymptotically O(n), it has a large constant factor.
  • This is where an interviewer might suggest clues, which one could build up on
  • Write down the optimized time and space complexities

• Walkthrough

  • Walk through of the algorithm with one or two examples
  • Use a variable tabular structure for iterative functions:

  index    a_count   last_two
  ------------------------------
  
  • Use a tabbed function signature structure for recursive function calls:

  	recfn(0,1,'A')
  		recfn(1,1,'AL')
  		recfn(1,1,'AP')
  	recfn(0,0,'L')
  		recfn(1,1,'LA')
  		recfn(1,0,'LL')
  		recfn(1,0,'LP')
  	recfn(0,0,'P')
  		recfn(1,1,'PA')
  		recfn(1,0,'PL')
  		recfn(1,0,'PP')
  		

  Note: One can clearly see that this is a 3-ary tree, thus leading to a time complexity of O(3**n). However, a simple memoization optimization makes this algorithm linear in n. As you will notice below, memoization when using Python3 is quite simple, just add @functools.lru_cache(None) decorator and the function is now effectively memoized based on the argument values as the dictionary keys

• Implement

  • Finally, coding. Translating your algorithm to your favorite language
  • If algorithm/pseudocode is clearly and granulary written, this step should flow naturally
  • Most interviewees tend to "think" at this step and thus demonstrate a lack of clarity and depth during the "design" phase (algorithm phase), and that is a red flag
  • In our case, the pseudocode easily translates to a simple Python code:

      MOD = 1_000_000_007
      
      @functools.lru_cache(None)
      def rec(index, a_count, last_two):
          
          if index == n - 1:
              return 1
          
          e1 = rec(index+1, a_count+1, (last_two+'A')[-2:]) if a_count == 0 else 0
          e2 = rec(index+1, a_count, (last_two+'L')[-2:]) if last_two != 'LL' else 0
          e3 = rec(index+1, a_count, (last_two+'P')[-2:])
          
          return ( e1 + e2 + e3 ) % MOD
      
      return ( rec(0, 1, 'A') + rec(0, 0, 'L') + rec(0, 0, 'P') ) % MOD
  

• Test

  • Walkthrough a few test cases against the code using the tabular or recursive structure I mentioned above