新鲜亚麻 SDE OA 可能是新题

想问下intern oa的题库会换吗？

第二个 有人发过吧

第二题有人发过吧

1. # Given an array of binary digits, 0 and 1, sort the array so that all zeros are at one
   
2. # end and all ones are at the other. Which end does not matter. To sort the array,
   
3. # swap any two adjacent elements. Determine the minimum number of swaps to sort the array.
   
4. 
   
5. # Example
   
6. # arr = [0, 1, 0, 1]
   
7. # With 1 move, switching elements 1 and 2 yields [0, 0, 1, 1], a sorted array
   
8. def minMoves(arr):
   
9.     count1 = 0
   
10.     dis = 0
    
11.     for num in arr:
    
12.         if num ==1:
    
13.             count1+=1
    
14.         if num==0:
    
15.             dis+=count1
    
16.     count0 = len(arr) - count1
    
17.     rev_dis = count1 * count0 - dis
    
18.     return min(dis, rev_dis)

复制代码

SlayerEcho 发表于 2022-1-30 14:38
第二题有人发过吧

啊？
OA面经看少了。。。可能是分不够， 看的不够多

第一题有什么思路吗？

匿名者 发表于 2022-1-30 21:02
第一题有什么思路吗？

排序然后比较左右边界 O(n),就和lc 56差不多。

楼主还记得 merge 的条件吗，感觉缺了很重要的判定条件。

[1,2],[2,3],[3,5],[1,5]
如果是这个，答案是多少，我猜是 3？

请问binary sort这题rev_dis = count1 * count0 - dis这行是为什么呀？我知道它是考虑把1和0换一个方向需要的swaps，但是我不懂为啥count1和0要乘起来？请问谁能解释一下不？

第二題的解法可以參考這個：
https://www.geeksforgeeks.org/mi ... -sort-binary-array/

ng和在职的题库一样吗？我觉得楼主的题很难诶。。