Problem Solving Meetup - October 9th

Questions for the 9th October, 2018 - online meetup

Note:

Regardless of whether you are new to ds/algo prep or are a seasoned veteran looking for practice, consider following this approach it may help organize your thoughts.

1. Grab a fresh notebook
2. From the front of the notebook, solve problem and as you solve
• Write down the question
• Write down the date/time of when you started and finished.
3. Once you solve, review your answer and reflect the solution.
• Write that down at the back of the notebook on what clues/hints could have made you solve this faster.
• Write down any revelations and hints.

Now on with the questions:

Q1. N-SUM Questions: Questions based on finding elements in an unordered array of integers.

a. Classic 2SUM problem: Given an unordered array of integers, find two numbers that add up to a given target number.

Leetcode link for reference: https://leetcode.com/problems/two-sum/description/

b. Extend 2SUM solution above to 3SUM .. 4SUM?

Followup questions:

• What is the Big O  (Time and Space) of your algorithm?
• Are there alternative approaches that yield better/worse Big-O
• Will you approach be any different if you are dealing with floating point numbers?

Q2. MAX N-PRODUCTS Question: Find the maximum product 

a. MAX - 2PRODUCT Question: Given an unordered array of integers, find two numbers that multiply to the maximum value.

b. MAX - NPRODUCT: Like 2a, but find N numbers. 

Followup question:

• How do you deal with overflows?

Q3. MAX XOR: This one is a tricky question. Given an unordered array of integers, find indices i,j such that a[i]^a[j] is maximum.