10 Replies - 2542 Views - Last Post: 24 February 2011 - 02:26 PM

#1 thursdayniac  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 255
  • Joined: 26-April 09

Interview Test Help

Posted 29 September 2010 - 02:55 PM

Hey guys, I have an in-person interview coming up and they gave me a written test to turn before hand.
I understand the policy of this forum regarding help on assignments... but I'm not asking anyone
to write anything.. I just want help understanding what they want.

Ok here's part of the first question:

Quote

Your first task is to design and implement an in-memory cache that has the following characteristics:

entries use an Object as the key and an Object as the stored value. Duplicate keys are not allowed

The cache supports a fixed number of total entries and does not grow. Rather, the cache will support various eviction strategies to removing old entries (least recently used, for example)

Supported operations of this cache include the following:

create(size) -- creates the cache with a maximum number of entries, specified by size

add(key, value) -- adds an entry to the cache, if an object already exists with the same key, replace the value with the new value, if the key does not already exist in the cache, then add the entry specified by key/value into the cache, evicting an existing entry, if necessary

get(key) -- retrieves the value of the entry specified by key or null if no entry exists

exists(key) -- returns true if an entry with key exists in the cache, false otherwise


And then they want me to implement 2 different evictions techniques..

So this is what I was thinking they wanted me to do:

store objects in a fixed size array and later implement a method for evicting
stored objects when the array is full.... am I on the right track?

One thing I dont understand from this is that is says: "entries use an Object as the key and an Object as the stored value"
I dont understand this... why do they use an object for the key? Cant the key just be an integer?
What do they mean by key? Do they want me to create a hashing algorithm? If not, could I just use the index of
each stored object as their key??


Another part that confuses me is the 3rd question, it says:

Quote

Now that you’ve gone through both implementation exercises, the final question focuses on design. Up to this point, we’ve assumed that the cache is a single in-memory cache that runs within the process of the client. This provides benefits such as low latency but also increases the risk of losing the cache if the client process were to crash. In this exercise, you should re-design the architecture of your cache implementation for robustness and high-availability


What do they mean by this? Do I have the first part of this test wrong?
What do they mean by: "robustness and high-availability"? Are they asking me to redesign
the program so that memory is not as much of an issue? I really don't understand this part.
Also, when they say design... what should I use to design this?

Is This A Good Question/Topic? 0
  • +

Replies To: Interview Test Help

#2 thursdayniac  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 255
  • Joined: 26-April 09

Re: Interview Test Help

Posted 29 September 2010 - 07:41 PM

Anybody? =(
Was This Post Helpful? 0
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,142
  • Joined: 14-September 07

Re: Interview Test Help

Posted 29 September 2010 - 08:31 PM

Looks like they want you to implement a HashMap. I would take some unique identifier or combo of identifiers for each object to use in the hash function. Then, since you have a set size, it looks like they want you to assign priority based on the last time it was used (in this context it means "accessed" to me).


Part Two basically says, now that you've played this game, how would change your design if the constraints were lifted and/or modified. In this case, we now have this HashMap that needs to be quickly available and generally crash/error free. "Robustness and high availability" seems to say "no memory constraints, but still be an efficient data structure".


All in all I would be surprised if they are actually looking for a/the "right answer", rather this is an exercise to get a glimpse of your thought process/problem solving abilities.


edit: I use the term HashMap as a blanket description for the <key,value> part of the assignment. It'll be a bit different since you'll be combining features of a priority queue with a HashMap of some nature.
Was This Post Helpful? 0
  • +
  • -

#4 thursdayniac  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 255
  • Joined: 26-April 09

Re: Interview Test Help

Posted 30 September 2010 - 12:00 AM

Thanks.. although I have another Q

Here is the actual 2nd question:

Quote

Developers using your cache implementation have found that they would like to be able to extract the eviction strategy as a plug-in provider rather than to deal with two distinct cache implementations. For this exercise, re-factor your existing cache implementations into a single implementation that supports an eviction plug-in provider. Then provide implementations for the LRU and random eviction providers.


What do they mean by plug-in provider??
Was This Post Helpful? 0
  • +
  • -

#5 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,142
  • Joined: 14-September 07

Re: Interview Test Help

Posted 30 September 2010 - 08:11 AM

It means your code should expect an extraction method but it's provided externally as a "plug in" to your program. At first thought, I would tell it to expect an interface of some kind (if you were doing this in Java per se); the plug in (written by you or whoever) would implement said interface.
Was This Post Helpful? 0
  • +
  • -

#6 thursdayniac  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 255
  • Joined: 26-April 09

Re: Interview Test Help

Posted 30 September 2010 - 08:24 AM

View PostKYA, on 30 September 2010 - 07:11 AM, said:

It means your code should expect an extraction method but it's provided externally as a "plug in" to your program. At first thought, I would tell it to expect an interface of some kind (if you were doing this in Java per se); the plug in (written by you or whoever) would implement said interface.


Ok thanks again... I pretty much did what you said... except I used an abstract class instead of an interface(using C#). Do you think this is OK?
I made the entire class abstract.. but I only made the method that needed to be overridden abstract... So basically all the person has to do it create a new class that inherits the base class and override the one function
Was This Post Helpful? 0
  • +
  • -

#7 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,142
  • Joined: 14-September 07

Re: Interview Test Help

Posted 30 September 2010 - 08:40 AM

Easiest way to test would be to write a couple plug ins and see how your system works. The definition of "OK" varies. It either works or doesn't. Then it's either efficient or it isn't. Then it's either "clean" or it isn't.

Once you get a workable prototype, then the shades of grey appear, not a moment sooner.
Was This Post Helpful? 0
  • +
  • -

#8 calvinthedestroyer  Icon User is offline

  • D.I.C Lover

Reputation: 167
  • View blog
  • Posts: 1,908
  • Joined: 13-October 07

Re: Interview Test Help

Posted 30 September 2010 - 09:15 AM

Very interesting, when they said "in-memory cache" I first thought of hardware design.
Was This Post Helpful? 0
  • +
  • -

#9 AlbuquerqueApache  Icon User is offline

  • D.I.C Addict

Reputation: 49
  • View blog
  • Posts: 523
  • Joined: 21-February 10

Re: Interview Test Help

Posted 04 October 2010 - 08:24 AM

View Postcalvinthedestroyer, on 30 September 2010 - 08:15 AM, said:

Very interesting, when they said "in-memory cache" I first thought of hardware design.



I was thinking some kind of a multidimensional array.
Was This Post Helpful? 0
  • +
  • -

#10 karthickanmani  Icon User is offline

  • New D.I.C Head

Reputation: -1
  • View blog
  • Posts: 1
  • Joined: 17-February 11

Re: Interview Test Help

Posted 21 February 2011 - 09:44 AM

Hi thursdayniac,
I got the same programming problem to do before the onsite visit. Would be mind giving me the idea how to approach the problem. I am trying to this in C#.NET. Do we have to create Hash map?...

This post has been edited by karthickanmani: 21 February 2011 - 09:49 AM

Was This Post Helpful? -1
  • +
  • -

#11 ForcedSterilizationsForAll  Icon User is offline

  • D.I.C Addict

Reputation: 33
  • View blog
  • Posts: 506
  • Joined: 16-July 09

Re: Interview Test Help

Posted 24 February 2011 - 02:26 PM

So you're asking for help without asking if he got the job? Brilliant!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1