DRW ng OA

刚做完drw sed ng OA, 一共200分钟共3道题，时间非常充裕，三道题都是medium难度，总体来说不难，不过test case 很少，无法确定能不能cover所有hidden test很难受。忘了拍照QAQ，下面口述所有题目。求大米，好久没登陆大米掉光了都


1. AND is a standard bitwise operation,  write a java function that given an a arrary A consisting of N integers, return the size of the largest possible subset of A such that AND of all its element is greater than 0; for

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

e digits, for example, N = 1765, you should return 1767 since 1766 has two identical consecutive digits, and 1767 is the smalleast one withnot (这道题对时间要求很高，普通的暴力解例遍所有char会time limit)

第二题是DP没得说

第三题的话
我的思路先从前往后历遍，找到最高的重复位，有重复的情况下直接替换全部后面0，１循环交替。并且追加标记。无标记则+1直到末2位非重复，复杂度是LENGTH +。
999999的情况下最高重复位99　0000，变成100　0000，重复所以继续变成101　0000不重复完事，后面就是　0101最终1010101
11223344的话最高重复位11，然后12000000，12010101

不过如果是89898989这类的话倒是很难处理，89898989》89898990》89899000》89900000》90000000

请问uu们第三题有什么优化思路吗？

第一题全子集历遍复杂度是N^2, 用二进制的话应该是32N或者64N，就是先转换为二进制STRING，然后每个char位置相加，取最高值就行。如果数组最大长度小于32的话那全历遍是比较快

二三题米不够看不到

Missings 发表于 2023-7-31 03:32
第一题全子集历遍复杂度是N^2, 用二进制的话应该是32N或者64N，就是先转换为二进制STRING，然后每个char位 ...

2. Ask how to merge (merge one element at most once) the elements in an array with the largest sum.
For example [1,2,3] the maximum merge sum is to merge 2 and 3 together, 1 + 23 = 24, note that after 2 and 3 are merged, 1 cannot be merged with 23. (普通dp)
3. function that given an integer N, return the smallest integer greater than N t‍‌‍‌‍‌‌‌‍‌‍‍‌‌‍‌‍‌‌‌hat does not contain two identical consecutive digits, for example, N = 1765, you should return 1767 since 1766 has two identical consecutive digits, and 1767 is the smalleast one withnot (这道题对时间要求很高，普通的暴力解例遍所有char会time limit)

Missings 发表于 2023-7-31 01:32
第一题全子集历遍复杂度是N^2, 用二进制的话应该是32N或者64N，就是先转换为二进制STRING，然后每个char位 ...

大佬能再举一个例子吗没有听懂谢谢

匿名用户 发表于 2023-8-2 11:15
大佬能再举一个例子吗没有听懂谢谢

A = [13, 7, 3, 8]
用4位的话就是你的结果
1101
0111
0011
0100
然后结果就是
1323
最大是3所以最大子集是3

然后由于不确定是32位还是64位，按照32位系统的话就是
0000 0000 0000 0000 0000 0000 0000 1101
0000 0000 0000 0000 0000 0000 0000 0111
0000 0000 0000 0000 0000 0000 0000 0011
0000 0000 0000 0000 0000 0000 0000 0100
结果
0000 0000 0000 0000 0000 0000 0000 1323
最大值为3
只要计算每个位之和就取最大值就行，所以根据系统位数32或者64，复杂度为32N或者64N

这道题没难度只是靠你对AND指令的理解而已

Missings 发表于 2023-8-2 15:59
A = [13, 7, 3, 8]
用4位的话就是你的结果
1101

明白了感谢

T3 数位dp求出小于等于n有多少个符合条件的数字记为cal(n)，然后二分找到最小的一个满足cal(x) = cal(n) + 1的数字感觉可以，复杂度O(loglogn)

请问收到oa后要多少天内做完呀？