Cisco Systems Interview Question for SDE-2s


Team: Video processing capabilities
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 5 vote

answer for this question is variation of QUICK SORT.

lets there are n bolts and n nuts, you can compare nut with bolt and can tell whether bolt is smaller, bigger or equal to nut.

1. lets take a random nut and compare with all bolts. after this exercise you will get one match that will fit with nut, one group of bolts those are bigger than nut and another group which is smaller than nut.
2. now compare the matching bolt with all other nuts in the same group, here also we get two groups.. one is bigger group and another is smaller group
3. finally we get one nut-bolt match and one group of nuts and bolts those are smaller than the match nut-bolt and another group of nuts and bolts those are bigger than the match nut-bolt combination
4. now apply recursion on both smaller and bigger groups... do this till all matches found
5. finally we get nut-bolt match combinations and also those are sorted.

time complexity is O(n log n).

- algos July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

@algos

Good one.

I think step 2 can be modified a bit to reduce the number of overall comparisons. .
Once the first matching bolt is placed in its correct position, take a 2nd nut at random and compare it with the first matching bolt. Based on the result, match the nut with bolts in either smaller group or bigger group.

Take a 3rd nut at random and based on the comparisons with the first and second matching bolts, compare it with bolts in the appropriate sub groups. Continue this until all nuts are matched.

This obviates the need to compare a matching bolt with all of the remaining nuts to divide them into sub groups. The nuts themselves don't seem to be required to divide into subgroups.

- Murali Mohan July 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1. This is a classic problem invented by G.J.E. Rawlins. The key point is that the solution is a "randomized" quicksort, where the nuts and bolts are picked randomly and therefore expected running time is Big-Theta(n log n). Randomness element in the solution is important, I think that's why @D,tox'mi's points are important, otherwise just like quicksort, this solution performs O(n^2) worst case, so +1 for D,tox'mi's comment too.

- oOZz July 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@algos

Stop up-voting yourself, you shameless fellow. I saw the following notification on 'What's Going On' section, when you were up-voting yourself.

>> algos up-voted algos's comment: answer for this question ...

- Anonimus July 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hey, your solution ultimately replies on the fact that for any nut there is a bolt that matches it, but I think this assumption is not true for all the bolts, at least since N is not M. You could get around this by using a random algorithm which keeps looping until one bolt is found such that it has a matching nut, but then what if only 1/10 of the nuts have matching bolts? So 9/10 of the times your step 2) which relies on the *existence* of a match is very inefficient.

- Chih.Chiu.19 July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@Ananimus: stop this non-sense talk, and contribute for better discussion... just go and check self voting is disabled and that will not count for voting...

- algos July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Ayahuasca: in 2nd point compare matching bolt with all other nuts, does not means that every time it compare all n elements for each recursive call.. we will be applying recursion in each sub group, so only that subgroup exists during that run so it will compare with all elements in that subgroup only.

- algos July 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We know sizes , first sort n nuts than compare it with each bolt which gives O(mlogn)

- pirate July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We don;t know sizes.. Only compare function is present. He asked me the question with sizes initially, so once i answered, he changed the question to compare function..which will return -1.0,1

- ronnie July 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, count the number of nuts and bolts with linear time, then do a randomized quick sort on the longer sequence. Does it work?

Sorry, just realized that "you cannot compare the sizes of two nuts or two bolts directly."

- koppie644 November 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can obtain the sizes as inputs in character array and return the result using strcmp function...

- ram rs July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the problem is as written, the answer is no. Consider the following edge case: there are big bolts and small nuts, except right in the middle there is one match (a medium bolt and and medium nut). Then the compare function always returns +1, except for that one match, where it returns 0. So basically we get no information from the compare function, except when we get lucky. It takes potentially O(mn) time to find that match.

- Charles Dietrich July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

o(nlogn) solution

/*
Developed By :Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
using namespace std;
int i_length;
void Print(int *a , int *b){
	for( int i=0 ;i<i_length ;i ++)
		std::cout<<a[i];
	std::cout<<std::endl;
	for ( int i=0 ; i<i_length ; i++ )
		std::cout<<b[i];
}

int Break( int *array , int i_start , int i_end ,int i_pivot){
	int i=i_start - 1;
	int temp;
	while ( i_start != i_end ){
		if ( array [ i_start ] == i_pivot ){
			temp=array[ i_start ];
			array [ i_start]=array [ i_end ];
			array[ i_end ]=temp;
		}

		if ( array [ i_start ] < i_pivot ) {
			temp=array [ i_start ];
			array [ i_start ]=array [ ++i ];
			array [ i ]=temp;
		}
			
		
		i_start ++;
	}
		temp=array [ ++ i ];
		array[i] = array [ i_end ];
		array [i_end]=temp;
		return i;
}
			

int count=0;
void Quicksort( int *array , int i_start , int i_end , int *b){
	while (  i_start < i_end ){
		int k=Break( array , i_start , i_end ,b[i_start]);
		Break( b , i_start , i_end , array[k] );
                count ++;
		Quicksort( array , i_start , k-1 , b );
		Quicksort( array , k+1 , i_end, b);
		return ;
	}
	return ;
}
int main(){
	int b[]={0,9,1,6,7,4};
	int a[]={4,7,1,6,0,9};
            i_length=6;
	Quicksort( a, 0 , i_length-1 , b);
	Pr int( a , b );
	}

Output

suman@suman-laptop:/media/D/coding/algo/search$ ./a.out 
014679
014679

- email.suman.roy July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a classic problem invented by G.J.E. Rawlins. Here is the solution:

w w w.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html

- oOZz July 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

From "The Algorithm Design Manual":

Stop and Think: Nuts and Bolts
Problem: The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different widths, and n corresponding nuts. You can test whether a given nut and bolt fit together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts are too small to see by eye, so you cannot compare the sizes of two nuts or two bolts directly. You are to match each bolt to each nut.
Give an O(n2) algorithm to solve the nuts and bolts problem. Then give a randomized O(n log n) expected time algorithm for the same problem.

Solution: The brute force algorithm for matching nuts and bolts starts with the first bolt and compares it to each nut until we find a match. In the worst case, this will require n comparisons. Repeating this for each successive bolt on all remaining nuts yields a quadratic-comparison algorithm.

What if we pick a random bolt and try it? On average, we would expect to get about halfway through the set of nuts before we found the match, so this randomized algorithm would do half the work as the worst case. That counts as some kind of improvement, although not an asymptotic one.

Randomized quicksort achieves the desired expected-case running time, so a natural idea is to emulate it on the nuts and bolts problem. Indeed, sorting both the nuts and bolts by size would yield a matching, since the ith largest nut must match the ith largest bolt.

The fundamental step in quicksort is partitioning elements around a pivot. Can we partition nuts and bolts around a randomly selected bolt b? Certainly we can partition the nuts into those of size less than b and greater than b. But decomposing the problem into two halves requires partitioning the bolts as well, and we cannot compare bolt against bolt. But once we find the matching nut to b we can use it to partition the bolts accordingly. In 2n − 2 comparisons, we partition the nuts and bolts, and the remaining analysis follows directly from randomized quicksort.
What is interesting about this problem is that no simple deterministic algorithm for nut and bolt sorting is known. It illustrates how randomization makes the bad case go away, leaving behind a simple and beautiful algorithm.


- rotinom July 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It it correct if we move in 2 directions one from 0 to n-1 and another from n-1 to 0 in both bolts and nuts and compare and store the equals into another 2 arrays in their respective order..
p---------q

i-----------j

compare
p&i
q&j
p&j
q&j

- Unknown July 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cisco gives hike once in 2-3 years.

New-Joinees only get hike after 2-3 years, so take 100% hike at the time of joining .. . otherwise don't cry after joining. :)

- Simple April 25, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More