# 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! You should also not be touching nodes beyond those in the range!**

** Task 0.**
Write an algorithm that solves Range Sum of BST in `Problem1.java`

.
Make sure you have the right algorithm by running the B Tests!

# 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.**

** Task 1.**
Write an algorithm that solves Merge Sorted Array in `Problem2.java`

.
Make sure you have the right algorithm by running the A Tests!

## 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`

** Task 2.**
Check to make sure you are passing all the tests 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:

** Task 3.**
Click the “Submit OpenEndeds” button below.
Then, call over a member of course staff by typing “`!question done`

” into your `workspace`

text channel. Someone will get to you as soon as possible.