Marostica is the former chief commercial officer of ITA Software, which Google acquired for $700 million in 2011. One legacy of that transaction is that Google still powers flight-shopping on about a dozen airline websites, including Air Canada, Delta, American, United, Iberia, Latam, Turkish, China Southern, and China Eastern. Other Google flight-shopping partners include companies such as Northrop Grumman, Sabre’s GetThere corporate booking tool, and StudentUniverse.
public class Solution {
public int LargestRectangleArea(int[] height) {
var stack = new Stack<int>();
var index = 0;
var largestArea = 0;
int length = height.Length; // 6
while (index < length) // true; index = 1; index = 2;
{
// stack empty going upward
if (stack.Count == 0 || height[stack.Peek()] < height[index]) // index = 1, false;
{
stack.Push(index++); // 0, index = 1;
}
else
{
// going downward and then pop stack, calculate rectangle.
popStackAndCalculate(ref largestArea, stack, height, index);
}
}
while (stack.Count > 0)
{
popStackAndCalculate(ref largestArea, stack, height, length);
}
return largestArea;
}
/// <summary>
/// downward and then pop stack to calculate the rectangle
/// </summary>
/// <param name="largestArea"></param>
/// <param name="stack"></param>
/// <param name="height"></param>
private static void popStackAndCalculate(ref int largestArea, Stack<int> stack, int[] height, int rightIndex)
{
int length = height.Length; // 6
int lastHeight = height[stack.Pop()]; // 2
int width = stack.Count == 0 ? rightIndex : rightIndex - stack.Peek() - 1; // 1
largestArea = Math.Max(largestArea, lastHeight * width); // 2 * 1
}
}It was 2008: I had been working in tech for nearly 10 years, or in Facebook terms, since Mark Zuckerberg was 13 years old. I was an early Facebook user, an avid fan and excited about Facebook’s bold mission. When Sheryl Sandberg joined Facebook as Chief Operating Officer, I noticed. I knew that helping to build Facebook would be a once-in-a-lifetime experience. At the very least, I had to raise my hand at the chance.
I picked up the phone and called Sheryl. I had met Sheryl socially, but did not know her well. I was oddly surprised when I was able to reach her. I had no idea what Facebook needed. I only knew I wanted to do something that mattered. I figured I didn’t have much time, so I launched right in: “Sheryl, what is your biggest problem and can I help solve it?” We later laughed that I hadn’t even taken time to exchange pleasantries.
public class Solution {
public int[] SearchRange(int[] nums, int target) {
if(nums == null || nums.Length == 0)
return new int[]{-1,-1};
var start = applyBinarySearchLeftmost(nums, target);
var end = applyBinarySearchRightmost(nums, target);
return new int[]{start, end};
}
/// leftmost
/// rightmost
// [2, 2]
private int applyBinarySearchLeftmost(int[] nums, int target)
{
// apply binary search
var length = nums.Length;
var start = 0; // 1
var end = length - 1; //1
while(start <= end)
{
var middle = start + (end - start)/ 2; // 0
var middleValue = nums[middle]; // 2
var findTarget = middleValue == target;// 2
if(findTarget)
{
if(middle == start || (middle == 0 || nums[middle - 1] != middleValue))
{
return middle; // 0
}
else
{
end = middle - 1;
}
}
else if(target < middleValue)
{
end = middle - 1;
}
else
{
start = middle + 1;
}
}
return -1;
}
// [2, 2]
// [1, 2, 3]
private int applyBinarySearchRightmost(int[] nums, int target)
{
// apply binary search
var length = nums.Length;
var start = 0;
var end = length - 1;
while(start <= end) // 0, 0
{
var middle = start + (end - start)/ 2; // 0
var middleValue = nums[middle]; //0 - [1, 2, 3], 1 return [0, 1], should be [0,0], not start
var findTarget = middleValue == target; // true
if(findTarget)
{
if(middle == end || nums[middle + 1] != middleValue) // change middle == length - 1 to middle == end
{
return middle; // 0
}
else
{
start = middle + 1; // caught by [2,2], 2 - time limit exceeded, start = middle + 1, not start = middle - 1;
}
}
else if(target < middleValue)
{
end = middle - 1; // 0
}
else
{
start = middle + 1;
}
}
return -1;
}
}public class Solution {
public IList<TreeNode> DelNodes(TreeNode root, int[] to_delete) {
if(root == null)
return new List<TreeNode>();
var list = new List<TreeNode>();
var set = new HashSet<int>(to_delete);
TreeNode parent = null;
applyPreorderTraversal(root, list, parent, set);
return list;
}
private void applyPreorderTraversal(TreeNode root,IList<TreeNode> list, TreeNode parent, HashSet<int> set )
{
if(root == null)
return;
var current = root.val;
if(parent == null || set.Contains(parent.val))
{
if(!set.Contains(current))
{
list.Add(root);
}
}
applyPreorderTraversal( root.left, list, root , set );
applyPreorderTraversal( root.right, list, root, set );
// set null pointer
if(set.Contains(current))
{
root.left = null;
root.right = null;
}
if(root.left != null && set.Contains(root.left.val))
{
root.left = null;
}
if(root.right != null && set.Contains(root.right.val))
{
root.right = null;
}
}
}