Can you please break down and explain these two lines ? I am really curious to know how you did it with just two lines of code !

Here's mine in Python.

import collections

values = collections.defaultdict(int)
for _ in range(int(input())):
    values[input()] += 1
for _ in range(int(input())):
    print(values[input()])

You can use an unordered_multiset (C++11) and its count method to make this easier:

#include <iostream>
#include <iterator>
#include <unordered_set>
using namespace std;

int main() {
    int n, q, i;
    string str;
    unordered_multiset<string> s;
    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> str;
        s.insert(str);
    }
    cin >> q;
    for (i = 0; i < q; ++i) {
        cin >> str;
        cout << s.count(str) << '\n';
    }
}

ArrayList<String> a = new ArrayList<String>();
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 0; i < n; i++) {
            a.add(scan.next());
        }
        int q = scan.nextInt();
        for(int i = 0; i < q; i++) {
            int count = 0;
            String s = scan.next();
            for(String str : a) {
                if(str.equals(s))
                    count++;
            }
            System.out.println(count);
        }

LOL

Your solution is very inefficient.

Here I suggest you functional approach, better efficiency and readability.

Scanner sc = new Scanner(System.in);

Map<String, Long> counterMap = Stream.generate(sc::next)
    .limit(sc.nextInt())
    .collect(groupingBy(identity(), counting()));

Stream.generate(sc::next)
    .limit(sc.nextInt())
    .map(query -> counterMap.getOrDefault(query, 0L))
    .forEach(System.out::println);

P.S. imports are omitted.

The complexity of your algorithm is very big

My solution:

str_seq = [input() for s in range(int(input()))]
qry_seq = [input() for q in range(int(input()))]
print(*(sum(q == s for s in str_seq) for q in qry_seq), sep='\n')

I like my third line.

This is concise, but not performant. You are iterating through the entire array on every query: O(NQ) when O(N+Q) is possible with the same memory usage O(N).

Yeah, I have no idea what the intention was with the naming. The intro is also very clumsy...

Your solution runs in O(n*q). It is possible to do O(n+q). Here is a faster algorithm.

Create a HashMap<String,Integer>
for each string in the first set
    if the map contains the string increment the associated int
    else put it in the map associated with 1
for each string in the second set
    if the map contains the string print the associated int
    else print 0

I believe this also could be implemented in two lines of code, but that's not my style. I used 7, thought it easier to read.

Agreed. I don't see what this problem has to do with sparse arrays either. I implemented to simplest solution using an array and iterating thorugh it to get the counts (since it is in the array problem section), but obviously there are other solutions that are much more efficient such as leveraging a hash table/map, or even a trie if you want to save space. Eitherway, not a very challenging problem.

If you're going to use a Trainwreck, at least format it more like this:

Scanner in = new Scanner(System.in);
List<String> strings = IntStream.range(0,in.nextInt())
    .mapToObj(i -> in.next())
    .collect(Collectors.toList());
IntStream.range(0, in.nextInt())
    .mapToObj(i -> in.next())  // over here, you can comment individual functions where appropriate.
    .mapToLong(q -> strings.stream()
               .filter(q::equals)
               .count())
    .forEach(System.out::println);

The line count metric is such a poor one.

Looks good for bragging right, but am sure it's not efficient , a hashMap would be faster

And here's in kotlin:

return queries.flatMap { s -> listOf(strings.count { it==s }) }.toTypedArray()

JavaScript :)

const matchingStrings = (strings, queries) =>
    queries.map(el => strings.filter(item => item === el).length)

def matchingStrings(strings: Array[String], queries: Array[String]): Array[Int] = {
  val lookupTable = strings.groupBy(s => s)
  queries.foldLeft(Array[Int]())((acc, next) => {
    val matches = lookupTable.get(next).map(_.length).getOrElse(0)
    acc :+ matches
  })
}

Functional style also :D

hello coding lover,

I have uploaded a tutorial on this problem which can solve this problem in O(N+Q) time.

I hope this comment will help you to optimize your solution.

https://www.hackerrank.com/challenges/sparse-arrays/forum/comments/598644

jesus chris. if you write code like that in a company, do you think that will ever pass code review for production?

C++ solution :

vector<int> matchingStrings(vector<string> strings, vector<string> queries) {
    map<string, int> m;
    vector<int> v;
    for (string s:strings)  m[s]++;
    for (string q:queries) v.push_back(m[q]);
    return v;
}

def matchingStrings(strings, queries):

data = {e: strings.count(e) for e in strings}
result = [data[q] if q in data else 0 for q in queries]

return result

I have solved this using my code, which is using a Tree to find an ultra fast and efficient solution, based on pattern matching of an tree based algorithm, something that is industry proven and a standard to be fast and efficient to solving pattern matching problems.

I have seen all the codes in comments, manipulating main methods to get your answer. By avoiding the reading time of inputs into string arrays, saves you time, but that time saved isn't actually meant to be saved, that isn't the way these challenges are supposed to be answered. You are asked to implement it in a method after receiving the input arrays in the method code. YOU MUST IMPLEMENT IT IN THE METHOD. Otherwise your answers are just useless.

Mine in C++ using solution involving sorting, lower_bound, and upper_bound

std::vector<int> matchingStrings(
    std::vector<std::string> strings,
    const std::vector<std::string>& queries)
{
    std::sort(strings.begin(), strings.end());
    std::vector<int> result;
    result.reserve(queries.size());
    for (const auto& query : queries)
    {
        auto lower = std::lower_bound(strings.begin(), strings.end(), query);
        auto upper = std::upper_bound(strings.begin(), strings.end(), query);
        int diff = (lower == strings.end()) ? 0 : std::distance(lower, upper);
        result.push_back(diff);
    }
    return result;
}

Agree. not sure what this "medium" difficulty quesion is aiming at.

Shorter description: Given an array of strings FOO and a an array of strings BAR find the count of string in BAR that occurs in FOO.

C#. Linq is your friend.

var results = new int[queries.Length];

        var index = 0;

        foreach (string s in queries)
        {
             results[index++] = strings.Where(i => i == s).Count();
        }

        return results;

int[] a = new int[queries.length]; int i =0; for(String s : queries){ a[i] = Collections.frequency(Arrays.asList(strings), s); i++; }

For the c++ folks

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int str_c,q_c;
    map<string,int> m;
    string s;

    cin>>str_c;
    while( str_c-- ){
        cin>>s;
        m[s] += 1;
    }
    cin>>q_c;
    while ( q_c-- )
    {
        cin>>s;
        cout<<m[s]<<"\n";
    }
}