public
Last active

interview street: zombie march, page rank

  • Download Gist
ZombieMarch.cpp
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
/*
* https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
* http://www.17sotv.com/ 17sotv电影天堂
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAXN 100000
#define PAGE_RANK_ITERATION_ROUND 50
 
int n, m, k;
vector<int> edges[MAXN];
double val[2][MAXN];
 
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d%d", &n, &m, &k);
while (m--)
{
int i, j;
scanf("%d%d", &i, &j);
edges[i].push_back(j);
edges[j].push_back(i);
}
for (int i = 0; i < n; ++i)
{
scanf("%lf", &val[0][i]);
}
k = min(k, PAGE_RANK_ITERATION_ROUND);
int now = 0, next = 1;
while (k--)
{
for (int i = 0; i < n; ++i)
{
val[next][i] = 0;
for (int j = 0; j < edges[i].size(); ++j)
{
int p = edges[i][j];
val[next][i] += val[now][p] / edges[p].size();
}
}
now = 1 - now;
next = 1 - next;
}
sort(val[now], val[now] + n);
for (int i = n - 1; i >= n - 5; --i)
{
int j = int(val[now][i]);
if (val[now][i] - j >= 0.5)
{
j++;
}
printf("%d ", j);
}
printf("\n");
for (int i = 0; i < n; ++i)
{
edges[i].clear();
}
}
return 0;
}
ZombieMarch.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
#!/usr/bin/python
 
"""
https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
http://www.17sotv.com/ 17sotv电影天堂
"""
 
import sys
import random
import time
 
page_rank_iteration_round = 50
 
def main():
# read t
line = sys.stdin.readline().strip()
t = int(line)
while t > 0:
t = t - 1
# test time
# print "start: %d" % time.time()
# read n, m, k
line = sys.stdin.readline().strip()
(n, m, k) = (int(i) for i in line.split())
# define node degree, and edges
degree = [0] * n
edges = [[] for i in xrange(0, n)]
# read edges
for i in xrange(0, m):
line = sys.stdin.readline().strip()
(p, q) = (int(x) for x in line.split())
degree[p] = degree[p] + 1
degree[q] = degree[q] + 1
edges[p].append(q)
edges[q].append(p)
# define zombie number
num = [[0.0] * n for i in xrange(0, 2)]
# read initial zombie number
for i in xrange(0, n):
line = sys.stdin.readline().strip()
num[0][i] = float(line)
# end input time
# print "end input: %d" % time.time()
# enumarate the process
k = min(k, page_rank_iteration_round)
(now, next) = (0, 1)
while k > 0:
k = k - 1
for i in xrange(0, n):
num[next][i] = 0
for j in edges[i]:
num[next][i] = num[next][i] + num[now][j] / degree[j]
(now, next) = (1 - now, 1 - next)
# sort the result
num[now].sort(reverse = True)
# end compute time
# print "end compute: %d" % time.time()
# output the result
for i in num[now][0:5]:
print int(round(i)),
print
 
if __name__ == '__main__':
main()
ZombieMarch_v2.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
#!/usr/bin/python
 
"""
https://www.interviewstreet.com/challenges/dashboard/#problem/4ff1484963063 Zombie March
http://www.17sotv.com/ 17sotv电影天堂
"""
 
import sys
import random
import time
 
page_rank_iteration_round = 50
 
def main():
# read t
line = sys.stdin.readline()
t = int(line)
for _ in range(t):
# test time
# print "start: %d" % time.time()
# read n, m, k
line = sys.stdin.readline().strip()
(n, m, k) = (int(i) for i in line.split())
# define node degree, and edges
degree = [0] * n
edges = [[] for i in xrange(0, n)]
# read edges
for i in xrange(0, m):
line = sys.stdin.readline()
(p, q) = (int(x) for x in line.split())
degree[p] += 1
degree[q] += 1
edges[p].append(q)
edges[q].append(p)
# define zombie number
num = [[0.0] * n for i in xrange(0, 2)]
# read initial zombie number
for i in xrange(0, n):
line = sys.stdin.readline()
num[0][i] = float(line)
# end input time
# print "end input: %d" % time.time()
# enumarate the process
k = min(k, page_rank_iteration_round)
now, next_ = 0, 1
for _ in range(k):
for i in xrange(0, n):
num[next_][i] = 0
for j in edges[i]:
num[next_][i] = num[next_][i] + num[now][j] / degree[j]
now, next_ = next_, now
# sort the result
num[now].sort(reverse = True)
# end compute time
# print "end compute: %d" % time.time()
# output the result
for i in num[now][0:5]:
print int(round(i)),
print
 
if __name__ == '__main__':
main()

the cpp code can pass all the test cases, but the python code will fail the 7th test case (Time Limit Exceed), who can help to improve this python code, and give some advise on writing optimized python code.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.