Han Zhu's Study Notes

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions: Excel(int H, char W):  This is the constructor. The inputs represents the height and width of the Excel form.  H  is a positive integer, range from 1 to 26. It represents the height.  W  is a character range from 'A' to 'Z'. It represents that the width is the number of characters from 'A' to  W . The Excel form content is represented by a height * width 2D integer array  C , it should be initialized to zero. You should assume that the first row of  C  starts from 1, and the first column of  C  starts from 'A'. void Set(int row, char column, int val):  Change the value at  C(row, column)  to be val. int Get(int row, char column):  Return the value at  C(row, column) . int Sum(int row, char column, List of Strings : numbers):  This function...

Design a Tic-tac-toe game that is played between two players on a  n  x  n  grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves is allowed. A player who succeeds in placing  n  of their marks in a horizontal, vertical, or diagonal row wins the game. Example: Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| toe.move(1, 1, 2); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| toe.move(2, 0, 1); -> Ret...

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. For example, MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3 Thought process: Use queue. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class MovingAverage { private double sum ; private int capacity ; private Queue < Integer > queue ; /** Initialize your data structure here. */ public MovingAverage ( int size ) { capacity = size ; sum = 0 ; queue = new LinkedList <>(); } public double next ( int val ) { if ( queue . size () == capacity ) { sum -= queue . poll (); } queue . offer ( val ); sum += val ; return sum / queue . size (); } } /** * Your MovingAvera...

Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling  next  repeatedly until  hasNext  returns  false , the order of elements returned by  next  should be:  [1, 3, 2, 4, 5, 6] . Follow up : What if you are given  k  1d vectors? How well can your code be extended to such cases? Clarification for the follow up question -  Update (2015-09-18): The "Zigzag" order is not clearly defined and is ambiguous for  k > 2  cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input: [1,2,3] [4,5,6,7] [8,9] It should return  [1,4,8,2,5,9,3,6,7] . Thought process: Combine two lists into one zigzag list in the constructor. Solution 1 (iterator): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public...

Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character  '#' ). For  each character  they type  except '#' , you need to return the  top 3  historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules: The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first). If less than 3 hot sentences exist, then just return as many as you can. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list. Your job is to implement the following functions: The constructor function: AutocompleteSystem(String[] sent...