CS 2 (Winter 2022) Lab 08: Technical Interviewing

This lab focuses on introducing students to software engineering interview coding problems.

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…

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:

Note: You are not allowed to use/import any data structure besides the TreeNode provided to you! You should also not be touching nodes beyond those in the range!

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, Snigdha, or Sarah 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

Getting Checked Off

At the end of every lab, you will need to call over a member of course staff to review your work. Sometimes, we will ask you to think about questions that you’ll review with the person who checks you off. For this lab, please answer the following questions: