[algogeeks] second highest elemt in an aary
I want an algo for finding second highest element in n + log n- 2 comparisons. The algo is first find the highest number and then highest among the number which get defeated during tournament. (details in corment). Can anyone do code implemenation for this one. Thanks Nagendra --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: crazy man in the airplane
1/2 On Thu, Sep 10, 2009 at 10:51 PM, ankur aggarwal ankur.mast@gmail.com wrote: crazy man in the airplane A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.) Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random. What is the probability that the last (100th) person to board the plane will sit in his proper seat (#100)? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] probabiltiy + DP
@all: There are k baised coins with probabilty of coming head is P(i) i = 1 to k. If all these coins are tossed together. find the probabilty of getting i heads ( i = k). think in Dynamic Programming. -Nagendra --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: random number...
@ankur: u r right. On Mon, Sep 7, 2009 at 9:36 PM, ankur aggarwalankur.mast@gmail.com wrote: I KNow a sol for given a rand_5() function which generates 0 to 5 and we have to find rand_7() for 0 to 7 could not think about it... On Mon, Sep 7, 2009 at 9:26 PM, ankur aggarwal ankur.mast@gmail.com wrote: Given a random number generator that generates numbers in the range 1 to 5, how can u create a random number generator to generate numbers in the range 1 to 7. (remember that the generated random numbers should follow a uniform distribution in the corresponding range) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find longest palindrom in a give n string in O(N)
@all:
T(i,j) : denotes the length of longest palindrome with start index
i and end index j index.
T(i,j )=
max {
1 , if i == j;
2+T(i+1,j-1) if x[i] == x[j];
max(T(i+1,j) T(i,j-1))
}
This is the recurrence relation
Now algorithm:
T(i,i-1) = 0 for 1= i = n.
for i= 1 to n
T(i)(i) = 1;
start with the distnace d
for d = 1 to n
for i = 1 to n -d
{j = i+d;
if(x[i] == x[j])
T[i][j] = 2+ T[i+1][j-1];
else
T[i][j] = max (T[i+1][j], T[i][j-1])
}
return T[1][n];
On Tue, Sep 1, 2009 at 12:01 AM, Dufusrahul.dev.si...@gmail.com wrote:
This is one of the most difficult dynamic programming problem I have
faced so far.
A good discussion on this problem and different solutions can be found
at
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/
_dufus
On Aug 31, 6:01 pm, ankur aggarwal ankur.mast@gmail.com wrote:
@abhijeet
dryrun on this
abbaabba
On Mon, Aug 31, 2009 at 5:45 PM, Abhijeet Kumar
abhijeet.k.s...@gmail.comwrote:
u can push the string onto a stack ... so last element will be on top ...
den u can pop out element and compare ...
if u have 2 or more set of palindromes ..
u can keep a counter and keep a check on dat...
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: adobe interview question
Can anyone recheck and rephrase the question becuase i think it would be always '0' On Wed, Sep 2, 2009 at 10:40 AM, Naynnayanish.hi...@gmail.com wrote: Guys, We are anticipating an algorithm here. The input would be an array containing 0/1 representing black and white boxes. On Sep 1, 8:37 pm, yash yashpal.j...@gmail.com wrote: Given a chessboard in which u dont know how the black and white boxes are arranged but this is sure that there will 32 black squares and 32 white squares.You have to find the least possible disatnce between any two sqaures of same colour ... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
Fwd: [algogeeks] Re: String- Anagrams.
@Anil: I will request you to completly explain the things. Not just write a bit of code. So what is map and how are you implementing the insert operation. -- Forwarded message -- From: Anil C R cr.a...@gmail.com Date: Mon, Aug 31, 2009 at 7:59 PM Subject: [algogeeks] Re: String- Anagrams. To: algogeeks@googlegroups.com If you have time for pre-processing, you can do this: for each string t in dictionary: s = sort(t) map[s].insert(t) so for printing anagrams of x, we'd just print the contents of map[sort(x)] --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@ all. how come it is O(log n). It should be order (height) whcih is not the O(log n) unless and until tree is not balanced. On Mon, Aug 31, 2009 at 11:39 AM, Dufusrahul.dev.si...@gmail.com wrote: Rama, I cannot agree with you more here. On Aug 31, 5:34 am, Ramaswamy R ramaswam...@gmail.com wrote: When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave dave_and_da...@juno.com wrote: When you say that checking if any of the ancestors is O(n log n) are you assuming that the tree is balanced? It wouldn't be O(n log n) if the tree degenerates into a linked list, would it? So what is your justification in assuming balance? Dave On Aug 30, 6:01 pm, Ramaswamy R ramaswam...@gmail.com wrote: To begin with I find the invariant doesn't hold in the system progressively. Forget about islock and assume that we only do lock / unlock. Given that a node cannot be locked if any of its descendants / ancestors is locked. It is never possible for the tree to enter a state where any of the descendant of a locked node is locked. If that invariant holds then all we need to check is if any of the ancestors are locked, which is O(log n). O(1) would either require hash table (and O(n) storage) unless we choose to replicate the lock state in all of the ancestors as well (which is a pretty ugly solution considering what unlock would have to do). If we can supplement the tree node with a lock status and pointer to child (only used while unlocking) which is locked we should be able to do it all in the asked for complexities :). Ugly but possible. Of course there is an O(n) extra storage. On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar nagendra@gmail.com wrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr-Hide quoted text - - Show quoted text - -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: adobe interview question
@all: Yah it's 100% true that for 32 white and 32 black we have min distance at 0. But question will become difficult when the number of white and blacks are less than 32. -Nagendra On Tue, Sep 1, 2009 at 9:30 PM, Ramaswamy Rramaswam...@gmail.com wrote: If the white and the black squares are not arranged as in a chess board then we can be sure that there are at least two whites and two blacks which are adjacent by the sides. If not they will be adjacent diagonally. So the distance really depends on how it is defined for squares adjacent by a side and by a vertex (diagonally). Only two possibilities! On Tue, Sep 1, 2009 at 8:37 AM, yash yashpal.j...@gmail.com wrote: Given a chessboard in which u dont know how the black and white boxes are arranged but this is sure that there will 32 black squares and 32 white squares.You have to find the least possible disatnce between any two sqaures of same colour ... -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
I thnik the statement is : a node cannot be locked of any of its ancestors and descendents are locked. On Tue, Sep 1, 2009 at 8:21 PM, ankur aggarwalankur.mast@gmail.com wrote: @narendra.. i think ques need to recheck becoz the statement u r giving A node cannot be locked if any of its descendant or ancestor is locked .. should not be A node cannot be locked if any of its ancestor is locked. On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar nagendra@gmail.com wrote: Given a n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But, A node cannot be locked if any of its descendant or ancestor is locked. I was supposed to - write the structure of node - write codes for - islock()- returns true if a given node is locked and false if it is not - lock()- locks the given node if possible and updates lock information - unlock()- unlocks the node and updates information. Codes should be : Islock –O(1) Lock()- O(log n) unLock()- O(log n) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Median Finding algorithms.
What ever you have just post here ! On Sun, Aug 30, 2009 at 5:08 PM, Nagendra Kumarnagendra@gmail.com wrote: Given a set S of n distinct numbers and a positive integer k = n. Determine the k numbers in S that are closest to the median of S. Find an O(n) algorithm --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@Priya:
How it will come to O(log n). The statement
while(cond)
m=m-parent;
will covers top to bottom in a tree.
whick will be O(n). explain ur logic hoiw is it O(log n).
-Nagendra.
On Sun, Aug 30, 2009 at 11:40 AM, priya kpriya.annau...@gmail.com wrote:
@Dufus: You mean to say do preprocessing and hash all the nodes that cannot
be locked, if am not wrong. And again, Everytime we lock a node, we need to
update the hash and that would be O(n) worst case. Can we do anything better
?
--Priya
On Sun, Aug 30, 2009 at 10:26 AM, Dufus rahul.dev.si...@gmail.com wrote:
Priya, as mentioned by you your isLock() takes O(logn) time.
We need to use Hash table as auxillary DS for O(1) query time.
_dufus
On Aug 30, 8:35 am, priya k priya.annau...@gmail.com wrote:
// Data Structure for the n-ary tree
struct node
{
int data;
node * child[m];
bool lockFlag; // Indicates if a node is locked or not
node *parent; //Holds the immediate parent of the node
int LockCount; //Holds how many nodes arrested this node
};
// Takes logm(N) in the worst case
bool check(node *NodeToBeLocked)
{
node *m=NodeToBeLocked;
if(m-flag==true || m-LockCount0)
return false; // since the node is already locked or any of its
subtrees already locked, return false
while(m !m-lockFlag)
m=m-parent;
if(m m-lockFlag)
return false; // if any of its ancestors have been already locked
return true;
}
// Takes logm(N) in the worst case
bool lock(node *NodeToBeLocked)
{
if(check(NodeToBeLocked)) // If true, Node is free to be locked
{
node *m=NodeToBeLocked;
m-lock=true;
node *prevChild=m;
m=m-parent;
while(m)
{
m-LockCount++;
prevChild=m;
m=m-parent;
}
return true;
}
return false; //err.. cannot be locked
}
// Takes logm(N) in the worst case
bool unlock(node *NodeToBeUnLocked)
{
node *m=NodeToUnBeLocked;
m-lock=false; // Unlock the Node
node *prevChild=m;
m=m-parent;
while(m)
{
m-LockCount--;
prevChild=m;
m=m-parent;
}
}
Thanks,
Priya
On Sat, Aug 29, 2009 at 11:35 PM, nagendra kumar
nagendra@gmail.comwrote:
Given a n-ary tree of resources arranged hierarchically. A process
needs to lock a resource node in order to use it. But,
A node cannot be locked if any of its descendant or ancestor is
locked.
I was supposed to
- write the structure of node
- write codes for
- islock()- returns true if a given node is locked and false if it is
not
- lock()- locks the given node if possible and updates lock
information
- unlock()- unlocks the node and updates information.
Codes should be :
Islock –O(1)
Lock()- O(log n)
unLock()- O(log n)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] String- Anagrams.
Write a method to print all valid anagrams of a string -Nagendra --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: String- Anagrams.
@Anil: Dictionary is given to you. For each string t in array u = sort(t). if(s == u) print (t). If dictionary has millions of words. So you will go for each word one by one. Then How will make it efficient in terms of time. -Nagendra On Sun, Aug 30, 2009 at 3:56 PM, Anil C Rcr.a...@gmail.com wrote: are we like given a dictionary or something? if we are, its quite simple... 1. load the dictionary into an array. 2. sort the given string lexicographically. call it s 3.t for each string t in the array, u = sort if s=u then print t then again, if we are asked to print all permutations, we can do it recursively...or there is Johnson-Trotter: http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find elements in array with odd frequency
Plz write the code here. On Sun, Aug 23, 2009 at 2:30 PM, Dufusrahul.dev.si...@gmail.com wrote: Idea is simple either to keep a count and emit elements with odd count (frequency) or XOR element with itself for each time it occurs in input and then emit elements which have non zero XORed result(which basically corresponds to elements with odd frequency). _dufus On Aug 23, 8:44 am, Nagendra Kumar nagendra@gmail.com wrote: How are u doing with xor. Can u post ur thought here. Thanks Nagendra On Sun, Aug 23, 2009 at 2:07 AM, Dufusrahul.dev.si...@gmail.com wrote: We can count or XOR but I couldnt find any advantage of XORing except for preventing overflow. _dufus On Aug 22, 5:03 pm, Nagendra Kumar nagendra@gmail.com wrote: I think you are trying sorting and then counting the frequency of the numbers. -Thanks Nagendra On Sat, Aug 22, 2009 at 11:21 AM, Dufusrahul.dev.si...@gmail.com wrote: I can think of a naive algorithm which takes O(n) time and O(n) space. or O(nlogn) with O(1) space. May be someone else might come up with a better algo. _dufus On Aug 21, 3:01 pm, nagendra kumar nagendra@gmail.com wrote: Given an array of integers,Print the integers whose appareance are in odd times. Need not worry abt order while printing the output. Need Algotithm in o(n) time complexity. Need efficient space complexity. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] find elements in array with odd frequency
Given an array of integers,Print the integers whose appareance are in odd times. Need not worry abt order while printing the output. Need Algotithm in o(n) time complexity. Need efficient space complexity. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find elements in array with odd frequency
I think you are trying sorting and then counting the frequency of the numbers. -Thanks Nagendra On Sat, Aug 22, 2009 at 11:21 AM, Dufusrahul.dev.si...@gmail.com wrote: I can think of a naive algorithm which takes O(n) time and O(n) space. or O(nlogn) with O(1) space. May be someone else might come up with a better algo. _dufus On Aug 21, 3:01 pm, nagendra kumar nagendra@gmail.com wrote: Given an array of integers,Print the integers whose appareance are in odd times. Need not worry abt order while printing the output. Need Algotithm in o(n) time complexity. Need efficient space complexity. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find elements in array with odd frequency
How are u doing with xor. Can u post ur thought here. Thanks Nagendra On Sun, Aug 23, 2009 at 2:07 AM, Dufusrahul.dev.si...@gmail.com wrote: We can count or XOR but I couldnt find any advantage of XORing except for preventing overflow. _dufus On Aug 22, 5:03 pm, Nagendra Kumar nagendra@gmail.com wrote: I think you are trying sorting and then counting the frequency of the numbers. -Thanks Nagendra On Sat, Aug 22, 2009 at 11:21 AM, Dufusrahul.dev.si...@gmail.com wrote: I can think of a naive algorithm which takes O(n) time and O(n) space. or O(nlogn) with O(1) space. May be someone else might come up with a better algo. _dufus On Aug 21, 3:01 pm, nagendra kumar nagendra@gmail.com wrote: Given an array of integers,Print the integers whose appareance are in odd times. Need not worry abt order while printing the output. Need Algotithm in o(n) time complexity. Need efficient space complexity. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find an element in sorted matrix
If it is o(n) only then we can do a normal search. But data is sorted left and down so how to use this property. On Thu, Aug 20, 2009 at 8:12 PM, Dufusrahul.dev.si...@gmail.com wrote: AFAIK, searching an element in sorted matrix (Young's Tableau) takes O (n) time. So I am not sure if O(logn) is actually possible. _dufus On Aug 20, 6:41 pm, nagendra kumar nagendra@gmail.com wrote: How can we find an element in the matrix [n*n] which is sorted row wise and column wise in O(log n). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Find an element in sorted matrix
How can we find an element in the matrix [n*n] which is sorted row wise and column wise in O(log n). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
