// Given a singly linked list without values defined by:

class Node {
Node next
}

// Write a function that removes all elements from the list whose _index_ is a fibonacci number
// o - o - o - o - o - o - o - o - o - o - o - o
// 0 1 2 3 4 5 6 7 8 9 10 11
// x x x x x
// becomes
// o ---------------- o ------ o - o ------ o - o - o
// 0 4 6 7 9 10 11

Question

// Given a singly linked list without values defined by:

class Node {
    Node next
}

// Write a function that removes all elements from the list whose _index_ is a fibonacci number
// o -> o -> o -> o -> o -> o -> o -> o -> o -> o -> o -> o
// 0    1    2    3    4    5    6    7    8    9    10   11
//      x    x    x         x              x
//                becomes
// o ----------------> o ------> o -> o ------> o -> o -> o
// 0                   4         6    7         9    10   11

Answer to Fib LLquestion · Accepted Answer

Here is a solution that should work. Basically you just reduce the current fib number by the number of elements that have already been removed ie for the 8th element you will have already removed the 1st, 2nd, 3rd and 5th element (4 elements in total) in the linked list meaning the the 8th is now in position 8 - 4 = 4:

public static void removeFib(LinkedList inputList)
{
	//initial fib numbers
	int Fib1 = 1;
	int Fib2 = 1;
	int tmp;
	
	int numRemoved = 0; //total number of elements that have been removed
	int rmvNext = 1; //element to be removed next
	
		
	while(rmvNext <= (inputList.size() - 1))
	{
		//remove current fib node from ll
		inputList.remove(rmvNext);
		numRemoved++;
		
		//find next fib number
		tmp = Fib1 + Fib2;
		Fib1 = Fib2;
		Fib2 = tmp;
		
		//compute the next number to be removed
		rmvNext = Fib2 - numRemoved;
	}
}

Tripadvisor

Sollicitatievraag bij Tripadvisor

Antwoord op sollicitatievraag

Gevolgde bedrijven

Vacatures