A Career Retrospective

SNEI(Sony)

Design Principles for Ingestors
Simple
Independent
- Ingesters are independent and can be ran at same time

Idempotent
- Able to rerun ingester (with new change/logic), not impact to clients
- Generate HashId

Testablity
Visibility - monitoring

Design Mistakes
Use Dynamodb to store data
Solr schema for the unique field
Why happened? 
- Only considered current requirements, didn't plan/think features that we need in near future, like need query and export data





How to Evaluate Job Opportunities - Worth trying?

Know the team
What the team is doing/tech stack
The manager
  - like work experience, how long he worked in this company and team, management style, tech talk
The team members
  - how diversity is the team, team members tech blog/talk
  - We can get this info from recruiter, friends, or linkedin

Know the interview
How many rounds of interview
Whether all (on-site) interviews will happen in one day
Whether decision maker(manager) is there
- In rare cases, some companies wants to have 2 rounds of onsite-interview, then if goes well, do the remaining on-site interview on another day
- Ask recruiter whether they can arrange all interviews on same day
The interviewers
  - Diversity of the interviewers

Reject it kindly if it doesn't match your expectation/skills, as for most companies, you can interview for just one team. If it fails, you have to wait till next year.

Ask Interviewer
How many coding questions will be asked
- Some interviewers/companies like to first ask some simple coding question then move on to a difficult one.
- In this case, you want to finish the first one quickly so you have time to work on the next one.

Learning from Interview

Talking aloud
Communication


- Have a good/friendly/happy conversation with the interviewer
- Eye contact, real discussion
- Make interviewer like you: your personality, your skills etc
- Show the process how you tackle the problem

Always think whether there are different/better approaches
- If you find it (even after you finish your current approaches) , still say it

If there are somethings that you didn't solve or understand
- Ask for hints/solutions 
- if possible
- Even that questions maybe not that important: that shows you want to learn in any cirsumstances

Before interview
- Know how many questions they would ask
- Some companies/interviewers likes to ask simple code questions as warm up, if you spend too much time on it, there may be no much time left for the next real question.
- Though, personally lots of warm up coding questions is not that useful - as it only causes confusion.
- Good warm up questions: 
-- different types: simple dfs/recursion question

When write code
What expectations from the interviewers:
- Do they care about details such as sanity check, corner cases
- Or they focus on the high level algorithm and your problem solving skills
- If they ask you simple coding questions, pay more attention to details when you write the code and later when re-check

- If possible - depend on timings
- Always say: let me check the code again after you finish your first draft code
- Always run some examples:
  - Generalize your example: isPalindromOneDiff

Never say:
I don't know
- Try to solve it, infer from your existing knowledge 

Even after you finish your code/design, think aloud what you can improve
What's the time/space complexity of your current approach
How you can improve it:
- your current approach: O(1) time, O(n) time,  can you use lesser space but still O(1) time, or lesser space but more time: like O(logn) time

When find/realize there are something you can improve: in the code, design
- Say it,
- Fix it 
- in the code, if possible before the interviewer takes the picture

Even after all this, ask the interviewer:
- Take this as a chance to learn something
Is there any better approach?
Did I miss anything in the design?

Reflection
- Think what you can do better, what mistakes you made, what lessons you learned after interview

When write code
What states/variables/invariants you are trying to maintain

Source of bugs
loop variables 
- forget to change them: next=current.next; 

Merge Sort - Algorithm

Merge sort
- divide and conquer: left, right, count values while merging left and right

Merge sort code
http://www.jiuzhang.com/solutions/reverse-pairs/
    private int merge(int[] A, int start, int mid, int end) {
        int[] temp = new int[A.length];
        int leftIndex = start;
        int rightIndex = mid + 1;
        int index = start;
        int sum = 0;
        
        while (leftIndex <= mid && rightIndex <= end) {
            if (A[leftIndex] <= A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
                sum += mid - leftIndex + 1;
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }
        
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
        
        return sum;
    }

LeetCode 493 - Reverse Pairs
- Merge sort
    private int mergeSort(int[] nums, int s, int e){
        if(s>=e) return 0; 
        int mid = s + (e-s)/2; 
        int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); 
        for(int i = s, j = mid+1; i<=mid; i++){
            while(j<=e && nums[i]/2.0 > nums[j]) j++; 
            cnt += j-(mid+1); 
        }
        Arrays.sort(nums, s, e+1); 
        return cnt; 
    }
- build the Binary Search Tree from right to left and search the partially built tree with nums[i]/2.0
class Node{
    int val, less = 0, same = 1;//less: number of nodes that less than this node.val
    Node left, right;
}


LeetCode 327 - Count of Range Sum
return the number of range sums that lie in [lower, upper] inclusive.
- merge sort
- presum: sum[i..j]
- Binary search tree 
56     private int rangeSize(TreeNode root, long lower, long upper) {
57         int total = root.count + root.leftSize + root.rightSize;
58         int smaller = countSmaller(root, lower);    // Exclude everything smaller than lower
59         int larger = countLarger(root, upper);      // Exclude everything larger than upper
60         return total - smaller - larger;
61     }

Count Inversions in an array
LeetCode 315 - Count of Smaller Numbers After Self
https://discuss.leetcode.com/topic/31554/11ms-java-solution-using-merge-sort-with-explanation
https://discuss.leetcode.com/topic/31162/mergesort-solution/12
int[] count;
public List countSmaller(int[] nums) {
    List res = new ArrayList();     

    count = new int[nums.length];
    int[] indexes = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
     indexes[i] = i;
    }
    mergesort(nums, indexes, 0, nums.length - 1);
    for(int i = 0; i < count.length; i++){
     res.add(count[i]);
    }
    return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
 if(end <= start){
  return;
 }
 int mid = (start + end) / 2;
 mergesort(nums, indexes, start, mid);
 mergesort(nums, indexes, mid + 1, end);
 
 merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
 int mid = (start + end) / 2;
 int left_index = start;
 int right_index = mid+1;
 int rightcount = 0;     
 int[] new_indexes = new int[end - start + 1];

 int sort_index = 0;
 while(left_index <= mid && right_index <= end){
  if(nums[indexes[right_index]] < nums[indexes[left_index]]){
   new_indexes[sort_index] = indexes[right_index];
   rightcount++;
   right_index++;
  }else{
   new_indexes[sort_index] = indexes[left_index];
   count[indexes[left_index]] += rightcount;
   left_index++;
  }
  sort_index++;
 }
 while(left_index <= mid){
  new_indexes[sort_index] = indexes[left_index];
  count[indexes[left_index]] += rightcount;
  left_index++;
  sort_index++;
 }
 while(right_index <= end){
  new_indexes[sort_index++] = indexes[right_index++];
 }
 for(int i = start; i <= end; i++){
  indexes[i] = new_indexes[i - start];
 }
}
- binary search tree

TODO Max Surpasser

LeetCode 327 - Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] sums = new long[n + 1];
    for (int i = 0; i < n; ++i)
        sums[i + 1] = sums[i] + nums[i];
    return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
    if (end - start <= 1) return 0;
    int mid = (start + end) / 2;
    int count = countWhileMergeSort(sums, start, mid, lower, upper) 
              + countWhileMergeSort(sums, mid, end, lower, upper);
    int j = mid, k = mid, t = mid;
    long[] cache = new long[end - start];
    for (int i = start, r = 0; i < mid; ++i, ++r) {
        while (k < end && sums[k] - sums[i] < lower) k++;
        while (j < end && sums[j] - sums[i] <= upper) j++;
        while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
        cache[r] = sums[i];
        count += j - k;
    }
    System.arraycopy(cache, 0, sums, start, t - start);
    return count;
}


Count Inversions in an array
Count pairs in an array that hold i*arr[i] > j*arr[j]


Find a permutation that causes worst case of Merge Sort


LeetCode 148 - Sort LinkedList
- fake head ListNode fakehead = new ListNode(-1);


X. How to merge
Maximum Sum Path in Two Arrays
We can switch from one array to another array only at common elements.
http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
if (ar1[i] < ar2[j])
     sum1 += ar1[i++];
 // Add elements of ar2[] to sum2
 else if (ar1[i] > ar2[j])
     sum2 += ar2[j++];

X. K Sorted List
- PriorityQueue

LeetCode 632 - Smallest Range
Find the smallest range that includes at least one number from each of the klists.
- PriorityQueue

LeetCode - Merge k Sorted Lists
Merge K Sorted Iterators - Linkedin
public class IntIter {
    int next;
    Iterator iter;
}


Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (39) Eclipse (33) Code Example (31) Linux (24) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Problem Solving (10) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (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) 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) Life (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) 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) Invest (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