Directi面试问题详细分享 _算法

我今天参加了Direct I校园招聘的编码第一轮。分享已提出的2个问题。
问题1(最佳子字符串反转)：
系统会为你提供字符串S。S的每个字符都是" a"或" b"。你希望精确地反转S的一个子字符串, 以使新字符串在字典上小于通过完全反转一个子字符串可获得的所有其他字符串。
例如, 给定" abab", 你可以选择反转从索引2(从0开始)的子字符串" ab"。这将为你提供字符串" abba"。但是, 如果你选择反向, 则从索引1开始的子字符串" ba"将得到" aabb"。无法获得较小的字符串, 因此反转[1, 2]范围内的子字符串是最佳选择。
输入如下：
第一行包含一个数字T, 即测试用例的数量。
每个测试用例都包含一个字符串S。该字符串的字符来自集合{a, b}。
输出如下：
对于每个测试用例, 请打印两个数字, 并用逗号分隔；例如" x, y"(不带引号, 也没有任何其他空格)。 " x, y"分别描述子字符串的开始索引(基于0的索引)和结束索引, 为了获得最小的字典字符串, 必须反转该索引。如果有多个可能的答案, 请用最小的" x"打印。如果仍然有多个答案, 请打印出最小的" y"。
限制条件：
1个？ 100
1个S的长度1000

Sample Input: 5 abab abba bbaa aaaa babaabbaSample Output: 1, 2 1, 3 0, 3 0, 0 0, 4

注意：
约束的设计使得O(N
3)每个测试用例的算法都不会通过。
问题2(数据库查询)：2分
你有一组N个对象。这些对象均具有与之关联的某些属性。属性由(键, 值)对表示。例如, 假定你具有以下两个对象。

Tower: { (height, 100), (weight, 50), (xposition, 25), (yposition, 36) }Tree: { (area, 100), (noofleaves, 500), (height, 25), (yposition, 36) }

你拥有的每个对象最多具有4个属性。一个对象将至少具有1个属性。请注意, 从上面的两个对象中, 不必将所有对象的属性键入都相同。同样, 密钥也不必不同。
现在, 给定N个这样的对象, 你希望回答M个查询。每个查询由一组属性表示(同样, 最多4个属性, 至少1个属性)。查询的答案是集合中具有所有给定属性的对象数。如果键和值匹配, 则认为两个属性相等。
例如, 如果你具有上述两个对象, 则以下查询的答案是
查询：
{(高度, 100), (位置, 36)}
回答：
1 //匹配塔, 但不匹配树
查询：
{(yposition, 36)}
回答：
2 //匹配塔和树
查询：
{(高度, 100), (无叶, 500)}
回答：
0 //塔和树都不满足这两个属性
输入如下：
输入的第一行包含N和M。其后是对N个对象的描述。第i个对象的描述将以数字k开头, k是与该对象关联的属性的数量。接下来的k行包含两个以空格分隔的字符串-属性键和属性值。请注意, 属性值不一定是整数(尽管上面的示例是这样)。
接下来是对M个查询的描述。查询的格式将与对象的格式完全相同。检查样本输入以进行澄清。
一个测试文件将仅包含一个测试用例。一个测试用例可能包含多个查询。
输出如下：
打印M行。每行必须是相应查询的答案。
限制条件：
1个N？ 10000
1个M？ 100000
【Directi面试问题详细分享】1个？ 4

Sample Input 2 3 4 height 100a weight 50b xposition 25a yposition 36b4 area 100a noofleaves 500 height 25 yposition 36b3 weight 80 xposition 25a yposition 36b1 yposition 36b2 xposition 25a yposition 36bSample Output: 0 2 1