CareerCup

This is how to answer the second question in old and boring SQL, join a table with itself by user id (so that each product is mapped with each product). Then remove rows with the same product and deduplicate them by filtering higher product id:

SELECT 
    FP.product AS product1, 
    T.product AS product2, 
    COUNT(1) AS bought_count
  FROM Purchases AS FP
  -- the < sign in the join so that we keep only 1 pair of (p1,p2) and (p2,p1)
  INNER JOIN Purchases AS T 
    ON FP.user = T.user AND FP.product < T.product
  GROUP BY FP.product, T.product
  ORDER BY bought_count DESC
  LIMIT 100

Though I have no idea how to do this in Spark. The bottleneck is obviously inner join, but what can we do to optimize it? Maybe the question means distributing the load proportionally among workers, I don't know.

Good luck coding this optimal solution with Fast Fourier transform within 30 minutes of phone interview:

"
The basic FFT algorithm itself runs in O(n log n) time; using FFTs for integer
multiplication incurs some small additional overhead.
The fastest integer multiplication algorithm currently known, published by David Harvey
and Joris van der Hoeven in 2018, runs in O(n * (log n) * (4^log$n))) time.
Here, log$n denotes the slowly growing iterated logarithm of n, which is the number of times
one must take the logarithm of n before the value is less than 1.
"

If you want to do this without libraries, it isn't easy for float numbers because even something like 20.04 will turn into 20.03999999999
If someone can find a way to fix the lines with my 'problems with rounding here' comments, this algorithm will work:

function toStr(num) {
  var n = Math.abs(num);
  var intPart = Math.floor(n);
  var floatPart = n - intPart; // problems with rounding here

  var intResult = [];
  while (intPart > 0) {
    intResult.unshift(String(intPart % 10));
    intPart = Math.floor(intPart / 10);
  }

  var floatResult = [];
  while (floatPart > 0) {
    floatPart *= 10;
    var floatDigit = Math.floor(floatPart);
    if (floatDigit >= 1) {
      floatResult.push(String(floatDigit));
      floatPart -= floatDigit;  // problems with rounding here
    } else {
      floatResult.push('0');
    }
  }
  var result = intResult.slice();
  if (floatResult.length > 0) {
    result.push('.');
    Array.prototype.push.apply(result, floatResult);
  }
  if (num < 0) {
    result.unshift('-');
  }
  return result;
}

Similar to leetcode 45 Jump Game II.

Generally it would be a dynamic programming solution. We either include the station or exclude it. 1) if we include the station, we add 1 stop to the result and add all gas; 2) if we exclude it, we add 0 stops and 0 gas. Something like this:

var incl = 1 + minStops(startIndex + 1, remainingGas + stations[startIndex].gas);
var excl = minStops(startIndex + 1, remainingGas);
return Math.min(incl, excl);

This would be O(N^2) with memoization because each function has 2 parameters.

But for some reason a greedy algorithm works here. Greedy algorithms almost never work, in 99% of cases dynamic programming is better, but this question for some reason is different. There should be a formal proof why a greedy algorithm works here, but I can't find it and can't prove it myself. But in the result it will be O(n):

var stations = [
  {pos: 16, gas: 3},
  {pos: 10, gas: 7},
  {pos: 14, gas: 11},
  {pos: 11, gas: 5},
  {pos: 7, gas: 6}
];
stations.push({pos: 20, gas: 10}); // add initial stop
stations.push({pos: 0, gas: 0}); // add final stop
console.log('min stops to take: ' + minStopsGreedy(stations));

function minStopsGreedy(stations) { 
  // Sort by position descending
  stations.sort((a, b) => b.pos - a.pos);

  var lastStepReach = 0;
  var currentStepReach = 0;
  var step = 0;

  for (var i = 0; i < stations.length; i++) {
    var distFromStart = stations[0].pos - stations[i].pos;
    if (distFromStart > lastStepReach) {
      step++;
      lastStepReach = currentStepReach;
    }

    currentStepReach =
        Math.max(currentStepReach, lastStepReach + stations[i].gas);
  }

  if (currentStepReach < stations[0].pos) {
    return Infinity;
  }

  return step;
}

Copy pasting a comment of fun4LeetCode from leetcode.
General structure

public int calculate(String s) {
    int l1 = 0, o1 = 1; // Initialization of level one
    int l2 = 1, o2 = 1; // Initialization of level two
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (c is a digit) {

           --> we have an operand of type number, so find its value "num"
           --> then evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);
       
        } else if (c is a lowercase letter) {

           --> we have an operand of type variable, so find its name "var"
           --> then look up the variable mapping table to find its value "num";
           --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

        } else if (c is an opening parenthesis) {

           --> we have an operand of type subexpression, so find its string representation
           --> then recursively call the "calculate" function to find its value "num";
           --> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);
       
        } else if (c is a level two operator) {

            --> o2 needs to be updated: o2 = (c == '*' ? 1 : -1);

        } else if (c is a level one operator) {

            --> demotion happens here: l1 = l1 + o1 * l2;
            --> o1 needs to be updated: o1 = (c == '+' ? 1 : -1);
            --> l2, o2 need to be reset: l2 = 1, o2 = 1;

       }

       return (l1 + o1 * l2); // end of expression reached, so demotion happens again
}

Recursive solution: O(n^2) time, O(n) space

public int basicCalculatorIII(String s) {
    int l1 = 0, o1 = 1;
    int l2 = 1, o2 = 1;
        
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
            
        if (Character.isDigit(c)) {
            int num = c - '0';
                
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                num = num * 10 + (s.charAt(++i) - '0');
            }
            
            l2 = (o2 == 1 ? l2 * num : l2 / num);
                
        } else if (c == '(') {
            int j = i;
                
            for (int cnt = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') cnt++;
                if (s.charAt(i) == ')') cnt--;
                if (cnt == 0) break;
            }
            
            int num = basicCalculatorIII(s.substring(j + 1, i));
            
            l2 = (o2 == 1 ? l2 * num : l2 / num);
                
        } else if (c == '*' || c == '/') {
            o2 = (c == '*' ? 1 : -1);
                
        } else if (c == '+' || c == '-') {
            l1 = l1 + o1 * l2;
            o1 = (c == '+' ? 1 : -1);

            l2 = 1; o2 = 1;
        }
    }
        
    return (l1 + o1 * l2);
}

If we have only 2 arrays, this is another example of KMP pattern searching. The answer can be found in O(n):

function findLongestSuffixPrefix(nums1, nums2) {
  return Math.max(
      findLongestSuffix(nums1, nums2),
      findLongestSuffix(nums2, nums1));
}

function findLongestSuffix(nums1, nums2) {
  var tf = buildTf(nums2);
  var state = 0;
  for (var i = 0; i < nums1.length; i++) {
    state = tf[state].get(nums1[i]) || 0;
  }
  return state;
}

function buildTf(nums) {
  var result = [];
  var lps = -1;
  for (var i = 0; i <= nums.length; i++) {
    result[i] = lps >= 0 ? new Map(result[lps]) : new Map();
    if (i < nums.length) {
      result[i].set(nums[i], i + 1);
      lps = lps >= 0 && result[lps].get(nums[i]) || 0;
    }
  }
  return result;
}

2d matrix is harder as you will need to split the second matrix into multiple rows, finding 1 row in the first matrix is O(n^2), finding k rows in the first matrix is O(kn^2), or max O(n^3).

Here is O(n * m * k) or slightly faster than O(n^3) implementation using Finite Automata based on kmp, it is actually not very hard and described in the article "Pattern Searching | Set 6 (Efficient Construction of Finite Automata)".
O (n * m * k) space. It requires some space, but O(n^3) is faster than O(n^4) from the comments above.

But I expect that even O(n^3) isn't the ideal answer, I think the proper answer requires using Rabin-Karp algorithm, it is much harder to implement though.

var matrix = [
  [1,1,1,1,2],
  [1,1,1,1,2],
  [1,1,1,1,2],
  [1,1,1,2,2],
];
var smallMatrix = [
  [1,1],
  [1,2],
];
findMatrix(matrix, smallMatrix); // i: 2, j: 2

function findMatrix(matrix, smallMatrix) {
  var calculatedStates = [];
  
  for (var k = 0; k < smallMatrix.length; k++) {
    calculatedStates[k] = [];
    // build state machine for each row of small matrix
    var tf = buildTf(smallMatrix[k]);
    
    for (var i = 0; i < matrix.length; i++) {
      calculatedStates[k][i] = [];
      var state = 0;
      for (var j = 0; j < matrix[i].length; j++) {
        // state is how many numbers of smallMatrix[k]
        // are matched at (i,j)
        state = tf[state].get(matrix[i][j]) || 0;
        calculatedStates[k][i][j] = state;
      }
    }
  }
  
  for (var i = 0; i < matrix.length; i++) {
    for (var j = 0; j < matrix[i].length; j++) {
      var matchingRows =
          getMatchingRows(i, j, calculatedStates, smallMatrix);
      if (matchingRows == smallMatrix.length) {
        return {i: i, j: (j - smallMatrix[0].length + 1)};
      }
    }
  }
  
  return {i: -1, j: -1};
}

function getMatchingRows(i, j, calculatedStates, smallMatrix) {
  for (var k = 0; k < smallMatrix.length &&
       i + k < calculatedStates[k].length; k++) {
    if (calculatedStates[k][i + k][j] != smallMatrix[k].length) {
      return k;
    }
  }
  return smallMatrix.length;
}

function buildTf(nums) {
  var result = [];
  var lps = -1;
  for (var i = 0; i <= nums.length; i++) {
    result[i] = lps >= 0 ? new Map(result[lps]) : new Map();
    if (i < nums.length) {
      result[i].set(nums[i], i + 1);
      lps = lps >= 0 && result[lps].get(nums[i]) || 0;
    }
  }
  return result;
}

If surrounded means "surrounded from 4 sides" and excludes white chess pieces on the boundary, you can find the answer in the article "Count all 0s which are blocked by 1s in binary matrix" on geekforgeeks:

- Idea is based on the DFS. First we remove all the zero value cells in the matrix which are reachable from boundary of Matrix using DFS. After that we count all zeros which are left in binary matrix.