Position: New Grad SWE 2021
Location: NYC
Interview Round: Phone Screen
Outcome: Rejection

Interviewer and I went through a project on my resume for the first 10 minutes, then we got right into the assessment.

Question 1)
Given two words, return the number of steps it takes to transform one into an anagram of the other.
**Note: interviewer didn't specify whether or not it should return the MINIMUM number of steps necessary

I gave him the solution verbally first, explaining that my approach (which is the approach provided by leetcode) would be to use an an array of size 26 that would mimic the english alphabet. Pass through the first word and increment its respective index count in the alphabet array, and also pass through the second word and decrement the respective index count for that character. By the end of this, we can pass through the alphabet array and add any values in the alphabet array not equal to 0 on to a running sum.

The interviewer agreed with my approach and then offered a twist to the question...
"What if instead of comparing characters among two strings we were to compare something like emojis?"

I told him that we could use two hashmaps (this is where I could have improved my algorithm - while the space complexity wouldn't necessarily change, two hashmaps was still very unnecessary). I used two maps containing characters and character counts for both words and ran through the key value pairs and added the difference between word2map.get(key) - word1map.get(key), and then I did the same run through and did word1map.get(key) - word2map.get(key) and returned the max of the two running difference sums.

With a given hint at the end of my implementation, I was able to get a running program.
I also gave the correct runtime and space complexity (which we both agreed to be O(26) reduced to O(1)).

Question 2)

During the last bit of my interview i was given this question below (didn't have to run, my interviewer just wanted me to talk about how I would solve this):

Given an array that begins in increasing fashion and at a random point begins to descend, find a given target value in less than O(n) time.

example input: [1,3,10,14,16,7,6,2], target value = 3

I verbalized that what we were interested in here was the inflection point of the array (in this example, 16) - the point at which we change direction. This would allow me to reduce my search space. However, my next step intuitively was to compare that inflection point against the first and last element in the array (hoping to draw some type of further conclusion). However, after realizing that the 3 could be on either side, the best solution would be to run a binary search on both sides of the inflection point (this took me too long to realize, in fact I believe it was the interviewer himself that hinted at running 2 binary searches).

He asked me to write the code for a binary search to find the inflection point, I did that and he agreed with my code.
He then asked me what the run time of running two binary searches would be - which I responded with as O(logn).

To sum up my experience, the interviewer was very patient with me and allowed me to express my ideas and guided me in the right direction when I needed it. I think I failed this interview because 1) I didn't consider optimizations after implementing my first program and 2) It took me a bit too long to realize that I could have ran two silmutaneous binary searches for the second question.

Hope this helps anyone preparing for this interview!