I am given a sequential algorithm that does a routine search
on an unordered list. N = 20.
The probability that the value x does NOT appear in the list
is exactly 60%, and the probability that x DOES appear is 40%.
The 3 questions that I could not get were:

A) What is the avg number of element comparisons performed
when n = 20 and x does NOT appear in the List.
(my answer was 20, is this correct?)

B) What is the avg number of element comparisons peformed
when n = 20 and x DOES appear in the list?

C) What is the avg number of element comparisons performed
when n = 20. This should be a single number answer they said.

Answers were Sorted based on User's Feedback



I am given a sequential algorithm that does a routine search on an unordered list. N = 20. The pr..

Answer / guest

a) 20 worst case scenario so it will take N comparison
b) 10 average case scenario N/2 omparisons
c) 16 (20*0.6 + 10*0.4 = 16) as stated above

Is This Answer Correct ?    17 Yes 1 No

I am given a sequential algorithm that does a routine search on an unordered list. N = 20. The pr..

Answer / ranjit

The second answer is partially correct.

a) 20. It will take 20 comparisons to determine that x does not appear in the unordered list of size N.

b) Assuming that x is equally likely to be in any of the 20 positions in the list, the average number of comparisons will be (1 + 2 + ... + 20)/20 = 10.5.

c) 20*0.6 + 10.5*0.4 = 16.2

Is This Answer Correct ?    9 Yes 0 No

I am given a sequential algorithm that does a routine search on an unordered list. N = 20. The pr..

Answer / bond

A) What is the avg number of element comparisons performed
when n = 20 and x does NOT appear in the List. (my answer
was 20, is this correct?)

è I guess 12.

B) What is the avg number of element comparisons peformed
when n = 20 and x DOES appear in the list?

è I guess 8.

C) What is the avg number of element comparisons performed
when n = 20. This should be a single number answer they
said.

è I guess 8.

Is This Answer Correct ?    5 Yes 10 No

Post New Answer

More Data Structures Interview Questions

Do you know how to find if linked list has loop?

0 Answers  


What is mean by abstract data type?

0 Answers  


What is the purpose of thread?

0 Answers  


How does insertion sort works?

0 Answers  


Why do we use hashset?

0 Answers  






What is complexity of bubble sort?

0 Answers  


Is unordered_map a hash table?

0 Answers  


What are data and data types?

0 Answers  


How is any data structure application is classified among files?

0 Answers  


What is a node in it?

0 Answers  


List some applications of tree-data structure?

0 Answers  


Which is faster array or linked list?

0 Answers  


Categories