Thursday, March 8, 2012

Interview Question : Nuts and Bolts

Well one more question for interview which is regarding nuts and bolts.
So the question is::
What if you have 10 nuts and 10 bolts. Each nut with different size and matches with 1 bolt. So how will you find the exact pair?
Well, Very first solution comes in mind is:
We can use sorting based on there sizes and depending upon that it will be clear that which bolt matches which nut.

So, You have passed level 1, Now tell me the answer for same question. Now you are restricted, no sorting. How will you find the pairs?

Hmm, level 2. Find more options.
So we can compare each nut with each bolt and the pairs will be separated out once the match is found, and take new nut for the purpose of comparison with remaining bolts.

Yes, that can be one solution but think about the iterations. Is that proper?
So, so many iterations for comparing. Well this can not be the solution.

So again, think hmm... :/ ok...
Other solution can be...
Nuts and bolts. Randomly pick 1 bolt from the bunch and compare it with each nut(as we know the sizes are different). But while doing this separate out the nuts in 2 parts, 1 the nuts smaller than current bolt and other larger. And also the pair will be matched. Now next pick 1 more bolt and compare it with the previous bolt. if this bolt is small then we will have to check the smaller nuts part and if not then the other part.

But the same thing if we want to run on console(here I will use IRB), it will be something like
Solution 1 :
we can have 2 arrays, I mean creating 2 arrays 1 for Nuts and 1 for Bolts, for iterating.
And 1 array will iterated through loop and other array can be compared with each object.
If we need to convert it as program, just for example will take 2 arrays

nuts = [1,4,5,7,3,6,8,2,9,0]
bolts = ['3','5','7','9','2','8','1','6','0','4']
count = 0 # For counting the exact number of iterations
pairs = [] # separating out the pairs of nuts and bolts
nuts.each do |nut|
  bolts.each do |bolt|
    if bolt.to_i == nut
      pairs << {nut => bolt}
      bolts.delete(bolt)
    end
    count += 1 # for counting bolts iteration
  end
  count += 1 # for counting nuts iteration
end
So if now we type pairs and count we w
pairs
[{1=>"1"}, {4=>"4"}, {5=>"5"}, {7=>"7"}, {3=>"3"}, {6=>"6"}, {8=>"8"}, {2=>"2"}, {9=>"9"}, {0=>"0"}]

count
57

Solution 2 :
Here is this array of nuts, and bolts(again)..
I randomly picked up 1 bolt(say x) and compared with nuts. As each 1 is of different size some nuts will be larger than this current bolt's size and some will be smaller and only 1 will be of exact match.
So great, while this comparison with each nut the large and small nuts will be separated in 2 different arrays.
Can be named as big and small. Now when the pair is done. I will keep it separately.

Now again randomly pick one more bolt and will first compare with the first bolt x. If this new bolt is smaller than x then I will ask it to search it in small array of nuts and if larger then in big array.

For each new bolt we will have to compare it with x as the 2 arrays small and big arrays are made on comparison with x.

nuts = [1,4,5,7,3,6,8,2,9,0]
bolts = ['3','5','7','9','2','8','1','6','0','4']
x = bolts[rand(bolts.length)]
count = 0
pairs = []
big = []
small = []
bolts.delete(x)
y = 0

So we have declared some variables over here and now the real work.
nuts.each do |nut|
  if x.to_i == nut
     pairs << {nut => x}
     y = nut
  elsif x.to_i < nut
    big << nut
  else
    small << nut
  end
  count += 1
end

nuts.delete(y)

pairs
[{5=>"5"}]
big
[1, 4, 3, 2, 0]
small
[6, 8, 9]

Ok. Now we have 2 arrays ready for next step
bolts.each do |bolt|
  if bolt.to_i < x.to_i
    small.each do |nut|
      if nut == bolt.to_i
        pairs << {nut => bolt}
        small.delete(nut)
      end
      count += 1
    end
  else
    big.each do |nut|
      if nut == bolt.to_i
        pairs << {nut => bolt}
        big.delete(nut)
      end
      count += 1
    end
  end
  count += 1
end

Now if I type bolt it will show the pairs
[{5=>"5"}, {3=>"3"}, {7=>"7"}, {9=>"9"}, {2=>"2"}, {8=>"8"}, {1=>"1"}, {6=>"6"}, {0=>"0"}, {4=>"4"}]
and count will be 45 which is much lesser that previous count 57.
Note:: Considering the solution 2 if we get the largest/ smallest bolt, separating the nuts in 2 parts will not be possible. In this situation keeping the pair aside we will have to again start from the beginning.

No comments:

Post a Comment