Snapchat全职跪经

pingfanzhilu

贴个2 pass的解法吧（the second pass is merge）有1 pass的吗？

import java.util.*;
class Interval {
public int left;
public int right;
public Interval(int l, int r) {
this.left = l;
this.right = r;
}
}
public class Solution {
public static void main(String[] args) {
List<String[]> input = new ArrayList();
input.add(new String[]{"f1", "start", "1"});
input.add(new String[]{"f1", "start", "2"});
input.add(new String[]{"f2", "start", "4"});
input.add(new String[]{"f2", "end", "8"});
input.add(new String[]{"f1", "end", "16"});
input.add(new String[]{"f1", "end", "32"});
input.add(new String[]{"f3", "start", "64"});
input.add(new String[]{"f3", "end", "128"});
Solution sol = new Solution();
Map<String, List<Interval>> result = sol.solve(input);
for (String k : result.keySet()) {
System.out.print(k + " : ");
for (Interval itv : result.get(k)) {
System.out.print("[" + itv.left + ", " + itv.right + "]");
}
System.out.println();
}
}
public Map<String, List<Interval>> solve(List<String[]> input) {
Map<String, List<Interval>> result = new HashMap();
String[] prev = null;
for (String[] current : input) {
if (current[1].equals("start")) {
if (prev != null && prev[1].equals("start")) {
if (!result.containsKey(prev[0])) {
result.put(prev[0], new ArrayList<>());
}
result.get(prev[0]).add(new Interval(Integer.valueOf(prev[2]), Integer.valueOf(current[2])));
}
} else { // end
if (!result.containsKey(prev[0])) {
result.put(current[0], new ArrayList<>());
}
result.get(current[0]).add(new Interval(Integer.valueOf(prev[2]), Integer.valueOf(current[2])));
}
prev = current;
}
for (String key : result.keySet()) {
result.put(key, merge(result.get(key)));
}
return result;
}
private List<Interval> merge(List<Interval> list) {
Stack<Interval> stack = new Stack();
for (Interval itv : list) {
if (stack.isEmpty()) {
stack.push(itv);
} else {
if (stack.peek().right < itv.left) {
stack.push(itv);
} else {
Interval top = stack.pop();
stack.push(new Interval(Math.min(top.left, itv.left), Math.max(top.right, itv.right)));
}
}
}
List<Interval> ret = new ArrayList();
while (!stack.isEmpty()) {
ret.add(stack.pop());
}
return ret;
}
}

复制代码

满城尽带黄金甲

所以需要merge么？

laonong15

写了个半伪码的code 懒得写map 操作抛砖：

laonong15

laonong15 发表于 2016-9-3 07:55
写了个半伪码的code 懒得写map 操作抛砖：

public Map<functioname,List<Interval> parseLog(List<Log> list) {
//coner casese
Map<functionanme,List<Interval> result = new HashMap<>();
Stack<Log>  stack = new Stack<>();
int intervalStart = 0;
for(Log log:list){

   if(stack.isEmpty()){
         stack.push(log)
   } else {
         Log top = stack.top();
         if(top.functioname == log.functioname){
               if(log.startorend is end){
                  Interval intvl = new Interval(top.timestamp,log.timestamp);
                  add intvl to the map;
                  stack.pop();
               } else {
                     stack.push(log);
               }
         } else {
               Interval intvl = new Interval(top.timestamp,log.timestamp);
                  add intvl to the map by the key is top.functioname;
         }
   }
   intervalStrat = log.timestamp;
   }
   reutrn result;
   }

importcoder

我也只能想到先把相同function的interval放到map里，然后依次merge。

// assuming following situation will never occur:
// f1 start 1
// f2 start 4
// f1 end 7
// f2 end 10
// meaning if there is an "end", the previous must be a "start" with same ID
public class LogParsing {
public Map<String, List<List<Integer>>> logParser(String[] log) {
Map<String, List<List<Integer>>> result = new HashMap<>();
Stack<String[]> stack = new Stack<>();
// put cpu occupied period for each function
for (String line: log) {
String[] cur = line.split("\t");
result.putIfAbsent(cur[0], new ArrayList<>());
if (stack.isEmpty()) {
stack.push(cur);
continue;
}
String[] pre = stack.peek();
int start = Integer.parseInt(pre[2]);
int end = Integer.parseInt(cur[2]);
List<Integer> interval = Arrays.asList(start, end);
result.get(pre[0]).add(interval);
if (cur[1].equals("start")) {
stack.push(cur);
} else if (cur[1].equals("end")) {
stack.pop();
if (!stack.isEmpty()) {
stack.peek()[2] = cur[2];
}
}
}
// merge occupied time lists
for (String id: result.keySet()) {
List<List<Integer>> list = mergeIntervals(result.get(id));
result.put(id, list);
}
return result;
}
private List<List<Integer>> mergeIntervals(List<List<Integer>> intervals) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> pre = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
List<Integer> cur = intervals.get(i);
if (overlap(pre, cur)) {
List<Integer> interval = Arrays.asList(Math.min(pre.get(0), cur.get(0)), Math.max(pre.get(1), cur.get(1)));
pre = interval;
} else {
result.add(pre);
pre = cur;
}
}
result.add(pre);
return result;
}
private boolean overlap(List<Integer> pre, List<Integer> cur) {
return pre.get(1) >= cur.get(0);
}
public static void main(String[] args) {
LogParsing solution = new LogParsing();
String[] log = {"f1\tstart\t1", "f1\tstart\t2", "f2\tstart\t4", "f2\tend\t8", "f1\tend\t16", "f1\tend\t32", "f3\tstart\t64", "f3\tend\t128"};
System.out.println(solution.logParser(log));
}
public static void print(String[] log) {
for (String s: log) {
System.out.println(s);
}
}
}

复制代码

eboyme

1 pass。大概写了一下。感觉这个应当假定输入总是合法的。比如f1 start 1, f2 start 2, f1 end 4这种情况不应该存在，否则CPU在时间[2,4]内的运行状态是不确定的。

import java.util.*;
class Log{
String program;
String status;
int timeStamp;
public Log(String program, String status, int timeStamp){
this.program = program;
this.status = status;
this.timeStamp = timeStamp;
}
}
public class FunctionLogParsing {
public static Map<String, List<int[]>> parsingLogFile(Log[] file){
Map<String, List<int[]>> res = new HashMap<String, List<int[]>>();
if (file == null || file.length == 0)
return res;
Log prev = file[0];
int start = prev.timeStamp;
int end = -1;
for (int i = 1; i < file.length; i++){
Log curr = file[i];
if (curr.status.equals("start")){
if (curr.program.equals(prev.program)){
if (prev.status.equals("end")){
addRes(start, end, res, prev);
}
}
else{
if (prev.status.equals("start")){
end = curr.timeStamp;
}
addRes(start, end, res, prev);
start = curr.timeStamp;
end = -1;
prev = curr;
}
}
else {
if (curr.program.equals(prev.program)){
end = curr.timeStamp;
}
else{
addRes(start, end, res, prev);
start = end;
end = -1;
prev = curr;
}
}
}
addRes(start, end, res, prev);
return res;
}
private static void addRes(int start, int end, Map<String, List<int[]>> res, Log prev){
int[] interval = {start, end};
if (!res.containsKey(prev.program)){
res.put(prev.program, new ArrayList<int[]>());
}
res.get(prev.program).add(interval);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Log[] logs = {
new Log("f1", "start", 1),
new Log("f1", "start", 2),
new Log("f2", "start", 4),
new Log("f2", "end", 8),
new Log("f1", "end", 16),
new Log("f1", "end", 32),
new Log("f3", "start", 64),
new Log("f3", "end", 128),
};
Map<String, List<int[]>> map = parsingLogFile(logs);
for (String key: map.keySet()){
System.out.print(key+": ");
for (int[] pair: map.get(key)){
System.out.print("[" + pair[0] + "," + pair[1] + "] ");
}
System.out.println();
}
}
}

复制代码

freemail165 · 2016-10-13 14:16:08

eboyme 发表于 2016-10-2 06:39
1 pass。大概写了一下。感觉这个应当假定输入总是合法的。比如f1 start 1, f2 start 2, f1 end 4这种情 ...

为什么不确定

既然单线程，当f2 start 2, we should get f1[1,2] f1 won't run
then f1 end 4 , we should get f2[2,4]

sophie729 · 2016-10-13 14:47:08

楼主好赞！希望加面通过。
想咨询下 onsite 调环境的时候是在自己电脑还是公司给安排一个电脑呢？

Snapchat全职跪经

浏览过的版块