Re: [algogeeks] Re: a google question
1.Suppose you have Array A and B like this. 2.A = [10,7,3,1] , B = [50,49,48,47,46] 3.Arrange/Assume numbers in a three column table such that First n rows are the made up of A[1] and members of B. Rest m rows are made up of B[1] and members of A. Column 3 keeps sum of column 1 and 2. It would look something like this. ⁃10 50 60 ⁃10 49 59 ⁃10 48 58 ⁃10 47 57 ⁃10 46 56 ⁃50 10 60 ⁃50 7 57 ⁃50 3 53 ⁃50 1 51 4.Now sort the rows based on column 3 in O(n) time. Remember its a merge operation of two sorted lists so O(n+m) time. 5. Pick any number of pairs from top. They are in decreasing order of their value. This algorithm takes time in O(n). But there might be space complexity issues if array size is too large. -Regards Amit Agarwal On Mon, May 3, 2010 at 9:48 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: @Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
it is impossible 2 give a formula or a generic method to calculate the complexity for any algo.. method to calcuate complexity differs per algo On Mon, May 3, 2010 at 11:45 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: question
@vivek : Hi , not sure , how your solution would work . Can you
explain with this set
A = { -5, 8, 9, 2 , -1 , 0 , 1 , 5, 7 }
On May 3, 8:33 pm, vivek bijlwan viv...@gmail.com wrote:
copy the array(A) in a different array(B) to store the index info.(space
O(n))
sort(A)
take each pair's sum ( complexity O(n^2) ) and with that do a binary search
for the 3rd element needed.(O(log(n))).
Check for the indices in B.
i believe it can be done in better time somehow.
On Mon, May 3, 2010 at 6:48 PM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
given an array(unsorted) may contain negative numbers too
find the index of three numbers whose sum is closest to zero in O(N2 log
N) time and O(N) space.
P.S -3 is more close to zero then -6 (number line ...)
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
athttp://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
check the design and analysis of algorithm by thomas cormen On Mon, May 3, 2010 at 11:45 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. In Computer science though, expressing T(N) as a pure mathematical function is seldom given importance. More important is knowing asymptotic behavior of algorithm or asymptotic growth rate i.e how quickly does T(N) grows as N goes to a extremely large values(approaching infinity or exhibits asymptotic behavior). So instead of expressing T(N) as a pure and precise mathematical function, different other notations have been devised. As far as I know, there are at least 5 notations used to express T(N) namely Big-O (O), Small-o(o), Big-Omega(Ω), Small-omega(w), Theta(*Θ). * Big-O is used for representing upper bound(worst case), while Big-Omega is for expressing lower bounds(best case). Small or Little notations are more stricter notations. Theta notation is used for expressing those functions whose upper and lower bounds are same or constant multiple of the same function For more thorough understanding, I suggest you to read the following: How to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24, 25, 26, 27 Regards Varun On Mon, May 3, 2010 at 8:15 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] question
The solution given by Afroz will work having O(N) extra memory.But in that case the collision in the will increase. If you want to remove collision totally than a hash of O(max_element_in_array) memory will be required. if you want to solve without extra memory then 1. sort the array O(N) 2. take each possible pair from array and sum it.O(N^2) 3. binary search the array for the nearest complement of this sum O(logN) So total complexity is O(N^2 * logN) -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Where does OS scheduling run??
yea if your processor has multiple cores or is Hyper Threading support then it can execute more than 1 instruction concurrently. On Thu, May 6, 2010 at 12:10 AM, praba garan prabagara...@gmail.com wrote: Windows Task Manager Performance tab shows the presence of two processors. Will 2 instructions be executed concurrently?? With Regards, Prabagaran. On Wed, May 5, 2010 at 4:56 PM, Varun Nagpal varun.nagp...@gmail.comwrote: I guess with Virtual machines, instructions that simulate instructions of microprocessor are scheduled onto the real processor. But good question is how the scheduling of real microprocessor instructions done in a virtual machine. And the answer is again that its done on virtual processor, which essentially has all hardware components of real processor modeled in software. All sub-parts of this software representing essential hardware components, again run synchronously (in parallel) either at instruction accurate level or cycle accurate level. All new processor that are designed as of today, are first mostly are verified using simulators written in hardware description languages like VHDL/SystemVerilog/SystemC and then simulated either in software or hardware. For hardware simulation, in some cases its eventually possible to create them on FPGA's and verify before they are sent to fab lab. Its an arduous task. For example, you can get HDL code for free for SUN Open Sparc processor and can flash it on FPGA. So It doesn't really matter whether your processor is real or virtual, so you need to understand architecture principles and some digital electronics to understand at hardware(VLSI ) level Intel x86 and now x64 are the most popular architectures. Other popular architectures are ARM, MIPS, SPARC, PowerPC, etc. You should probably read the book: Computer Architecture, by hennrey Peterson On Tue, May 4, 2010 at 10:49 PM, praba garan prabagara...@gmail.com wrote: I think it is necessary to study the full architecture of INTEL MotherBoard to get a full picture. How does scheduling happen incase of Virtual Machines?? Then how does a packet coming to the Guest OS is sent to Guest OS. ie, either directly to Guest OS or through Host OS. With Regards, Prabagaran. On Mon, May 3, 2010 at 12:25 PM, Varun Nagpal varun.nagp...@gmail.com wrote: I think its a good question and fairly complicated to explain at hardware(RTL) level. Anyways, let me give it a try : You suggested that only 1 instruction is executed by one processor, which is not true(if you have read computer architecture). Briefly, lets assume the instruction pipeline(assuming only single hardware thread) is filled with instructions from the present thread(or process) of execution. Assume number of pipeline stages to be 20. In the pipeline, 20 instructions from the current instruction control flow are executing synchronously on every clock tick. Depending upon the design of pipeline, data from registers/memory is read in different pipeline stages. Also there may also be many execution stages(ALU) before the data is written to register/memory. The OS kernel keeps a track of all the threads/processes presently executing, active, waiting, suspended etc. in memory in the form of a data structure, which is to say that it always knows the next thread/process it needs to schedule on to the processor. I think it has a compare register that stores an arbitrary number(as decided by kernel) of clock ticks for a time slice expiry and keeps another counter register to keep track of time slice expiration for present thread. At every clock tick, it increments the counter register and compares it with compare register. This summing and comparison is done by inserting an instruction in the current instruction flow. The point is that a clock interrupt is generated whenever the values of the counter and the compare registers match. When this does occur, the next PC value,registers etc(i.e its context information) is pushed onto the stack and a jump is made to an area in memory storing an interrupt vector table. I also assume that when this jump is made, the OS kernel supplies some information to the jump instruction about the next thread to be executed. This information maybe stored in another dedicated register. Now by using this information and interrupt vector table, it can find out the memory address of next thread(ii.e next instruction) to be executed. The PC including other registers is then simply loaded with context information of the new thread. Important thing here is again that when all of this is happening, the pipeline may still be executing instructions from the previous thread. In addition it will contain interrupt instructions! Only when PC is updated(in some stage of pipeline) that the instruction fetch stage will start fetching instructions from instruction memory area of new thread. In
Re: [algogeeks] question
@Sathaiah, I don't think there is any need to store the pairs. Space complexity is O(n). Lets see this. 1. Put a nested for loop on the given array so that it runs in O(n^2) time. 2. Inside body of the inner loop, I have two numbers for that time and then I'll look for the third number in binary tree which makes my total minimal. (Binay tree is already made and stored in seperate array. So this takes O(n)). 3. By the time I am done with nested loops, I'll be having three numbers in my hand along with thier indexes. 4. (For finding the index of third number, you need to keep it in the node value itself so that there is no extra searching for index. So I think, it will eventually take space complexity of O(Cn). Which is again O(n)). [Correct me if I am wrong] 5. So you completed the algorithm in O(n^2)*log(n) time. -Regards Amit Agarwal On Tue, May 4, 2010 at 8:52 AM, Sathaiah Dontula don.sat...@gmail.comwrote: @vivek, Where do you store pairs sum ?, Space is O(N) ... :) Thanks, Sathaiah On Mon, May 3, 2010 at 9:03 PM, vivek bijlwan viv...@gmail.com wrote: copy the array(A) in a different array(B) to store the index info.(space O(n)) sort(A) take each pair's sum ( complexity O(n^2) ) and with that do a binary search for the 3rd element needed.(O(log(n))). Check for the indices in B. i believe it can be done in better time somehow. On Mon, May 3, 2010 at 6:48 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: given an array(unsorted) may contain negative numbers too find the index of three numbers whose sum is closest to zero in O(N2log N) time and O(N) space. P.S -3 is more close to zero then -6 (number line ...) -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] tree from linked list
Cant we do something like this:
Make the middle element as root, middle element of the left side as its left
child and mid of the right half as its right child.
and so on for the left and right subtrees.
it would bring out a balanced tree without rotations..
On Mon, May 3, 2010 at 5:41 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
for simplicity in writin algo i've taken sorted array instead of list
struct node * create( int *sorted,number of elements){
struct node *temp,*left,*right;
int tempii[100],tempiii[100];
if(number of elemnts ==0)
return NULL;
temp-data=sorted[mid];
temp-left=NULL;
temp-right=NULL;
if number of elements == 1
return temp;
int count=0;
for(int i=0;imid;i++){
tempii[i]=sorted[i];
count++;
}
left=create(int *tempii,count);
temp-left=left;
count=0;
for(i=mid+1;inumberofelemnts;i++){
tempiii[i]=sorted[i];
count++;
}
right=create(int *tempiii,count);
temp-right=right;
return temp;
}
On Mon, May 3, 2010 at 5:36 PM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
1) Make the middle element the root.
Recursively make the left and right subtrees from the left and right
halves of the link list.
2) Implement balanced insertion in trees (via rotations on every step...).
Now insert each element
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, May 2, 2010 at 6:38 PM, divya sweetdivya@gmail.com wrote:
u are given a sorted lnked list construct a balanced binary search
tree from it.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Varun Bhatia
Research Intern
Advanced Development Prototyping Group
Microsoft Research Lab India Pvt Ltd
Bangalore
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Complexity of Algorithms
use master theorem or recursion tree method On Wed, May 5, 2010 at 7:29 PM, Varun Nagpal varun.nagp...@gmail.comwrote: Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. In Computer science though, expressing T(N) as a pure mathematical function is seldom given importance. More important is knowing asymptotic behavior of algorithm or asymptotic growth rate i.e how quickly does T(N) grows as N goes to a extremely large values(approaching infinity or exhibits asymptotic behavior). So instead of expressing T(N) as a pure and precise mathematical function, different other notations have been devised. As far as I know, there are at least 5 notations used to express T(N) namely Big-O (O), Small-o(o), Big-Omega(Ω), Small-omega(w), Theta(*Θ). * Big-O is used for representing upper bound(worst case), while Big-Omega is for expressing lower bounds(best case). Small or Little notations are more stricter notations. Theta notation is used for expressing those functions whose upper and lower bounds are same or constant multiple of the same function For more thorough understanding, I suggest you to read the following: How to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24, 25, 26, 27 Regards Varun On Mon, May 3, 2010 at 8:15 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm
Re: [algogeeks] tree from linked list
i guess the rotation solution i gave will take O(n) with the list as well (btw.. u can convert a list to array :P) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: tree from linked list
On May 2, 7:08 am, divya sweetdivya@gmail.com wrote: u are given a sorted lnked list construct a balanced binary search tree from it. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en. There is a simple iterative solution to this problem that obviously runs in linear time. I have implemented a version of it that builds a weighted binary tree. I'll refrain from describing it here though because I suspect this is someones homework. :-) I will give this clue though. The tree is built bottom up, not top down which is more difficult. Regards, Ralph Boland -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
