# Homework 23 February, 2022

## Q1

If you open the keypad of your mobile phone, it'll likely look like this: ->

Almost every digit is associated with some letters in the alphabet; this allows certain phone numbers to spell out actual words. Ex: the phone number 2686463 can be written as `antoine` or as `ant6463`.

It's important to note that a phone number doesn't represent a single sequence of letters, but rather multiple combinations of letters. For instance, the digit 2 can represent three different letters (a, b, and c).

Given a stringified phone number of any non-zero length, write a function that returns all mnemonics for this phone number, in any order.

For this problem, a valid mnemonic may only contain letters and the digits 0 and 1. In other words, if a digit is able to be represented by a letter, then it must be. Digits 0 and 1 are the only two digits that don't have letter representations on the keypad.

Note that you should rely on the keypad illustrated right for digit-letter associations.

#### Hint

> The first thing you'll need to do is create a mapping from digits to letters. You can do this by creating a hash table mapping all string digits to lists of their respective characters.
>
> This problem can be solved fairly easily using recursion. Try generating all characters for the first digit in the phone number one at a time, and for each character, recursively performing the same action on the the next digit, and then on the digit after that, and so on and so forth until you've done so for all digits in the phone number.

## Q2

Write a function that takes in an array of integers and returns the length of the longest peak in the array.

A peak is defined as adjacent integers in the array that are strictly increasing until they reach a tip (the highest value in the peak), at which point they become strictly decreasing. At least three integers are required to form a peak.

For example, the integers 1, 4, 10, 2 form a peak, but the integers 4, 0, 10 don't and neither do the integers 1, 2, 2, 0. Similarly, the integers 1, 2, 3 don't form a peak because there aren't any strictly decreasing integers after the 3.

#### Hint

> Iterate through the array from left to right, and treat every integer as the potential tip of a peak. To be the tip of a peak, an integer has to be strictly greater than its adjacent integers. Expand outwards from any potential tip until you no longer have a peak

## Q3

Write a function that takes in a string made up of parentheses `(` and `)`. The function should return an integer representing the length of the longest balanced substring with regards to parentheses.

A string is said to be balanced if it has as many opening parentheses as it has closing parentheses and if no parenthesis is unmatched. Note that an opening parenthesis can't match a closing parenthesis that comes before it, and similarly, a closing parenthesis can't match an opening parenthesis that comes after it.

#### Hint

> The most efficient way to solve this problem is to use only two variables to keep track of the numbers of opening and closing parentheses, respectively, as you traverse the string.
> Think about how you can use these two pieces of information alone to find the longest balanced substring.
> You may have to traverse the string twice, once left to right, and once right to left.

## Q4

You're given three inputs, all of which are **Nodes** that have a **directReports** property pointing to their direct reports. The first input is the top manager in an organizational chart (i.e., the only instance that isn't anybody else's direct report), and the other two inputs are reports in the organizational chart. The two reports are guaranteed to be distinct.

If you look at the graph at right, Node B has **directReports**: **[D, E]**. Then Node D has **directReports**: **[H, I]**. So lowest common manager between Node E and Node I is Node B.

A node can report to himself while having people under him reporting to him too. So lowest common manager between **Node C** and **Node G** is **Node C**.

Write a function that returns the lowest common manager to the two reports.

Note:
This problem is very similar to common ancestor problem we solved before. Difference is instead of nodes pointing to parent connection, here we have nodes pointing to children connections. You may have the idea to convert nodes in this input to a tree of nodes having parent connection, then apply the solution of common ancestor. **This will not be regarded as a valid solution**.

#### Hint

> The lowest common manager to two reports in an organizational chart is the root of the lowest subtree containing those two reports. Find that lowest subtree to find the lowest common manager.
>
> To find the lowest subtree containing both of the input reports, try recursively traversing the organizational chart (DFS from root), and keeping track of amount of important report currently traversing node contains, It could be 0, 1 (either of reportOne or reportTwo) or 2 (both reportOne and reportTwo). The first node to contain both should return the lowest common manager for all of the subtrees above it that contain it, including the entire organizational chart, Effectively returning the result of the problem.

## Q5

From Wikipedia, the concept of six degrees of separation "is the idea that all people are six, or fewer, social connections away from each other."

For example, if Clement and Antoine are friends, they share **one** degree of separation. If Simon is Antoine's friend but not Clement's friend, then Clement and Simon share **two** degrees of separation, since they're connected by Antoine.

You're given a directory of friends lists (a map of people's names pointing to lists of their friends' names) as well as the names of two target people.

Note that if Antoine is Clement's friend, it follows that Clement is Antoine's friend. Thus, if person A's name is found in person B's friends list, then person B's name will be found in person A's friends list.

Picking one target person, you have to implement a intermediate function that returns the amount of people having more than six degrees of separation away from **target** person.

Now write another function that returns the name of the person having fewer "six degrees of separation". AKA run the intermediate function on both target person, return name of person who returned lower amount. If both target person returns same amount, output empty string "".

#### Hint

> You can solve this question pretty simply by treating the friends lists as a graph and using breadth-first search.
>
> Create a helper method that traverses the friends lists using breadth-first search, starting at a given person. This method will have to keep track of every visited person, so as not to traverse parts of the graph multiple times, and it'll also have to keep track of the distance of each friend from the starting person; this will be the degree of separation.