[Hackerrank] Sherlock and Array

Posted on January 8, 2016 by admin

Problem

Watson gives Sherlock an array A of length N. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.
Formally, find an i, such that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.

Input Format
The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each test case contains Nspace-separated integers, denoting the array A.

Output Format
For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.

Constraints
1≤T≤10
1≤N≤105
1≤Ai ≤2×104
1≤i≤N

Sample Input

Sample Output

NO
YES

Explanation
For the first test case, no such index exists.
For the second test case, A[1]+A[2]=A[4], therefore index 3 satisfies the given conditions.

Analysis

First calculate the sum of all elements
Maintain curr as the cumulated sum in the left parts, when traversing the array

if (curr == sum – curr – arr[i]), then it means the sum in the left part and right part of arr[i] equals

Time:

O(n), as the array has been traversed twice

Space

O(1)

Code

[Hackerrank] Time Conversion

Posted on January 8, 2016 by admin

Problem

Given a time in AM/PM format, convert it to military (24-hour) time.

Note: Midnight is 12:00:00AM on a 12-hour clock and 00:00:00 on a 24-hour clock. Noon is 12:00:00PM on a 12-hour clock and 12:00:00 on a 24-hour clock.

Input Format

A time in 12-hour clock format (i.e.: hh:mm:ssAM or hh:mm:ssPM), where 01≤hh≤12.

Output Format

Convert and print the given time in 24-hour format, where 00≤hh≤23.

Sample Input

07:05:45PM

Sample Output

19:05:45

Explanation

7 PM is after noon, so you need to add 12 hours to it during conversion. 12 + 7 = 19. Minutes and seconds do not change in 12-24 hour time conversions, so the answer is 19:05:45.

Analysis

首先截取后两位字母，判断是AM还是PM
注意关于时间，只需要改hour

取hour
如果PM

若hour<12, 则加12，否则不变
如 12:xx:xxPM, should be 12:xx:xx
11:xx:xxPM should be 23:xx:xx

如果AM

若hour>12, 则转为0
否则不变

Code

[Group] Google Technical Infrastructure Resource Management

Posted on January 7, 2016 by admin

Functionality

Responsible for the efficient utilization for all the Google data centers through software, services, and business operations
Develop management software for all Google products (e.g., Google Cloud, Gmail, Youtube, Maps, Android, Search, Ads, etc) to manage their machine, compute, and storage needs.

Focus

Cloud resource distribution
Efficient management
Product catalog
Pricing automation
Demand planning
Fleet planning
Ordering
Cost allocation
Usage collection
Financial policy control
Data warehouse
Reporting

Questions

How can I contribute as an intern?

Questions about Borg

Scalability

How the nodes are added and removed?

How Borg handles with failure

In page 2, it said it will restarts the tasks if fail. Will this cause some errors, e.g., some operations are conducted more than once. Should user’s program handle the failure through roll-back by themselves?

Security

Will it be possible that there are some malicious jobs that try to interrupts other jobs, or breach the system?
Borg monitors the health of the jobs.

But it seems the health is in the response time etc.

Migration

Scheduling of tasks is very critical since there is not virtualization of physical machines

It seems job migration is not possible?

Over-selling

As users may over-purchase the resources, the Borg use over-selling approach

What if the over-selling cannot be satisfied. e.g., United Airline over-sell the tickets, will it cause trouble?
Or it seems the over-sell is only for low priority?
How to predict the future resource usage for the other Google groups, so that they can purchase the Quota as accurate as they can?

Users pay for what they use? or for what they reserved?

The idea of simulator of Borgmaster is cool

To decide whether a configuration changes will evict any important jobs

Fake-estimation in order to be scheduled earlier

Purposely stating less CPU needs in order to scheduled earlier

Will the user specify the running time of the job?

How will a false estimation that affects the schedule?

How Borg is different from Google Compute Engine

Can Borg be replaced by GCE

Questions Answered by Myself

Q: As all Google groups pay for the resource they use, is the price a fixed value, or does it has incentive to motivate people to make better utilization of the resources

For example, a more urgent request for the machine is more expensive. This can motivate people to make plan for their machine usage.
A: Yes. Jobs are of different priority, jobs with higher priority are more expensive.

[Leetcode] Remove Duplicates from Sorted List

Posted on January 6, 2016 by admin

Problem

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.

Analysis

Use pointer operation
If next element is repeated, then

curr.next = curr.next.next

Else

curr = curr.next

Code

[Leetcode] Remove Duplicates from Sorted Array

Posted on January 6, 2016 by admin

Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Analysis

Keep track of the right positive to write the valid number, it is also the length of the valid numbers
Keep track of current number

Write it to the array only when it is different from next number

Time: O(n)
Extra space: O(1)

Code

[Leetcode] Minimum Depth of Binary Tree

Posted on January 6, 2016 by admin

Problem

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Analysis

Recursive calculate the depth of the tree

1 + Math.min(left-tree, right-tree)

Need to deal with the case when left-tree or right-tree is null

If left-tree is null, return right-tree
If right-tree is null, return left-tree

Time: O(n)

As it traverses each node once

Code

[Leetcode] Happy Number

Posted on January 6, 2016 by admin

Problem

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Analysis

Since the computation is a recursive process, so that we can recursive check whether a number is a happy number
We need to maintain a hashset to track whether a number has shown up before

If yes, then it will not be possible to reach 1 in the future

Code

[Leetcode] Binary Tree Paths

Posted on January 6, 2016 by admin

Problem

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

["1->2->5", "1->3"]

Analysis

Recursive constructing the path in bottom up fashion
For each node, get its left and right paths recursively, denote them as left and right, then the recursion is

(node.val + (each path in left))
(node.val + (each path in right))

Time: O(N) where N is the number of nodes in the tree

Code

[Leetcode] 3Sum Cloest

Posted on January 3, 2016 by admin

Problem

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Analysis

Brute force approach

Enumerate the first, second, third number respectively
Update the distance compared with the target
Time: O(n^3)
Space: O(1)

Code

[Leetcode] Merge Sorted Array

Posted on January 1, 2016 by admin

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Analysis

题目是把两个sorted的数组合并成一个，这里假设数组1足够大，所以直接合并到数组1
记录当前要写入的index，初始值为 m+n-1
对两个数组从后往前扫描

谁比较大，谁就先写入
同时update index

Time: O(m+n)
Space: O(1)

Code

Reference
[1] https://leetcode.com/problems/merge-sorted-array/