Hi,
If we don't have to preserve the order than,
a[1...N] can be used and if we have input like 1,4,3,6
Insertion can be done as
a[1]++, a[4]++, a[3]++, a[6]++
and deletion using a[1]--- and so on.
searching is also using a[X].
On Thu, Nov 4, 2010 at 11:18 AM, jagannath wrote:
>
>
> Design
Design a data structure that allows one to search, insert, and delete
an integer X in O (1) time in a table (i.e. constant time, independent
of the total number of integers stored). Assume that 1≤X≤N. Also
assume that the maximum number of integers in the table can only be M
at any one time. You
@kanika
1.
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return
@sumat
In the example given by you. the longest interval is [0...7] and not
[3...8]. Something wrong with your algo.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscri
1.
int main(){
int max=0;
int max_till_here=0;
for(i=0;i0){
if(max_till_here>max)
max=max_till_here; // update maximum sum till here
}
else { // in case continuous sum cums to <=0;
max_till_here=0;
}
return max;
}
2. BST ... i think y
A sorted array A[1...n] composed of distinct integers
=> A[i] < A[i+1]for i = 1..n-1
=> A[i]-i < A[i+1]-ifor i = 1..n-1
=> A[i]-i <= A[i+1]-(i+1) for i = 1..n-1
Let B[i]=A[i]-i for i=1..n, then B[1..n] is sorted in non-decrease
order. A[i]=i <=> B[i]=0.
Do a binary
Let n be the length of the array.
1. If the middle element is equal to its index return success.
2. If the middle element is greater than its index search the left
half, since all the elements to its right will be greater than or
equal to it and hence cannot be equal to their index.
3. Else search
do binary search ... if A[i]http://groups.google.com/group/algogeeks?hl=en.
*Sure Shot - Lead .Net Developer - Wilmington, DE (Direct F2F) - 6+months
contract - $42/Hr on C2C*
*Job Title : Lead .Net Developer
Location : Wilmington, DE
Duration : 6+months contract*
*Rate : $42/Hr on C2C*
We are currently looking for Lead .Net Develop
*Sure Shot - PeopleSoft Reports Developer w/FSCM - Horsham, PA - 4+months
contract - $55/Hr on C2C
*
*Job Title: PeopleSoft Reports Developer w/FSCM
Location :Horsham, PA
Duration :4+Months Contract*
*Rate :$55/Hr on C2C*
Programmer/analyst to do re
*Immediate Hire - C# Programmer - Sanjose, CA - 6+months contract - $40/Hr
on C2C.*
*
Job Title: C# Programmer
Location :San Jose, CA*
*Duration :6+Months Contract*
*Rate :$40/Hr on C2C
*
Experience programming on C# platform
Experience working with Po
Thanx 4 rply but not getin ur solutions.
1.cn u gve easy algorithm(python dify to undrstand)
2.how to run selection sort on BST,BST has some different structure(dese
algos run on arrays ).cn u gve code in C for undrstanding.
--
regards
kanika suri
MCS 2nd yr
DUCS
University of Delhi
--
You rec
Agree, the true answer is [0,7]. My previous post happened to be incorrect
illustration of a correct program, as the attached code returns 0,7 only.
The code (correctly) assumes a hidden 0 at *diff [-1]* always, so the
longest interval that can be retained is (0,7) in this case.
On Wed, Nov 3, 201
why not the answer (0,7)?
On Nov 1, 4:02 pm, sumant hegde wrote:
> Say diff [i] = (no. of 1s in B[ 0...i ]) - (no. of 1s in A[0...i]). In other
> words the subarray B(0,i) contains diff(i) no. of more 1s than the subarray
> A[0,i]. And diff[i] < 0 indicates the excess of 1s in A's subarray.
> Ex
2. Well known problem and a simple solution:
http://wuhrr.wordpress.com/2008/01/11/find-largest-sum-of-contiguous-numbers-in-an-array/
1.
a. Run 4 iterations of selection sort.
b. Use quicksort based selection algorithm:
http://www.ics.uci.edu/~eppstein/161/960125.html
c. Use linear alorithm to fi
OK , I see . Thank you Dave
2010/11/3 Dave
> @Vaibhav: Your array doesn't work, because the problem statement says
> that the array elements are distinct, but 2 is not distinct in your
> array.
>
> Elaborating on how to decide whether to look to the left or right, if
> A[i] < i, look to the
Thanks Dave for the clarification. It works
On Wed, Nov 3, 2010 at 7:20 PM, Dave wrote:
> @Vaibhav: Your array doesn't work, because the problem statement says
> that the array elements are distinct, but 2 is not distinct in your
> array.
>
> Elaborating on how to decide whether to look to t
@Vaibhav: Your array doesn't work, because the problem statement says
that the array elements are distinct, but 2 is not distinct in your
array.
Elaborating on how to decide whether to look to the left or right, if
A[i] < i, look to the right, while if A[i] > i, look to the left.
Dave
On Nov 3,
Hi Dave,
How can we do a binary search on this array by using the function:
Let f(i) = A[i] - i
Please elaborate. I mean how can we take a decision whether to look into
left or right.
For example -> Pick array {1,2,2,4,5,6,8}
Vaibhav
On Wed, Nov 3, 2010 at 6:44 PM, Dave wrote:
> @Lichenga24
@Lichenga2404: Assuming that the array is sorted into increasing
order:
If A[1] > 1 or A[n] < n, return false.
Let f(i) = A[i] - i. Do a binary search to find i such that f(i) = 0.
If such an i is found, return true; else return false.
Binary search is O(log n). It works because f(i) is an increas
@Lichenga2404:
Examine the leftmost bit of each number, using n operations.
Make a list of the indices of the numbers with 0 bits and a list of
the indices of the numbers with 1 bits.
One of the lists will be of even length, and one will be of odd
length.
The missing number has the leftmost bit tha
we are given a sorted array A[1...n] , composed of distinct integers,
(the values can be negative). We want to determine if there is an
index i such that A[i] = i.
Give an O(logn) algorithm to solve this problem , and justify its
correctness
--
You received this message because you are subsc
You are given an array A of n distinct integers , expressed in binary.
Each integer is in the range [0,n] .As there are n+1 values in this
range, there is exactly one number missing .As a single operation, you
may access the jth integer(A[i][j]) . Note that it would take O(nlogn)
time to read the f
23 matches
Mail list logo
