Dropbox [90min] [OA]
Grid Illumination: Given an NxN grid with an array of lamp coordinates. Each lamp provides illumination to every square on their x axis, every square on their y axis, and every square that lies in their diagonal (think of a Queen in chess). Given an array of query coordinates, determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on, that query get turned off. The ranges for the variables/arrays were about: 10^3 < N < 10^9, 10^3 < lamps < 10^9, 10^3 < queries < 10^9.
This problem was quite hard for an internship OA. I got it in first semester freshman year with next to zero coding practice, not to mention reading up CTCI to learn the “right way” to solve problems.
Tips: Use time accordingly to plan solution.
Twitter [easy – medium] [45min] [onsite]
1 Given two numbers as strings, output their sum as a string.
Straightforward. For this question, be careful in the way you handle the carry. Make sure to consider a lot of different cases when testing.
2 Given an array of integers with duplicates, find the int that isn’t a duplicate (this int is guaranteed in the input array). followup: given that your solution will be used as a backend utility function, how to design a return value for invalid inputs?
You can approach it with a straightforward hash map and expect the interviewer to follow up asking for improvement in space complexity (hint: use bit manipulation). For the followup example answers are exception handling mechanisms or constants. I bombed the followup because I simply did not know how to answer it with a lack of design knowledge, but it seems like most of the time interns don’t get this kind of questions.
Behavioral: why major, what’s your proudest achievement, talk about a challenge you’ve encountered in group/team setting
Tips: Follow the process strictly but(!) also listen closely and communicate frequently with interviewer.
Amazon [easy] [OA * 2 + video interview]
debugging and logical questions (straightforward but time goes by really fast so manage it well!)
- amazon fulfillment center, find two boxes whose weight is less or equal to maximum weight
Classic combinatorial optimization, a variant to the knapsack problem.
- amazon data center, round-robin style access, find average waiting time of all clients
This problem was very hard in the sense that there were a lot of things one needs to keep track of when crafting a solution. You need a crystal clear understanding of the problem and plan your solution meticulously.
*Rumors say that if you did exceptionally well in OA2 they will skip the last round of interview and give you an offer
1-on-1 video interview [45min]:
Tell me about a project you’ve worked on with a tight time frame and how you got it done on time
General software engineering knowledge:
What is the difference between an array and linked list?
What is a foreign key in database?
What is TCP? How is reliable data transmission implemented?
1 Find the nth Fibonacci number
I bombed this question because I tried to recall an optimal bottom-up solution but was blanking out on the details of it. After being stuck for about 10 minutes I had to go back to the basic recursive solution, talked about optimization with memoization but ran out of time to actually implement it. I was sure that this left a bad impression; it showed the interviewer that I was unorganized and hasty by trying to jump to code without thinking through my solution first.
2 Check if a string is palindrome
Straightforward. Make sure you can go beyond the solution using something like reverse()
Tips: Don’t pretend to know something that you don’t actually. Never, ever try to come up with an optimal solution upfront without being 100% sure how it works and how to explain it. Start by talking about a naive solution and build it up elegantly to better solutions.
Box (Security Automation) [easy, specialized] [OA]
1 Check if a string is valid ipv4 or ipv6 address
3 Parse base url
Tips: Familiarize yourself with Python features. Know how to use regexp.
* Make sure your interviewer understands every step you take
* Practice problems, see patterns of best solutions (clean code, high performance)
* Be highly comfortable and familiar with one coding language (Python recommended because it’s used pretty ubiquitously at companies for interviews, UNLESS if you’re interviewing with Amazon because only Java and C++ are allowed for OAs)
Good luck and practice often!