Programming challenge "Friend Request in Social Network"

Question

I am trying to solve a programming problem on a coding platform. When I execute it on my PC, it works perfectly, but when I submit the code on the coding platform, it throws a "Time Limit Exceeded" error. Can someone check my solution and help optimize it?

In a social network, a person can invite friends of his/her friend. John wants to invite and add new friends. Complete the program below so that it prints the names of the persons to whom John can send a friend request.

Input format:

The first line contains the value of the N which represent the number of friends. N lines contain the name of the friend F followed by the number of friends of F finally their names separated by space.

Input:

3
Mani 3 Ram Raj Guna
Ram 2 Kumar Kishore
Mughil 3 Praveen Naveen Ramesh

Output:

Raj Guna Kumar Kishore Praveen Naveen Ramesh

Explanation:

Ram is not present in the output as Ram is already John's friend.

My Approach

1. Extract the first word of each line and store them in HashSet and remove them from the string. Names stored in HashSet are already friends of the person (John).
2. Now extract the names from the String using StringTokenizer and check whether the name is contained in the HashSet. If it is not present then print it.

And can we solve this problem using graph/trees. The problem statement and my code can be found here.

import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;
class Ideone {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int N = sc.nextInt(); // No of friends
 sc.nextLine();
 HashSet<String> hs = new HashSet<>(); // to store name of the John's friends 
 String invitation = "";
 for(int i =0; i < N; i++)
 {
 String str = sc.nextLine();
 String friend = "";
 int j =0;
 while(str.charAt(j)!= ' ') 
 {
 friend = friend + str.charAt(j++);
 hs.add(friend); // add the name before the number to HashSet
 }
 j= j+2;
 invitation=invitation+str.substring(j)+" "; // remove name of John's friend from the string and store back remaining string
 } 
 int j =0;
 StringTokenizer st = new StringTokenizer(invitation); // divide string into tokens
 while(st.hasMoreTokens())
 {
 String str = st.nextToken();
 if(!hs.contains(str)) {
 /* check if token(string) is already in hashset ie if the person already friend with John or not 
 if he is not then print str 
 */
 System.out.print(str+" ");
 }
 }
 }
}

Answer 1

The big performance issue with the current solution is that you're relying on building a String to keep the list of persons that were sent a friend request. A String is immutable in Java so every single operation on it will result in the creation and allocation of a new String. When doing those sorts of repeated allocation in a loop, the performance degrades rapidly.

We need another approach to the problem that doesn't rely on a simple String, and with that, a better data structure.

1. From the problem description, we need to maintain a collection of the friends of John. To pick a suitable data structure, let's examine what we'll need to do with it: we want to add elements to it (each friend name read), and we want to check whether that collection contains a specific name (to not add it to the list of invited persons). Additionally, we don't care about a particular order for this collection. The perfect data structure for that is a HashSet, just like the one you used: it has a constant-time add and contains methods.
2. Then, we also need to maintain a collection of the invited persons, those that were sent the friend request. This is where you used a String and we can do better. Like the above, we want a data structure capable of adding elements (the name of the invited persons), but we also want it to be capable of removing elements (the friend names we might read further down the input). Also, we want to keep an order here, specifically, the order in which the elements were added. For that, LinkedHashSet is perfect: add and remove are both constant-time operations, and it keeps the insertion order.

With that in mind, we can refactor the code to use those data structures:

Collection<String> friends = new HashSet<>(); // to store name of the John's friends
Collection<String> invited = new LinkedHashSet<>();
for (int i = 0; i < N; i++) {
 Scanner scanLine = new Scanner(sc.nextLine());
 String friend = scanLine.next();
 friends.add(friend);
 invited.remove(friend); // potentially remove this invited as it is actually a friend
 scanLine.next(); // ignore the number of friends, we can deduce it anyway
 while (scanLine.hasNext()) {
 String name = scanLine.next();
 if (!friends.contains(name)) {
 invited.add(name);
 }
 }
}

Notice that I changed other things in there:

• When you have the line of input, that is space-separated, you don't need to read manually characters by characters. You can either split(" "), which would return an array of all the tokens space separated, or you can use another Scanner, which by default tokenizes over white spaces, meaning every call to Scanner.next() will return the next word.
• The variables have a meaningful name: friends represent the collection of John's friend and invited represents the collection of persons to whom John sent a friend request.

At the end of the process, we have our wanted collection inside invited, so we can finally print it. For that, we can use String.join starting from Java 8, which is built-in.

System.out.println(String.join(" ", invited));

If you are on a lower Java version, you would need to write the for loop explicitely and use a StringBuilder to construct the result, like shown here. Don't use the old StringTokenizer, it isn't officially deprecated but it is only kept for compatibility reasons and is considered a legacy class.

• Rajat Khandelwal: Thanks alot sir, your approach worked.. Learnt some important concepts from you.. Sir you did not answer my second question i.e. can we solve this question using Graphs or Trees?? If yes can you please elaborate your approach.. Thanks again sir :)
• Tunaki: @Rajatk95 Ah I missed that. But I don't really see how this could be solved more efficiently using a tree-like data-structure.