1	

Consider a system where users query for and buy Songs. The system stores the purchase transactions that have happened so far in the form of a tuple (Ux,Sy) form meaning User x bought Song y.

Question: Whenever a user reviews content of a song S1, we want to present the user the top 5 songs that other users have bought who also have bought song S1. The program should not terminate and after printing out the list of users, wait for the next input. The input could also be a purchase transaction which would necessitate updating the transaction history. Further details are given below

Input:
<transaction-history> This is the name of a file that contains all transactions that have happened so far in that system; this will be in the form of a text file which contains one transaction per line. Each transaction is a tuple containing the user ID and the song ID (both are 32 bit numbers) separated by a space. For e.g., line "123 452" (file contains no quotes) represents that user with ID 123 has bought song ID 452.
<purchase-history> This is the name of the file that contains the purchase transactions that have to be updated to the system. The format of this file is the same as that of transaction-history file.
<song-id> The current query - the song ID that is being queried

Output:
Top 5 songs (sorted in decreasing number of purchases of that song and separated by spaces) that other users bought who have also bought the song that was input

Design characteristics:
a. The transaction history can contain up to 1,000,000 transactions.
b. Every day on an average 100,000 users use the system to review content of some songs (not necessarily buy). Every user has got a unique ID and every song has got a unique ID.
c. The solution should work for 1,000,000 songs and 100,000 users.
d. Every day 100,000 users review song details
e. Every day 10,000 users buy songs. (means every day there will be 10000 purchase transactions)

Example: In this example there are 4 users and 4 songs and whenever a user selects a song one top other song that users bought when they bought the selected song is displayed (note: u and s are given below for illustration, the real file contains only numbers corresponding to unique user and song IDs)
Transaction history: (U1, S1), (U1, S3), (U2, S2), (U3, S3), (U3, S4), (U4, S1), (U4, S2) and (U4, S3)
song: S3 (only U1, U3, U4 bought this song)
output: S1 (was bought by U1 and U4, two people)

Commandline of the program

The program is invoked with the filename of the transaction-history file. After the transaction history is read into the program, program waits for input - which is of one of the following types:
1. query <song-id> command - will print to standard output the list of songs that other users bought who also bought this song (top 5 - sorted in decreasing number of purchases of that song); print a new-line after the list
2. purchase <purchase-file> command gives an input file that lists the latest purchases that have happened. The file has the same format as the transaction history. The program should update the history with the purchases listed in the file
3. exit command exits the program

An example run of the program could be as follows (the numbers are for illustration only)

problem1 history.txt
query 1907
12 23990 2311
query 67621
123 52322 5378
purchase pur0202.txt
query 9792
89023 3289 23424
query 2308
91 391 1 1232
exit 


2	

Design and implement an efficient algorithm to remove consecutive 1char, 2char, 3 char... so on recurrences in dictionary words.
For example, "abbabccbc" first will become "ababcbc", then become "abc". Similarly, "abcaab" will become "abcab" and but stays as it is after that. You need to output only the last string ("abc" and "abcab" for the above two examples).

The input to the file will be an ASCII string (of arbitrary size) from standard input and output string should be sent to standard output.

The commandline of the program will be as follows

problem3 <input-str>
For eg., problem3 abbcabcc



3	

Given a dictionary of words and a character set, design and implement the most efficient search model to retrieve all dictionary words for a given character set; for example, given a character set, {'o', 'd', 'g'}, "dog" and "god", "go" and "do" (but not "good" } are the words that would be output (considering that these words exist in the dictionary).

The dictionary is static and is input from a file present in the same directory as the program. The file is an ASCII text file with each word on a separate line. The words in the file are sorted in lexicographical order. Dictionary as well as the character set contains only English alphabets (upper and lower case not distinguished). There is no limit on the number of words in the dictionary, and you should make your program scale to large dictionaries. For example, the file could look like the following.


Aberration
Abrasion
An
And
...

The character set is given as a sequence of characters (with no separator between them). For example, it could be "odg" for a set that represents three characters 'o', 'd' and 'g'.

The output of the program should be written to an ASCII text file in the same directory sorted in lexicographical order, which contains all the dictionary words for a given character set - one word per line.

You can use the standard file I/O functions for your program.

The commandline of the program will be as follows

problem2 <input-filename> <character-set> <output-filename>

For eg., problem2 dict.txt odg output.txt