f*******t 发帖数: 7549 | 1 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... 阅读全帖 |
|
h*********3 发帖数: 111 | 2 多谢分享。
我觉得还是有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... 阅读全帖 |
|
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 ... 阅读全帖 |
|
s*******n 发帖数: 344 | 6 来自主题: JobHunting版 - 一道算法题 假设,3个数组分别是arr1 arr2 arr3
建一个priority queue,
顺序入队pair ---:arr1[i]作为key.
arr2 arr3以此类推.
然后pop出来。
是不是就可以了?请大牛点评赐教 |
|
M***6 发帖数: 895 | 7 1和2都是投出4个才打印出来是不是就可以了? 其他的摇到一个就打印一个。。
用一个arr1来保存各个数字投出几次才算投了1次。另一个array count来计数保存当前
各个数字已投出的个数。
比如 输入时 int p{1/3, 1/5, 1/5, 1/3, 1/5};
那么,int[] arr1 = {5, 3, 3, 5, 3}
int[] count = new int[arr1.length]
int num = rollDice();
count[num]++;
if(count[num] == arr1[num]){
count[num] = 0;
println(num);
}
或者自己实现一个概率函数决定当前摇出的数字要不要用。产生一个0到1之
间的随机数,如果它小与选中的概率就return true,否则就return false。 |
|
g*******y 发帖数: 1930 | 8 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 | 9 翻译成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 += (... 阅读全帖 |
|
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... 阅读全帖 |
|
a******e 发帖数: 124 | 13 以前写程序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... 阅读全帖 |
|
d*****0 发帖数: 72 | 14 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 | 15 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... 阅读全帖 |
|
s***k 发帖数: 23 | 16 【 以下文字转载自 Programming 讨论区,原文如下 】
发信人: stock (Microsoft is dead), 信区: Programming
标 题: Perl for programmers(2): Assignment of variables
发信站: The unknown SPACE (Tue May 23 14:59:26 2000) WWW-POST
$n=43;
$n1=4.3;
$n2=4.3e12;
$str="djfk";
$str1="n is $n.";
Note: Use single quote unless you want to interpret some
variables
$str2='n is 43.';
$n2=$n1*$n;
@arr=("1","2","3","4");
($n1,$n2,$n3,$n4)=@arr;
$arr[0]="1";
sort @arr; #output ("1","2","3","4");
$arr1="0","7";
sort @arr,@arr1; #output ("0","1"," |
|
d****e 发帖数: 251 | 17 正解。你是说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.
复杂的就是数组重叠部分,不过应该很快。 |
|
b******g 发帖数: 1721 | 18 大概的还不错。
A[] = {1};
B[] = {5, 6, 7, 8, 9};
m = 1
n = 5
用楼上的例子,你的算法要越界啊,是针对第一个数组arr1在第二次循环的时候。
|
|
D****6 发帖数: 278 | 19 首先每个array都是sorted是吧,arr1和2merge完之前没其他arr的事啊,完后生成新的
sorted arr在和3 merge. 还有为什么“ array 1里放的都是比array2小的”?你来个
简单的实际的例子。 |
|
c********p 发帖数: 1969 | 20 arr1 和 arr2 merge之后生成的是2个array 还是1个array,因为memory不够大不是么
。。。 |
|
c*******r 发帖数: 610 | 21 多谢分享。
第三题没看明白,是什么意思呢?
String[] sarr = getID(arr1[0]) --> sarr {A, B}, 这个方法的意思是给定数组元
素,提取该元素里面涉及到的element吗?那么两个元素是否相等需要自己提取吗? |
|
c*******r 发帖数: 610 | 22 多谢分享。
第三题没看明白,是什么意思呢?
String[] sarr = getID(arr1[0]) --> sarr {A, B}, 这个方法的意思是给定数组元
素,提取该元素里面涉及到的element吗?那么两个元素是否相等需要自己提取吗? |
|
j*********5 发帖数: 362 | 23 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 | 24 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|
w*********n 发帖数: 439 | 25 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|
w*********n 发帖数: 439 | 26 题目: 如果有一个二维数组 (包括两个以上一维数组 Arr1, Arr2, Arr3 ...), 把
里面每个一维数组的共同元素取出来放入一个新数组。 要求JAVA code只能用数组
Array,不能用List等容器。
我的思路是:
1. 先对的每个一维数组按大小排序(冒泡排序),确保二维数组里面的一维数组是按
元素个数从小到大排列的。
2. 对每个一维数组中的元素进行从小到大排序,用的是快速排序方法 (quickSort).
3. 把第一个数组和第二个数组比较(我写了compare方法)生成共同元素的新数组,
然后把这个新数组依次和后面的每个数组比较,每次都生成新数组;
最后得到所有数组的共同元素的新数组。
但是我测试我的JAVA code的时候,在compara方法里面有空指针异常。
哪位大侠能愿意在百忙之中帮我看下我的code?不胜感激。
愿意的留个email吧。有包子 |
|