Mock Interview: Microsoft #

557. Reverse Words in a String III

class Solution:
    def reverseWords(self, s: str) -> str:
        
        words = s.count(" ") + 1
        
        cut = s.split(" ")
        result = ""
        for c in cut:
            newc = c[::-1]
            result = result + " " + newc

        return result[1:]
        

Runtime: 32 ms, faster than 80.47% of Python3 online submissions for Reverse Words in a String III.
Memory Usage: 15 MB, less than 25.85% of Python3 online submissions for Reverse Words in a String III.

24. Swap Nodes in Pairs

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        start = ListNode(-1)
        start.next = head
        cur = start
        
        while head and head.next:
            first = head
            second = head.next
            
            cur.next = second
            first.next = second.next
            second.next = first
            
            cur = first
            head = first.next
        
        
        return start.next

Runtime: 32 ms, faster than 64.17% of Python3 online submissions for Swap Nodes in Pairs.
Memory Usage: 14.2 MB, less than 74.50% of Python3 online submissions for Swap Nodes in Pairs.

212. Word Search II

class TrieNode {
  HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
  String word = null;
  public TrieNode() {}
}

class Solution {
  char[][] _board = null;
  ArrayList<String> _result = new ArrayList<String>();

  public List<String> findWords(char[][] board, String[] words) {

    // Step 1). Construct the Trie
    TrieNode root = new TrieNode();
    for (String word : words) {
      TrieNode node = root;

      for (Character letter : word.toCharArray()) {
        if (node.children.containsKey(letter)) {
          node = node.children.get(letter);
        } else {
          TrieNode newNode = new TrieNode();
          node.children.put(letter, newNode);
          node = newNode;
        }
      }
      node.word = word;  // store words in Trie
    }

    this._board = board;
    // Step 2). Backtracking starting for each cell in the board
    for (int row = 0; row < board.length; ++row) {
      for (int col = 0; col < board[row].length; ++col) {
        if (root.children.containsKey(board[row][col])) {
          backtracking(row, col, root);
        }
      }
    }

    return this._result;
  }
  
  private void backtracking(int row, int col, TrieNode parent) {
    Character letter = this._board[row][col];
    TrieNode currNode = parent.children.get(letter);

    // check if there is any match
    if (currNode.word != null) {
      this._result.add(currNode.word);
      currNode.word = null;
    }

    // mark the current letter before the EXPLORATION
    this._board[row][col] = '#';

    // explore neighbor cells in around-clock directions: up, right, down, left
    int[] rowOffset = {-1, 0, 1, 0};
    int[] colOffset = {0, 1, 0, -1};
    for (int i = 0; i < 4; ++i) {
      int newRow = row + rowOffset[i];
      int newCol = col + colOffset[i];
      if (newRow < 0 || newRow >= this._board.length || newCol < 0
          || newCol >= this._board[0].length) {
        continue;
      }
      if (currNode.children.containsKey(this._board[newRow][newCol])) {
        backtracking(newRow, newCol, currNode);
      }
    }

    // End of EXPLORATION, restore the original letter in the board.
    this._board[row][col] = letter;

    // Optimization: incrementally remove the leaf nodes
    if (currNode.children.isEmpty()) {
      parent.children.remove(letter);
    }
  }
}

Runtime: 15 ms, faster than 96.69% of Java online submissions for Word Search II.
Memory Usage: 39.9 MB, less than 13.68% of Java online submissions for Word Search II.