How to find the kth largest element in a linked list? Can you do this without using extra memory and also without modifying (sorting) the list?

Anonymous

• Jun 19th, 2017

It does not work when duplicate elements are present.

batman

• Oct 4th, 2011

Not enough information about the data in the linked list. Solution 1. Assuming int & no duplicates & rather small [min,max] interval: Iterate through the list once to find the min&max. Make a bi...

Answer Question  Select Best Answer

You have an array of size '2n' of these, 'n+1' elements are distinct and 1 element is repeated 'n' times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?

cullensun

 Profile Answers by cullensun Questions by cullensun

• Sep 23rd, 2013

1st, 2nd, 3rd,......, (n-1)th, (n)th, (n+1)th, (n+2)th, ...... (2n)th Focus: Identify the the repeated element 1. take the 1st element to compare with the rest one by one, worst case: compare wi...

shankar

• Oct 16th, 2012

Since an element is repeated more than half the occurance of the array, for every two didtinct elements discard them from the array. At the end of the loop, the most repeated element will be left.

This is O(n)

Answer Question  Select Best Answer