CareerCup

Here is a solution with O(N*log(N)) time and O(N) space. I think the trick to this question is to make an appropriate data structure to represent the medal distribution. I used a hashmap to remember where and by how much the medal count per officer varies.
Ex:
If the medal count is:

20 20 20 25 25 10 10 10 10 10

My data structure remembers:

0 -> 20 (starting at index 0, officers have 20 more medals than previously)
3 -> 5 (starting at index 3, officers have 5 more medals than previously)
5 -> -15 (starting at index 5, officers have 15 less medals than previously)

Here is my solution in Java:

int firstOfficerToExceedCumulativeThreshold(
    int N, int[] count, int[] from, int[] to, int THRESHOLD) {
  MedalDestribution MD = new MedalDestribution();
  for (int i = 0; i < N; ++i) {
    MD.awardMedals(count[i], from[i], to[i] + 1);
  }
  return MD.getOfficerWithNthMedal(THRESHOLD + 1);
}

class MedalDestribution {

  private static int NUMBER_OF_OFFICERS = 1000000;

  private Map<Integer, Integer> valueChange;

  public medalDestribution() {
    valueChange = new HashMap<Integer, Integer>();
    valueChange.put(NUMBER_OF_OFFICERS + 1, 0);
  }

  // 'from' is inclusive while 'to' is exclusive.
  public int awardMedals(int count, int from, int to) {
    valueChange.put(from, valueChange.getOrDefault(from, 0) + count);
    valueChange.put(to, valueChange.getOrDefault(to, 0) - count);
  }

  public int getOfficerWithNthMedal(int N) {
    int[] changeIndices = valueChange.keySet().toArray();
    Arrays.sort(changeIndices);
    int sum = 0;
    int rangeValue = 0;
    int lastOfficer = 0;
    for (int currentOfficer : changeIndices) {
      sum += rangeValue * (currentOfficer - lastOfficer);
      if (sum >= N) {
        return currentOfficer - 1 - (sum - N) / rangeValue;
      }
      rangeValue += valueChange.get(currentOfficer);
      lastOfficer = currentOfficer;
    }
    return -1;
  }
}

Note that a * b = (2 * a) * (b / 2).
So we'll use the recursive formula multiply(a, b) = multiply(2 * a, b / 2) with base case b equal to 0. (We also have to be a bit careful when b is not a multiple of two, in that case we use a * b = a + (2 * a) * ((b - 1) / 2)).
This will use O(log(b)) operations. We can optimize a bit and make sure b is the smallest of the two numbers and then we get O(log(min(a, b))).
Here is the code in Java:

int multiply(int a, int b) {
  if (Math.abs(a) >= Math.abs(b)) {
    return multiplyHelper(a, b);
  }
  return multiplyHelper(b, a);
}

int multiplyHelper(int largerNumber, smallerNumber) {
  if (smallerNumber == 0) {
    return 0;
  }
  if (smallerNumber % 2 == 0) {
    return multiplyHelper(largerNumber * 2, smallerNumber / 2);
  }
  if (smallerNumber > 0) {
    retrurn largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
  }
  retrurn -largerNumber + multiplyHelper(largerNumber * 2, smallerNumber / 2);
}

I'm assuming that there is a Booking class with an interface like

public class Booking {
  //Returns how many days in the season the guest arrives.
  public int getArrivalDate();
  //Returns how many days in the season the guest leaves.
  public int getDepartureDate();
}

I'm also assuming that the departure date must be later than the arrival date.

Here is an O(nlog(n)) solution:

boolean doIHaveEnoughRooms(int numberOfRooms, Collection<Booking> bookings) {
  return numberOfRooms >= numberOfRoomsNeeded(bookings);
}

int numberOfRoomsNeeded(Collection<Booking> bookings) {
  int n = bookings.size();
  int[] arrivals = new int[n];
  int[] departures = new int[n];
  int i = 0;
  for (int d : bookings) {
    arrivals[i] = d.getArrivalDate();
    departures[i] = d.getDepartureDate();
    ++i;
  }
  Arrays.sort(arrivals);  // Built in O(nlog(n)) sorting.
  Arrays.sort(departures); // Built in O(nlog(n)) sorting.
  int aIndex = 0;
  int dIndex = 0;
  int current = 0;  // Current number of guests.
  int max = 0;  // Max number of guests
  while (aIndex < n) {
    // You need <= instead of < if you can't use a room the same day the guest leaves.
    if (arrivals[aIndex] < departures[dIndex]) {  
      ++aIndex;
      ++current;  // Someone needs a room.
      max = Math.max(max, current);
    } else {
      ++dIndex;
      --current;  // Someone vacates a room.
    }
  }
  return max;
}

Note that the bottleneck is the sorting, everything else is simply O(n). So if you use a linear sorting algorithm instead (counting sort seems like a reasonable choice, especially if the season doesn't have too many days and you expect many people to arrive/leave on the same day), you get an O(n) algorithm.

Here is a linear solution.
1. Have three variables. "start", "mid", and "end".
2. initialize "start" at 0. initialize "mid" at the index of the first "0" in the string (if the string has no '0's just return the size of the string), and initialize 'end' at the index of second '0' (or the size of the string if there is no second '0').
3. If you flip the '0' at "mid", you get a block of (end - start) '1's.
4. Now start becomes mid + 1, mid becomes end, and end becomes the index of the next '0'.
5. Keep doing thing while keeping track of the max block size until you run out of '0's.

Here is the algorithm in Java:

// I'm assuming that the input string only contains '0's and '1's.
int maxConsecutiveOnesAfterAtMostOneFlip(String s) {
  int maxBlockSize = 0;
  int start = 0;  // The first character of the block.
  int mid = s.indexOf('0');  // The first '0' of the block.
  if (mid == -1) {  // if the string is all '1's.
    return s.length();
  }
  int end = s.indexOf('0', mid + 1);  // The first '0' after the block.
  while (end != -1) {
    maxBlockSize = Math.max(maxBlockSize, end - start);
    start = mid + 1;
    mid = end;
    end = s.indexOf('0', mid + 1);
  }
  maxBlockSize = Math.max(maxBlockSize, s.length() - start);
  return maxBlockSize;
}

You could push the values in a stack while going through the list in order and then print the values as you remove them from the stack: O(n) time and O(n) memory.

You could also keep track of the index of the last printed element and start from the beginning and traverse the list one less than that index until you print the first element: O(n^2) time and O(1) memory. I feel this is not a good solution though.

If you are allowed to alter the linked list as long as you restore it by the end of the algorithm, you can reverse the list (O(n) time O(1) memory), print it in order (O(n) time O(1) memory), and reverse it again (O(n) time O(1) memory) for a total of O(n) time and O(1) memory.

If you must use recursion, then you want something like this:

void printListInReverse(Node* head) {
  if (head != NULL) {
    printListInReverse(head->next);
    cout << head->data;
  }
}

Which is basically the first solution but using the stack frame for the function calls instead of a stack for the node values.

Nope that's it.

You can't have better than linear because you have to at least look at each of the values in the sequence (it only takes one value to break the progression).

Brute force BFS solution in Java:

int minNumberOfMoves(String initialPosition) {
  if (isSolved(initialPosition)) {
    return 0;
  }

  List<boolean[]> actions = new LinkedList<boolean[]>();
  actions.add(new boolean[] { true,  true, false, false, false, false, false, false});
  actions.add(new boolean[] { true,  true,  true, false, false, false, false, false});
  actions.add(new boolean[] {false,  true, false, false,  true,  true,  true, false});
  actions.add(new boolean[] {false, false,  true, false, false,  true, false, false});
  actions.add(new boolean[] {false, false, false,  true, false,  true, false, false});
  actions.add(new boolean[] {false, false, false,  true, false, false, false,  true});
  actions.add(new boolean[] {false, false, false, false, false,  true, false,  true});
  actions.add(new boolean[] {false, false, false, false, false, false,  true,  true});
  
  Set<String> seenPositions = new HashSet<String>();
  Set<String> currentPositions = new HashSet<String>();
  Set<String> nextPositions = new HashSet<String>();
  seenPositions.add(initialPosition);
  currentPositions.add(initialPosition);
  
  for (int moveCounter = 1; currentPositions.size() > 0; ++moveCounter) {
    for (String current : currentPositions) {
      for (boolean[] action : actions) {
        String next = performAction(current, action);
        if (!seenPositions.contains(next)) {
          if (isSolved(next)) {
            return counter;
          }
          seenPositions.add(next);
          nextPositions.add(next);
        }
      }
    }
    currentPositions = nextPositions;
    nextPositions = new HashSet<String>();
  }
  
  return -1;
}

String performAction(String position, boolean[] action) {
  StringBuilder result = new StringBuilder();
  for (int i = 0; i < position.length(); ++i) {
    if (action[i]) {
      switch (position.charAt(i)) {
        case 'N':
          result.append('E');
          break;
        case 'E':
          result.append('S');
          break;
        case 'S':
          result.append('W');
          break;
        case 'W':
          result.append('N');
          break;
      }
    } else {
      result.append(position.charAt(i));
    }
  }
  return result.toString();
}

boolean isSolved(String s) {
  for (int i = 1; i < s.length(); ++i) {
    if (s.charAt(0) != s.charAt(i)) {
      return false;
    }
  }
  return true;
}

What about "19191919"? Clearly, every 1 can be seen alone or as part of 19, so there is 2^4 = 16 ways to decode the string which is more than 8, the fibonacci number you would get using your algorithm.

What you have to do is find the correct fibonnaci number for consecutive blocks of 1s and 2s and then multiply those numbers. Also, when you encounter a 2, make sure the digit after is 6 or less ("27" can only be decoded one way).

This idea in Java:

public void printDifference(String[] a, String[] b) {
  TrieSet setA = new TrieSet(a);
  TrieSet setB = new TrieSet(b);
 
  for (String s : a) {
    if (!setB.contains(s)) {
      System.out.println(s);
      setB.add(s);  // To avoid printing the same word twice if "a" contains duplicates.
    }
  }
  for (String s : b) {
    if (!setA.contains(s)) {
      System.out.println(s);
      setA.add(s);  // To avoid printing the same word twice if "b" contains duplicates.
    }
  }
}

Here is one possible implementation of the TrieSet class (a "real" implementation would also have methods to remove words from the set and to iterate through the elements, but adding and checking is sufficient for this question):

public class TrieNode {
  private Map<Character, TrieNode> children;
  private boolean isTerminal;

  public TrieNode() {
    children = new TreeMap<Character, TrieNode>();
    isTerminal = false;
  }

  public TrieNode getChild(char c) {
    return children.getOrDefault(c, null);
  }

  public TrieNode getOrCreateChild(char c) {
    TrieNode child = getChild(c);
    if (child != null) {
      return child;
    }
    return addChild(c);
  }

  private TrieNode addChild(char c) {
    TrieNode child = new TrieNode();
    children.put(c, child);
    return child;
  }

  public boolean isTerminalNode() {
    return isTerminal;
  }

  public void markAsTerminalNode() {
    isTerminal = true;
  }
}

public class TrieSet {
  TrieNode root = new TrieNode();

  public TrieSet() {} 

  public TrieSet(String[] words) {
    for (String s in words) {
      add(s);
    }
  }

  public void add(String s) {
    TrieNode current = root;
    for (int i = 0; i < s.length(); ++i) {
      current = current.getOrCreateChild(s.charAt(i));
    }
    current.markAsTerminalNode();
  }

  public boolean contains(String s) {
    TrieNode current = root;
    for (int i = 0; i < s.length(); ++i) {
      current = current.getChild(s.charAt(i));
      if (current == null) {
        return false;
      }
    }
    return current.isTerminalNode();
  }
}

The above algorithm with the above data structure has average and worst-case time complexity of "total number of characters" * log("size of the alphabet") (which is simply O(n) if the alphabet is fixed and you are guaranteed that all words are under a certain length). Using a HashSet instead of a TrieSet is also possible and reduces the expected runtime to O(n) no matter what, but increases the worst case to O(n^2).

How do you make O(n^2) swaps in O(n) time?
This algorithm is correct, but it is an O(n^2) algorithm.

Use the fact that if n is not prime, then n has at least one factor less or equal to the square root of n.

Keep a list of primes so you don't have to check if composite numbers factor n. Expand it as needed.

An implementation in Java:

List<Integer> firstFivePrimesWithTenDigits() {
  List<Integer> knownPrimes = new ArrayList<Integer>();
  knownPrimes.add(2);
  knownPrimes.add(3);
  List<Integer> bigPrimes = new ArrayList<Integer>();
  for (int i = 1000000001; bigPrimes.size() < 5; i += 2) {
    if (isPrime(i, knownPrimes)) {
      bigPrimes.add(i);
    }
  }
  return bigPrimes;
}

// Assumes "knownPrimes" is a list of the first k primes from some k >= 2
boolean isPrime(int n, List<Integer> knownPrimes) {
  int squareRoot = (int) Math.sqrt(n);
  while (knownPrimes.get(knownPrimes.size() - 1) < squareRoot) {
    addNextPrime(knownPrimes);
  }
  for (int i = 0; i < knownPrimes.size(); ++i) {
    int prime = knownPrimes.get(i);
    if (prime >= squareRoot) {
      break;
    }    
    if (n % prime == 0) {
      return false;
    }
  }
  return true;
}

// Takes in a list of the first k primes for some k >= 2 and makes it a list of the first k+1 primes.
void addNextPrime(List<Integer> knownPrimes) {
  for (int i = knownPrimes.get(knownPrimes.size() -1) + 2; true; i += 2) {
    if (isPrime(i, knownPrimes)) {
      knownPrimes.add(i);
      return;
    }
  }  
}

This is a simple approach. More sophisticated solutions can be found by looking up "primality test" online.

Nice idea, but in the the case of "helloworld", what if you get "low" and "wol"?
How do you deal with duplicate characters?

First, the question tells us to assume that we have all numbers from 1 to n*n EXACTLY once, so your situation cannot happen.

Also, if you're not guaranteed distinct integers, the algorithm does not make any sense. What do you store in arr[5] if one of the 6s is adjacent to 7 but the other one isn't?

I hope that clears up some confusion.

1. In an array, store the position of every integer from 1 to n^2 by simply reading every entry of the matrix.

2. Iterate through the array. At every step, check if the next position is adjacent to the current position. If so, your current sequence's size increases by 1. If not, your current sequence is over. Every time a sequence terminates, if its length is greater than the longest sequence seen so far, remember its length and where it ends.

3. Knowing the size of the longest sequence and on which number it ends, you can easily print the sequence by printing the numbers from "end - length + 1" to "end".

Running the algorithm on the given example looks like this:

input
1 5 9 
2 3 8 
4 6 7

1. Produce the following array:
[(0,0), (0,1), (1,1), (0,2), (1,0), (1,2), (2,2), (2,1), (2,0)]

2.
Set length counter to 1.
(0,0) is adjacent to (0,1): +1;
(0,1) is adjacent to (1,1): +1;
(1,1) is not adjacent to (0,2): sequence length is 3, our current best, so lets remember the length and that it ended on the 3rd entry. Reset length counter to 1.
(0,2) is not adjacent to (1, 0): sequence length is 1, not our best. Simply reset counter to 1.
(1,0) is not adjacent to (1, 2): sequence length is 1, not our best. Simply reset counter to 1.
(1,2) is adjacent to (2,2): +1;
(2,2) is adjacent to (2,1): +1;
(2,1) is adjacent to (2,0): +1;
(2,0) is the end of the array, so the sequence ends: sequence length is 4, our current best, so lets remember the length and that it ended on the 9th entry.

3.
Our longest sequence has length 4 and ends at 9. So it starts at 9 - 4 + 1 = 6. So we output 6 7 8 9.

This algorithm has O(n^2) time and space complexity. O(n^2) is optimal for time complexity because you have to at least look at all of the entries, but O(n^2) is not optimal for space complexity. I can't seem to reduce the space complexity without increasing the time complexity however...

In Java:

void printLongestSnake(int[][] matrix) {
  int n = matrix.length;
  int nSquared = n * n;
  Coordinate[] positions = new Coordinate[nSquared];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      positions[matrix[i][j] - 1] = new Coordinate(i, j);
    }
  }
  int maxLength = 1;
  int maxEnd = 1;
  int currentLength = 1;
  for (int i = 1; i < nSquared; ++i) {
    if (positions[i].isAdjacent(positions[i - 1])) {
      ++currentLength;
    } else {
      if (currentLength > maxLength) {
        maxLength = currentLength;
        maxEnd = i;
      }
      currentLength = 1;
    }
  }
  if (currentLength > maxLength) {
    maxLength = currentLength;
    maxEnd = nSquared;
  }
  for (int i = maxEnd - maxLength + 1; i < maxEnd; ++i) {
    System.out.print(i + " ");
  }
  System.out.println(maxEnd);
}

where Coordinate is the following simple class (you could just use an array of size 2 instead of making a class if you want to be more efficient, but then, you shouldn't be using Java lol)

class Coordinate {
  private int x;
  private int y;

  public Coodinate(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public boolean isAdjacent(Coordinate c) {
    if (x == c.x && (y == c.y - 1 || y == c.y + 1) {
      return true;
    }
    if (y == c.y && (x == c.x - 1 || x == c.x + 1) {
      return true;
    }
    return false;
  }
}

I assumed that you want to print the *longest* sequence of of consecutive numbers that are adjacent in the array. If not could you please clarify your question please, thanks.

In Java, strings are immutable.

Just read the number from right to left.
In Java:

int longestSequenceOfOnes(int input) {
  int max = 0;
  int current = 0;
  for (i = input; i > 0; i = i >> 1) {
    if (i % 2 == 1) {
      ++current;
    } else {
      max = Math.max(max, current);
      current = 0;
    }
  }
  return Math.max(max, current);
}

vgeeks's 3rd algorithm in java:

boolean twoSum(int[] input) {
  int sum = getSum(input);
  if (sum % 2 == 1) {
    return false;
  }
  int target = sum / 2;
  Set<Integer> seen = new HashSet<Integer>();
  for (int i = 0; i < input.length; ++i) {
    if (seen.contains(target - input[i])) {
      return true;
    }
    seen.add(input[i]);
  }
  return false;
}

int getSum(int[] input) {
  int sum = 0;
  for (int i = 0; i < input.length; ++i) {
    sum += input[i];
  }
  return sum;
}

akkaiah.j's solution (assuming non-negative integers):
(I'm not checking if the two largest integers are greater or equal to the target sum as it isn't necessary and doesn't improve the asymptotic run time)

boolean nonNegativeTwoSum(int[] input) {
  sum = getSum(input);
  if (sum % 2 == 1) {
    return false;
  }
  int target = sum / 2;
  int[] candidates = new int[4];
  int candidatesFound = 0;
  int halfTarget = (target + 1) / 2; // Adding 1 to target in case it is odd. I want it to round up. Needed to guarantee at most 4 candidates (if we round down, [1,1,1,1,1,1] will give us 6 candidates...). 
  for (int i = 0; i < input.length; ++i) {
    if (input[i] >= halfTarget) {  
      candidates[candidatesFound++] = i;
    }
  }
  for (int i = 0; i < input.length; ++i) {
    for (int j = 0; j < candidatesFound; ++j) {
      if (input[i] + input[candidates[j]] == target && i != candidates[j]) {
        return true;
      }
    }
  }
  return false;
}

Very nice solution.
Only works if you are guaranteed non-negative integers however.

In java:

String removeDuplicates(String input) {
  Set<Character> seen = new HashSet<Character>();
  StringBuilder result = new StringBuilder();
  for (int i = 0; i < input.length(); ++i) {
    char c = input.charAt(i);
    if (seen.add(c)) {
      result.append(c);
    }
  }
  return result.toString();
}