Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. Solution: public class Solution { public int divide(int dividend, int divisor) { if(divisor==0 || (dividend==Integer.MIN_VALUE && divisor==-1)) return Integer.MAX_VALUE; int sign = (dividend<0)^(divisor<0) ? -1 : 1; long dvd = dividend<0 ? -(long)dividend : dividend; long dvs = divisor<0 ? -(long)divisor : divisor; int ans = 0; while(dvd>=dvs){ long mult = 1; long tmp = dvs; while(dvd>=(tmp<<1)){ tmp <<= 1; mult <<= 1; } dvd -= tmp; ans += mult; } return sign==-1 ?

Given an input string, reverse the string word by word. For example, Given s = “the sky is blue”, return “blue is sky the”. Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space. Solution: public class Solution { public String reverseWords(String s) { String ans = ""; for(int i=s.length()-1; i>=0; i--){ while(i>=0 && s.charAt(i)==' ') i--; if(i>=0){ int j=i; while(j>=0 && s.charAt(j)!=' ') j--; String word

Given an absolute path for a file (Unix-style), simplify it. For example, path = “/home/”, => “/home” path = “/a/./b/../../c/”, => “/c” click to show corner cases. Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo".

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: public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<>(); for(int n : nums){ Integer val = map.get(n); map.put(n, val==null ?

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array’s length. Solution: public class Solution { public int findKthLargest(int[] nums, int k) { int lo=0, hi=nums.length-1; int pos = -1; while(lo<=hi){

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]…. Example: (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6]. (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2]. Note: You may assume all input has valid answer. Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Solution: public class Solution { public void sortColors(int[] nums) { int start = 0; int end = nums.length-1; for(int

Sort a linked list using insertion sort. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummy=new ListNode(0), cur=head; while(cur!=null){ ListNode pre = dummy; while(pre.next!=null && pre.next.val<cur.val) pre=pre.next; ListNode tmp = pre.next; pre.next = cur; cur = cur.next; pre.next.next =

Sort a linked list in O(n log n) time using constant space complexity. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head==null || head.next==null) return head; ListNode dummy=new ListNode(0), fast=dummy, slow=dummy; dummy.next=head; while(fast!=null && fast.next!=null){ fast = fast.next.next; slow =

Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. Solution: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(0); dummy.next =