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

** 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, 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`

** Task 2.**
Check to make sure you are passing all the tests on gitlab.