CareerCup

swap constraint: exchange only adjacent element.

Can you explain your comment as to why the above are not O(n) and why the optimal runtime is O(n log n)?

Here was my solution from the interview:

// Day runs from minute 0 to minute 1440 (exclusive)
// Input: example 9:30 => 570
// arr [570, 675, 990]
// dept [705, 690, 1005]
// Assume data is valid - i.e. length, no neg, etc.

int[] arr = { 570, 675, 990 };
int[] dept = { 705, 690, 1005 };

// Create a frequency map for the day
Map<Integer, Integer> freqMap = new HashMap<>();
for (int n = 0; n < arr.length; n++) {
    int a = arr[n];
    int d = dept[n];
    for (int i = a; i < d; i++) {
        int count = freqMap.containsKey(i) ? freqMap.get(i) : 0;
        freqMap.put(i, count + 1);
    }
}

// Calculate the max value
int maxVal = 0;
for (Integer n : freqMap.values()) {
    if (n > maxVal) {
        maxVal = n;
    }
}

System.out.println("Gates needed: " +maxVal);

Time complexity O(n) since the map is bounded by constant 1440 min per day
assuming HashMap has time O(1) with a decent hash algorithm.

The problem sounds like a variation of the subset sum problem. (See Wikipedia.) If you sum the entire list, then the sum is equivalent to the sum of the subset that remains after you remove all of the subsets that sum up to zero.

I did a breadth first search variation, because we want the shortest subset that sums to our target, so it doesn't contain additional subsets that sum to zero. I was a little lazy and just printed out the subset, but code could easily be modified to return the list.

class Solution {
  
  public static class Potential {
    int sum;
    List<Integer> partial;
    List<Integer> remaining;

    public Potential(int s, List<Integer> p, List<Integer> r) {
      sum = s;
      partial = p;
      remaining = r;
    }

    public String toString()
    {
      return "(" + sum + ", " + Arrays.toString(partial.toArray()) 
        + ", " + Arrays.toString(remaining.toArray()) + ")"; 
    }
  }
  
  static void subsetSum_BFS(List<Integer> numbers, int target) {
    Queue<Potential> queue = new LinkedList<>();

    Potential start = new Potential(0, new ArrayList<Integer>(), numbers);
    queue.add(start);

    while (!queue.isEmpty()) {
      Potential current = queue.remove();
      int sum = current.sum;
      
      for (int i = 0; i < current.remaining.size(); i++) {
        List<Integer> remaining = new ArrayList<Integer>();
        int n = current.remaining.get(i);
        sum += n;
        List<Integer> partial = new ArrayList<>(current.partial);
        partial.add(n);

        if (sum == target) {
          System.out.println("sum="+target);
          System.out.println(Arrays.toString(partial.toArray()));
          return;
        }

        for (int j= i + 1; j < current.remaining.size(); j++) {
          remaining.add(current.remaining.get(j));
        }
        Potential next = new Potential(sum, partial, remaining);
        queue.add(next);
                
        sum -= n;
      }
    }
    System.out.println("Matching subset not found.");
  }

  static void removeZeroSum(List<Integer> numbers) {
    int sum = 0;
    for (Integer n : numbers) {
      sum += n;
    }
    System.out.println("target="+sum);
    if (sum == 0) {
      System.out.println("[]");
      System.out.println("Subset empty, bypassing search.");
      return;
    }
    subsetSum_BFS(numbers, sum);
  }
  
  public static void main(String[] args) {
    
    // case 1: 6 -6 8 4 -12 9 -8 8
    // O/P : 9
    Integer[] case1 = {6, -6, 8, 4, -12, 9, -8, 8};
    List<Integer> case1List = new LinkedList<>(Arrays.asList(case1));
    removeZeroSum(case1List);
    
    // case 2: 20, 5, 6, 10, -11, 10, 2, 2
    // O/P : 20 2 2
    Integer[] case2 = {20, 5, 6, 10, -11, -10, 2, 2};
    List<Integer> case2List = new LinkedList<>(Arrays.asList(case2));
    removeZeroSum(case2List);
    
    // case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25 
    // O/P : 20 25
    Integer[] case3 = {4, 6, -10, 8, 9, 10, -19, 10, -18, 20, 25};
    List<Integer> case3List = new LinkedList<>(Arrays.asList(case3));
    removeZeroSum(case3List);
  }
}

Much like the subset sum problem, the worst case time complexity is exponential because we can't assume the values are non-negative and hence can't eliminate combinations. So worst case O(2^N*N) when there are no subsets that sum to zero, since there are 2N subsets and, to check each subset, we need to sum at most N elements. Best case would be O(N), when the list sums to zero, because we don't have to check any and the result is just an empty list.

There is a problem with your code and test case #3 above.
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25

HashMap<Integer,Node> mp=new HashMap<Integer,Node>();

HashMap can't handle multiple values of 10 in the same list, so it overwrites the node value.

If I read the problem correctly, if you can shuffle and/or remove characters, then the longest palindrome is the sum of all of the even count chars and the longest odd count char (if there is one).

public static int maxLengthPalindrome(String s) {
    String[] sArr = s.split("");
    Map<String, Integer> charFreq = new HashMap<String, Integer>(); 

    for (int i = 0; i < s.length(); i++) {
      String c = sArr[i];
      if (charFreq.containsKey(c)) {
        int count = charFreq.get(c);
        charFreq.put(c, count + 1);
      } else {
        charFreq.put(c, 1);
      }
    }
    
    int maxPal = 0;
    int maxOdd = 0;
    for (String c : charFreq.keySet()) {
      int count = charFreq.get(c);
      if (count % 2 == 0) {
        maxPal += count;
      } else if (count > maxOdd) {
        maxOdd = count;
      }
    }
    return maxPal + maxOdd;
  }

First pass creates the frequency map and is O(n) where n is length of string. Second pass adds up the frequency map and is O(k) where k is the number of keys. Generally k will be bounded by both n and max of the character set, so in practice O(kn) should reduce to O(n).

Modified binary search is definitely the way to go. If numbers are in sequence, then the difference between two array values should equal the difference of their indices. If not, then the missing number is somewhere in that range.

public static int findMissingNumber(int[] a) {
    // Validate... Assume -1 is fine to return for not found.
    if (a == null || a.length == 0) {
      System.out.println("Invalid sequence: length.");
      return -1;
    }
    int low = 0;
    int mid;
    int high = a.length-1;
    while (low < high) {  
      mid = low + (high - low) / 2;
      if (a[mid] - a[low] == mid - low) {
        // Missing number is in upper half
        if (mid + 1 < a.length && a[mid + 1] != a[mid] + 1)  {
          return a[mid] + 1;
        } else {
          low = mid + 1;
        }
      } else {
        // Missing number is in lower half
        if (mid - 1 >= 0 && a[mid] - 1 != a[mid - 1]) {
          return a[mid] - 1;
        } else {
          high = mid -1;
        }
      }
    }
    System.out.println("Invalid sequence: not found.");
    return -1;
  }

Best case: O(1) Average case: O(log n) Worst case: O(log n)

Close but I believe your while loop needs to be:

while(head != NULL)
	{
	    ...

Nice use of the Java LinkedList data type, with convenient access to list size. However you need to be careful how you define your index parameter. The problem definition says Kth position from the start and end of a linked list. Since Java uses a zero-based index, if you passed K=2 into your method, you’d actually be swapping 4 & 5, instead of 2 & 7.