• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Ganesh Patekar

Difficult University Assignment - Where to start ?

 
Ranch Hand
Posts: 46
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Apologies if this is in the wrong forum.

I would class myself as efficient at Java but awful at problem solving without a bit of help.

I just cant get the knack of breaking a problem into smaller steps and solving each step individually while testing in parallel.



(Just in case the image is difficult to read ... Link to larger picture )


I have a blank A4 page in front of me and no idea how to go about tackling this problem.

Any help on how to get started would be appreciated.
 
Bartender
Posts: 3517
150
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Kevin,

well, first things that come up to me are:

1) turn the different room Types into classes
2) make a List of the type of room that is cheapest when that room contains 1, 2, 3 or 4 persons.
3) ever heard of dynamic programming? You can apply that here. I won't give details here, but have a look at this topic: Dynamic Programming
Suppose that you have a grid with horizontally the number of persons 1, 2, 3, 4, 5, 6, 7, and vertically the Room Types?
 
Piet Souris
Bartender
Posts: 3517
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A hint, after my perhaps somewhat cryptic reply:

suppose you have the cheapest solution for a group of 1 person, 2 persons, 3 and 4.
Now, let the arrar a[] be such that a[k] contains the cheapest solution for a group of K persons.
It is clear what a[0] is. And also what a[1] is, given that you already have the cheapest solution for a group of 1.
Suppose person 2 enters the scene. Now, mr 2 can be given the cheapest solution for 1 person as well, total cost being 2 * a[1], but we can also put the two into th cheapest solution for a group of 2 persons.
What will a[2] be? And then mr 3 comes in. We can give him a[1] as well, now having a total cost of a[2] + a[1]. But there is another solution as well. What is that? And how do we continue?

 
Kevin Mckeon
Ranch Hand
Posts: 46
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've been doing a good bit of research into the topic of Dynamic Programming since your reply.

I want to get a good grasp of DP before tackling this problem.

I have a good understanding now of the Longest Increasing SubSequence Problem found here Link to Increasing SubSequence Problem

I have one question, does your method and hint above use the method of Memoization or Tabulation when finding the optimal solution. Is it possible to use both methods and still get a solution ?

Memoization vs Tabulation

 
Piet Souris
Bartender
Posts: 3517
150
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Kevin,

Kevin Mckeon wrote:I have one question, does your method and hint above use the method of Memoization or Tabulation when finding the optimal solution. Is it possible to use both methods and still get a solution ?

Memoization vs Tabulation


Well I didn't know these terms when it comes to DP, but your link is very clear about that (GeeksForGeeks is an excellent site for all kinds of algorithms, I've used it often myself).

I always use the Bottom Up approach, but it is certainly possible to do the Top Down way. I don't think it is more difficult, but as said I have never used it that way. Maybe if you have come up with a solution, that we discuss how to do it the other way?

One possible problem with the top down is that a recursion may lead to a StackOverflow, which happened to me lately. I was given an N-nary Tree (a Tree where each Node can have 0 to N nodes). Each Node had a value that was the sum of its autonomous value and the sum of all its Nodes underneath. Now, I had this implemented recursively, so all I needed was: topnode.getValue(), but of course that Tree I was given contained 100.000 Nodes, completely sequentiial. So I had to think of something else.
 
Kevin Mckeon
Ranch Hand
Posts: 46
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for the help but im sill having a few issues.

I've created a method (cheapestForN) to return the for the cheapest room for 1, 2, 3 or 4 persons.
But trying to fill the array by dynamic programming is proving difficult

Its had to describe over text so i've attached an image


(the maximum number of guests allowed in a room is in brackets beside the room number. Green number shows the cheapest option)

1. The cheapest room for one person is obvious (6117)

2. The cheapest room for two people is either going to be :
   a. The result of cheapestForN(2) = 6096 or
   b. Filling cheapestForN(1) with two people

3. The cheapest room for three people is either going to be :
   a. Filling cheapestForN(3) = 6145
   b. Filling cheapestForN(2) with three people
   c. Putting two people in room 6096 and one person in room 6117
   d. Putting two people in room 6096 and one person in room 6145
   e. Some other combination that I cant see at the moment

As far as i can see, moving from a[1] to a[2] onto a[3] and onto a[4] - the number of combination checks grow exponentially which defeats the purpose of dynamic programming

Even as I type I am beginning to see that the options i have put in bold above are not viable because of the results in a[1] and a[2]. Maybe i am doing it right after all.
 
Piet Souris
Bartender
Posts: 3517
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Kevin,

don't worry, DP doesn't come cheap, it takes quite some effort to get to grips with it.

It is a pity that you are using roomnumbers instead of amounts, since all I have is the limited list you showed in your opening post, and it makes it hard to follow. So, although I get the impression you are on the right track, I can't say for sure.

Let me show you how I would do it. And don't worry, we only have to take four combinations into account, instead of an exponentially grwoing number!

Let s[n] denote the cheapest solution when we put n persons into one room. If I am not mistaken, I get this list:

s[1] = 95
s[2] = 140
s[3] = 210
s[4] = 400

And let a[n] denote the cheapset solution when we are dealing with a group of n persons. So, a[0] = 0, since that costs nothing.

We get:

a[1] = s[1]
      = 95

a[2] = cheapest of a[1] + s[1] = 190
                   a[0] + s[2] = 140

a[3] = cheapest of a[2] + s[1] = 235
                   a[1] + s[2] = 235
                   a[0] + s[3] = 210

a[4] = cheapest of a[3] + s[1] = 305
                   a[2] + s[2] = 280
                   a[1] + s[3] = 305
                   a[0] + s[4] = 400

et cetera

And since there is no s[5] and higher, we only have to consider the four steps as in a[4]:

a[5] = cheapest of a[4] + s[1]
                   a[3] + s[2]
                   a[2] + s[3]
                   a[1] + s[4]

 
Kevin Mckeon
Ranch Hand
Posts: 46
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fantastic, this makes perfect sense. This is what I was getting near in my head but was struggling to get in down on paper.

I have one issue with your method though and I think the answer is probably straightforward with one additional check (or otherwise I'm wrong)


s[1] = 95
s[2] = 140
s[3] = 210
s[4] = 400

a[1] = s[1]
     = 95

a[2] = cheapest of a[1] + s[1] = 190
                           a[0] + s[2] = 140

a[3] = cheapest of a[2] + s[1] = 235
                           a[1] + s[2] = 235
                           a[0] + s[3] = 210

a[4] = cheapest of a[3] + s[1] = 305
                           a[2] + s[2] = 280
                           a[1] + s[3] = 305
                           a[0] + s[4] = 400

et cetera


Lets just say for arguments sake (without me actually changing the figures) that the four lines i have marked red above were the cheapest solution for a[1], a[2] , a[3], a[4]  

The problem arises when the room a[1] / s[1] only has space for two people.

By the time the algorithm is computing a[5],  s[1] would have been used in all the previous calculations hence the room would be full before a[3] is even calculated .

Isn't that right ? Or am I confusing myself even further
 
Piet Souris
Bartender
Posts: 3517
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A very good question, worth a cow!

All the s[1]'s that I mention need not be the same s[1]. If I look at the image in your opening post, I see that there are 20 s[1] rooms, and 20, 10 and 5 of the other rooms, and that the group is only 7 persons large. Therefore, the number of used rooms does not come into play here. If a[2] = s[1] + s[1], then I mean two different rooms s[1].

If the group of persons becomes larger than 20 (there are only 5 rooms that can contain 4 people), then we have to take the available rooms into account. How, I haven't given that a thought yet, Maybe that's the next assignment you will be facing!    
 
Kevin Mckeon
Ranch Hand
Posts: 46
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think ill leave that problem to another day ! But thanks for all your help - its been great. Ill post up the link to my Source code after I finish if people want to view it

One last question I have is - This question was given to us as an example of a typical interview question for a software developer

What level of developer would it be aimed at ?

And assuming it was given to applicants of all levels how far would they expect someone to get ?

A senior dev should be able to knock out a reasonable solution in a few hours I would guess.  I would class myself and somewhere between Junior and Intermediate developer but its difficult to know whats expected.

Its taken me a long time to get to a level where I understand and can now make a decent attempt to solve. But it would still take hours of work to come up with a solution without help!

My project has 5 files.
  • App - Does the dynamic populating the arrays and finding the cheapest values
  • Room - Room object
  • RoomUtils - Finds the cheapest room for 1,2,3,4 people and other methods
  • CheapestRoomObject - Stores the details of the cheapest room
  • FileUtils - Reads in the Excel file and creates a list of room Objects


  •  
    Piet Souris
    Bartender
    Posts: 3517
    150
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Kevin Mckeon wrote:What level of developer would it be aimed at ?


    I've never worked in the IT industry and never had to face interview questions like this. But we have quite some very experienced developers at CodeRanch, I hope they can answer this question.

    But if I look at the files you mention, I'd say with the very limited knowledge I have, that I could not do this in a couple of hours. I've never sofar had to read in an Excel file for instance, so before I could do that, I would have to download the Apache library, read the manuals, et cetera. I would not stand a chance in such an interview, I guess.
     
    Marshal
    Posts: 14049
    234
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Caveat: The comments below are my own perspective. They do not necessarily characterize what others might be looking for when screening potential hires using programming problems (although I know a few folks who share my perspective)

    When screening candidates, it's not so much about whether or not they come up with a working solution. That would be nice but it wouldn't be the point of having someone solve a problem like this. I would be more interested in some of the following:

    1. What's the candidate's problem solving approach? Is it logical? Systematic? Are they willing to try things and fail?
    2. What does the candidate do when they get stuck? Do they fire up a browser and Google? Do they ask relevant and probing questions? Do they ask for clarification?
    3. Is the candidate open to coaching? Do they seem coachable? That is, when given reasonable coaching, can they pick up and run with an idea quickly or do they need more help?
    4. Do they show good development habits? Do they unit test their work? Do they use a version control system like Git or Subversion? Do they Test-Driven Development? Do they refactor their code often for clarity?

    My "quick" auditions last for about a couple of hours, enough time to get a sense of the above. A longer audition might go for a whole day and will be reserved for candidates who show potential early and make me (and/or my team) want to explore their skills and character in more depth.
     
    Junilu Lacar
    Marshal
    Posts: 14049
    234
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    As for the problem itself, if I were looking for knowledge about DP because the actual work the candidate will be doing if chosen is related, then that's appropriate. Otherwise, I tend to use simpler problems that would allow a good  candidate to make consistent forward progress but is still non-trivial to allow me to see what I said I look for in my previous reply.

    In other words, since I don't usually need to solve DP-related problems on the projects I work on, I would probably use a simpler problem.

    I often start with a relatively simple problem that helps me quickly weed out those who don't have the kind of engineering discipline I look for and adherence to good coding practices like unit-testing and refactoring. I have found that it takes as few as ten lines of code to weed out 80% of candidates who just don't have the basic skills I'm looking for.
     
    Kevin Mckeon
    Ranch Hand
    Posts: 46
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:

    Let s[n] denote the cheapest solution when we put n persons into one room. If I am not mistaken, I get this list:

    s[1] = 95
    s[2] = 140
    s[3] = 210
    s[4] = 400

    And let a[n] denote the cheapset solution when we are dealing with a group of n persons. So, a[0] = 0, since that costs nothing.

    We get:

    a[1] = s[1]
          = 95

    a[2] = cheapest of a[1] + s[1] = 190
                       a[0] + s[2] = 140

    a[3] = cheapest of a[2] + s[1] = 235
                       a[1] + s[2] = 235
                       a[0] + s[3] = 210

    a[4] = cheapest of a[3] + s[1] = 305
                       a[2] + s[2] = 280
                       a[1] + s[3] = 305
                       a[0] + s[4] = 400

    et cetera

    And since there is no s[5] and higher, we only have to consider the four steps as in a[4]:

    a[5] = cheapest of a[4] + s[1]
                       a[3] + s[2]
                       a[2] + s[3]
                       a[1] + s[4]



    This looks like a fairly straightforward nested loops question on first look but when trying to program it its actually damn hard !

    How would you do this ? Nested loops gets very messy with i's and j's all over the place. Is there an easier structure to use ?

     
    Junilu Lacar
    Marshal
    Posts: 14049
    234
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    DP often involves recursion. My sense is that's what would work best for this kind of problem, and memoization to make recursion more efficient. Haven't tried solving it but I might give it a shot if I have some extra time on my hands.
     
    Piet Souris
    Bartender
    Posts: 3517
    150
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Here is a not so elegant solution:

    Note that this gives only the cheapest solutions and not the three cheapest solutions!


    @Junilu,
    the question was not to use DP. See Kevins opening post, where you can see that the exercise goes far beyond finding the cheapest solution. For instance, a big role is the quality of the solution. Then there is finding the three cheapest solutions instead of only the cheapest. The DP is not mentioned, it was a suggestion of mine. Another way would be to see this exercise as the famous coin problem, where we have in this case 4 coins of value 1,2, 3 and 4, and finding all the ways to write N as the sum of a combination of these values. Then giving a suitable cost-function to these combinations, and findig the cheapest ones.
     
    There are 10 kinds of people in this world. Those that understand binary get this tiny ad:
    Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
    https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!