In this HackerRank Favorite sequence problem solution In the input, there are N sequences of natural numbers representing the N copies of the sequence M after Mary’s prank. In each of them, all numbers are distinct. Your task is to construct the shortest sequence S that might have been the original M. If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.
Problem solution in Python.
# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/bin/python3
import math
import os
import random
import re
import sys
from collections import defaultdict, deque
import bisect
class Graph:
def __init__(self, vertices, graph=defaultdict(list), in_coming=defaultdict(int)):
self.V = vertices # No. of vertices
self.graph = graph # dictionary containing adjacency List
self.in_coming = in_coming
self.n = len(vertices)
# print(self.V)
# print(self.graph)
def recursion(self, node, visited, res):
visited[node] = True
for c in self.graph[node]:
if not visited[c]:
self.recursion(c, visited, res)
res.append(node)
def topological_sort(self):
res = []
# temp_mark = [False] * self.n
visited = {node: False for node in self.V}
for node in self.V:
if not visited[node]:
self.recursion(node, visited, res)
# visited[i] = True
# res.append(self.V[i])
return res[::-1]
def kahn_algo(self):
res = []
s = deque([node for node in self.V if node not in self.in_coming])
while len(s):
node = s.popleft()
res.append(node)
c_list = self.graph[node]
while len(c_list):
c = c_list.pop()
self.in_coming[c] -= 1
if self.in_coming[c] == 0:
bisect.insort(s, c)
return res
def favourite_sequence(n, copies):
# Write your code here
edges = defaultdict(list)
in_coming = defaultdict(int)
nodes = set()
# in_coming = set()
for c_list in copies:
k = len(c_list)
# in_coming = in_coming.union(set(c_list[1:]))
nodes = nodes.union(set(c_list))
for i in range(k-1):
edges[c_list[i]].append(c_list[i+1])
in_coming[c_list[i+1]] += 1
# no_coming = nodes.difference(in_coming)
# no_coming = sorted(list(no_coming))
nodes = sorted(list(nodes)) # reverse=True
for node in edges.keys():
edges[node].sort(reverse=True) # reverse=True
g = Graph(nodes, edges, in_coming)
# res = g.topological_sort()
res = g.kahn_algo()
return res
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input().strip())
copies = []
for t_itr in range(n):
k = int(input())
copies.append(list(map(int, input().rstrip().split())))
result = favourite_sequence(n, copies)
fptr.write(' '.join(map(str, result)))
# fptr.write('n')
fptr.close()
Problem solution in Java.
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.TreeSet;
public class Solution {
public static final int MAXN = 1000000;
public static void main(String[] args) {
int[] cnt = new int[MAXN+1];
int[] pcnt = new int[MAXN+1];
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
TreeSet<Integer> tree = new TreeSet<Integer>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] A = new int[N][];
int pnum = 0;
int mp = 0;
for (int i = 0; i < N; ++i) {
int M = sc.nextInt();
int[] AM = new int[M];
A[i] = AM;
pnum = 0;
for (int j = 0; j < M; ++j) {
cnt[pnum] += 1;
pnum = sc.nextInt();
AM[j] = pnum;
pcnt[pnum]++;
if (pnum > mp) {
mp = pnum;
}
}
}
int[][] B = new int[mp + 1][];
B[0] = new int[N];
int[] BP = new int[mp + 1];
for (int i = 0; i <= mp; ++i) {
B[i] = new int[cnt[i]];
}
for (int i = 0; i < N; ++i) {
int M = A[i].length;
int[] AM = A[i];
pnum = 0;
int[] Bpnum = B[pnum];
for (int j = 0; j < M; ++j) {
int AMj = AM[j];
Bpnum[BP[pnum]++] = AMj;
pnum = AMj;
Bpnum = B[pnum];
}
}
for(int i=0;i<B[0].length;++i) {
pcnt[B[0][i]]--;
}
for (int i = 1; i <= mp; ++i) {
if(cnt[i]>0 || pcnt[i]>0) {
tree.add((i - 1) + pcnt[i] * MAXN);
}
}
try {
boolean first = true;
while (true) {
Integer t = tree.pollFirst();
if (t == null) {
break;
}
int tv = t % MAXN + 1;
if(first) {
first = false;
}else {
bw.write(' ');
}
bw.write(Integer.toString(tv));
int[] Btv = B[tv];
for (int i = 0; i < Btv.length; ++i) {
assert(pcnt[Btv[i]]>0);
tree.remove((Btv[i] - 1) + (pcnt[Btv[i]]--) * MAXN);
tree.add((Btv[i] - 1) + (pcnt[Btv[i]]) * MAXN);
}
}
} catch (IOException e) {
}finally {
try {
bw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
int main() {
set<int> s;
map<int, vector<int> > g;
map<int, int> c;
int n, k;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> k;
int tmp, past;
cin >> tmp;
past = tmp;
c[tmp];
for(int j = 1; j < k; ++j){
cin >> tmp;
g[past].push_back(tmp);
c[tmp]++;
//cout << past << " " << tmp << " " << c[tmp] << endl;
past = tmp;
}
}
for (std::map<int,int>::iterator it=c.begin(); it!=c.end(); ++it){
//cout << it -> first << " " << it->second << endl;
if(it->second == 0)
s.insert(it->first);
}
vector<int> ans;
while(!s.empty()){
int curr = *(s.begin());
ans.push_back(curr);
s.erase(curr);
for(int i = 0; i < g[curr].size(); ++i){
c[g[curr][i]]--;
if(c[g[curr][i]] == 0)
s.insert(g[curr][i]);
}
}
for(int i =0; i < ans.size(); ++i){
if(i != 0)
cout << " ";
cout << ans[i];
}
}
Problem solution in C.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct node
{
int val;
struct node* next;
}node;
node* a[100010];
int h[1000010],f[1000010],g[1000010],b[1000010],len,d[1000010],e[1000010];
void swap(int e,int f)
{
int temp=b[e];
b[e]=b[f];
b[f]=temp;
}
node* Insert(node *head,int val)
{
node* temp;
temp=(node*)malloc(sizeof(node*));
temp->val=val;
temp->next=NULL;
if(head==NULL)
{
head=temp;
return head;
}
temp->next=head;
return temp;
}
void shift_up(int idx)
{
if(idx/2<1)
return;
if(b[idx]<b[idx/2])
{
swap(idx,idx/2);
shift_up(idx/2);
}
return;
}
void shift_down(int idx)
{
int lc=2*idx,rc=2*idx+1;
if(lc>len)
return;
if(lc==len)
{
if(b[idx]>b[len])
swap(idx,len);
return;
}
if(b[lc]<=b[rc] && b[lc]<b[idx])
{
swap(lc,idx);
shift_down(lc);
}
else if(b[rc]<=b[lc] && b[rc]<b[idx])
{
swap(rc,idx);
shift_down(rc);
}
return;
}
void insert(int x)
{
len++;
b[len]=x;
shift_up(len);
return;
}
void delete()
{
swap(1,len);
len--;
shift_down(1);
return;
}
int main()
{
node* temp;
int x,n,i,l=1,r;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&x,&g[1]);
h[g[1]]=1;
for(i=2;i<=x;i++)
{
scanf("%d",&g[i]);
a[g[i-1]]=Insert(a[g[i-1]],g[i]);
d[g[i]]++;
h[g[i]]=1;
}
}
for(i=1;i<=1000000;i++)
if(h[i]==1 && d[i]==0)
insert(i);
while(len>0)
{
r=0;
temp=a[b[1]];
while(temp!=NULL)
{
x=temp->val;
d[x]--;
if(d[x]==0)
f[r++]=x;
temp=temp->next;
}
e[l++]=b[1];
delete();
for(i=0;i<r;i++)
insert(f[i]);
}
for(i=1;i<l;i++)
printf("%d ",e[i]);
printf("n");
return 0;
}