• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

April 27, 2015 by Dhaval Dave

With First look you think practical way of solving this question, and that is randomly taking a bolt and finding (by Looking at all nuts) perfect fit nut for it.
but does such logic to find approximate fit nut doing hit and try is possible in simple coding practice ?
No , so in order to achieve that what can be simple ways

Method 1) Brute Force Approach

Take a nut and find its pair bolt in all Bolts.
Complexity : O(n^2)

Method 2) Simple and Efficient

Sort all bolts and all nuts based upon diameter ..  All pairs will be automatically formed.
Nuts[i] <-> Bolt[i]. (as same diameter bolt and nut will fit )
But this will be inefficient as question is asked with least comparisons .
here comparisons  will increase (as You are sorting Nuts and Bolts both)
with less sorting complexity also it can be done if you use non-comparison based  methods.

Method 3)  With help of Map.

Algorithm :
1) Create a Map of  <diameter, Address of Bolt>
2) For all N nuts.
check diameter and search in map.
if diameter matches =   declare them both as pair
else print “no bolt for this nut”
3) end

With this simple algo you can find all pairs of nuts and bot in N comparisons only.

Similar Articles

Filed Under: Adobe Interview Questions, Interview Questions, problem Tagged With: Array, Hashmap

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Amazon Interview On-Campus For Internship – 1

Binary Tree Isomorphic to each other

Maximum size of square sub matrix with all 1’s in a binary matrix

Doubly linked list

Generate next palindrome number

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Right view of Binary tree

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

The Magic HackerEarth Nirvana solutions Hiring Challenge

Find Pythagorean Triplets in an array in O(N)

Length of the longest substring without repeating characters

Cisco Hiring Event 21st – 22nd Feb 2015

Maximum difference between two elements s.t larger element appears after the smaller number

Find min element in Sorted Rotated Array (With Duplicates)

Apriori algorithm C Code Data Mining

Python Dictionaries

Mirror of Tree

Add Sub Multiply very large number stored as string

Wrong Directions given find minimum moves so that he can reach to the destination

Printing intermediate Integers between one element & next element of array

flattens 2 D linked list to a single sorted link list

Sort an array according to the order defined by another array

Amazon Interview Experience – SDE Chennai

VMWare Openings

How Radix sort works

Minimum insertions to form a palindrome

Edit Distance ( Dynamic Programming )

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Diagonal Traversal of Binary Tree

Copyright © 2023 · Genesis Framework · WordPress · Log in