Reverse Thinking - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series

---

Scan from right to left

• From end to start instead from start to end
• when element’s value/state is related with afterwards elements
  • use stack
  • or maybe traverse from end
• LeetCode 844 - Backspace String Compare

public boolean backspaceCompare(String S, String T) {
    for (int i = S.length() - 1, j = T.length() - 1;; i--, j--) {
        for (int b = 0; i >= 0 && (b > 0 || S.charAt(i) == '#'); --i) b += S.charAt(i) == '#' ? 1 : -1;
        for (int b = 0; j >= 0 && (b > 0 || T.charAt(j) == '#'); --j) b += T.charAt(j) == '#' ? 1 : -1;
        if (i < 0 || j < 0 || S.charAt(i) != T.charAt(j)) return i == -1 && j == -1;
    }
}

• LeetCode 174 - Dungeon Game: minimum initial health so that he is able to rescue the princess
  • reverse thing: from princess to knight
  • dp[i][j] = max(1, min(dp[i][j+1] - mat[i][j], dp[i+1][j] - mat[i][j]))
• LeetCode 55 - Jump Game
  • track maxReach: we don’t care what positions a[i] can reach, only the maxReach
  • LeetCode 769 - Max Chunks To Make Sorted
    • merge interval
    • maxSoFar: jump game
• LeetCode 45 - Jump Game II: find the minimum number of jumps
  • two pointers to maintain a cover range
• LeetCode 482 - License Key Formatting
• HackerRank: Stock Maximize
• Leaders in an array
• LeetCode 439 - Ternary Expression Parser

public String parseTernary(String expression) {
    if (expression == null || expression.length() == 0) return "";
    Deque<Character> stack = new LinkedList<>();

    for (int i = expression.length() - 1; i >= 0; i--) {
        char c = expression.charAt(i);
        if (!stack.isEmpty() && stack.peek() == '?') {

            stack.pop(); //pop '?'
            char first = stack.pop();
            stack.pop(); //pop ':'
            char second = stack.pop();

            if (c == 'T') stack.push(first);
            else stack.push(second);
        } else {
            stack.push(c);
        }
    }
    return String.valueOf(stack.peek());
}

• LeetCode 880 - Decoded String at Index

public String decodeAtIndex(String S, int K) {
  long size = 0;
  int N = S.length();
  for (int i = 0; i < N; ++i) {
    char c = S.charAt(i);
    if (Character.isDigit(c))
      size *= c - '0';
    else
      size++;
  }
  for (int i = N - 1; i >= 0; --i) {
    char c = S.charAt(i);
    K %= size;
    if (K == 0 && Character.isLetter(c))
      return Character.toString(c);
    if (Character.isDigit(c))
      size /= c - '0';
    else
      size--;
  }
  throw null;
}

• LeetCode 880 - Decoded String at Index

public String decodeAtIndex(String S, int K) {
  long size = 0;
  int N = S.length();
  // Find size = length of decoded string
  for (int i = 0; i < N; ++i) {
    char c = S.charAt(i);
    if (Character.isDigit(c))
      size *= c - '0';
    else
      size++;
  }
  for (int i = N - 1; i >= 0; --i) {
    char c = S.charAt(i);
    K %= size;
    if (K == 0 && Character.isLetter(c))
      return Character.toString(c);
    if (Character.isDigit(c))
      size /= c - '0';
    else
      size--;
  }
  throw null;
}

• LeetCode 853 - Car Fleet
  • from closet to furthest

  public int carFleet(int target, int[] position, int[] speed) {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int n = position.length;
    for(int i=0; i<n; ++i){
        map.put(target - position[i], speed[i]);
    }
    int count = 0;
    double r = -1.0;
    for(Map.Entry<Integer, Integer> entry: map.entrySet()){
        int d = entry.getKey(); // distance
        int s = entry.getValue(); // speed
        double t = 1.0*d/s; // time to target
        if(t>r){ // this car is unable to catch up previous one, form a new group and update the value
            ++count;
            r = t;
        }
    }
    return count;
  }

From (potential) target to source

• LeetCode 780 - Reaching Points
  • if we start from sx and sy, there is two possibility, but if we start from target, there is only one possibility
  • use modulo to speed minus

bool reachingPoints(int sx, int sy, int tx, int ty) {
    while(tx >= sx && ty >= sy){
        if(tx > ty){
            if(sy == ty) return (tx - sx) % ty == 0;
            tx %= ty;
        }else{
            if(sx == tx) return (ty - sy) % tx == 0;
            ty %= tx;
        }
    }
    return false;
}

public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    if (sx > tx || sy > ty) return false;
    if (sx == tx && (ty - sy) % sx == 0) return true;
    if (sy == ty && (tx - sx) % sy == 0) return true;
    return reachingPoints(sx, sy, tx % ty, ty % tx);
}

• LeetCode 174 - Dungeon Game
• LeetCode 55 - Jump Game
  • track maxReach
  • from target to source

  public boolean canJump(int[] nums) {
  int lastPos = nums.length - 1;
  for (int i = nums.length - 1; i >= 0; i--) {
    if (i + nums[i] >= lastPos) {
      lastPos = i;
    }
  }
  return lastPos == 0;
  }

• LeetCode 477 - Largest Palindrome Product
  • from potential target palindrome
• HARD LeetCode 991 - Broken Calculator: Double or ++
  • guess, assume and prove/anti-example
  • from target to source

  public int brokenCalc(int X, int Y) {
  int ans = 0;
  while (Y > X) {
    ans++;
    if (Y % 2 == 1)
      Y++;
    else
      Y /= 2;
  }
  return ans + X - Y;
  }

• LeetCode 803 - Bricks Falling When Hit
  • reverse thinking: from end state + union find
    • res[i] = (newSize - count > 0) ? newSize - count - 1 : 0;

Reverse

• LeetCode 186 Reverse Words in a String II: in-place
• LeetCode 189 - Rotate an array right by k element
• Sort the sequence using pancake sorting as few reversals as possible
• LeetCode 969 - Pancake Sorting
  • swap max to top
  • swap max to bottom
  • reduce size then repeat

Reverse - call same function again

• Find maximum difference between nearest left and right smaller elements
  • reverse and call same function again

Guess

• [LeetCode 843 - Guess the Word]
  • [minimum our worst outcome]
    • worse case: only 0 match,
    • we guess the word with minimum words of 0 matches

// random
public void findSecretWord(String[] wordlist, Master master) {
  for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
      String guess = wordlist[new Random().nextInt(wordlist.length)];
      x = master.guess(guess);
      List<String> wordlist2 = new ArrayList<>();
      for (String w : wordlist)
          if (match(guess, w) == x)
              wordlist2.add(w);
      wordlist = wordlist2.toArray(new String[wordlist2.size()]);
  }
}

public void findSecretWord(String[] wordlist, Master master) {
  for (int i = 0, x = 0; i < 10 && x < 6; ++i) {
      HashMap<String, Integer> count = new HashMap<>();
      for (String w1 : wordlist)
          for (String w2 : wordlist)
              if (match(w1, w2) == 0)
                  count.put(w1, count.getOrDefault(w1 , 0) + 1);
      Pair<String, Integer> minimax = new Pair<>("", 1000);
      for (String w : wordlist)
          if (count.getOrDefault(w, 0) < minimax.getValue())
              minimax = new Pair<>(w, count.getOrDefault(w, 0));
      x = master.guess(minimax.getKey());
      List<String> wordlist2 = new ArrayList<String>();
      for (String w : wordlist)
          if (match(minimax.getKey(), w) == x)
              wordlist2.add(w);
      wordlist = wordlist2.toArray(new String[0]);
  }
}