30 Dec 2015
###Task1
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
histogram
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
histogram
The largest rectangle is shown in the shaded area, which has area = 10 unit.
Have you met this question in a real interview? Yes
Example
Given height = [2,1,5,6,2,3],
return 10.
###java
public class Solution {
/**
* @param height: A list of integer
* @return: The area of largest rectangle in the histogram
*/
public int largestRectangleArea(int[] height) {
// write your code here
if (height == null || height.length == 0) {
return 0;
}
int N = height.length;
int max = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i <= N; i++) {
int cur = i == N ? -1 : height[i];
while (!stack.isEmpty() && cur < height[stack.peek()]) {
int h = height[stack.pop()];
int w = stack.isEmpty() ? i : (i - stack.peek() - 1);
max = Math.max(max, h * w);
}
stack.push(i);
}
return max;
}
}
###Points
- Tricky way to use stack.
- Maintain an increasing height in the stack, once get a height less than the top of stack, keep poping(computing area at same time) until the increasing order remains.
###Task2
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
###Python
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height) == 0:
return 0
left = [0 for i in range(len(height))]
right = [0 for i in range(len(height))]
left[0] = height[0]
right[-1] = height[-1]
for i in range(1, len(height)):
left[i] = max(left[i - 1], height[i])
right[-1 - i] = max(right[-i], height[-1 - i])
ret = 0
for i in range(len(left)):
ret += min(left[i], right[i]) - height[i]
return ret
###Points
- Two iteration from both side: find the min height from both side;
- current point water = min(left[i], right[i]) - height[i]
###Task3
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
###java
public class Solution {
public int maxArea(int[] height) {
int length = height.length;
if (length < 2) {
return 0;
}
int left = 0;
int right = length -1;
int max = 0;
while (left < right) {
max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
###Points
30 Dec 2015
###Task1
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
return 10.
###java
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] num) {
// write you code here
if (num == null || num.length == 0) {
return 0;
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i: num) {
map.put(i, 0);
}
int max = 0;
for (int i: num) {
if (map.get(i) == 1) {
continue;
}
int cur = i;
int len = 1;
while (map.containsKey(--cur)) {
len++;
map.put(cur, 1);
}
cur = i;
while (map.containsKey(++cur)) {
len++;
map.put(cur, 1);
}
max = Math.max(max, len);
}
return max;
}
}
###Points
- No magical part, need to check one by one. But we have to eliminate duplicated checkings by the use of HashMap: 0 value stands for “have this value and available”, 1 value stands for “have this value but not available”
25 Dec 2015
###Task1
Given a list, rotate the list to the right by k places, where k is non-negative.
Have you met this question in a real interview? Yes
Example
Given 1->2->3->4->5 and k = 2, return 4->5->1->2->3.
###java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: the List
* @param k: rotate to the right k places
* @return: the list after rotation
*/
public ListNode rotateRight(ListNode head, int k) {
// write your code here
if (head == null || head.next == null) {
return head;
}
int len = 0;
ListNode itr = head;
while (itr != null) {
itr = itr.next;
len++;
}
k = k % len;
ListNode pre = findKth(head, len - k - 1);
ListNode newHead = pre.next;
pre.next = null;
itr = newHead;
while (itr.next != null) {
itr = itr.next;
}
itr.next = head;
return newHead;
}
public ListNode findKth(ListNode head, int k) {
while (k > 0) {
head = head.next;
k--;
}
return head;
}
}
###Points
- find length –> modulo
- find kth then disconnect
25 Dec 2015
###Task1
Given a linked list, remove the nth node from the end of list and return its head.
Have you met this question in a real interview? Yes
Example
Given linked list: 1->2->3->4->5->null, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note
The minimum number of nodes in list is n.
Challenge
O(n) time
###java
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: The head of linked list.
*/
ListNode removeNthFromEnd(ListNode head, int n) {
// write your code here
if (head == null || n < 1) {
return null;
}
ListNode fast = head.next;
while (n > 0 && fast != null) {
fast = fast.next;
n--;
}
if (fast == null) {
return head.next;
}
ListNode itr = head;
while (fast != null) {
itr = itr.next;
fast = fast.next;
}
itr.next = itr.next.next;
return head;
}
}
###Points
- The case when to delete the first node: fast will be null!
25 Dec 2015
###Task1
Given a linked list, swap every two adjacent nodes and return its head.
Have you met this question in a real interview? Yes
Example
Given 1->2->3->4, you should return the list as 2->1->4->3.
Challenge
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
###java
####Iterative
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @param head a ListNode
* @return a ListNode
*/
public ListNode swapPairs(ListNode head) {
// Write your code here
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null && head.next.next != null) {
ListNode n1 = head.next;
ListNode n2 = head.next.next;
head.next = n2;
n1.next = n2.next;
n2.next = n1;
head = n1;
}
return dummy.next;
}
}
Recursive
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @param head a ListNode
* @return a ListNode
*/
public ListNode swapPairs(ListNode head) {
// Write your code here
if (head == null || head.next == null) {
return head;
}
ListNode n1 = head;
ListNode n2 = head.next;
n1.next = swapPairs(n2.next);
n2.next = n1;
return n2;
}
}
###Points
- head = n1; move head to n1 instead of n2 !!!!