Favorite sequence – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Favorite sequence HackerRank Solution
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#define pb push_back
#define getcx getchar//_unlocked
using namespace std;
inline void inp(int &n )
{n=0; int ch=getcx();
while(ch<'0'||ch>'9') ch=getcx();
while(ch>='0'&&ch<='9') n=(n<<3)+(n<<1)+ch-'0',ch=getcx(); }
int n,k,b,a,i;
int xr[1000001];
bool f[1000001];
vector < int > nx[1000001];
priority_queue < int > st;
int main() {
inp(n);
while (n--) {
inp(k);
cin>>b; f[b]=1;
for (i=2;i<=k;i++) {
inp(a); xr[a]++;
nx[b].pb(a);
b=a; f[b]=1;
}
}
for (i=0;i<=1000000;i++)
if (f[i] && xr[i] == 0)
st.push(-i);
while (st.size() > 0)
{
k=-st.top();
printf("%d ",k);
st.pop();
for (i=0;i<nx[k].size();i++) {
xr[nx[k][i]]--; if (xr[nx[k][i]] == 0) st.push(-nx[k][i]); }
}
printf("\n");
}
Java Favorite sequence HackerRank Solution
import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class HR_favourite_sequence {
public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
ArrayList<Integer>[] g = new ArrayList[1000001];
for (int i = 0; i < g.length; ++i) {
g[i] = new ArrayList<Integer>();
}
boolean[] col = new boolean[g.length];
int[] l = new int[g.length];
for (int it = 0; it < n; ++it) {
int k = in.nextInt();
int prev = -1;
for (int i = 0; i < k; ++i) {
int x = in.nextInt();
col[x] = true;
if (i > 0) {
g[prev].add(x);
l[x]++;
}
prev = x;
}
}
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int i = 0; i < g.length; ++i) {
if (col[i] && l[i] == 0) {
pq.add(i);
}
}
while (!pq.isEmpty()) {
int i = pq.poll();
for (int j : g[i]) {
l[j]--;
if (l[j] == 0) {
pq.add(j);
}
}
out.print(i + " ");
}
out.println();
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
out.close();
}
static class Input {
BufferedReader in;
StringBuilder sb = new StringBuilder();
public Input(BufferedReader in) {
this.in = in;
}
public Input(String s) {
this.in = new BufferedReader(new StringReader(s));
}
public String next() throws IOException {
sb.setLength(0);
while (true) {
int c = in.read();
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
int c = in.read();
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}
Python 3 Favorite sequence HackerRank Solution
from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
k = int(input())
sequence = map(int, input().split())
prev = 0
for num in sequence:
if prev:
before_maps[num].add(prev)
after_maps[prev].add(num)
prev = num
m = []
actives = set(active for active in after_maps[0] if not before_maps[active])
while actives:
next_step = sorted(actives)[0]
actives.remove(next_step)
for step in after_maps[next_step]:
before_maps[step].remove(next_step)
actives.update(active for active in after_maps[next_step] if not before_maps[active])
m.append(next_step)
print(' '.join(map(str, m)))
Python 2 Favorite sequence HackerRank Solution
import heapq
import sys
# Parse input
sequences = []
T = int(raw_input())
for _ in xrange(T):
line = [int(x) for x in sys.stdin.readline().split()]
K = line[0]
if len(line) == 1:
line = [int(x) for x in sys.stdin.readline().split()]
sequences.append(line)
else:
sequences.append(line[1:])
# Calc number of predecessors for each value
node_heap = []
number_of_predecessors = {}
for idx_seq, seq in enumerate(sequences):
for idx_val, val in enumerate(seq):
if not val in number_of_predecessors:
number_of_predecessors[val] = 1
else:
number_of_predecessors[val] += 1
# initialise
pointers = [0]*T
which_sequences = [[] for _ in xrange(1000000+1)]
# inital possibilities
for seq_idx, seq in enumerate(sequences):
if len(seq) == 0:
continue
which_sequences[seq[0]].append(seq_idx)
if number_of_predecessors[seq[0]] == len(which_sequences[seq[0]]):
heapq.heappush(node_heap, seq[0])
# Construct sequence
res = []
while len(node_heap) > 0:
value = heapq.heappop(node_heap)
res.append(value)
sequence_indices = which_sequences[value]
which_sequences[value] = None
for seq_id in sequence_indices:
pointers[seq_id] += 1
if pointers[seq_id] < len(sequences[seq_id]):
val = sequences[seq_id][pointers[seq_id]]
which_sequences[val].append(seq_id)
if number_of_predecessors[val] == len(which_sequences[val]):
heapq.heappush(node_heap, val)
print ' '.join(str(r) for r in res)
C Favorite sequence HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int u;
int w;
int p;
} node;
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
int main(){
int N,i,j,max=0,size=0,tsize=0,heap_size=0,temp=0;
int *K,*e,*p,*pp,*u,*v,*ptr;
node t,*heap;
e=(int*)malloc(1000000*sizeof(int));
p=(int*)malloc(1000000*sizeof(int));
pp=(int*)malloc(1000000*sizeof(int));
for(i=0;i<1000000;i++)
e[i]=p[i]=pp[i]=0;
scanf("%d",&N);
K=(int*)malloc(N*sizeof(int));
int **table=(int**)malloc(N*sizeof(int*));
for(i=0;i<N;i++){
scanf("%d",&K[i]);
size+=K[i]-1;
table[i]=(int*)malloc(K[i]*sizeof(int));
for(j=0;j<K[i];j++){
scanf("%d",&table[i][j]);
e[table[i][j]-1]=1;
if(table[i][j]-1>max)
max=table[i][j]-1;
}
}
u=(int*)malloc(size*sizeof(int));
v=(int*)malloc(size*sizeof(int));
size=0;
for(i=0;i<N;i++)
for(j=1;j<K[i];j++){
u[size]=table[i][j-1]-1;
v[size]=table[i][j]-1;
p[table[i][j]-1]++;
size++;
}
sort_a2(u,v,size);
for(i=0;i<N;i++)
free(table[i]);
free(K);
free(table);
ptr=(int*)malloc(1000000*sizeof(int));
heap=(node*)malloc(1500000*sizeof(node));
for(i=0;i<=max;i++)
if(e[i]){
t.p=p[i];
t.w=(p[i])?2000000+i:i;
t.u=i;
heap_insert(heap,&t,&heap_size,ptr);
}
while(heap_size){
heap_read(heap,&heap_size,ptr,&t);
pp[tsize++]=t.u;
for(i=get_i(u,pp[tsize-1],size);i>=0 && i<size && u[i]==pp[tsize-1];i++){
t=heap[ptr[v[i]]];
t.p--;
if(t.p==0)
t.w-=2000000;
heap_update(heap,&t,ptr);
}
}
for(i=0;i<tsize;i++)
printf("%d ",pp[i]+1);
return 0;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int *heap_list){
int index=heap_list[elem->u];
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
(*ans)=heap[1];
int index=1;
while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
heap[index/2]=heap[index];
heap_list[heap[index].u]=index/2;
}
heap[index]=heap[*size];
heap_list[heap[index].u]=index;
(*size)--;
return;
}
Leave a comment below