Flipkart Interview Question
SDE-2sCountry: United States
Interview Type: Written Test
//
// BookCatelog.cpp
// BookCatelog
//
// .
//
#include<string>
#include<stdio.h>
#include<map>
#include<list>
enum category {A , B, C};
class Book
{
std::basic_string<char> name; // assuming to be unique
std::basic_string<char> author;
std::basic_string<char> publisher;
std::basic_string<char>publishing_date;
double price;
category category;
int count;
public: Book(std::basic_string<char> name,std::basic_string<char> author,std::basic_string<char> publisher,std::basic_string<char> publishing_date,double price,enum category category,int count)
{
this->name = name;
this->author = author;
this->publisher =publisher;
this->publishing_date = publishing_date;
this->price = price;
this->category = category;
this->count= count;
}
Book(Book &b)
{
this->name = b.name;
this->author = b.author;
this->publisher =b.publisher;
this->publishing_date = b.publishing_date;
this->price = b.price;
this->category = b.category;
this->count= b.count;
}
std::string get_name ()
{
return name;
}
int get_count()
{
return count;
}
std::string get_author_name()
{
return author;
}
Book()
{
name = " ";
author = " ";
publisher = " ";
publishing_date = " ";
price = 0.0;
category = A;
count = 0;
}
};
class TrieNode
{
public:
int value;
TrieNode* child[26];
TrieNode()
{
value = 0;
for(int i =0;i<26;i++)
child[i] = 0;
}
};
class Trie
{
TrieNode root;
int count;
public:
std::list<std::basic_string<char>> search(std::basic_string<char> book_name);
void insert(std::basic_string<char> key);
std::list<std::basic_string<char>> words(TrieNode t, std::basic_string<char> prefix);
Trie()
{
root = new TrieNode();
count = 0;
}
};
void Trie::insert(std::basic_string<char> key)
{
TrieNode t = root;
int i;
int length = key.length();
int index;
for(int i =0; i< length; i++)
{
index = key[i] - '0';
if(t.child[index])
{
t.child[index] = new TrieNode();
}
t = t.child[index]
}
t.value = count;
}
std::list<std::basic_string<char>> Trie :: words(TrieNode t, std::basic_string<char> prefix)
{
TrieNode curr = t;
std::list<std::basic_string<char>> list;
static int count = 0;
for(int i = 0;i< 26;i++)
{
if(t.child[i])
list.push_back(words(t.child[i],prefix[i]));
}
return list;
}
std::list<std::basic_string<char>> Trie :: search(std::basic_string<char> key)
{
TrieNode t = root;
int i;
int length = key.length();
int index;
std::basic_string<char> prefix = "";
std::list<std::basic_string<char>> l;
int count = 0;
for(int i =0;i<length;i++)
{;
index = key[i] - '0';
prefix += key[i];
if(!t.child[index] == 0)
{
break;
}
t = t.child[index];
}
//..
if(t.value > 0)
{
l.push_back(prefix);
return l;
}
else
{
l= words(t,prefix);
}
}
class BookCatelog
{
Book books[1000];
static int book_count;
std::map<std::string, int> book_name_map;
std::map<std:string,list<std::string>> author_books_map;
Trie book_name_tree;
Trie author_name_tree;
public:BookCatelog()
{
book_count = 0;
for(int i = 0; i< 1000;i++)
books[i] = new Book();
}
void addbook(Book b)
{
if(book_name_map[b.get_name()] > -1 )
{
(books[book_name_map[b.get_name()]].get_count())++;
}
else
{
books[book_count++](&b);
book_name_tree.insert(b.get_name());
author_name_tree.insert(b.get_author_name());
author_books_map[b.get_author_name()].push_back(b.get_name());
book_name_map[b.get_name()] = 1
}
}
};
Not complete...but it would give you an idea :
#include <iostream>
using namespace std;
enum category
{
science,
fiction,
biography
};
class Book
{
private:
string name;
string author;
string publisher;
int publish_year;
category book_category;
int price;
int sold_count;
public:
Book(string name, string author, string publisher, int publish_year, category book_category,int price, int sold_count)
{
this->name = name;
this->author = author;
this->publisher = publisher;
this->publish_year = publish_year;
this->book_category = book_category;
this->price = price;
this->sold_count = sold_count;
}
Book (Book &b)
{
this->name = b.name;
this->author = b.author;
this->publisher = b.publisher;
this->publish_year = b.publish_year;
this->book_category = b.book_category;
this->price = b.price;
this->sold_count = b.sold_count;
}
};
class trie
{
public:
bool index;
int map_index;
trie *list[256];
};
class trie_search
{
private:
trie *root;
trie* create_node()
{
int i;
trie *temp = new trie;
temp->index = false;
temp->map_index = -1;
for (i = 0; i<256; i++)
temp->list[i] = NULL;
return temp;
}
public:
trie_search()
{
int i;
root = new trie;
root->index = false;
root->map_index = -1;
for (i = 0; i<256; i++)
root->list[i] = NULL;
}
int add_node(string value, int map_index)
{
int i;
int str_len = value.length();
trie *temp = root;
for (i = 0; i < str_len; i++)
{
if (temp->list[value[i]] != NULL)
{
temp = temp->list[value[i]];
}
else
{
trie * new_node = create_node();
if(i == str_len-1)
{
new_node->index = true;
new_node->map_index = map_index;
}
temp->list[value[i]] = new_node;
temp = temp->list[value[i]];
}
}
}
int search_node(string value)//, string *result[])
{
int i;
int str_len = value.length();
trie *temp = root;
for (i = 0; i < str_len; i++)
{
if (temp->list[value[i]] != NULL)
{
temp = temp->list[value[i]] ;
}
}
if (temp->index == true)
cout << " \n yesss!!!";
}
};
class Book_catalog
{
private:
Book *books_list[1000];
trie_search trie_book_search;
int book_count;
public:
Book_catalog()
{
books_list[0] = new Book("one","auth1", "pub1",1980,science,50,200);
books_list[1] = new Book("two","auth2", "pub1",1980,science,50,200);
books_list[2] = new Book("three","auth3", "pub1",1980,science,50,200);
books_list[3] = new Book("four","auth4", "pub1",1980,science,50,200);
books_list[4] = new Book("five","auth5", "pub1",1980,science,50,200);
trie_book_search.add_node("one",0);
trie_book_search.add_node("two",0);
trie_book_search.add_node("three",0);
trie_book_search.add_node("four",0);
trie_book_search.add_node("five",0);
book_count = 5;
}
int add_book(string name, string author, string publisher, int publish_year, category book_category,int price, int sold_count)
{
books_list[book_count] = new Book(name,author,publisher,publish_year,book_category,price,sold_count);
book_count++;
return 0;
}
int search_book(string name)
{
trie_book_search.search_node(name);
}
};
int main()
{
Book_catalog book_cat;
book_cat.search_book("five");
return 0;
}
1. Store the books in a Map<BookId, Book>
- psyco May 14, 20152. Maintain a Suffix tree for the BookName and Author, Nodes will contain list of book ids, matching the suffix. If there is a match, return books for book ids at that node
3. Maintain a Max heap, with the sold count and book id