Check duplicates in a stream of strings

Check duplicates in a stream of strings

Given an array arr[] of strings containing the names of employees in a company. Assuming that the names are being entered in a system one after another, the task is to check whether the current name is entered for the first time or not.
Examples:
Input: arr[] = {“geeks”, “for”, “geeks”}
Output:
No
No
Yes
Approach: Create an unordered_set to store the names of the employees and start traversing the array, if the current name is already present in the set then print Yes else print No and insert it into the set.
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to insert the names
// and check whether they appear
// for the first time
void insertNames(string arr[], int n)
{
  
    // To store the names
    // of the employees
    unordered_set<string> set;
    for (int i = 0; i < n; i++) {
  
        // If current name is appearing
        // for the first time
        if (set.find(arr[i]) == set.end()) {
            cout << "No\n";
            set.insert(arr[i]);
        }
        else {
            cout << "Yes\n";
        }
    }
}
  
// Driver code
int main()
{
    string arr[] = { "geeks", "for", "geeks" };
    int n = sizeof(arr) / sizeof(string);
  
    insertNames(arr, n);
  
    return 0;
}
Output:
No
No
Yes

// Java implementation of the approach
import java.util.*;
  
class GFG 
{
  
// Function to insert the names
// and check whether they appear
// for the first time
static void insertNames(String arr[], int n)
{
  
    // To store the names
    // of the employees
    HashSet<String> set = new HashSet<String>();
    for (int i = 0; i < n; i++) 
    {
  
        // If current name is appearing
        // for the first time
        if (!set.contains(arr[i]))
        {
            System.out.print("No\n");
            set.add(arr[i]);
        }
        else 
        {
            System.out.print("Yes\n");
        }
    }
}
  
// Driver code
public static void main(String[] args)
{
    String arr[] = { "geeks", "for", "geeks" };
    int n = arr.length;
  
    insertNames(arr, n);
}
}
  
// This code contributed by PrinciRaj1992
Output:
No
No
Yes



# Python3 implementation of the approach
  
# Function to insert the names 
# and check whether they appear 
# for the first time 
def insertNames(arr, n) : 
  
    # To store the names 
    # of the employees 
    string = set();
      
    for i in range(n) :
  
        # If current name is appearing 
        # for the first time 
        if arr[i] not in string :
            print("No"); 
            string.add(arr[i]); 
      
        else : 
            print("Yes"); 
      
# Driver code 
if __name__ == "__main__" : 
  
    arr = [ "geeks", "for", "geeks" ]; 
    n = len(arr); 
  
    insertNames(arr, n); 
  
# This code is contributed by AnkitRai01
Output:
No
No
Yes





























































Comments

Post a Comment

Popular posts from this blog

[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not

Check if a given sequence of moves for a robot is circular or not Link:  https://www.youtube.com/watch?v=f7Zd8hEbCz0 Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following. G - Go one unit L - Turn left R - Turn right Input: path[] = "GLGLGLG" Output: Given sequence of moves is circular Input: path[] = "GLLG" Output: Given sequence of moves is circular The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not. N | | W -------------- E | | S The move ‘G’ changes either x or y according to following rules. a) If current direction is North, then ‘G’ increments y and doesn’t cha...
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more