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吧。有包子 |
|
