h*********3 发帖数: 111 | 1 多谢分享。
我觉得还是有2个问题:
1)一个corner case: a[]={1} b[]={2}, 找第一个最小的,你的j会变成-1,溢出了
2) (i == upper-1) 只判断 Math.min(a[upper], b[j]);
是不够的, 一个例子
a[] = {1,2,3} b[]={4,5,6}, 找第4个最小的,你的程序似乎是返回 5 .
写了一个c的,欢迎指正。
int m_FindKthFromTwoSortedArray(int arr1[],int len1,int arr2[],int len2,int k)
{
int m1,m2;
int l1=max(0,k-len2-1),r1=min(len1-1,k-1);
if ( k == 1 )
return min(arr1[0],arr2[0]);
m1 = l1 + (r1-l1)/2;
m2 = k-(m1+1)-1;
while ( arr1[m1] != arr2[m2] && m1 <= min(len1-1,k-1) && m1 >= max(0,k-len2-1))
{
i... 阅读全帖 |
|
f*******t 发帖数: 7549 | 2 lgk查找递归方法不长的,我顺便发个收藏的代码吧。记不得作者是谁……
int findKthFrom2SortedArraysIterative(int *arr1, int *arr2, int k){
int result;
int mid;
int curPosOfArr1 = 0, curPosOfArr2 = 0;
while(k > 1){
mid = k/2;
if(arr1[curPosOfArr1 + mid - 1] < arr2[curPosOfArr2 + mid - 1]){
curPosOfArr1 = curPosOfArr1 + mid;
}else{
curPosOfArr2 = curPosOfArr2 + mid;
}
k = k - mid;
}
if(arr1[curPosOfArr1] > arr2[curPosOfAr... 阅读全帖 |
|
s**********e 发帖数: 326 | 3 第三题:
int findKth(int *arr1, int *arr2, int k, int arr1Index, int arr2Index){
if(k == 0){
if(arr1[arr1Index] <= arr2[arr2Index])
return arr1[arr1Index];
else
return arr2[arr2Index];
}
int mid = (k + 1)/2;
if(arr1[arr1Index + mid - 1] <= arr2[arr2Index + mid - 1])
findKth(arr1, arr2, k - mid, arr1Index + mid, arr2Index);
else
findKth(arr1, arr2, k - mid, arr1Index, arr2Index + mid);
}
main调用时arr1Index,arr2Index传入值都是0,assum... 阅读全帖 |
|
Z*****Z 发帖数: 723 | 4 public static void main(String[] args) {
System.out.println(getCommon("1234", "3451"));
System.out.println(getCommon("12", "123"));
System.out.println(getCommon("123", "12"));
System.out.println(getCommon("12", "12"));
}
static String getCommon(String s1, String s2) {
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
int[] failure = buildFailureTable(arr2);
int i = -1, j = -1;
if(arr2.length < arr1.leng... 阅读全帖 |
|
p*****2 发帖数: 21240 | 5 好久没写了。刚才写了一个练练。大牛给指点一下。
class Version implements Comparable
{
private String version;
private String[] getNumbers(String ver)
{
return ver.split("\\.");
}
public Version(String _version)
{
version=_version;
}
public String getVersion()
{
return version;
}
public int compareTo(Version v)
{
String[] arr1=getNumbers(version);
String[] arr2=getNumbers(v.getVersion());
int ... 阅读全帖 |
|
g*******y 发帖数: 1930 | 6 seems like:
you have K arrays of integers:
example: K=3
arr1: 1, 3, 4, 7, 14
arr2: 2, 5, 8, 15...
arr3: 3, 12, 13, 19 ...
arrK[i] is the position of ith ocurrence of the k-th word in the doc.
question: find min{distance(i,j,k)}
where:
distance(i,j,k) = max{|arr1[i]-arr2[j]|,|arr1[i]-arr3[k]|,|arr2[j]-arr3[k]|}
This is very easy and can be done in one scan of K arrays. Complexity is O(K*N)
Hint: just try plot some dots on the two/three number axis to represent two/three arrays, and keep in mind t |
|
Q*******e 发帖数: 939 | 7 翻译成C.
void
addBinary(char *arr1, char *arr2)
{
int i,j;
int len1 = 0, len2 = 0, len3;
char tmp, carry=0;
char *arrR;
char *arrT1 = arr1;
char *arrT2 = arr2;
while (*arrT1++) len1++;
while (*arrT2++) len2++;
len3 = (len1 > len2) ? len1 : len2;
arrR = (char*) malloc(len3 + 2);
len1--; len2--;
len3 = 0;
while ((len1>=0) || (len2>=0) || carry) {
tmp = carry;
if (len1 >= 0) tmp += (arr1[len1--] - '0');
if (len2 >= 0) tmp += (... 阅读全帖 |
|
s*******n 发帖数: 344 | 8 来自主题: JobHunting版 - 一道算法题 假设,3个数组分别是arr1 arr2 arr3
建一个priority queue,
顺序入队pair ---:arr1[i]作为key.
arr2 arr3以此类推.
然后pop出来。
是不是就可以了?请大牛点评赐教 |
|
a******e 发帖数: 124 | 9 以前写程序test时候只是在main函数里简单输出一下看看对不对,最近想学一下unit
test,这个有什么格式要求吗(我看有些人用assert())?比如用c++语言想写一个
binary search的unit test该如何写,谢谢!
试着写了一个,不知道这样算不算unit test
#include
using namespace std;
int BinarySearch(int arr[], int size, int target){
int high=size-1;
int low=0;
int mid;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==target){
return mid;
}
else if(arr[mid]>target){
high=mid-1;
}
else{
low... 阅读全帖 |
|
x****1 发帖数: 118 | 10 Linkedin
phone1:烙印
lowest common ancestor w/ and w/o parent pointer
phone2:国人
search in rotated sorted array
onsite:
1.两个国人
implement addInterval(start, end) and getcoverage(),
2.两个国人
talk projects and some behavior question
3.烙印
lunch, talk about technologies interest
4.亚裔,不确定是否国人
Manager, talked a lot of behavior questions, interest and projects
5.烙印
Design: tinyurl
6.烙印+小白
1.exclusive array, give an arr1, return a new arr2, arr2[i] is the
multiplication of all elements in arr1 except arr1[i]
... 阅读全帖 |
|
f******h 发帖数: 45 | 11 也找工作了一段时间了,从版上学了很多,上周G家面完了,求个bless。
之前的一些都挂了,还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦!!
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
b*****i 发帖数: 76 | 12 首先说明,我是做用户界面的,不是什么大数据,云计算,操作系统方向的牛人。考我
的题大家应该不太可能遇到,但希望这个过程对大家有所帮助。
顺便问下,B的senior developer的工资base一般在什么范围呢?除了医保和401k还有
其他福利吗?
这个职位是recruiter联系的我,当时对老东家有(xiang1)点(dang1)不满,就答应申请
了。Recruiter一共列了前端相关的4个职位,我选了其中两个,都拿到了第一轮技术面
和onsite,但是只onsite了一个。
第一轮就是先简单介绍一下自己,然后就上hackerrank做题,我CS本科毕业六七年了,
C,Java,C++全忘干净了,工作中主要就是JavaScript,略带自娱自乐的学了一点
python,于是厚着脸皮一路拿JS解题。都是最基本的算法和数据结构,包含一些常见的
前端问题。然后轮到我问问题,我问他这个position具体干嘛,他表示不知道因为他不
在这个组干,我有点无语,就说好吧我没问题了 thank you and have a nice day。
技术面过了以后就拿到onsite了,先是两个local... 阅读全帖 |
|
d****e 发帖数: 251 | 13 正解。你是说padding? 譬如n < m, 直接将数组一扩充到和数组二一样?
或者每次甩min(n/2, m/2), where n, m are remaining array length.
同时可快速解决一些特例:
if median1 == median2:
return median1
else if median1 < median2:
if arr1[-1] < arr2[0]:
very simple math here.
复杂的就是数组重叠部分,不过应该很快。 |
|
g**********y 发帖数: 14569 | 14 谢谢指出错误,我写边界条件总容易出错,还是考虑不周密。
arr2[],int len2,int k) |
|
s*****y 发帖数: 897 | 15 How about this one?
int Find_KthElement(int A[], int m, int B[], int n, int k)
{
if (k > m+n)
return 0;
if (m > n) {
return Find_KthElement(B,n,A,m,k);
}
int lo = 0;
int hi = min(m,k)-1;
while (lo < hi) {
int mid = lo + (hi-lo)/ 2;
int bIndex = k - mid - 2;
if (A[mid] < B[bIndex]) {
lo = mid +1;
} else {
hi = mid;
}
}
... 阅读全帖 |
|
o********8 发帖数: 821 | 16 由于已经答应了其他家offer,本来想跟Google搞好关系,方便以后申请,没有cancel掉约好的电面,
结果来了俩不寻常的电面。。。
第一个,迟到了10分钟打来,一上来让我介绍下自己的project,他不是跟我做一个方
向的,但还非要问详细的东西,跟他解释的费劲啊。。。20分钟过去了
接着说考考编程的东西吧,我以为开始不如常规算法题了,结果。。。。
1. Java 和 C/c++ error handling的区别是啥 (一开始听成了array handling,
blabla了一通发现不对。。。),然后讲了exception等等的。
2. 举例说几个Java常见的Exception,一个具体的名字没想起来。。。
3. 如果要实现JVM的话,怎么在JVM层实现throw,catch exception。怎么返回,返回
的error flag存在哪等等等等很底层的东西。。。纯猜着给了答案
55分钟了,终于来了个编程题,
4. 给三个数组,怎么穷举所有的组合。。。比如array1={a,b}, arr2={3,4,5}, arr3=
{true, false}. 不相信这么简单,确定了... 阅读全帖 |
|
c********p 发帖数: 1969 | 17 arr1 和 arr2 merge之后生成的是2个array 还是1个array,因为memory不够大不是么
。。。 |
|
d*****0 发帖数: 72 | 18 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1():能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数,包括0、负整数、正整数
,注意edge case
2. given 一个字符串,这个字符串是一个算式,包含加减乘除,没有括号,符号和数
字之间以一个空格格开,比如:“1 + 2 * 4 / 5”,return算式的结果
3. given两个字符串,分别表示两个元素等和不等,比如:
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾,这个例子就有矛盾:A!=C
given提取元素的method: getID(..),这个不用自己写:String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
d*****0 发帖数: 72 | 19 May 23面的
一共三轮
就第一轮简单问了一下resume的intern
其他的每轮就只有一个算法题
1. 给定rand1():能够产生random数字0,1
用rand1()实现:
rand3()--> 0, 1, 2, 3
rand4()--> 0, 1, 2, 3, 4
randN(int n)--> 0, 1, ..., N n可以是任意整数,包括0、负整数、正整数
,注意edge case
2. given 一个字符串,这个字符串是一个算式,包含加减乘除,没有括号,符号和数
字之间以一个空格格开,比如:“1 + 2 * 4 / 5”,return算式的结果
3. given两个字符串,分别表示两个元素等和不等,比如:
arr1 = {“A=B”, "B=C", ...}
arr2 = {"A!=C", "F!=R", ...}
判断是否有矛盾,这个例子就有矛盾:A!=C
given提取元素的method: getID(..),这个不用自己写:String[] sarr = getID(arr1
[0]) --> sarr {A, B... 阅读全帖 |
|
j*********5 发帖数: 362 | 20 Hiring Manager面的,没说几句话就写code。
题不难,大概就是leetcode的变体,但也不是10行15行能解决的,相当于Medium难度吧。
主要是感觉interviewer比较傲慢,不断打断我的思路和想法,不允许任何脱离他的思
路的想法。
一开始我就分析,应该这样这样,还有那些情况,他就打断我说赶紧写code,写code中
处理最好;
结果我一开始有些expectation都没有弄清楚就开始写了;
没写几行,他就开始抓细节,比如数组长度我习惯一般弄个int len = array.length这
种,后面loop用着方便,他非要说没必要不够简洁,就帮我删了;我loop习惯用i,j,
他说要改成有意义的比如arr1,arr2等;
我自己问题也不少,下午才电面,因为上午偷偷刷题刷得很累,注意力不集中(看来电
面最好在早上,注意力最好时),就有点慌了。
还有故意误导我,比如我刚写个while写完他就说有infinite loop,看了半天浪费了好
几分钟,才发现没有。
我刚写另外一行他就说你某行某行好像有问题,你去看看先。
结果大概折腾了半个小时,我就完全脑子空白了。
我提... 阅读全帖 |
|
w*********n 发帖数: 439 | 21 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|
w*********n 发帖数: 439 | 22 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|
w*********n 发帖数: 439 | 23 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|