Setup

Register for the lab using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

Goals and Outcomes

In this lab, you will solve some classic software engineering interview questions! By the end of this lab, you will…

By the end of this lab, you will…

• have some experience with interview questions
• see some real life applications of all you’ve learned!

Software Engineering Interviews

Almost all software engineering internships and full-time roles require a technical interview. These interviews usually consist of one or two interviewers, a few coding questions, and a strong emphasis on maximizing and analyzing efficiency. The questions typically focus on applying data structures and algorithms to various problems. That’s great news for us since that is exactly what we have been studying for the last 10 weeks!
We also want to note that while we are focusing on SWE Interviews, these problems are applicable in various scenarios such as competitive programming, algorithms courses, research, and so on! Solving problems like these are a great way to improve your critical thinking skills.

Problem 1: Range Sum of BST

Relevant Companies: Amazon, Meta (formerly Facebook)

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Here’s an example:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.

Constraints:

• The number of nodes in the tree is in the range [1, 2 * 104].
• 1 <= Node.val <= 10^5
• 1 <= low <= high <= 10^5
• All Node.val are unique.

Note: You are not allowed to use/import any data structure besides the TreeNode provided to you!

Problem 2: Merge Sorted Array

Relevant Companies: Meta (formerly Facebook), Apple, Twitter, Google, Netflix, Microsoft

You are given two integer arrays nums1 and nums2, sorted in ascending order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array in ascending order.

The final sorted array should not be returned by the function, but should instead be stored inside the array nums1. To accomodate this, nums1 has a length of m+n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. Remember, nums2 has length n.

Hint: Consider how merge sort works. How can you use the “merge” part of the merge sort algorithm and modify it for this problem?

Note: You are not allowed to use/import any data structure! Do not create a new array. You should simply be overwriting the elements of nums1.

What next?

At this point, you have tried (and solved!) at least two problems that have been asked by top companies in the software industry. This means you are absolutely capable of acing these interviews and getting software engineering internships. We see that the material of CS2 is useful for a variety of problems, and this is exactly why technical interviews test these skills in their interviews.

Note that some companies are still looking for interns for the summer - feel free to ask Adam, Eshani, or Snigdha for some opportunities or look them up online! Further, most companies begin the recruitment process in August, so keep practicing on sites like LeetCode, CodeSignal, HackerRank, etc to prepare yourself.

Lastly, Caltech actually offers a course to help prepare yourself for interviews! Checkout CS12: Technical Interviewing (Section 2) - it is only offered in the fall and consists of mock interviews, weekly practice problems, resume help, and more to help you ace software engineering interviews!

Checking the Results on gitlab