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