Answered Questions

  • Linked List Kth largest Element

    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...

  • Duplicate Elements Array

    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?

    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)

  • There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..).

    Star Read Best Answer

    Editorial / Best Answer

    Answered by: David Rachutin

    • Dec 27th, 2006


    use the following method:

    mark the missing number as M and the duplicated as D

    1) compute the sum of regular list of numbers from 1 to N call it RegularSum

    2) compute the sum of your array (the one with M and D) call it MySum

    now you know that MySum-M+D=RegularSum

    this is one equation.

    the second one uses multiplication:

    3) compute the multiplication of numbers of regular list of numbers from 1 to N call it RegularMultiplication

    4) compute the multiplication of numbers of your list  (the one with M and D) call it MyMultiplication

    now you know that MyMultiplication=RegularMultiplication*D/M

    at this point you have two equations with two parameters, solve and rule!

    bakesh

    • Mar 16th, 2015

    9