• Post Reply Bookmark Topic Watch Topic
  • New Topic

Interview Question  RSS feed

 
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Following is the interview question which I faced most of the time.
I have a requirement where i have to design classes for Pencil type, let say Natraj Pencil and Camel Pencil.
So I designed classes as follows

But the next question that they asked me,
"What if we want to add one more type say Wilson Pencil?"
Are you going to create one more class? If yes then suppose we have thousands of pencil type so are going to create thousand classes for that.

Is anyone having idea to fix above design as per the requirement?

Next question they asked me
Let assume we have an Array of 101 element from number 1 to 100. And only one element duplicate. How did you find that duplicate code.
My Answer: - I said that I will use nested loop

But they expected good solution with good performance
 
Ranch Hand
Posts: 49
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, for the first question: Does every of the thousand pencils really need to be represented by its own class?
Assuming you could auto-create new classes: If every pencil is different, you still need to add different class methods or
variables manually. If they are not different, why would you need a extra class for eachone?


For the second question: You could loop only once through the array and add each element to a List by checking
if List.contains(element) already. As soon as that if block returns true, you have the duplicate. So maximum
amount of iterating (worst-case) is arraysize, if the duplicate is the last element.
 
Bartender
Posts: 4568
9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jon Avadis wrote:For the second question: You could loop only once through the array and add each element to a List by checking
if List.contains(element) already. As soon as that if block returns true, you have the duplicate. So maximum
amount of iterating (worst-case) is arraysize, if the duplicate is the last element.

Using a HashSet will be faster. If you use a List then you're effectively using a nested loop, you're just not implementing the inner loop yourself. But contains in a HashSet can be up to constant time, if the hash code is suitable.
 
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If the array is already sorted you can check at regular intervals if the index matches the value. You start with the center (element 49). Its value should be 50. If it is, check the upper half (as all values before there will be valid as well), otherwise check the lower half. Continue until you find the erroneous element.

This way of finding will be of order O(log n), but the sorting is O(n log n). If the sorting is necessary it will be slower than a single loop, but still faster than a nested loop.
 
Jon Avadis
Ranch Hand
Posts: 49
Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:If you use a List then you're effectively using a nested loop, you're just not implementing the inner loop yourself.


Arrgh, i didnt think of that. Ill check out the HashSet you mentioned.
 
Ranch Hand
Posts: 164
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd think that all those pencils share the same attribute set i.e name, shape, size, color, etc so you would not require more than one class with a constructor that accepts these attributes, so instead of doing You'd say

As for the second question: Since all the elements are between 1 and 100 you could simply create an empty array of size 100, loop through the original array and copying each element into the empty one where element with the value X gets copied into index X-1 ([0] => 1, [1] => 2, etc) if the index you are trying to copy too is non-empty you've found yourself the duplicate.
 
Rob Spoor
Sheriff
Posts: 21135
87
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Which will not work if the duplicate number is 0, unless you initialize the second array with a -1 value at index 0. The remaining values can remain at 0.
 
Unnar Björnsson
Ranch Hand
Posts: 164
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Rob Spoor wrote:Which will not work if the duplicate number is 0, unless you initialize the second array with a -1 value at index 0. The remaining values can remain at 0.


The numbers range from 1-100 so no zeros
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shahid Pathan wrote:Let assume we have an Array of 101 element from number 1 to 100.

I'd ask them how they got 101 elements into something with only 100 slots...

But seriously...I'd ask more questions first. Is this a one-off project? will i later need to need to find a duplicated element in a list of 1000 or 1,000,000? What is more important to them - speed or memory? If i am on a mobile device, memory restrictions may prohibit the use of duplicating each and every element into a HashSet...although you could possibly get the hashvalue as a key and simply stick in a dummy object...

Sometimes, the efficiency lost by using nested loops is outweighed by the speed of development.
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Unnar Björnsson wrote:The numbers range from 1-100 so no zeros

But do you really want to develop a solution that relies on that, when other simple solutions are available that can cope with any distribution of values?
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Unnar Björnsson wrote:I'd think that all those pencils share the same attribute set i.e name, shape, size, color, etc so you would not require more than one class with a constructor that accepts these attributes


Very possibly. This is another case where you need to ask some more questions. What is specialabout the different types of pencil? Can they be described simply by different attribute values, or do some of them have additional properties, or radically different behaviour?
 
Shahid Pathan
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to all. Just I want to mention that, all are interview question. As i know they will give small requirement and they test how you design or solve and later they will cross question.


I have given above solution, but they asked another question. Let say I want to call a function only when type is "NatrajPencil" then you have to write n no of if else to find the type first which is not feasible.
 
Unnar Björnsson
Ranch Hand
Posts: 164
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:
Unnar Björnsson wrote:The numbers range from 1-100 so no zeros

But do you really want to develop a solution that relies on that, when other simple solutions are available that can cope with any distribution of values?

This is just something that I thought up in an instance, it fits this particular problem since this particular range of numbers is specified, but in general I wouldn't do it like this.
 
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
im way out of my league here, but i was wondering, couldnt you just use a pencil() object?
like:
and then just call 1000 pencil objects instead of using 100 classes?
I very new to this, but im curious as to why this wouldnt work.
 
Sheriff
Posts: 22845
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wes McClintock wrote:I very new to this, but im curious as to why this wouldnt work.


Well, it might. The question to ask would be "Do we need subclasses of Pencil? Why?" The answer might turn out to be "Yes, because..." but we know nothing about the application for which we designed this Pencil class in the first place. And neither does anybody else, not even the interviewer. The interview question is designed to elicit intelligent comments (even yours qualifies for that) rather than to produce a system design.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!