Algorithmic Thinking

Strategy
- Talking loud
- Always saying/doing
  -- Let me check it again

Checking
-- loop invariant, loop variables: like p = p.next;

What data structures to use:
 - Stack
- PriorityQueue
- TreeMap, TreeSet


Starts from simple solution that works
- First brute force DFS
- brute force DFS + Cache: (easier to write)
- DP

- Save state, existing already known info, use them

X. Left, right array
Scan from left to right or from right to left
Map lastPosMap

left[], right[] maintains some value till current index (ending at idx)

Mistakes/Bugs to check:
- Return right result
- index, or element value?
- do again after while loop

Edge Cases:
- Check code,
  - ==null, whether element can be null
- Element is null
- What if the NestedInteger can be null

Misc
- Map: preSum:index

TreeSet
- floor, higher
TreeMap
- lowerKey, higherKey
- lowerEntry, ceilingEntry

Arrays
- binarySearch
Interval[] sortedIntervals = Arrays.copyOf(intervals,intervals.length);

Character
.isDigit

X. Left right array
Scan from left to right or from right to left
O(N)
- left[], right[]: right[] is not really needed
- leftMin[], LeftMax[], rightMin[], rightMax[]
- the array maintains some value till current index (ending at idx)
  -- runningSum/Product

Lintcode 45 - Maximum Subarray Difference
Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

LeetCode 238 - Product of Array Except Self

Given an array arr[], find the maximum j - i such that arr[j] > arr[i]
- leftMin[], rightMax

Maximum Length Bitonic Subarray
- O(1) space: end, start

Related: Longest Bitonic Subsequence
- DP lis[], lds[]

LeetCode 42 - Trapping Rain Water
- two pointers, left, right and maintain leftMax, rightMax
int min = Math.min(leftMax[i], rightMax[i]);
if (height[i] < min) {
  volume += min - height[i];
}
- ordered stack
- leftMax[], rightMax[]

Related: LeetCode 407 - Trapping Rain Water II
- BFS + PriorityQueue
- Add borders first

LeetCode 11 - Container With Most Water
- two pointers

Post a Comment

Labels

Java (159) Lucene-Solr (110) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (36) Eclipse (34) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Nutch2 (18) Tools (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (12) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Problem Solving (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) Lesson Learned (5) Programmer Skills (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) System Design (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts