A research student is given a singly-linked list. Each node
of the list has a color, which is either “Black”
or “White”. He must find if there are more black nodes than
white nodes, or vice versa. His advisor
gives him 5,000Rs to buy a computer to do the work. He goes
to the computer store and finds a
slightly defective computer which costs a mere 3,000Rs. This
computer has the small problem of not
being able to do arithmetic. This means that he cannot use a
counter to count the nodes in the list to
determine the majority color. The computer is otherwise
fully functional. He has the evil idea that he
could buy the defective computer and somehow use it to do
his work, so that he can use the rest of
the money on enjoyment. Show how he can accomplish this
amazing task. Write code for an algorithm
called ‘findMajorityColor’ which takes a singly-linked list,
L, with n nodes and returns the majority color
among nodes of L. This algorithm should have the same
asymptotic running time as counting the
nodes (O(n)). Note: No arithmetic is allowed.
- 2 Answers
- 4013 Views
- I also Faced
- E-Mail Answers
Answer Posted / tayyab nasir
The best way to do this is to create a new linked list and insert Black nodes at head and White nodes at tail from the previous to the new list. Then find the middle point of the new list. If middle point is Black then Black nodes are more in number else the White nodes.
| Is This Answer Correct ? | 0 Yes | 0 No |
Post New Answer View All Answers
We need to write the function to check the password entered is correct or not based on the following conditions.. a) It must have atleast one lower case character and one digit. b)It must not have any Upper case characters and any special characters c) length should be b/w 5-12. d) It should not have any same immediate patterns like abcanan1 : not acceptable coz of an an pattern abc11se: not acceptable, coz of pattern 11 123sd123 : acceptable, as not immediate pattern adfasdsdf : not acceptable, as no digits Aasdfasd12: not acceptable, as have uppercase character
Write a C/C++ program that connects to a MySQL server and checks if the InnoDB plug-in is installed on it. If so, your program should print the total number of disk writes by MySQL.
Write a (n) algorithm that sorts n distinct integers, ranging in size between 1 and kn inclusive, where k is a constant positive integer. (Hint: Use a kn-element array.)
How to swap two ASCII numbers?
Definition of priority queue was given. We have to implement the priority queue using array of pointers with the priorities given in the range 1..n. The array could be accessed using the variable top. The list corresponding to the array elements contains the items having the priority as the array index. Adding an item would require changing the value of top if it has higher priority than top. Extracting an item would require deleting the first element from the corresponding queue. The following class was given: class PriorityQueue { int *Data[100]; int top; public: void put(int item, int priority); // inserts the item with the given priority. int get(int priority); // extract the element with the given priority. int count(); // returns the total elements in the priority queue. int isEmpty(); // check whether the priority queue is empty or not. }; We had to implement all these class functions.
can you please write a program for deadlock that can detect deadlock and to prevent deadlock.
How can I Draw an ellipse in 3d space and color it by using graph3d?
output for printf("printf");
how to take time as input in the format (12:02:13) from user so that controls remains between these columns?
Performance Algorithm A performs 10n2 basic operations and algorithm B performs 300 lg n basic operations. For what value of n does algorithm B start to show its better performance?
What output does the following code generate? Why? What output does it generate if you make A::Foo() a pure virtual function? class A { A() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; class B : public A { B() { this->Foo(); } virtual void Foo() { cout << "A::Foo()" << endl; } }; int main(int, char**) { A objectA; B objectB; return 0; }
write a program that reverses the input number of n.Formulate an equation to come up with the answer.
What output does this program generate as shown? Why? class A { A() { cout << "A::A()" << endl; } ~A() { cout << "A::~A()" << endl; throw "A::exception"; } }; class B { B() { cout << "B::B()" << endl; throw "B::exception"; } ~B() { cout << "B::~B()"; } }; int main(int, char**) { try { cout << "Entering try...catch block" << endl; A objectA; B objectB; cout << "Exiting try...catch block" << endl; } catch (char* ex) { cout << ex << endl; } return 0; }
solve the problem in the programming language C++"if a five digit number is input through the keyboard.Write a program to calculate the sum of its digits(hint: use the modulus operator)
write a program that can LOCATE and INSERT elements in array using c++ programming languages.
