Cool Summer 2012 Internship Problem Set 2

We had very interesting surprises last week, therefore we want to encourage you to innovate!

Do not forget about the rules. The deadline to submit your solutions is Monday, April 9th, 9:00 AM GMT. Results must be submitted here. Don’t forget, you can work in small teams!

Problem 1: Meet Me!

Design and implement an address book application for a mobile device with limited memory. The application should be able to display the values in alphabetical order. The mobile device has support for your favorite programming language.

What you have to do

  • Send us a document describing the algorithms, specify the algorithm complexity, the data structures used for storing the contacts, and the design trade-offs.
  • Construct a prototype.

Suggestions

  • On mobile devices, you want to keep as much memory as possible available for data storage.
  • The application should be fast enough because it is frequently used.

Problem 2: Distributed Log System

Assuming you have multiple nodes with multiple services spread in your network, you want a method of collecting logs from all those services.

What you have to do

You are requested to design a distributed log system that meets criteria:

  • scalability (you can log from one node or from 10000 nodes, it should not matter)
  • consistence (log data can uniquely be tied to a (hardware) node, a service, a moment in time, etc)
  • availability (logging function is critical in your infrastructure)
  • redundancy (no single point of failure)
  • statistics and analysis friendly (the logging format should be easily processed by applications)
  • granularity (depending on gravity the messages should be labeled/used differently)
  • small footprint (on host and network level)
  • data storage is taken into account (the storage should be as light, yet complex enough to respect the criteria above)

Suggestions

  • Innovate, you should not be afraid of untypical solutions.
  • Consider network, service and nodes failures.
  • The communication protocol is important!
  • Think to a language specific implementation (C, C++, PHP, JS, Python, Ruby, Java, C#) for the designed system.

If you can build a prototype, this is big plus! You may publish it on github, bitbucket or any other similar service.

We wish you a very, very productive weekend!

5 Comments

You can post comments in this post.


  • At problem #1: it is necessary to fully implement the address book to the point where it can be fully tested? For example there are some operations on mobile phones that you cannot be simulated on this prototype unless it’s an actual phone app (like an Adroid app built in Java). One such operation is simply scrolling down the contact list screen and there could be design ideas which could use this “feature” of phones :).

    Răzvan Botea 13 years ago Reply


  • Nope, it’s not necessary because it depends on the phone. However, when you have a list of objects (eg: contacts), you must have an iterator (for example) in order to scroll through them. We want to see in your prototype that you designed it on an abstract level taking into account the constraints.

    Andrei 13 years ago Reply


    • What format should the document have? I’m thinking of using Office Word 2007+ docx for making a real project report :).

      Răzvan Botea 13 years ago Reply


  • No preference. BTW, we hate using Office for this purpose. 🙂 But we are not going to lower your score due to Office.

    Blog wizard 13 years ago Reply


    • I have no problems in accommodating to any document editor :). It’s that that’s what I have at the moment (not going to use vim plain/text), but I will send the document in PDF format.

      Răzvan Botea 13 years ago Reply


Post A Reply