注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
全是新题
快问快答
1. 一段代码 是quickselect求一个数的index, 问time complexity 和 space complexity
2. An engineer is given the task of writing a tool to find the Kth largest number in an array of size N.
For example, for the following array:
[6, 1, 6, 8, 9]
the 2nd largest number would be 8.
the 4th largest number would be 6.
The engineer decided to use a min heap (the root's value is the smallest number) to store all the numbers. After popping top k-1 elements of the min heap, the min heap's top would be the answer.
Does this implementation meet the given requirements? Why or why not? 我回答不行
3.function sort(arr: array of integers)
if len(arr) == 1:
return arr
mid = len(arr) / 2
sorted_left_arr = sort(arr.copy(0, mid))
sorted_right_arr = sort(arr.copy(mid+1, len(arr)-1))
combined_array = sorted_left_arr.append(sorted_right_arr)
return bubble_sort(combined_array) # bubble_sort runs in `O(N^2)` time and `O(1)` space.
end
问能不能实现排序和时间空间复杂度 这个题不太清楚 瞎答的
代码 是log 问题,这里
第一题问的是每个user 第一次访问和最后一次访问的时间戳 eg [user1, starttime, endtime] 不难sort一下就行
第二题就是link里面那个 也不难
第三题/*
Write a function that takes the logs as input, builds the transition graph and returns it as an adjacency list with probabilities. Add __START__ and __END__ states.
Specifically, for each resource, we want to compute a list of every possible next step taken by any user, together with the corresponding probabilities. The list of resources should include __START__ but not __END__, since by definition __END__ is a terminal state.
Expected output for logs1:
transition_graph(logs1) # =>
{
'_START_': {'resource_1': 0.6, 'resource_2': 0.2, 'resource_6': 0.2},
'resource_1': {'_END_': 0.71, 'resource_3': 0.14, 'resource_5': 0.14},
'resource_2': {'resource_1': 0.5, 'resource_2': 0.5},
'resource_3': {'resource_1': 1.0},
'resource_5': {'resource_1': 1.0},
'resource_6': {'resource_1': 1.0}
}
For example, of 5 total users, 3 users have resource_1 as a first visit (user_1, user_9, user_22), 1 user has resource_6 as a first visit (user_3), and 1 user has resource_2 as a first visit (user_6), so the possible next steps for __START__ are resource_1 with probability 3/5, resource_2 with probability 1/5, and resource_6 with probability 1/5.
These are the resource paths per user for the first logs example, ordered by access time:
{
List<Integer>> map = new HashMap<>();
for(String[] log : logs) {
String resource = log[2];
Integer time = Integer.valueOf(log[0]);
if(!map.containsKey(resource)) {
map.put(resource, new ArrayList<>());
}
map.get(resource).add(time);
}
int max = 0;
for(Map.Entry<String,List<Integer>> entry: map.entrySet()) {
String resource = entry.getKey();
List<Integer> curr = entry.getValue();
Collections.sort(curr);
int countOfthis = 0;
for(int i=0;i<curr.size();i++) {
int range = curr.get(i) + 300;
int count =1;
for(int j=i+1; j< curr.size();j++) {
if(curr.get(j) <= range) {
count+=1;
}
else {
break;
}
}
countOfthis = Math.max(count, countOfthis);
}
if(countOfthis > max) {
max = countOfthis;
ans = resource + ", " + countOfthis;
}
}
return ans;
}
public static List<String> buildgraph(String[][] logs) {
for(String[] log: logs) {
}
}
class Pair {
int time;
String resource;
Pair(int time, String resource) {
this.time = time;
this.resource = resource;
}
}
}
要build很复杂的graph,没有时间build完只讲了思路
打算redo因为第三题没写完,运气也是有点差了 |