OA2 host crowding/pagination(OA2和OA21一起准备)
点击展开
You’re given an array of CSV strings representing search results. Results are sorted by a score initially. A given host may have several listings that show up in these results. Suppose we want to show 5 results per page, but we don’t want the same host to dominate the results. Write a function that will reorder the list so that a host shows up at most once on a page if possible, but otherwise preserves the ordering.
Your program should return the new array and print out the results in blocks representing the pages.
Input: An array of csv strings, with sort score number of results per page. example:
“host_id,listing_id,score,city”
“1,28,300.1,San Francisco”
典型OA2
display list page
OA4 simulating diplomacy/军队
点击展开
题也确实不难，只要弄明白逻辑然后写几个循环就可以了，之前准备的时候自己一直想复杂了，觉得如果a支持b，b支持c，那么当b胜出以后还可以继续支持c，但是事实上不需要考虑这个，只要被攻击就不会支持别的军队了
补充一下输入输出的形式吧，其他的小伙伴们已经说的很详细了，输入输出都是list形式的
我是直接用的TreeMap，就自动排序了
public static void Battle(String[] input) {
ArrayList<String> res = new ArrayList<>();
// deal with support
HashMap<String, List<String>> posMap = new HashMap<>(); // position--army
HashMap<String, String> resMap = new HashMap<>(); // army--res
HashMap<String, Integer> strengthMap = new HashMap<>();// army--strength
for (String line : input) {
String[] parse = line.split(" ");
// initialize the strength map
String army = parse[0];
strengthMap.put(army, 1);
// initialize the position map
String pos = "";
if (parse[2].equals("Hold") || parse[2].equals("Support")) {
pos = parse[1];
}
if (parse[2].equals("Move")) {
pos = parse[3];
}
if (!posMap.containsKey(pos)) {
posMap.put(pos, new ArrayList<String>());
}
posMap.get(pos).add(army);
}
// update strength map through support
for (String line : input) {
String[] parse = line.split(" ");
if (parse[2].equals("Support")) {
String supportPos = parse[1];
String supportTo = parse[3];
if (posMap.get(supportPos).size() == 1) { // No other attack for support
strengthMap.put(supportTo, strengthMap.get(supportTo) + 1);
}
}
}
// attack compute
for (String pos : posMap.keySet()) {
List<String> armyList = posMap.get(pos);
if (armyList.size() == 1) {
resMap.put(armyList.get(0), pos);
} else {
int maxStrength = 0;
String win = "";
for (String army : armyList) {
int curStrength = strengthMap.get(army);
if (curStrength > maxStrength) {
if (win.length() > 0) {
resMap.put(win, "[dead]");
}
maxStrength = curStrength;
win = army;
resMap.put(army, pos);
} else if (curStrength == maxStrength) {
resMap.put(army, "[dead]");
resMap.put(win, "[dead]");
} else if (curStrength < maxStrength) {
resMap.put(army, "[dead]");
}
}
}
}
for (String armyItem : resMap.keySet()) {
System.out.println(armyItem + " " + resMap.get(armyItem));
}
}
public static void test() {
HashMap<String, Integer> map = new HashMap<>();
HashMap<String, String> res = new HashMap<>();
map.put("A", 2);
map.put("B", 3);
map.put("C", 1);
int maxStrength = 0;
String win = "";
for (String item : map.keySet()) {
int curStrength = map.get(item);
if (curStrength > maxStrength) {
if (win.length() > 0) {
res.put(win, "[dead]");
}
win = item;
maxStrength = curStrength;
res.put(win, "Win");
} else if (curStrength == maxStrength) {
res.put(win, "[dead]");
res.put(item, "[dead]");
} else if (curStrength < maxStrength) {
res.put(item, "[dead]");
}
}
for (String armyItem : map.keySet()) {
System.out.println(armyItem + " " + res.get(armyItem));
}
}
public static void main(String[] args) {
String[] input = new String[] { "A Mu Hold", "B Bohemia Move Mu", "C Pru Move Mu", "D war Hold" };
String[] input2 = new String[] { "A Mu Hold", "B Bo Move Mu", "C Wa Support B" };
String[] input3 = new String[] { "D XX Hold", "B Bo Move Mu", "C DF Support B", "M Wa Support B",
"G FC Move Mu", "F dd Support G" };
Battle(input3);
}
OA6 Hogwarts meetup
点击展开
就是一群巫师，每个人都有rank和可以refer 你去认识的别的巫师的ids，你现在是一个rank 0 的巫师，问你如何通过最小的cost去认识级别最高的巫师
cost的定义是：假设你通过wizard i去认识wizard k，那么cost就是 k-i 的平方。
可以用狄杰斯特拉算法做，简化版因为不需要更新节点的最小值，所有的case都可以过。
ps：题目一开始给你一堆raw input，看起来要scanner readline，但是翻到题目后发现不需要自己prase raw input，input都是给 好的 list of string，大家不用担心parse input的问题。
有可能图是有环的，但是不影响，加个visited set判断一下就好
oa过了，下一步是打个15分钟的电话说一下这次oa的思路，过一遍代码. followup了十五分钟，就是过一遍思路，非常水，说是要给onsite
input是parsed好的String array 还是 raw input (需要自己处理)?
raw input, I used split() in java. 是String, just iterate through it, then split
需要注意的是：
并不是10个巫师啊， 为什么大家都说是10个巫师，数量是变的呀，虽然没什么影响，但这描述不准确呀！！！
还有就是这个题不是让你输出最短的路径的长度，而是返回最短的路径，要把路径打印出来，要比单纯的算长度多一点工作量
还有就是从0个到第0个的邻居的距离是为0的，之后的路径才是差的平方
题上说了，是个有向图
我用了迪杰斯特拉的方法做的，test case都过了。做之前按面经的描述自己先做了一遍，结果发现实际的题和地 里讨论的样子还是有点出入，不过影响不大，主要就是要加上打印路径的这一步。。。
再补充一条：函数的输入是List, string 的形式是“1 3 5”这种，所以需要先做个处理转化成int，自己做的时候还以为是List<List>…
OA8 Minimum Window Substring
LC 76 Minimum Window Substring
OA12 rounding prices
点击展开
HackerRank的code challenge 12, 题没变。但是给的代码似乎不靠谱。。。而且函数接口也不对
public static List getNearlyArrayWithSameSum(List arr, int target) {// 思路：// 把所有price先取floor, 算出
target - floorSum 得到一个差值diff// 考虑如何把这个diff分配到arr，使整体差值最小// 对diffWithCeil排个序，diff应该分配给diff个最小值// 题目要求按arr的元素顺序输出rounded int，所以一开始要记录index// 输入输出都是用的List，所以遍历起来有一些不同，没有数组顺手。。。}关于这道题，stackoverflow上有很详尽的讨论，似乎没有更好的解法了。反证一下应该是对的。
algorithm - How to round floats to integers while preserving their sum? - Stack Overflow
看地里OA的testcase通过没通过的都被拒了，所以就佛系了。不过OA还是要好好做，尤其new grad简 历没太大差别的，不然它看啥呢。所以注释写清楚点儿，List reconstruct用最高效的方式（这一步我还没想到很好的方法，要么就开个arr，要么就再排一遍序）,以及先在IDE里跑一遍，我当时直接就run了，3次编译不通过，感觉是凉了，邮件说每次run都会提交。过几天就会出结果，let’s see 
给一个数组，里面是小数，[1.2, 1.3. 2.3, 4.2], 给一个target 9, 输出一个整数数组，要求数组合等于target, 每个数是小数数组的 floor 或者 ceiling, 但是总变动最小， 比如1.2 可以变成1 或者2， 变1 的话变动就是.2, 变2 的话变动就是.8。
每个数取 floor, 然后算每个数的差值，然后排序，差值求和存起来， 0.2+0.3+0.3+0.2 = 1 [(0.2, 1), (0.2, 4), (0.3, 1), (0.3, 2)] 然后从大的开始填，填到差值合为0， 就是答案 ［1,4,1,3］
感觉是dp吧
dp(i-1, target) = min( dp(i-2, target), dp(i-2, target-floor(nums[i-1])) + diff1, dp(i-2, target-ceil(nums[i-1])) + (1-diff1))
看到好多人最近收到这道题但表示follow up 有的面试官想要听O(n) 的解法，刚好刷过类似的就发一下吧
- 用一个数组存所有数的小数部分float fraction
- 在获得上述数组过程中求floor sum 然后target - floor sum = k求出有多少个数需要被ceil
- 关键是求出后不要sort， 在fraction的数组中用quick select找到kth largest（假设求出的这个数是X），于是prices中第一个要被ceil的数的小数部分就是X
- 在prices数组中所有小数部分比X 小的数都要取floor，其他取ceil
由于quick select的平均复杂度是O（n） 所以这道题的时间复杂度也就变成了O（n）
quick select的思路和quick sort差不多，专门用于找kth largest（或者 kth sm allest） in an unsorted array。不了解的同学可以查一下
今天刚follow up结束，什么都没问就go through 了代码和讲了时间复杂度
输入是List prices 和 int target，需要return一个list全都是integer，但是sum又等于target，并且roundoff
error最小。
做法很简单，就是遍历一遍prices, 全部round up到floorValue得到一个floorSum，记录下来index和diff (pric - floorValue)。将floorSum跟target进行比较，少于K个，然后sort by diff，找到diff 最大的k个，每个减1得到最终结果。
说一下15min follow up电面吧
recruiter不是很专业，并没有把我在hackerrank的code贴到codepad，国人大哥一直在联系，直到最后也没贴上代码。
眼看五分钟了还没开始，我就很尴尬的开始说要不我说一下我做的题把，国人大哥就开始跟我说中文。
虽然是中文，但是感觉要跪。
题目很简单做法也是标准做法，问了一下时间复杂度(O(nlogn))，然后开始问follow up能不能优化到O(n)，我说了priority
queue和min heap，本质都是heap，时间其实还是一样好像，尴尬了。
感觉国人大叔不是很满意，说虽然这个问题并不是要求作答的，然后让我去看算法导论第九章第十章，哭了，瑟瑟发抖简直。
他就提示我说找到第k大个数怎么找，他说的做法是找到pivot，小于pivot放在前面，大于pivot的放在后面，直到找到top k个，类似于quick sort，这样就可以 到O(n), 最差情况是O(n^2)但是也没那么倒霉吧，我带着疑惑这时候又脑抽了我说那不是O(nlogn)嘛。。。哭了。最后象征性的问了一下问题，感觉要跪
static List<Integer> roundPricesToMatchTarget(List<Float> prices, int target) {
List<Integer> result = new ArrayList<Integer>();
int floorSum = 0;
PairWithDiff[] numWithDiff = new PairWithDiff[prices.size()];
// set the num index together with its diff to its floor value
for (int i = 0; i < prices.size(); i++) {
int floor = prices.get(i).intValue();
// set result with floor value first
// then our sum will be smaller than the target
result.add(floor);
floorSum += floor;
numWithDiff[i] = new PairWithDiff(i, prices.get(i) - (float) floor);
}
// sort the pairs with the diff
Arrays.sort(numWithDiff, new Comparator<PairWithDiff>() {
public int compare(PairWithDiff n1, PairWithDiff n2) {
if (n1.diffToFloor <= n2.diffToFloor)
return -1;
else
return 1;
}
});
int i = prices.size() - 1;
// we want to round up some values
// but we want to minimize each diffs
// so we choose the biggest diff value, which means we can minimize each diffs
while (target > floorSum) {
int resI = numWithDiff[i].index;
result.set(resI, result.get(resI) + 1);
floorSum++;
i--;
}
return result;
}
// the class store the corresponding index, and the diff between this float num
// to its floor int
static class PairWithDiff {
int index;
float diffToFloor;
public PairWithDiff(int index, float diffToFloor) {
this.index = index;
this.diffToFloor = diffToFloor;
}
};
OA19 csv parser
点击展开
Input:
format: first_name, last_name, email, interest, xxx(忘了…), location, age
e.g.:
[‘’‘Weronika,Zaborska,njkfdsv@dsgfk.sn,“running, sci-fi”,new,Krakow,25’‘’,
‘’‘Ryuichi,Akiyama,jkg@ljnsfd.fjn,music,guide,Tokyo,65’‘’,
‘’‘Elena,Martinez,emrt@lsofnbr.rt,“cooking, traveling”,superhost,Valencia,42’‘’,
‘’‘“John ““Mo”””,Smith,sfn@flkaei.km,biking and hiking,“Seattle, WA”,23’‘’]
希望output:
Weronika, 25 years old, is from Krakow and is interested in running, sci-fi.
Ryuichi, 65 years old, is from Tokyo and is interested in music.
Elena, 42 years old, is from Valencia and is interested in cooking, traveling.
John “Mo”, 23 years old, is from Seattle, WA and is interested in biking and hiking.
会给出format:
[first_name], [age] years old, is from [location] and is interested in [interest].
没什么edge cases,只要按规定的处理就行.
规定:
- ,为分隔符,除非在“”里 如“John, L”,则不分割
- “”里有连续两个“”则只要一个“
*很多奇怪的edge case其实不需要考虑: 所谓奇怪,你感觉要拐3道弯以上就不用管了,基本规则满足后就会发现test可以过了的
这题搜了stack overflow上的regular expression先处理逗号分隔section的问题再每个section检查去掉多重引号就可以，最后组成一段话print。面经里的CSV题解法应该也是可以写的。
一个小时一道题
之前面经里面有提到过的csvParser
/*
John,Smith,john.smith@gmail.com,Los Angeles,1
Jane,Roberts,janer@msn.com,"San Francisco, CA",0
"Alexandra ""Alex""",Menendez,alex.menendez@gmail.com,Miami,1
"""Alexandra Alex"""
John|Smith|john.smith@gmail.com|Los Angeles|1
Jane|Roberts|janer@msn.com|San Francisco, CA|0
Alexandra "Alex"|Menendez|alex.menendez@gmail.com|Miami|1
"Alexandra Alex"
*/
题意：
- 对于逗号，将它当做分隔符，然后将分隔符之间的那部分（field）插入到一个string的列表中，将该列表返回
- 如果逗号在引号内，则不把它当做分隔 ： “San Francisco, CA” => San Francisco, CA
- 如果有双重引号，移除一个。
关于这一点，题目保证了不会出现不合法的字符串，比如"“Alex"和Alax, “Ha"这样就不合法。
其次，如果有这个field是被引号包括的，那么引号一定只会该field的首位
最后，如果这个field引号内有双重引号，即两个引号连在一起 “”， 就删除其中的一个，保留另一””“Alexandra”" ““Alex””" =>
“Alexandra” “Alex”.
然后从csvParser中返回一个vector，再进行其他格式化输出
直接从标准输入流读取文本，一行一行读
输出也是输出到标准输出流
tricky的case没有，我觉得就是要理解题意，关于双重引号的处理。
给一个错误的示范：
OA20.2 subsequences
点击展开
两个题时间其实没有很难，但读题其实挺花时间的，如果没有一下子想到怎么做，可能时间会比较紧。
第一题还有顺序的问题，一开始我以为某个词序列乱了就把这个词挑出来加到结果里就好了，后来等我写完了测试，才发现一个词乱了后面的都认为是乱的。建议如果OA 要求不清楚的时候还是先跑几个test cases看看到底是什么情况再做。
吐槽一下第一个题，个人认为，这个description写的语法结构欠缺。出题人想把很多事情在一句话里面描述清楚。然而最后却把一句话的句式结构变得非常复杂，并不能让人很容易理解出题人想要表达的是什么。有些句子的甚至连主语和谓语的使用都有问题，需要多上两边才能明白在说什么。这种情况，如果人与人当面交流的话很容易通过提问来问清楚，但是OA的话有点浪费时间，不能最快的集中注意力去解决真正要解决的问题。
刚做了欧艾 尔食。两道题，跟地里面经那个题目是一样的，但是问的东西好像不太一样
第一题 两个字符串 词用空格分开 要求找出串a缺少哪些串b的词 按照缺的顺序输出
第二题 给一个序列 问有多少 个严格递减的长度为3的subsequence
两个指针的话，应该可以做到O(N)
例如 int array: int A = new int { 5, 4, 3, 2, 4, 6, 5, 3 }，指针p1 = 0, p2 = 0;
首先移动p2，因为严格递减，确保A[p2] < A[p2-1].
如果不满足，移动p1到p2。
如果满足，同时检查p2-p1==2是否为true，如果是，就是找到一组解；此时只移动p1++；
只扫描A一遍，所以是O(N)
“p2-p1==2是否为true“ …这个和长度为3的subsequence有关系，如果p2-p1==2，则p1到p2的长度为3 （包含p1,p2本身）
