Interesting mod problem

in Uncategorized | No Comments »

Found an interesting problem on hackerrank(https://www.hackerrank.com/challenges/sherlock-and-the-beast), the problem actually requires you to find an N digits largest “decent number” with:

1. 3, 5, or both as its digits. No other digit is allowed.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

One trivial approach is iterate from 1 to N/5 to find the smallest number of k that after subtracting the k*5 from n, the rest can be divisible by 3 ((n-k*5)%3==0), if not, then return -1.

This solution will take O(c) for one input, actually is O(2000) because the N is less than 100000. Unfortunately, when using Java, half of the test case will exceed the time limit (FML it works for C/C++).

Interestingly, I saw another approach on the discussion form that takes significantly less time than the previous, when an input divide by 3, there will be 3 cases:

case1: the remainder is 0, then we can simply output all 5.
case2: the remainder is 1, after subtracting 10, the output should be divisible by 3, or output -1
case3: the remainder is 2, after subtracting 5, the output should be divisible by 3, or output -1

the code:

Bit Manipulation on Leetcode

in Uncategorized | No Comments »

1. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Solution:

A sample one, at first glance, my code is like converting the unsigned int to binary and counting the number ones, as follow.

But sadly it did not pass the Leetcode’s OJ with a Wrong answer error when the input int is 2147483648 (10000000000000000000000000000000), well the range of int in Java is -2147483648 to 2147483647, apparently 2147483648 is out the range of signed int but still a 32bit unsigned int, but there is no unsigned int data type in Java, there must be some problems in Leetcode’s OJ.

We can still solve this problem by using bit rotate as follow:

Also there is a fancy way to do the bit rotation:

The running time of the following approaches should be O(C).

TO be continued

LeetCode Two Sum I and II

in Uncategorized | 2 Comments »

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution

The first and the simplest solution is apparently O(n^2) brute force method, which using two nested for loop to find if there is any pair of two numbers in the array added up to the target, which is not the solution we want.

If we could build up a hash table using the numbers in the array as the key and using index in the array as the value which only takes O(1) time to find the key(numbers) equal to target – numbers[i], so it will only take O(n) time to traverse all the array to find the other number which added up to the target.

First we put all the <key,value> in the hash table, then we traverse the arrays to find if there exists a key which is exactly target – numbers[i], then we return i+1 and the value of that key +1. (+1 because non-zero based.) The running time is O(2*n).

the running time in Leetcode is 332 ms.

There is a better version of this hash implementation (at least looks fancy), we can put the table building and checking target number in the same for loop,

The running time should be as same as the first one.

Actually we can perform a sorting to the array, then comes to the sorted version of this problem:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Solution 1:
Step 1. use two indices for the array, one is in the top(smallest number) the other in the tail(largest number):
Step 2. Check if two numbers of the indices are added up to the target, if the sum is larger than the target, then reduce the tail index, if the sum is smaller than the taget, increase the top index, repeat the step 2 until they sum up to the target, or top index equals to the tail, which means can not find.

This Solution should take O(n) time and O(1) space.

The running time in the Leetcode is 346 ms.

There is also another solution which will take O(n) time but O(n) space,

Step 1, Check if there is two copies of target/2 in the array, if yes, return these two indices.
Step 2, eliminate the same numbers in the array.
Step 3, subtract the target from every number in the array, take the abs value of the number but keep track which number is negative, name this array S’
Step 4, Put S’ and S in the same array with size of double, namely S2, sort S2, check if there is same two numbers in S2 and one of the number is come from S and is originally kept tracking as negative, then return these two indices.

The running time for Step 1, Step 2, Step 3 are all O(n), the step 4 is O(nlogn). So the running time is O(nlogn).

Actually we don’t need to create another array S’, the only thing we need to do is applying binary search over the sorted array finding if exists target-number[i], which is also O(nlogn)

The running time in Leetcode is 312 ms.

Differences between Hashmap and Hashtable in JAVA

in Uncategorized | No Comments »

When it comes to the detail implementation of hash in Java, I’m always confused with the hashmap and hashtable, which one should be used?

Below is a good solution comes from Stack overflow by Josh Brown (http://stackoverflow.com/questions/40471/differences-between-hashmap-and-hashtable)

There are several differences between HashMap and Hashtable in Java:

  1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.
  2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
  3. One of HashMap’s subclasses is LinkedHashMap, so in the event that you’d want predictable iteration order (which is insertion order by default), you could easily swap out the HashMap for a LinkedHashMap. This wouldn’t be as easy if you were using Hashtable.

Since synchronization is not an issue for you, I’d recommend HashMap. If synchronization becomes an issue, you may also look at ConcurrentHashMap.

墨西哥Merida 梅里达续签F1攻略整理

in Uncategorized | No Comments »

F1签证在6.5号过期,打算在过期前续签又不想回国,加拿大续签还需要办加拿大签证,而墨西哥对美签持有者免签,于是就选择在墨西哥续签。

注意如果F1签证已过期,无论I20是否还有效,美国这边航空公司是不予放行(去墨西哥)的,这种情况下只能开车去美墨边境城市续签,详情见攻略:http://www.utcssa.net/forum.php?mod=viewthread&tid=25273

如果F1签证还未过期,并且能保证返程时F1签证还有效(我就是买的4号的返程机票,5号签证过期),那就可以放心大胆的买机票约签证起来了。

 

我主要根据这个攻略(http://www.mitbbs.com/article_t/Visa/31419293.html)准备的行程以及面试,攻略说的非常清楚,但是还有几点可以补充。

 

1、 填写完DS160表格后,需要进墨西哥的美国签证预约网站填写信息、付签证费和约签证(https://usvisa-info.com/en-MX/selfservice/ss_country_welcome),在填写信息时,表格的最后一栏有点奇怪,问的是 “Is the applicant traveling from another country to apply for a visa in Mexico? *”, 这里要填yes,不然就默认你是墨西哥人,就不让你面试了(免面试),但是显然我们是需要面试的,而且面试也会加快签证办理的速度。

2、在上面那个网站填完信息,交完钱后,可以开始约录指纹的时间和面试的时间,如果约完后发现时间不对,是可以撤销重新约的;如果发现交完钱后,之前填写的信息有误,也可以直接取消整个申请,钱会自动当做账户余额退到你的账户里,然后可以再重新填写正确的信息,再用余额交钱。(别问我为什么会知道)

3、梅里达ASC和大使馆的位置:

Merida visa

 

黑线框里的那个星就是asc的位置,也就是拍照按指纹的地方;红线框里的那个星就是大使馆的位置,也就是面试的地方;而绿线框里有梅里达市中心里最好玩的景点(真的没别的景点了),市政厅和大教堂,按完指纹可以顺便去荡一圈。

如果你是坐大巴从坎昆来的梅里达,那巴士站就在红框下面的那个星这儿,可以把酒店订在附近,这样去ASC和大使馆都可以不用打车 直接走过去了。

ASC的具体地址:

CENTRO DE ATENCIÓN A SOLICITANTES

Por 67 y 69
Calle 66 561-D
Centro
97000 Mérida, Yuc., Mexico

大使馆的具体地址:

UNITED STATES OF AMERICA CONSULATE GENERAL

X 58 A Y 56 A
Calle 60 338 K
Alcala Martin
97050 Mérida, Yuc., Mexico
4、网上的攻略还提到了大使馆有locker可以存包,但是问题是如果你的包太大他还是不给你存的。。比如我的相机包(也就书包这么大)就被保安大叔拒绝了,还是花了50比索存到隔壁的旅馆的,所以去大使馆可以只带材料和小包。然后还有,在大使馆门前别拍照,会被保安勒令删除(也别问我为什么会知道的)。
5、我面试时什么问题也没被问,就看了下I20就approve了,过两天就可以拿护照,也祝大家签证好运~

Hello world!

in Uncategorized | No Comments »

终于又开始写博客了!终于又开始写博客了!终于又开始写博客了!

加这个又的原因是因为几天之前博客开张,写完第一篇博客后的第二天,服务器停电了。

然后重启之后因为各种奇怪的原因wamp跑不起来了,虽然最后经历千辛万苦恢复了,但总之数据是没有了。

然后我绞尽脑汁也想不出来当时写了啥,好像提到了https://sites.google.com/site/gaohengxiu/ 以及还提到了扣扣空间

 

F1签证续签水过,等下写个小攻略给博客开张骗点点击量(真的有用?)

坎昆是个好地方就是我来的不是时候啊别人都是冬天来过冬 可是现在是墨西哥最热的时候。。。

酒店装死ing

 

哦对,为了补完这个第一篇博客 还得传一张照片

DSC4609

 

总觉得服务器是因为这张照片才down的?

© 2016 Hengxiugao's Site - Powered by Wordpress / Theme: Tabinikki