Cisco SDE OA 真题分享 + 思路（3题/90分钟）

题量：3 道编程题 · 时长：90 分钟

考点分布：矩阵操作（空间/时间优化）、字符串处理（palindrome 高频 + 字典序规则）、HashMap 应用（频率统计与抽象建模）。整体难度中等偏上，关键在于识别规律与写出高效解法。

1) Matrix Rotation Print

Question：给定 N×M 矩阵，顺时针旋转 90° 后按行打印。

优化：无需额外矩阵。顺时针 90° 后，结果第 r 行对应原矩阵第 r 列自底向上，按列倒序输出即可，时间 O(NM) / 额外空间 O(1)。

2) Longest Palindromic Substring（Tie → Lexicographically Smallest）

Question：返回最长回文子串；若长度并列，取字典序更小。

中心扩展：对每个中心做奇/偶两次扩展，更新答案时先比长度，再在长度相等时做字典序比较。O(N²)/O(1)。

动态规划：dp[i][j] 表示 s[i..j] 是否回文，倒序填表，遇到并列长度同样比较字典序。O(N²) 时间与空间。

3) Maximum Coordinates in One Flight

Question：给定若干坐标 (x,y)，你只能横向（同 y）或纵向（同 x）飞一次；问最多能经过多少个点。

建模：本质是最大同 x 或同 y 的数量。用两个 HashMap 统计：x_count[x]++、y_count[y]++；答案取两者最大值。复杂度 O(N)/O(N)。

稳拿 Offer 的秘诀

Cisco 的 OA 节奏快且题量足，若用 brute force 容易超时。我们可通过 无痕联机助攻 带你演练矩阵优化/回文/HashMap 统计等高频题；上场时提供实时思路提醒，避免陷入低效解法。