# Tutor profile: Ryan P.

## Questions

### Subject: Java Programming

What is the difference between an interface and an abstract class in Java?

There are several key differences between the two, but the most important ones are: 1. Interfaces can have only abstract methods. An abstract class can have abstract and non-abstract methods. 2. An interface can extend another Java interface only, an abstract class can extend another Java class and implement multiple Java interfaces. 3. A class can implement more than one interface. It is called multiple inheritances.

### Subject: Software Engineering

Given a string s, find the length of the longest substring without repeating characters.

Keep a hashmap that stores the characters in a string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string, and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward. Since we are using a two-pointer sliding window approach, the time complexity will be O(N) because each pointer would only at most traverse N elements in the array, and so we get O(2N) which simplifies to O(N).

### Subject: Computer Science (General)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Give the time complexity of your solution as well. You can return the answer in any order.

In this problem, we are looking to find the two elements in an array that add up to a target number. If we want to programmatically find which two numbers add up to the target value, we could start by doing the simple brute-force approach to this problem. It's sometimes helpful to start with the brute-force approach to learn how to better optimize the solution later. The most obvious solution for this problem is to check every index in the array and compare it with every other index in the array until you have found the two that add up to the target sum. A more formalized way of putting that is for every index i, we want to check all indices j, such that the array[i] + array[j] equals the target, and that i is not equal to j. This solution works, however, there is an overlap in the numbers we check. This solution would be O(N^2) (where N is the number of elements in the array) because, for every index in the array, we need to compare with every other element in the array, so for N elements, we need to compare with all other (N - 1) elements. Since big O only cares about the highest degree polynomial, that simply reduces to O(N^2). Now that we have a brute-force solution, we can think about how we can optimize this. We can do some reasoning to determine that there's no reason we need to check both array[i] + array[j] = target and array[j] + array[i] = target because addition is commutative, so only one of these checks need to be performed. Additionally, since we're already doing a linear scan of the array, we can memoize the values before, so that we can avoid doing duplicate checks. In this optimized solution, we can use some data structure, to store information about which values we have already seen, and instead of checking each index in the array for every index i, we now just need to check if for each index i, there was an index before it such that array[i] + array[j] = target. If we use a HashMap we can find that information in O(1) time which means that each index would only need to make a single comparison, which reduces our time complexity to O(N). We can deduce that this is the optimal solution because we know each index will need to be checked at least once. After all, if we want to check for the existence of two numbers that add up to a target sum, how would we be able to definitively say it does or does not exist if we haven't exhausted each of the possible numbers in the original list? If we checked all but the last two elements of the list, it's still not possible to conclude the sum doesn't exist, because the last two elements could be the correct solution.

## Contact tutor

needs and Ryan will reply soon.