SWE · CodeSignal OA

Capital One Target 比较:Greater、Smaller 或 Tie

OA 第一题按数组中严格大于/小于 target 的元素数作三态判断,等于 target 不参与两边计数。

题目重点:OA 第一题按数组中严格大于/小于 target 的元素数作三态判断,等于 target 不参与两边计数。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 输入为可比较的数值数组;与 target 相等的项不计入 greater/smaller。
  • 返回英文小写 `greater`/`smaller`/`tie`;空数组两边为零,返回 tie。
  • 数组中重复值按每个位置独立计数。

解题路线

  1. 分别初始化 greater=0、smaller=0,逐元素用严格 > 和 <;等于的直接跳过。
  2. 扫完比较两个计数并返回对应标签;只需要差值 delta 也可 +1/−1 累积,但双计数更便于解释。
  3. 验证所有值相等、空数组、重复元素、负数与两边计数相同。

手动走一遍

target=5、arr=[6,6,5,3] 时 greater=2、smaller=1,返回 greater;arr=[6,5,3] 两边各 1,返回 tie。

规模与取舍

n 个数字一次扫描 O(n) 时间、O(1) 空间。

易错点与追问

容易失分的边界

  • 把等于 target 的值计入任一侧。
  • 对 distinct 数值计数而不是按位置计数。
  • 用数组总长度减大于数量推小于数量,误把相等项算进去。

继续深挖

  • 数据流到来时如何 O(1) 更新三态?
  • 比较阈值改为一段区间如何统计?
✓已复制微信号!