Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is working code in C++.

#include <string>
#include <map>
#include <iostream>
#include <fstream>

typedef struct Node AdNode;

struct Node{
  int id;
  int bid;
  AdNode * next;
};

typedef struct siteNode {
  int id;
  int reserve;
  std::string name;
  AdNode *bestBid;
  AdNode *ads;
} site;

site* parse_site(std::string& line);
void add_ads(std::map<int, site*>& site_map, std::string& line);
void do_auction(std::map<int, site*>& map, int ad_id);
bool add_to_site(std::map<int, site*>site_map, int site_id, int id, int bid);
void print_sites (std::map<int, site*> site_map);

int main (int argc, char* argv[])
{

  if (argc < 3)
  {
    std::cout << "Usage: adserver [path_to_site_csv] [path_to_ads_csv]" <<std::endl;
    return 1;
  }
  std::map <int, site*> site_map;

  std::cout << "site = "<< argv[1] <<std::endl;
  std::ifstream s_file;
  s_file.open(argv[1]);
  std::string line;

  while(!s_file.eof())
  {
    std::getline(s_file, line);
    std::cout << "line = " << line << std::endl;
    site* new_site = parse_site(line);
    if (new_site)
    {
      std::cout << "site id = " <<new_site->id << std::endl;
      site_map.insert(std::pair<int, site*>(new_site->id, new_site));
 }
  }
  s_file.close();

  std::cout << "ads = " <<argv[2] << std::endl;
  std::ifstream a_file;
  a_file.open(argv[2]);

  while (!a_file.eof())
  {
    std::getline(a_file, line);
    add_ads(site_map, line);
  }
  a_file.close();

  print_sites(site_map);
  int ad_id;

  do {
    std::cout << "Input an add id:" <<std::endl;
    std::cin >> ad_id;
    do_auction(site_map, ad_id);

  }while(ad_id != 1);
  return 0;
}

site* parse_site(std::string& line)
{
  site* new_site = nullptr;
  int count = 0;
  size_t spos = 0;
  size_t pos = line.find(',', spos);

  while (pos != std::string::npos)
  {
    if (!new_site)
    {
      new_site = new site();
      new_site->bestBid = nullptr;
      new_site->ads = nullptr;
    }

    if (count == 0)
    {
      new_site->id = atoi(line.substr(spos, pos-spos).c_str());
    } else if (count == 1)
    {
      new_site->reserve = atoi(line.substr(spos, pos-spos).c_str());
    }
    spos = pos + 1;
pos = line.find(',', spos);
    if (pos == std::string::npos && spos < line.size())
    {
      new_site->name = line.substr(spos, line.size() - spos);
      std::cout << "name = " << new_site->name <<std::endl;
    }
  }
  return new_site;
}

void add_ads(std::map<int, site*>& site_map, std::string& line)
{
  AdNode* new_ad = nullptr;
  int count = 0;
  size_t spos = 0;
  size_t pos = line.find(',', spos);
  int num_sites = 0;
  int id;
  int bid;

  std::cout << "ad : " << line <<std::endl;
  while (pos != std::string::npos)
  {
    if (count == 0)
    {
      id = atoi(line.substr(spos, pos-spos).c_str());
    } else if (count == 1)
    {
      bid = atoi(line.substr(spos, pos-spos).c_str());
    } else if(count == 2)
    {
      num_sites = atoi(line.substr(spos, pos-spos).c_str());
    } else {
      int site_id = atoi(line.substr(spos, pos-spos).c_str());
      if(!add_to_site(site_map, site_id, id, bid))
      {
        continue;
      }

    }
    spos = pos + 1;
    count++;
    pos = line.find(',', spos);

    if (pos == std::string::npos && spos < line.size())
    {
      int site_id = atoi(line.substr(spos, line.size() -spos).c_str());
      if(!add_to_site(site_map, site_id, id, bid))
      {
        continue;
      }
std::cout << "id =  " <<site_id  <<std::endl;
    }

  }

}

void do_auction(std::map<int, site*>& map, int ad_id)
{
  std::map<int, site*>::iterator found = map.find(ad_id);

  if (found == map.end())
    return;
  site* s = found->second;

  if(s->ads && s->ads->bid >= s->reserve)
  {
    AdNode * winner = s->ads;
    int price;
    if (s->ads->next)
    { //more than one ads
      price =  (s->ads->next->bid >= s->reserve)?s->ads->next->bid: s->reserve;
    } else {
      price = s->reserve;
    }
   
    std::cout<< winner->id << " " << price << std::endl;
  } else {
    std::cout << "0 0" <<std::endl;
  }
}

void print_sites (std::map<int, site*> site_map)
{
  std::map<int, site*>::iterator it = site_map.begin();

  for (; it != site_map.end(); it++)
  {
    site* s = it->second;
    std::cout<<"site : "<< s->id << " reserve : " << s->reserve <<std::endl;
    AdNode * c = s->ads;
    while (c)
    {
      std::cout << "ad id : " << c->id << " bid : " << c->bid <<std::endl;
      c = c->next;
    }

  }
}
bool add_to_site(std::map<int, site*>site_map, int site_id, int id, int bid)
{
      std::map<int, site*>::iterator found = site_map.find(site_id);
      if (found == site_map.end())
      {
        return false;
      }

      AdNode * new_ad = new AdNode();
      new_ad->id = id;
      new_ad->bid = bid;
      new_ad->next = nullptr;

      site * site = found->second;
      std::cout << "adding a ad ( "<<new_ad->id<<") to a site : " << site->id <<std::endl;
      std::cout<< "add price: " << new_ad->bid <<std::endl;

      if (!site->ads)
        site->ads = new_ad;
      else
      {
        AdNode* current = site->ads;
        AdNode* prev = nullptr;
        while (current)
        {
          if (new_ad->bid > current->bid)
          {
            new_ad->next = current;
            if (prev)
              prev->next = new_ad;
            else
              site->ads = new_ad;
            break;
          } else if (new_ad->bid == current->bid)
          {
            if (new_ad->id < current->id)
            {
              new_ad->next = current;
              if (prev)
                prev->next = new_ad;
              else
                site->ads = new_ad;
              break;
            }
          }
 prev = current;
          current = current->next;
        }
        if (!current)
          prev->next = new_ad;
      }
    return true;
}

- hankm2004 April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@hankm2004, please describe the performance of your adserver: Time and Space complexities

- neoh1b April 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let say there are N sites and M ads.
Assume that parsing the text file is trivial.

For build initialization take two steps:
- build hash table going through sites: O(N)
- Adding one ad to hash table:
1) Finding site: O(1)
2) Adding to Site: worst case O(M) (if one site has all M Ads)
- I could optimize that by searching up to second node since what we need for the actual operation is the highest and second highest node. In that case,
I will be O(1)

Therefore, adding ads to site hash table would take O(M*M) worst case, O(M) best case.

Storage complexity will be O(NXM) for the first case, O(N) for the optimized case.

For the actual searching for adds given site id, it would be O(1)

Is it enough ?

- hankm2004 April 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For starters If I were to do this in Java:
Algo:

Site_Map

Create a Dictionary/HashMap of All the Site_ID<Key> An their Price

Ad_Map:

Create a Dictionary/HashMap of All the Ad_ID<Key> and the Ammount they Have

Site_to_Ad Map:

Create a Dictionary/HashMap of All the Site_ID<Key> and the Ad_IDss Interested to be on them.

Iterate through the Site_to_Ad Map.
Fetch the Ammount for Each ad from the Ad_Map and let the add with highest bid win.
Add Constraints to the Auction block.

How do we do this in C

- chaos April 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@hankm2004 Can you please add some comments in your code so that I can understand it better. I am a java developer trying to implement a C++ solution, also the comment will help me understand the approach better.

- chaos April 16, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More