• 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

ADOBE Aptitude C Language Test

BFS (Breath First Search)

C++ OOPs Part2

Find if two rectangles overlap

LeetCode: Container With Most Water

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

How strtok() Works

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Diagonal Traversal of Binary Tree

Sequence Finder Dynamic Programming

VMWare Openings

Test Cases for Round Function

The greedy coins game Dynamic Programming

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

C Program for TAIL command of UNIX

Possible sizes of bus to carry n groups of friends

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

Facebook Interview Question : Interleave List

The Magic HackerEarth Nirvana solutions Hiring Challenge

Reverse a Linked List in groups of given size

Skiing on Mountains Matrix

Python Dictionaries

Closed Parentheses checker

Generate next palindrome number

Length of the longest substring without repeating characters

LeetCode: Binary Tree Maximum Path Sum

Count Possible Decodings of a given Digit Sequence

Python String and numbers

Binary Tree in Java

Stickler thief

Copyright © 2025 · Genesis Framework · WordPress · Log in