Intro

Questions that didnt came off of a specific source

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Input:
nums = [2, 7, 11, 15], target = 9

Output:
[0, 1]

Implementation: TwoSum

First question is, can there be duplicate numbers. Lets assume no for now. Second question is, can there be multiple soltions. Lets assume no here as well.

In that case, the first solution is to run a set of nested loops, where the outer loop fixes an element and the inner loop searches for its compliment. The time complexity is O(n^2) in that case and the space complexity is O(1) since we are not using any extra space. We can improve the time complexity at the expense of space complexity by keeping a Set.

If there were duplicates, we would need to make sure all indices are captured. However, with this logic, we cannot return the indices with the same time complexity. Note that we will be storing the indices in the Set for the Map's value in an unsorted order. So, if the index of the number we are checking exists, it could potentially take us another O(n) time to find the compliment index from the Set. We can do better, sort the set and change this to O(nlogn), but it will never be constant. The only way it can be constant is if we change the question requirements to return the number and compliment, not the indices.

2Sum Follow up: What if the input array is sorted?

If the array is sorted, then we know the biggest numbers are to the right, and the smallest numbers are to the left. Let's take the above example:

nums = [2, 7, 11, 15], target = 9

2       7       11      15
l                       r

We can start with two pointers: l and r. 

The sum is 17. Since, its larger than target, the actual target, if it exists, must be with a lesser number. So we move right.

2       7       11      15
l               r

Sum is 13 now, so we move r again.

2       7       11      15
l       r

We get the target here.

This approach has a time complexity of O(n) and a space complexity of O(1). This works with duplicates too, because we simply keep moving one of the pointers. Albeit, it's rather in-efficient with duplicates. One optimization could be we skip all duplicates once we detect a duplicate. Why? We know that if we cannot form the target with one duplicate, we cannot form the target with any duplicate, because they are literally the same number.

2Sum Variant: Find how many pairs in the array such that their sum is less than or equal to a specific target number.

Implementation: TwoSumPairs

Taking our old example:

nums = [2, 7, 11, 15], target = 13

So here, the pairs {2,11}, {2,7} or 2 pairs would be the solution. If we use the two pointer approach from above, we hit the first pair at 2,11. Anything between that range will either make the target or be less than the target if the array is sorted.

Now the movement would be: 1. If sum <= target, we move right (low++) till we can. At the same, we keep a count: count = count + (high-low). 2. Else we move left (high--);

The time complexity if O(n) and the space complexity O(1).

2Sum Variant: Find the sum of the two integers such that the sum is closest to target.

Implementation: ClosestSumToTarget

Pretty much the same movement as before but we keep track of the min diff sum seen so far and keep updating it.

Time Complexity

O(nlogn) because of the sort.

Space Complexity

O(1) because we are not using any extra space. Assuming we use some kind of in-place sort.

2Sum Variant: Find how many unique pairs in the array such that their sum is equal to a specific target number.

Implementation: UniquePairs

When they say unique pairs, that must mean the array contains duplicates. Not just that, the pairs making the target must be unique. Lets define that first.

Input:
nums = [1, 1, 2, 45, 46, 46], target = 47

Output:
2

Explanation:
1 + 46 = 47 (only 1 selected althogh there could be 2 pairs)
2 + 45 = 47
Hence, return 2 sets.

So, to keep the "pair uniqueness", we are going to consider only one element from a repeating set. The rest is the same as finding the target, except we dont stop when we find a target and we need to keep the count of the number of targets found.

3Sum: Given an array nums of n integers, find all unique triplets in the array which gives the sum of zero.

Implementation: UniqueTriplets

We can re-use the 2Sum approach with a sorted array. But, because we need a triplet, we are going to have a loop to fix the first number and find the other two numbers using the 2Sum approach.

  1. So first we sort the numbers.
  2. Then we start and outer loop and, fix the first number and look for a pair with target=0-nums[i].
  3. If we find one we capture it in a result array and move to the next non-duplicate number.
  4. At the end, we return all pairs, that can form triplets = 0 with that fixed number.
  5. We repeat this for all numbers.

Time complexity

O(n^2)

Space complexity

O(1)

4Sum: Given an array nums of n integers and an integer target, find all unique quadruplets in the array which gives the sum of target.

Implementation: UniqueQuadruplets

Pretty much the same concept as 3SUM, we need an additional loop because we need to find quadruplets now.

Time complexity

O(n^3)

Space complexity

O(1)

4Sum Variant: Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

Implementation: PairTuples

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

The naive way to do it is four nested loops resulting in a O(n^4) time complexity. Another option is to take a couple of pairs, find the sum between them and store them in a map alongwith the frequency of the sum occuring.

Then take the next two lists and find the sum. Now if there's a compliment sum in the map, then that would make the quadruplet.

Count the number of quadruplets.

Time complexity

O(n^2)

Space complexity

O(1)

Given a list of file paths, print the file hierarchy.

file_paths: [
"/users/home/html/a.html",
"/users/home/html/b.html",
"/users/home/index.html",
"/users/home/js/a.js"
],

print -->>

users
  home
    html
    index.html
      a.html
      b.html
   js
     a.js

Implementation: FileHierarchy

First, we need to think of a datastructure that can capture this hierarchy. Trie is the best option here since it naturally captures the hierarchial nature of common paths between elements.

            users
                home
index.html(end)       html                       js
                  a.html(end)   b.html(end)           a.js(end)

A file marks the "end" in trie concept.

But we dont need to search for anything here. We just need to print all paths with proper indentations. So our logic could be: 1. Print the current node with x number of tabs for indentation. 2. Recursively call all children nodes with x+1 number of tabs for indentation. 3. Rinse and repeat.

Time complexity

For creating the trie, we go through every file/folder and then insert. Going through every file/folder takes O(n) time, where n=number of files/folders. Insertion takes O(logn) time. So total time complexity is O(nlogn).

For printing, we recursively traverse through every node. The total number of nodes is the total number of files/folders, which is O(n).

Space complexity

We store all files/folders, which is O(n).

Given two rectangles, find their union and subtract.

Given two rectangles, find the regions covered by the subtraction of the two rectangles. The output should be a list of rectangles.

For example:

Given two rectangles (1 and 2):

-------------------------
|      rectangle 1      |
|                       |
|     -------------     |
|     |rectangle 2|     |
|     -------------     |
|                       |
|                       |
-------------------------

If we subtract rectangle 2 from rectangle 1, we will get an area with a hole:

-------------------------
|                       |
|                       |
|     -------------     |
|     |    hole   |     |
|     -------------     |
|                       |
|                       |
-------------------------

This area can be decomposed into 4 rectangles:

-------------------------
|          A            |
|                       |
|-----------------------|
|  B  |   hole    |  C  |
|-----------------------|
|                       |
|          D            |
-------------------------

OR

---------------------------
|     |     A     |       |
|     |-----------|       |
|     |           |       |
|  B  |   hole    |  C    |
|     |           |       |
|     |-----------|       |
|     |     D     |       |
---------------------------


Assume the following exists: 

class Rectangle {
  int top;
  int bottom;
  int left;
  int right;
}

Implement:

List<Rectangle> subtract(Rectangle other) {....}


Source: https://stackoverflow.com/questions/3765283/how-to-subtract-a-rectangle-from-another

Implementation: Rectangle

Logic in implementation class.

Return to Index