Question
Please someone explain how to set up the memory for this problem. I have no idea where to start Friendship You are working on a
Please someone explain how to set up the memory for this problem. I have no idea where to start
Friendship You are working on a social network site called FriendWork. It was not your first choice, but it will have to do. You are going to write the backend of the website for this assignment. The backend of the website needs to manage the users and their friendships. You need to be able to add a friend ship, remove a friendship, and print out the friend(s) for a particular user. You can assume that friendships go both ways, i.e. if A is friends with B, then B is also friends with A. Input Specification The input will begin with an integer q (q 500,000), number of queries to your webpage. The next q lines will each contain 1 server query. There are 3 query types. The first query type is the add query. The add query will begin with the word ADD followed by two names, a and b. The word ADD and the names will all be separated by a single space. This query implies the people named a and b have become friends. The second query is the remove query. The remove query will begin with the word REMOVE followed by two names, a and b. The word REMOVE and the two names will be separated by a single space. The remove query will denote that user a and b are no longer friends. The last query type is the list query. The list query will begin with the word LIST followed by one name, a, representing the user we wish to list the friends of. Each name will be at most 100 lower case characters and will contain no whitespace. No user will become a friend of themselves. No user will remove themselves as a friend. If a friendship is added, it will be between two users that are currently not friends. If a friendship is removed, it will be between two users that are currently friends. Output Specification For each list query print out on a line by itself the number of friends the user has. After which print out the names of each friend of the given user (in any order) each on their own line. For this assignment, your method does not need to worry too much about runtime efficiency as much as memory efficiency.
Advice My solution to this problem incorporates a fair bit of memory structure I used an array list of array lists of strings for one solution and an array list of array lists of integers for a different one. Either way I needed to create functions for both type of array lists. To implement the data structure for my string-based solution I used the following structs and prototypes, // Array List of strings typedef struct SmallList { int size, cap; char ** arr; } SmallList; // Array List of Array List of Strings typedef struct BigList { int size, cap; SmallList * arr; } BigList; // Prototypes for the Big Array Lists BigList * createBig(); void expandBig(BigList *); void add2Big(BigList *, char * val); // Prototypes for the Small Array Lists void expandSmall(SmallList *); void initializeSmall(SmallList *); void add2Small(SmallList *, char * val); // Method to find an index for the given string int getInd(BigList *, char * val); In terms of data management, in each small array list I store in index 0 the name belonging to a particular user. Each name in indices greater than 0 of the small array list represent the friends of the user store in index 0. For example, if Alice is friends with Bob and David, then there would exist a small array list within the big list that would have the following values,
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started