• #### Sorted Matrix

You are given a matrix. The matrix elements are such that they are sorted both horizontally and vertically. Given an element of the matrix, your job is to obtain its position in an efficient manner.Example: 10 20 30 15 35 98 48 76 110Input: 76Output: 3rd row, 2nd column.

#### sandy

• Mar 24th, 2013

I assume you can do it in the following way: "python class Coordinate: def __init__(self,x=0,y=0): self.x = x self.y = y def findElement(a,n): if a == Non...

#### frogInSea Profile Answers by frogInSea Questions by frogInSea

• Mar 14th, 2013

I think it can be solved in a two dimensional Binary-Search way

• #### 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?

#### 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)

• #### To calculate distance between two text strings

Give an algorithm that calculates the distance between two text strings (only operations you can have are: delete, add, and change, one by one).

#### rrc_83 Profile Answers by rrc_83 Questions by rrc_83

• Jun 20th, 2010

In python - # Input is string s1 and string s2# Check which string is bigger (compares ascii value)if s1 > s2:  b, s = s1, s2else :  b, s  = s2, s1# Covert string to listl1, l2 = lis...

#### yzesong Profile Answers by yzesong Questions by yzesong

• Aug 9th, 2009

The distance of two strings, like "car" and "cat", is 1. So all we need to do is, compare two strings one character by one character and get the distance value. The complexity is O(max(m,n)), m, n are the length of each string.

• #### 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..). Read Best Answer

• 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!

#### Gaurav.khurana Profile Answers by Gaurav.khurana Questions by Gaurav.khurana

• Apr 25th, 2015

@vandita Just a minor correction i think we should go till n-1 only so the in for loop it should be and should use i+1 since nbrs are starting from 1 and not 0

```Codefor (int i=0 ; i<n ; i++)
{
swap(a[i],a[a[i]-1]
}
//since 1 is stored at 0th position```

#### bakesh

• Mar 16th, 2015

9