LC link
Maintain a deque to
1. line 23, convert to float and make sure divisor is not zero
1. line 1 import collections
2. line 5 declare deque with maxlen by collections.deque(maxlen = size)
Thursday, August 17, 2017
[Leetcode] Meeting Rooms I and II
LC link1
Sort based on start time and check conflicts
1. Line 7,8 old drill, valid inputs
2. Line 10, sort element in place based on object's attribute python programming sugar
3. Line 12, how to handle the case where len(intervals) == 1
Use for i in xrange( 1, len(intervals)) It will ignore the case where len(intervals) == 1
LC link
Create sorted start/end list, use rooms/end_pointer trick to iterate through
1. Line 20, should be smaller, cuz start time == end time, it means a room is released
2. Line 20, don't forget to use end_pointer
3. Line 22, 23, it means a new room is release, don't need a new room, but move end_pointer
Sort based on start time and check conflicts
1. Line 7,8 old drill, valid inputs
2. Line 10, sort element in place based on object's attribute python programming sugar
3. Line 12, how to handle the case where len(intervals) == 1
Use for i in xrange( 1, len(intervals)) It will ignore the case where len(intervals) == 1
LC link
Create sorted start/end list, use rooms/end_pointer trick to iterate through
1. Line 20, should be smaller, cuz start time == end time, it means a room is released
2. Line 20, don't forget to use end_pointer
3. Line 22, 23, it means a new room is release, don't need a new room, but move end_pointer
[Leetcode]Binary Tree Level Order Traversal (AKA BFS)
LC link
Push root to queue then traverse level by level
1. Line 7, 8, old drill, validate input and ask what they want if input is not valid
2. Line 13, use for loop to simulate level by level visiting
3. line 12, 15, 20, know what they want for output,
4. Line 14, queue, FIFO pop(0) stack FILO pop()
Push root to queue then traverse level by level
1. Line 7, 8, old drill, validate input and ask what they want if input is not valid
2. Line 13, use for loop to simulate level by level visiting
3. line 12, 15, 20, know what they want for output,
4. Line 14, queue, FIFO pop(0) stack FILO pop()
[Leetcode]Number of Islands
LC link
Summary:
Ignore boundaries, sink method handles all logic and sink up/down left/right
1. Line 14, old drill, when I wrote line 14, i and j could not be negative, but in line 17,18, we access i - 1, j - 1, we need to check whether i and j are negative. Always check validness of objects or index.
Test case ["1011011"]
2. Line 17, 18 Whenever create or change method signature, check signatures!
3.
# 000
# 010
# 000 is a valid island
4. 0 == '0' returns False
5. Line 14, 17, 18 our approach ignores values on edges. So we need to sink up, down, left ,right whenever we find a island
["111","010","111"] for example, case like that
Summary:
Ignore boundaries, sink method handles all logic and sink up/down left/right
1. Line 14, old drill, when I wrote line 14, i and j could not be negative, but in line 17,18, we access i - 1, j - 1, we need to check whether i and j are negative. Always check validness of objects or index.
Test case ["1011011"]
2. Line 17, 18 Whenever create or change method signature, check signatures!
3.
# 000
# 010
# 000 is a valid island
4. 0 == '0' returns False
5. Line 14, 17, 18 our approach ignores values on edges. So we need to sink up, down, left ,right whenever we find a island
["111","010","111"] for example, case like that
6. let sink method takes care of input check and most of logics
[Leetcode]Add Two Numbers
LC Link
1. line 11, use while loop controls on 11, l2 and carry
2. line 13,16, take care of l1 and l2 separately. Cuz you always want to check Nullness before you access its attributes.
3. line 21, use carry, curr_val = divmod(raw_num, 10) to speed up process
4. line 9,22, be clear on the requirement. output as problems wanted
2. line 13,16, take care of l1 and l2 separately. Cuz you always want to check Nullness before you access its attributes.
3. line 21, use carry, curr_val = divmod(raw_num, 10) to speed up process
4. line 9,22, be clear on the requirement. output as problems wanted
[Leetcode]Excel Sheet Column Number
LC Link
1. Line 11, make sure they are all upper case cuz that's our assumption that we will process upper case
2. Line 12, whenever deal with problem to convert bla bla to another number. just use same template
res = res * (10 or 8 or 26 or whatever) + value on current digit value
You don't need to consider most right digit value cuz res equals zero at very beginning
2. Line 12, whenever deal with problem to convert bla bla to another number. just use same template
res = res * (10 or 8 or 26 or whatever) + value on current digit value
You don't need to consider most right digit value cuz res equals zero at very beginning
Wednesday, August 16, 2017
Python programming sugar
1. how to sort list of objects, based on attribute of the objects
2. compare Unicode difference between B and A ord('B') - ord('A')
3. carry, curr = divmod(val1 + val2 + carry, 10)
2. compare Unicode difference between B and A ord('B') - ord('A')
3. carry, curr = divmod(val1 + val2 + carry, 10)
What happens when you press Google.com in your browser?
1. Parse
The line gets parsed and the protocol, server, port, query gets retrieved
2. Resolve to IP Address
Browser connects to server at the default/specified port
2.1. If it is in local DNS cache, fetch it
2.2. Else, recursively check IPS's DNS servers
3. Send Request
Browser sends a GET request followed a crlf sequence then by the headers all followed by respective crlf-s
3.1 If this server has already cached cookies, the browser sends them as cookie headers
3.2 If the browser supports compression it tells the server what compression is using (via headers) as well as what compression it could accept in return
3.3 Sends a content-length header set to value "0"
3.4. Sends a header instructing the server how to denote the end of its transmission stream. Connection: Close would be the most common
3.5 Sends a crlf sequence to mark the end of the headers (after eventual other headers are sent)
4. Handle Response
4.1. Parses the response code / status
4.2. If this response starts with 2 it caches cookies, decompresses (if header is mentioning compression) parses and displays the html content of message body (executing eventual scripts hooked to different DOM elements/events)
4.3 If the response code starts with 3 redirects t the server mentioned in the response (goto 11)
4.4 If the response code starts with 4 or 5 parses the response and displays it to the user
[Leetcode]Balanced Binary Tree
0. Line 8, 10, Use root as method signature, cuz if you use left and right, it would be tricky to implement line 11,12
1. Line 22, handle normal case by making sure left and right values are inbound and then return the bigger height
2. Line 23, cuz the current root also has height of 1, so should return 1
Tree Related knowledge
1. What is a balanced binary tree?
Absolution difference between left sub-tree and right sub-tree is bigger than 1
Absolution difference between left sub-tree and right sub-tree is bigger than 1
A good video can be found here https://www.youtube.com/watch?v=TWDigbwxuB4
2. What is BFS:
scan level by level
3. What is DFS:
go down first then go back.
we have preorder, inorder and postorder. pre/in/post describe where is the root node.
1
2 3
4 5 6 7
preorder: 1, 2, 4, 5, 3, 6, 7
inorder: 4, 2, 5, 1, 6, 3, 7
postorder: 4, 5, 2, 6, 7, 3, 1
[Leetcode] How to practice Leetcode
BUG FREE / CODING STYLE
Blog them.
Whenever you submit a solution, document what is the mistake and try to remember common mistakes
When you do a new problem, see if you make same mistake again. Document old and new mistakes until bug free
Summarize your approach with one sentence
Always check Nullness/Length/IndexOutOfBounds
Use memory curve
Practice by tags
Use lintCode to test coding style
Blog them.
Whenever you submit a solution, document what is the mistake and try to remember common mistakes
When you do a new problem, see if you make same mistake again. Document old and new mistakes until bug free
Summarize your approach with one sentence
Always check Nullness/Length/IndexOutOfBounds
Use memory curve
Use lintCode to test coding style
[Leetcode] Construct Binary Tree from Preorder and Inorder Traversal / Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
1. Line 9, definitely check null of inputs
2. Line 12, pop() pops last element, pop(0) pops from beginning
3. Line 12, you want to create a root. cuz preorder and inorder only contains int
4. Line 15,16, build left subtree then right subtree. For constructing b-tree from postorder and inorder, build right sub tree first then left subtree
1. line 8, old drill, check inputs
2. line 11, we are using postorder to build b-tree. root node locates at the end of postorder
3. line 14/15, build right sub tree first, then left sub tree.
1. Line 9, definitely check null of inputs
2. Line 12, pop() pops last element, pop(0) pops from beginning
3. Line 12, you want to create a root. cuz preorder and inorder only contains int
4. Line 15,16, build left subtree then right subtree. For constructing b-tree from postorder and inorder, build right sub tree first then left subtree
1. line 8, old drill, check inputs
2. line 11, we are using postorder to build b-tree. root node locates at the end of postorder
3. line 14/15, build right sub tree first, then left sub tree.
Subscribe to:
Comments (Atom)