Given billions of text messages and a list of keywords. design the index for the messages in order to efficiently retrieve messages that contain given keywords. Suppose each message can be identified and retrieved by a unique sequence number.\n\nTask 1: Design data structure to organize the keyword index.\nTask 2: How to search messages that contain a single keyword.\nTask 3: How to search messages that contain multiple keywords. Optional coding: implement the method.\n\nMy solution - \nLet\'s form a trie with given keywords. Then pick up each message one by one and search it\'s words in trie. This way form a map of [Keyword , {messageId1, messageId2,...}]\nBut, interviewer said number of messages are in billions so we can\'t store these many messageIds in a map. \n\n\nCan anyone think of a better solution?\n\n\n

Given billions of text messages and a list of keywords. design the index for the messages in order to efficiently retrieve messages that contain given keywords.