LEETCODE

Question 1

What algorithm should be utilized for :
maximum or minimum subarray?

What are the steps?

Whats the sexy way to implement the updates?

Answer 1

KADENES!

Create two variables, initialized to the first value of the array [CurrentSubArray] && [maxSubArray]

Iterate through the array, starting at the second element because we already assigned the first..

add each number to currentSubArray, throwing it away if negative.

update max SubArray each time we find max.

Sexy –

currentSubarray = Math.max(nums[i], currentSubarray + nums[i]);

————implementation———-
Kaden’s Algo

function maxSubArray(a){
 if (a.length === 0){
  return []
 }
 currentSum = a[0]
 maxSum = a[0]
 for (let i =1;i

Question 2

Find the Max Absolute sum of any SubArray

How do you solve this?

Answer 2

Kadenes Algorithm, with a twist because we are testing for absolute value.

Run algo twice, keeping track of max_Sum, and min_Sum , then get the absolute maximum from those results

for (var n : nums) {
max_sum = Math.max(0, n + max_sum);
min_sum = Math.min(0, n + min_sum);
res = Math.max(res, Math.max(max_sum, -min_sum));

Question 3

DFS - When do you pick pre-order traversal?

How do you implement it?

Answer 3

CURRENT, LEFT, RIGHT
First, check for base case node value, then visit current node. Visit left tree, and right tree.

public void traversePreOrder(Node node) {
    if (node != null) {
        visit(node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}
Pre-order: Used to create a copy of a tree. For example, if you want to create a replica of a tree, put the nodes in an array with a pre-order traversal. Then perform an Insert operation on a new tree for each value in the array. You will end up with a copy of your original tree.

Question 4

DFS- When do you pick in order traversal?

How do you implement it?

Answer 4

In order = LEFT, CURRENT, RIGHT

98. Validate Binary Search Tree can be done with in order traversal.

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        visit(node.value);
        traverseInOrder(node.right);
    }
}

In-order: : Used to get the values of the nodes in non-decreasing order in a BST.

Question 5

743 Network Delay Time optimizations

Answer 5

You can probably use N and times.length to calculate how dense the graph is, which will determine which implementation you use (a sparse optimal or dense-optimal implementation)