1. Suppose you are implementing the address book feature for a cellphone. The address book needs to be kept sorted by person’s last name and support fast access when queried by last name. Which of the following data structures would be a good choice to use for storing the address book? Explain why. Which would be the bad choice and why? a. unsorted linked list (b) sorted linked list b. binary search tree (d) hash table.
2. Write an algorithm to remove duplicate lines from a text file.
3. Write an algorithm to find the sum of n elements after a kth smallest element in Binary Search Tree.
1. Suppose you are implementing the address book feature for a cellphone. The address book needs to be kept sorted by person’s last name and support fast access when queried by last name. Which of the following data structures would be a good choice to use for storing the address book?
Ans. Good choice would be
b) binary search tree --> insertion, deletion and
search would be O(log n).
d) hashtable --> insertion, deletion and search
would be O(1)
Bad choice would be
a)unsorted linked list ->insertion, deletion and
search would be O(n)
b) sorted Linked list -> insertion, deletion and
search would be O(n)
2. Write an algorithm to remove duplicate lines from a text
file
Ans. Use either Set or HashMap
Explaination:
SInce Set always keep unique element or data.(Keep sentence as
element)
and HashMap key always a unique value(Keep sentence as
key)
Algorithm for HashMap
----------------------------
let n<- total lines of text file
for(line 0 to line n)
if(map has not line)
add this
Algorithm for Set
----------------------------
let n<- total lines of text file
for(line 0 to line n)
add to set
Since set has property if element has duplicate value, it will skip
to insert giving value false means insertion failed.
3.Write an algorithm to find the sum of n elements after a
kth smallest element in Binary Search Tree.
Ans: Do Inorder traversal in reverse way. To track the kth element,
put counter. For reverse, use stack.
Algorithm:
INITILIZATION:
let K = kth element
startPointer = root
SET STACK = null
// Traverse in left only
while(startPointer is not null )
stack.push(startPointer)
startPointer = startPointer.left
//Look others
while( startPointer = stack.pop() is valid )
stop if kth number of elements are popped.
if( startPointer.right is valid )
startPointer = startPointer.right
while( startPointer is valid )
stack.push(startPointer)
startPointer = startPointer.left
END
1. Suppose you are implementing the address book feature for a cellphone. The address book needs to be kept sorted by pe...
Suppose you are implementing the address book feature for a cellphone. The address book needs to be kept sorted by person’s last name and support fast access when queried by last name. Which of the following data structures would be a good choice to use for storing the address book? Explain why. Which would be the bad choice and why? a. unsorted linked list (b) sorted linked list b. binary search tree (d) hash table
Interfaces 1. What is inside an interface definition? What does a class do to an interface and what keyword is involved? How does a class do this to an interface (what should we find in the class)? Can an interface have a generic parameter? How do you instantiate an interface as an object? What methods can’t you use on an interface type? Abstract Data Types 2. What does an ADT define? Does an ADT specify programming language and/or data structures...
SHORT ANSWER QUESTIONS Part 1 Classes Abstraction: What is Abstraction in terms of representation? Specifically what choices does one make when creating a class that is an example of Abstraction? Encapsulation: What is encapsulation? What is information hiding? What does a public interface to a class consist of (not in the sense of actual java interfaces but what the client uses to manipulate objects of the class) What is an object of a class? What is the constructor? How do...
Can you please help with the below? 1) Which of the following is true about using a 2-3-4 tree? a. It is designed to minimize node visits while keeping to an O(log n) search performance b. It is designed to self-balance as new values are inserted into the tree c. As soon as a node becomes full, it performs the split routine d. None of the above 2) Which of the following is true about a binary search tree? a. ...