Design Questions

1. Design TinyURL

Sample Answer: Answer

2. Consistent Hashing

Graph Related Questions

There might several ways to even represent graphs. For example: only represent by node, if we consider all edges having the same weight.

public class GraphNode {
      int label;
      ArrayList neighbors;
      GraphNode(int x) { label = x; neighbors = new ArrayList(); }
  };
 

Or represented by both node and edges if edges have different weights.

public class Vertex {
  final private String id;
  final private String name;
  
  
  public Vertex(String id, String name) {
    this.id = id;
    this.name = name;
  }
  //getter and setter methods
}

public class Edge  {
  private final String id; 
  private final Vertex source;
  private final Vertex destination;
  private final int weight; 
  
  public Edge(String id, Vertex source, Vertex destination, int weight) {
    this.id = id;
    this.source = source;
    this.destination = destination;
    this.weight = weight;
  }
  //getter and setter methods
}

public class Graph {
  private final List vertexes;
  private final List edges;

  public Graph(List vertexes, List edges) {
    this.vertexes = vertexes;
    this.edges = edges;
  }

  public List getVertexes() {
    return vertexes;
  }

  public List getEdges() {
    return edges;
  }

With above data setup, then some simple task like: searching for neighbors of one vertex is like:

private List getNeighbors(Vertex node) {
    List neighbors = new ArrayList();
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)) {
        neighbors.add(edge.getDestination());
      }
    }
    return neighbors;
  }

The distance between two nodes is:

private int getDistance(Vertex node, Vertex target) {
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)
          && edge.getDestination().equals(target)) {
        return edge.getWeight();
      }
    }
    throw new RuntimeException("Should not happen");
  }

1. Question: finds the shortest path from a source to all destination in a directed graph
Answer: classical Dijkstra algorithm, refer to Tutorial and Wiki.

public class DijkstraAlgorithm {

  private final List nodes;
  private final List edges;
  private Set settledNodes;
  private Set unSettledNodes;
  private Map predecessors;
  private Map distance;

  public DijkstraAlgorithm(Graph graph) {
    // create a copy of the array so that we can operate on this array
    this.nodes = new ArrayList(graph.getVertexes());
    this.edges = new ArrayList(graph.getEdges());
  }

  public void execute(Vertex source) {
    settledNodes = new HashSet();
    unSettledNodes = new HashSet();
    distance = new HashMap();
    predecessors = new HashMap();
    distance.put(source, 0);
    unSettledNodes.add(source);
    while (unSettledNodes.size() > 0) {
      Vertex node = getMinimum(unSettledNodes);
      settledNodes.add(node);
      unSettledNodes.remove(node);
      findMinimalDistances(node);
    }
  }

  private void findMinimalDistances(Vertex node) {
    List adjacentNodes = getNeighbors(node);
    for (Vertex target : adjacentNodes) {
      if (getShortestDistance(target) > getShortestDistance(node)
          + getDistance(node, target)) {
        distance.put(target, getShortestDistance(node)
            + getDistance(node, target));
        predecessors.put(target, node);
        unSettledNodes.add(target);
      }
    }

  }

  private int getDistance(Vertex node, Vertex target) {
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)
          && edge.getDestination().equals(target)) {
        return edge.getWeight();
      }
    }
    throw new RuntimeException("Should not happen");
  }

  private List getNeighbors(Vertex node) {
    List neighbors = new ArrayList();
    for (Edge edge : edges) {
      if (edge.getSource().equals(node)
          && !isSettled(edge.getDestination())) {
        neighbors.add(edge.getDestination());
      }
    }
    return neighbors;
  }

  private Vertex getMinimum(Set vertexes) {
    Vertex minimum = null;
    for (Vertex vertex : vertexes) {
      if (minimum == null) {
        minimum = vertex;
      } else {
        if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
          minimum = vertex;
        }
      }
    }
    return minimum;
  }

  private boolean isSettled(Vertex vertex) {
    return settledNodes.contains(vertex);
  }

  private int getShortestDistance(Vertex destination) {
    Integer d = distance.get(destination);
    if (d == null) {
      return Integer.MAX_VALUE;
    } else {
      return d;
    }
  }

  /*
   * This method returns the path from the source to the selected target and
   * NULL if no path exists
   */
  public LinkedList getPath(Vertex target) {
    LinkedList path = new LinkedList();
    Vertex step = target;
    // check if a path exists
    if (predecessors.get(step) == null) {
      return null;
    }
    path.add(step);
    while (predecessors.get(step) != null) {
      step = predecessors.get(step);
      path.add(step);
    }
    // Put it into the correct order
    Collections.reverse(path);
    return path;
  }

2. 
   Question: Permutation
   Given a collection of numbers, return all possible permutations.
   
   For example,
   [1,2,3] have the following permutations:
   [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
   
   
   
   Answer:
   Solution#1
   
   

   public class Solution {
       public ArrayList<ArrayList<Integer>> permute(int[] num) {
           if (num==null) return null;
           return permuteHelper(num, 0);
       }
       
       //create a helper method to avoid cut elements from array num
       public ArrayList<ArrayList<Integer>> permuteHelper(int[] num, int startIdx) {
           int length=num.length;
           ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
           
           if(length==startIdx) {
               ArrayList<Integer> emptyList = new ArrayList<Integer>();
               result.add(emptyList);
               return result;
           } 
           int firstNum = num[startIdx];
           ArrayList<ArrayList<Integer>> subPermutations = permuteHelper(num, startIdx+1);
           for(ArrayList<Integer> subPers: subPermutations) {
               for (int i=0; i<=subPers.size(); i++) {
                   ArrayList<Integer> newArray = addElementToIth(subPers,i,firstNum);
                   result.add(newArray);
               }
           }
           return result;
       }
       
       //creating a new ArrayList by inserting newNum at its 'idx' index place
       public ArrayList<Integer> addElementToIth(ArrayList<Integer> arrList, int idx, int newNum) {
           ArrayList<Integer> newArr = new ArrayList<Integer>();
           int length = arrList.size();
           for(int i=0; i<=length; i++) {
               if(i==idx) {
                  newArr.add(newNum);
               }
               //check if i<=length to avoid outOfIndex error
               if(i!=length) {
                  newArr.add(arrList.get(i));
               }
           }
           return newArr;
       }
   }
   
   

Tree related questions

1. 
   Question:Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. QuestionLink
   
   
   Answer: bottom up approach: build subtree first up to the root analysis from LeetCodeDiscussion In the previous array to BST, we construct the BST in a top-down way.
   For the list data structure, to get the mid point every time is a waster of time. So construct the BST in a bottom-up way. However, the length of the list must be computed.
   Recursively
   
   1. construct the left tree
   2. construct the root node, list pointer +1.
   3. construct the right node
   
   

   public ListNode list = null; //use class variable to address Java only pass parameter by references
       public TreeNode sortedListToBST(ListNode head) {
           if(head==null) return null;
           list = head;
           ListNode curr= head;
           int length=0;
           while(curr!=null) {
               curr=curr.next;
               length++;
           }
           return sortedListToBSTHelper(0, length-1);
       }
       public TreeNode sortedListToBSTHelper(int start, int end) {
           if(start>end) return null;
           int mid = (start+end)/2;
           TreeNode left = sortedListToBSTHelper(start, mid-1);
           TreeNode parent = new TreeNode(list.val);
           list=list.next;
           TreeNode right = sortedListToBSTHelper( mid+1, end);
           parent.left = left;
           parent.right = right;
           return parent;
       }
   

2. 
   Question:Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.QuestionLink
   
   
   Answer: just to remember to remove the tailing node saved in the path after finishing recursion
   
   

   public ArrayList< ArrayList<Integer> > pathSum(TreeNode root, int sum) {
           ArrayList< ArrayList<Integer> > result = new ArrayList< ArrayList<Integer> >();
           ArrayList<integer> path = new ArrayList<integer>();
           pathSumHelper(root,sum, path, result);
           return result;
    }
       
    public void pathSumHelper(TreeNode root, int sum, ArrayList<integer> path, ArrayList< ArrayList<Integer> > result) {
           if (root==null) return;
           path.add(root.val);
           if (root.left==null&&root.right==null&&root.val==sum) {
               ArrayList<integer> onePath = new ArrayList<integer>(path); //have to make a copy of path
               result.add(onePath);
           } else {
               pathSumHelper(root.left, sum-root.val, path, result);
               pathSumHelper(root.right, sum-root.val, path, result);
           }
           path.remove(path.size()-1);
    }
   

   
   Question:Implement In-order/Pre-Order/Post-Order Iterator for Binary Tree QuestionLink
   
   Interface looks like:
   

   public interface InOrderBinaryTreeIterator extends Iterator { 
     /** Returns the next integer a in the in-order traversal of the given binary tree.
      *  For example, given a binary tree below,
      *       4
      *      / \
      *     2   6
      *    / \ / \
      *   1  3 5  7
      * the outputs will be 1, 2, 3, 4, 5, 6, 7. 
      */ 
     public Integer next(); 
   
     /** Return true if traversal has not finished; otherwise, return false.
      */ 
     public boolean hasNext();
   }
   

   
   Answer: Iterator means we can NOT save all tree nodes into a container and then iterating through the container.
   
   idea like:
   1) Find the left-most node of the root and store previous left children in a stack;
   2) Pop up the top node from the stack;
   3) If it has a right child, find the left-most node of the right child and store left children in the stack.
   
   
   

   //InOrder (LNR) iterator key: when initialize the stack, push root and all its left child into the stack; 
   public class InOrderBinaryTreeIteratorImpl implements InOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Push node cur and all of its left children into stack */  
      private void pushLeftChildren(TreeNode cur) {  
        while (cur != null) {  
          stack.push(cur);  
          cur = cur.left;  
        }  
      }  
      
      /** Constructor */  
      public InOrderBinaryTreeIterator(TreeNode root) {  
        pushLeftChildren(root);  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop();  
        pushLeftChildren(res.right);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   //PreOrder (NLR) iterator key: only push root into Stack in Constructor; push right and then left into Stack in Next function
    public class PreOrderBinaryTreeIteratorImpl implements PreOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Constructor */  
      public PreOrderBinaryTreeIterator(TreeNode root) {  
        if (root != null) {  
          stack.push(root); // add to end of queue 
        }  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop(); // retrieve and remove the head of queue 
        if (res.right != null) stack.push(res.right);  
        if (res.left != null) stack.push(res.left);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   //PreOrder (NLR) iterator key: only push root into Stack in Constructor; push right and then left into Stack in Next function
    public class PreOrderBinaryTreeIteratorImpl implements PreOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** Constructor */  
      public PreOrderBinaryTreeIterator(TreeNode root) {  
        if (root != null) {  
          stack.push(root); // add to end of queue 
        }  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop(); // retrieve and remove the head of queue 
        if (res.right != null) stack.push(res.right);  
        if (res.left != null) stack.push(res.left);  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }    
   
   public class PostOrderBinaryTreeIteratorImpl implements PostOrderBinaryTreeIterator {  
      Stack<TreeNode> stack = new Stack<TreeNode>();  
      
      /** find the first leaf in a tree rooted at cur and store intermediate nodes */  
      private void findNextLeaf(TreeNode cur) {  
        while (cur != null) {  
          stack.push(cur);  
          if (cur.left != null) {  
            cur = cur.left;  
          } else {  
            cur = cur.right;  
          }  
        }  
      }  
      
      /** Constructor */  
      public PostOrderBinaryTreeIterator(TreeNode root) {  
        findNextLeaf(root);  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public boolean hasNext() {  
        return !stack.isEmpty();  
      }  
      
      /** {@inheritDoc} */  
      @Override  
      public Integer next() {  
        if (!hasNext()) {  
          throw new NoSuchElementException("All nodes have been visited!");  
        }  
      
        TreeNode res = stack.pop();  
        if (!stack.isEmpty()) {  
          TreeNode top = stack.peek();  
          if (res == top.left) {  
            findNextLeaf(top.right); // find next leaf in right sub-tree 
          }  
        }  
      
        return res.val;  
      }  
      
      @Override  
      public void remove() {  
        throw new UnsupportedOperationException("remove() is not supported.");  
      }  
    }
   
   public ArrayList<Integer> postorderTraversal(TreeNode root) {  
      PostOrderBinaryTreeIterator iterator = new PostOrderBinaryTreeIteratorImpl(root);  
      ArrayList<Integer> results = new ArrayList<Integer>();  
      while (iterator.hasNext()) {  
        results.add(iterator.next());  
      }  
      return results;  
    }      
   

LinkList Questions

1. 
   Question: Remove Nth Node From End of List QuestionLink
   Given a linked list, remove the nth node from the end of list and return its head.
   

   For example,
   
      Given linked list: 1->2->3->4->5, and n = 2.
   
      After removing the second node from the end, the linked list becomes 1->2->3->5.
   Note:
   Given n will always be valid.
   Try to do this in one pass.
   

   
   
   Answer:
   
   

   public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
        val = x;
        next = null;
     }
   }
   
   public ListNode removeNthFromEnd(ListNode head, int n) {
       //use Dummy node to keep list head
       ListNode dummy = new ListNode(0);
       dummy.next = head;
   
       ListNode p = dummy;        
       ListNode q = dummy;
       for(int i=0; i< n+1;i++){   // With n+1(start with dummy node), when q reaches the end of the list, p is at the one before the to-delete node
           q = q.next;
       }
       while(q!=null){
           p = p.next;
           q = q.next;
       }
       p.next =p.next!=null?p.next.next:null;
       return dummy.next;     
   }
   

2. 
   Question: Merge k Sorted Lists QuestionLink
   
   Answer:
   
   Solution#1: merge every two lists into one and recursively finish all lists
   
   
   

   //O(n*k) method: recursively merge two lists (n is total node number)
   public ListNode mergeKLists(ArrayList lists) {
           if(lists==null || lists.isEmpty()) return null;
           if(lists.size()==1) return lists.get(0);
           if(lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
           int count = 2;
           ListNode twoMergeList = mergeTwoLists(lists.get(0), lists.get(1));
           while (count < lists.size()) {
               twoMergeList = mergeTwoLists(twoMergeList, lists.get(count));
               count++;
           }
           return twoMergeList;
   }
   
       //answer of http://oj.leetcode.com/problems/merge-two-sorted-lists/
       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           
           //trick: create a dummy node and use dummyNode's next as newHead
           ListNode dummyNode = new ListNode(0);
           ListNode currNode = dummyNode;
           while(l1!=null||l2!=null) {
               if(l1!=null&&l2!=null) {
                   if(l1.val < l2.val) {
                       currNode.next=l1;
                       l1=l1.next;
                   } else {
                       currNode.next=l2;
                       l2=l2.next;
                   }
               } else if (l1!=null) {
                   currNode.next=l1;
                   l1=l1.next;
               } else {
                   currNode.next=l2;
                   l2=l2.next;
               }
               currNode = currNode.next;
           }
           return dummyNode.next;
       }
   

   Solution#2:

   //use mini-heap to keep the smallest number in k list total listnode in all lists is n, 
       //then time complexity is: O(n*lgk)
       public ListNode mergeKLists2(ArrayList lists) {
       if (lists == null || lists.isEmpty())  return null;
   
       Comparator comparator = new Comparator() {
           @Override
           public int compare(ListNode n1, ListNode n2) {
               if (n1.val < n2.val)  return -1;
               if (n1.val > n2.val)  return 1;
               return 0;
           }
       };
   
       PriorityQueue heap = new PriorityQueue(lists.size(), comparator);
       //O(klogk)
       for (ListNode node : lists) {
           if (node != null)  heap.add(node);
       }
   
       ListNode head=null, cur=null;
       //n
       while (!heap.isEmpty()) {
           if (head == null) {
               head = heap.poll();
               cur = head;
           } else {
               cur.next = heap.poll();
               cur = cur.next;
           }
           if (cur.next != null)  {
              heap.add(cur.next); //heap insert: O(lgk)   
           }
       }
   
       return head;
   }
   

3. 
   Question: Reverse Nodes in k-Group QuestionLink
   
   

   Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
   If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
   You may not alter the values in the nodes, only nodes itself may be changed.
   Only constant memory is allowed.
   For example,
   Given this linked list: 1->2->3->4->5
   
   For k = 2, you should return: 2->1->4->3->5
   
   For k = 3, you should return: 3->2->1->4->5
   

   Answer:
   
   

   public ListNode reverseKGroup(ListNode head, int k) {
           if(head ==null || head.next == null || k<=1) return head;
           ListNode dummy = new ListNode(0);
           dummy.next = head;
           ListNode tail = dummy;
           ListNode kbegin = null;
           ListNode kend = null;
   
           ListNode node = head; //node starts with actual head, not dummy
           int count =0;
           while(node!=null){
               if(count%k==0) { //count starting with 0, recording the kbegin node
                   kbegin = node;
               }
               if(count%k==k-1) { //recording kend node
                   kend = node;
               }
               node = node.next;
               if(count%k==k-1){
                   reverseList(kbegin, kend);
                   tail.next = kend; //link tail head to kend(now beginning node)
                   tail = kbegin; //move tail to the new tail(kbegin)
                   tail.next = node; //kbegin's next was set to null in reverseList, now link to next node in following k
               }
               count++;
           }
           return dummy.next;
       }
       
       public void reverseList(ListNode start, ListNode end) {
           //set end.next=NULL to indicate the end. Don't need this line when actually reversing a list
           end.next = null; 
           ListNode prev = null;
           ListNode curr = start;
           while(curr!=null) {
               ListNode next = curr.next;
               curr.next = prev;
               prev = curr;
               curr = next;
           }
       }
   

4. 
   Question: A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. QuestionLink
   
   Answer:
   
   Solution#1: recursive way. Use a hashmap to save the nodes which are already copied.
   
   

   public RandomListNode copyRandomList(RandomListNode head) {
           Map copiedNodes = new HashMap();
           return copyRandomListHelper(head, copiedNodes);
   }
       
   public RandomListNode copyRandomListHelper(RandomListNode head, Map nodeMap) {
           if(head ==null) return null;
           if(nodeMap.containsKey(head)) return nodeMap.get(head);
           RandomListNode newHead = new RandomListNode(head.label);
           nodeMap.put(head, newHead);
           newHead.next = copyRandomListHelper(head.next, nodeMap);
           newHead.random = copyRandomListHelper(head.random, nodeMap);
           return newHead;
   }
   

   
   
   
   Solution#2: iterative way. Idea from Link.
   Analysis:
   This problem returns a new linked list, which has the same value and structure of the original one. First we can create a new linked list without considering the Random pointer, which is straight forward: Scan every node in the original list and create the new list (line 9- 15 in the code below).
   
   But how to keep the random pointer also correct ? If we only point the new random pointer to the original random pointer, which is not a deep copy (since the deletion of nodes in original list will delete the new one as well). So, how to memorize the relative position of the random node to the current node? Firstly I think to use the length from head node to the random node. For each node, I stored the position of its random node, same position node in the new list is the random node for the node in the new list. This idea can work, but is not efficient. For every node you have to search from the start to the end to find the random, the total complexity is O(n^2). Can we quickly locate the position of the node? Yes! Hash map! A map with the node as key and node as the value can finish the job! We can use the original list node as the key, and the same node in the new list as the value. Now the map[node_old] = node_new, therefore the node_new->random = map[node_old->random]. In this way, the complexity decreases to O(n).
   
   
   

   public RandomListNode iterativeSolution(RandomListNode head) {
            if (head==null) return null;
            Map oldNewMap = new HashMap();
            RandomListNode dummy = new RandomListNode(0);
            RandomListNode newCurr = dummy; //use dummy node as previous node to clone list with only next pointers
            RandomListNode curr = head;
            
            //finish cloning list with next pointers
            while(curr != null) {
                RandomListNode copy = new RandomListNode(curr.label);
                oldNewMap.put(curr, copy);  //key is old node, value is copied node
                newCurr.next = copy;
                curr = curr.next;
                newCurr=newCurr.next;
            }
            
            curr=head;
            newCurr=dummy.next;
            while(curr!=null) {
                if(curr.random == null) {
                    newCurr.random = null;
                } else {
                    newCurr.random = oldNewMap.get(curr.random);
                }
                curr = curr.next;
                newCurr = newCurr.next;
            }
            return dummy.next;
       }
   

Matrix Related Questions

1. 
   Question:
   Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
   
   Answer: idea from this post, I feel it's easier to understand than the layer switch approach on the book. Depending on whether it's clock-wise/counter clock-wise rotation, we first switch the elements along the main diagonal/reverse diagonal and switch row i with row n-i.
   
   
   

   // counter-clockwise rotate: switch elements along main diagonal
       public static void rotateCounterClock(int[][] matrix, int n) {
           // only mirror switch elements on upper, right triangle
           for (int i = 0; i < n; i++) {
               for (int j = i + 1; j < n; j++) {
                   int tmp = matrix[i][j];
                   matrix[i][j] = matrix[j][i];
                   matrix[j][i] = tmp;
               }
           }
   
           for (int i = 0; i < n / 2; i++) {
               for (int j = 0; j < n; j++) {
                   int tmp = matrix[i][j];
                   matrix[i][j] = matrix[n - 1 - i][j];
                   matrix[n - 1 - i][j] = tmp;
               }
           }
       }
   
       // clockwise rotate: switch elements along reverse diagonal
       public static void rotateClock(int[][] matrix, int n) {
           // only switch the elements in the upper left triangle
           for (int i = 0; i < n; i++) {
               for (int j = 0; j < n - 1 - i; j++) {
                   int tmp = matrix[i][j];
                   matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
                   matrix[n - 1 - j][n - 1 - i] = tmp;
               }
           }
   
           for (int i = 0; i < n / 2; i++) {
               for (int j = 0; j < n; j++) {
                   int tmp = matrix[i][j];
                   matrix[i][j] = matrix[n - 1 - i][j];
                   matrix[n - 1 - i][j] = tmp;
               }
           }
       }
   

2. 
   Question: TEMPLATE QuestionLink
   
   
   Answer: