HackerRank Favorite sequence problem solution

In this HackerRank Favorite sequence problem solution Johnny, like every mathematician, has his favorite sequence of distinct natural numbers. Let’s call this sequence M.

Johnny was very bored, so he wrote down N copies of the sequence M in his big notebook. One day, when Johnny was out, his little sister Mary erased some numbers(possibly zero) from every copy of M and then threw the notebook out onto the street. You just found it. Can you reconstruct the sequence?

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.

HackerRank Favorite sequence 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()

Favorite sequence 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;
}