Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

solution is similar to bucket sort.  with help or hash table, this can be O(n).
1. calculate statistics of frequency by using hash table/map
2. putting map entries to priority queue by defining proper comparator that makes it sorting by frequency high to low

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

public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> frequencyMap = new HashMap<Integer,Integer>(); //counte frequence with dict/hashmap/hashtable for(int i=0;i<nums.length;i++){ if(frequencyMap.get(nums[i])==null){ frequencyMap.put(nums[i],1); } else{ frequencyMap.put(nums[i],frequencyMap.get(nums[i])+1); } } //sort according to frequency by putting them in priority queue backed by reversed number order PriorityQueue<Map.Entry<Integer, Integer>> pq= new PriorityQueue<Map.Entry<Integer, Integer>>( new Comparator<Map.Entry<Integer, Integer>>(){ public int compare(Map.Entry<Integer, Integer> e1,Map.Entry<Integer, Integer> e2){ return e2.getValue()-e1.getValue(); } }); pq.addAll(frequencyMap.entrySet()); List<Integer> aList = new ArrayList<Integer>(); //retrieve top k numbers while(k>0&&!pq.isEmpty()){ k--; aList.add(pq.poll().getKey()); } return aList; } }

Understanding Finding loop entry in LinkedList

This is an ugly way to understand it, but it works for me.

Assuming there are K steps from start to entry of loop, assuming loop's length is O.

let p-slow steps 1 step each time, p-fast stenos 2 steps each time.

The first time they meet, let's say the meeting point is called M, distance between e and M is m. slower pointer has moved x circles starting from e, faster pointer has moved y circles starting form e, then we have

slower pointer moving distance = K+xO+m
faster pointer moving distance = K+yO+m

We know K+yO+m=2(K+xO+m)
so that K=(y-2x)O-m
that is equivalent to K=(y-2x-1)O+(O-m)
let's name O-m=m', which is distance from M to e.

K-m'=(y-2x-1)O
This means after m' steps, reset of K is certain number of circles.
We know after m' steps, slow pointer will do circles starting from e.

So if have another slow pointer starting from head, they must meet at e after moving K steps since after m' steps, the moves are number of circles.

Longest Substring without Repeating Characters

Evey time revisiting this problem, there will be slightly different solution coming up. not always more optimized, many times, new solution is worse than old ones. I need to remember the best solution to this one, not only because it is so elegant, but also because of the common use of character array, or hash table.

Here is an old version of solution, similar to the ones provided by leetcode, but thinking reversely, the moving cursor.

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 33 34 35 36 37 38

public class Solution {     public int lengthOfLongestSubstring(String s) {       if(s==null)return -1;     if(s.isEmpty())return 0;     //this set contains only one check's visiting condition     Set<Character> charSet = new HashSet<Character>();     int maxLen=0,h=0,t;String longestStr="";         //having two pointers, one for head adjustment, one for substring tail adjustment     //end of substring is marked by first repeated character     //for character being repeated, its left side positions won't construct longer string     //then current one, so it is safe to start from its next position. that  means, header     // can be moved to next position of character being repeated     while (h<s.length()){         //the inner loop will end when first repeat character is found         //that also marks end of substring currently being checked         //it start from header+number of characters between the repeated characters         t=h+charSet.size();         while(t<s.length() && !charSet.contains(s.charAt(t))){             charSet.add(s.charAt(t));             t++;         }                 maxLen = Math.max(maxLen, charSet.size());         if(t==s.length())break;         if (t-h+1>maxLen)longestStr=s.substring(h,t);         //advance h to character being repeated, removing characters from charSet at same time         //because new string start from right of character being repeated         while(h<s.length() && s.charAt(h)!=s.charAt(t)){             charSet.remove(s.charAt(h));             h++;         }         //move to new substring start position         h++;     }     return maxLen;     } }

This is the one by leetcode:

1  2  3  4  5  6  7  8  9 10 11 12 13

public int lengthOfLongestSubstring(String s) { boolean[] exist = new boolean[256]; int i = 0, maxLen = 0; for (int j = 0; j < s.length(); j++) { while (exist[s.charAt(j)]) { exist[s.charAt(i)] = false; i++; } exist[s.charAt(j)] = true; maxLen = Math.max(j - i + 1, maxLen); } return maxLen; }

And here is a better version with only one pass:

1  2  3  4  5  6  7  8  9 10 11 12 13 14

public int lengthOfLongestSubstring(String s) { int[] charMap = new int[256]; Arrays.fill(charMap, -1); int i = 0, maxLen = 0; for (int j = 0; j < s.length(); j++) { if (charMap[s.charAt(j)] >= i) { i = charMap[s.charAt(j)] + 1; } charMap[s.charAt(j)] = j; maxLen = Math.max(j - i + 1, maxLen); } return maxLen; }

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,
Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

Subscribe to see which companies asked this question
 

Method 1: slower scanning the lower bound and high bound. easy to understand, cleaner code.

 

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21

public boolean searchMatrix(int[][] matrix, int target) {         int x=0,y=matrix.length-1;         //binary search y         if(target<matrix[0][0])return false;         if(matrix.length==1&&matrix[0].length==1)             return target==matrix[0][0];                         while(x<matrix[0].length && y>=0){                         if(target>matrix[y][x]){                 x++;             }             else if(target<matrix[y][x]){                 y--;             }             else{                 return true;             }         }         return false;

 

Method 2: binary search on both x and y

to be continuued

Search 2D Array

Search a 2D Matrix Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.

Analysis:

 every dimension is sorted, and this is for searching. so binary search is natural selection. the difference is two binary search to locate y and then x coordination. Tricky part is y should be searched first, and on row should be selected if its first value is less than target.

Review binary search:

left, right, calculated middle, compare middle element with target, adjust left and right accordingly: if target>a[mid], then left=mid+1, if target <a[mid] then right=mid-1, otherwise, found it. In this solution, for y, if searching is missed, index should be right/bottom.

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 boolean searchMatrix(int[][] matrix, int target) { int xl,xr,yu,yd,mid; //binary search y yu=0;yd=matrix.length-1; if(target<matrix[0][0])return false; while(yu<=yd){ mid=(yu+yd)/2; if(target>matrix[mid][0]){ yu=mid+1; } else if(target<matrix[mid][0]){ yd=mid-1; } else{ return true;//matrix[mid][0]; } } yu=yd; //binary search x xl=0;xr=matrix[0].length-1; while(xl<=xr){ mid=(xl+xr)/2; if(target>matrix[yu][mid]){ xl=mid+1; }else if(target<matrix[yu][mid]){ xr=mid-1; }else return true; } return false; }

Longest Palidrolimic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. Method: palindrome string can had even number of character, which is balanced from virtual middle. it can also be odd number of characters, which is balanced from its real middle character. I want to check out the palindrome string at each position, so each position need to check both of above situations. below s generic solution without thinking of the 1000 and unique longest pelindrome substring.

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 33 34 35 36 37 38 39 40 41 42 43

public String longestPalindrome(String s) { if(s==null || s.length()==1)return s; if(s.length()==1||(s.length()==2&&s.charAt(0)==s.charAt(1)))return s; String maxPalindrome = null; int maxLen=0; ///no nneed to check first and last char for(int i=0;i<s.length();i++){ String p = palindromeLen(s,i); if(maxLen<p.length()){ maxLen=p.length(); maxPalindrome=p; } } return maxPalindrome; } String palindromeLen(String s, int i){ int left=i,right=i+1; String s1="",s2=""; while(left>=0&&right<s.length()){ if(s.charAt(left)==s.charAt(right)){ left--; right++; } else break; } if(left!=i) s1=s.substring(++left,right); left=i;right=i+2; while(left>=0&&right<s.length()){ if(s.charAt(left)==s.charAt(right)){ left--; right++; } else break; } if(left!=i) s2=s.substring(++left,right); return (s1.length()>s2.length()?s1:s2) ; }

Identical Binary Tree

Check if two binary trees are identical.

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

package BinaryTree; /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class IdenticalTree { /** * @param a, b, the root of binary trees. * @return true if they are identical, or false. */ public boolean isIdentical(TreeNode a, TreeNode b) { // Write your code here if (a == null && b == null) return true; if (a != null && b != null) { return a.val == b.val && isIdentical(a.left, b.left) && isIdentical(a.right, b.right); } return false; } }

Missing Number

giving N numbers in 0 .. N, find the one that is missing.

somebody is using binary search to find it.

it is actually can be n(n+1) -(sum of numbers). if they are equal, then 0 is missing, otherwise, the missing number is the value from formula.

Wiggle Sort

Given an unsorted array nums, reorder it in-place such that

nums[0] <= nums[1] >= nums[2] <= nums[3]....

Notice

Please complete the problem in-place.

Wow, first one finish in 5 minutes :)

1  2  3  4  5  6  7  8  9 10 11 12 13 14

public class Solution {     /**      * @param nums a list of integer      * @return void      */     public void wiggleSort(int[] nums) {         Arrays.sort(nums);         for(int i=1;i<nums.length-1;i+=2){             int tmp=nums[i];             nums[i]=nums[i+1];             nums[i+1]=tmp;         }     } }

Anagram

From cracking the coding interview.

What's the easiest way of checking if two words are anagrams?

We could count the occurrences of the distinct characters in each string and return true if they match. Or,
we could just sort the string. After all, two words which are anagrams will look the same
once they're sorted.

Free Linux Caches

Sometimes, when linux become sluggish, it might be related to inefficiency on cache management.

To check it on server run: free - m -t

and if free less than 20% - issue is here

to fix it

free && sync && echo 3 > /proc/sys/vm/drop_caches && free;

run command above