taro_curly Posted October 22, 2007 Share Posted October 22, 2007 An array A[1...n] is said to be k-ordered if A[i - k] \leq A \leq A[i + k] for all i such that k For example, the array A = [1, 4, 2, 6, 3, 7, 5, 8] is 2 ordered. Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered? a) 2n-1 b) 2 c) n/2 d) 1 e) n Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered? a) 2n-1 b) 2 c) n/2 d) 1 e) n Quote Link to comment Share on other sites More sharing options...
f2003800 Posted October 22, 2007 Share Posted October 22, 2007 answer for Q1 is n/2 which can be found by verification of given example!!! Quote Link to comment Share on other sites More sharing options...
ethanph Posted October 22, 2007 Share Posted October 22, 2007 q2 is d, i think Quote Link to comment Share on other sites More sharing options...
taro_curly Posted October 22, 2007 Author Share Posted October 22, 2007 @f2003800 Do you know of a more analytical way in which this problem can be approached? Relying on an example can be misleading... @ethanph If the array was at least 2-ordered, the answer should be atleast as large as the answer to Q1. Quote Link to comment Share on other sites More sharing options...
grabanca Posted October 22, 2007 Share Posted October 22, 2007 Consider the 2-ordered Array of size 10 (n = 5) 1 6 2 7 3 8 4 9 5 10 6 is put into position 2 instead of position 6 => distance is 4, which is greater than n/2. So the answer could only be n or 2n-1. Thinking about the fact that any number is sorted in raport to n other numbers leads to the conclusion that the answer is n. Quote Link to comment Share on other sites More sharing options...
R0jkumar Posted October 22, 2007 Share Posted October 22, 2007 For the 1st question, if the array is 2-ordered, then the elements are such that the following hold : a[0] and a[1] In other words, we have 2 non-decreasing sequences of numbers each of length n. And 1-ordered is basically a sorted array. In a sorted array we have a[0] If you take any number from a 2-ordered list, it is already in its correct position relative to the rest of the (n-1) numbers from the same list but it maybe out of order with respect to the n-numbers from the other list. Hence each number can be a maximum of n-positions from its correct position in the sorted list. I am still thinking about the second part :) Quote Link to comment Share on other sites More sharing options...
iamdaisy Posted October 23, 2007 Share Posted October 23, 2007 For Q2 , I think the correct answer is 1. The no. below are for array index ( eg: 3 = a[3]) For 2-0rdered : 0 1 2 3 4 5 6 7 where 0 1 For 3-ordered : 0 1 2 3 4 5 6 7 8 where 0 1 2 This implies that we can only choose between the positions 0 and 1. Correct me if I am wrong Quote Link to comment Share on other sites More sharing options...
f2003800 Posted October 23, 2007 Share Posted October 23, 2007 @f2003800 Do you know of a more analytical way in which this problem can be approached? Relying on an example can be misleading... @ethanph If the array was at least 2-ordered, the answer should be atleast as large as the answer to Q1. i didn't notice "maximum number of positions" in teh given problem. I just checked it for the given example... it led to wrong answer :( ..... the number of positions vary... thanks taro_curly Quote Link to comment Share on other sites More sharing options...
grabanca Posted October 23, 2007 Share Posted October 23, 2007 My answer for Q2 is E as well, though I am not sure... Any number is ordered correctly relative to n-1 other items. It is also ordered correctly relative to 1/3 of the remaining items (because it is 3-ordered) which implies that a number is ordered correctly relative to |_4n/3_| items. Generally a number can be up to [2n/3] positions away from its place in the ordered array. For n = 1, 2n/3 = 1 as well. Ex. [2,1] is 2-ordered and 3-ordered, n=1 and the maximum distance is 1. I would choose 2n/3 if there were such a choice. Otherwise I think n makes most sense. Quote Link to comment Share on other sites More sharing options...
admiyo Posted October 26, 2007 Share Posted October 26, 2007 If an n-ordered subset is all of the numbers that are n ordered together, then any number is in two n-ordered subset, one that is 2 ordered and one that is three ordered. When there was only a single 2 ordering forced on the whole set, there was no relationship between the subset beginning with the first value and the subset beginning with the second value. Same with three orderings: there are three distinct sets. I'll label the two ordred subsets s2-1 and s2-2, and the three 3ordered sets as s3-1 s3-2 and s3-3. If you only have to deal with s2-1 and s2-2, you can have the case where the loweset value in s2-2 is greater than the highest value of s2-1 as in this set {1, 7, 3, 9, 5, 11}. However, since a set is both two and three ordered, there is a relationship forced by the fact that a given value is in both sets. The set {1, 7, 3, 9, 5, 11} fails 3 ordering because 7 > 5. Thus 1/6th of the numbers are going to common between each 2 ordered and 3 ordred subset. The question is how much "wiggle room" do you have? The fully ordered set {2, 6, 8, 10, 11, 12, 13 ,14, 17 } Is 2 ordered and three orded. Within the 2 ordering, I can switch any two adjacent values and still be two ordred. Within the three ordering, I can switch any value with the one two prior or two after it and still be three ordred. Additionally I cannot switch any value with a member of a disjoint n-set further away, as I will violate the ordering of one or both sets. Take the smallest value and: Move it one away {6, 2, 8, 11, 10, 12, 13 ,14, 17 } OK Move it two away {8, 6, 2, 10, 11, 12, 13 ,14, 17 } and violate the ordering of n2-1 Move it three away {10, 6, 8, 2, 11, 12, 13 ,14, 17 } and violate the ordering of n3-1 Move it four or more away and violate the ordering of n2-1 {11, 6, 8, 10, 2, 12, 13 ,14, 17 } {12, 6, 8, 10, 11, 2, 13 ,14, 17 } {13, 6, 8, 10, 11, 12, 2 ,14, 17 } {14, 6, 8, 10, 11, 12, 13 ,2, 17 } {17, 6, 8, 10, 11, 12, 13 ,14, 2 } from a relationship perspective Each position is in a sub set of ordering with the other positions marked with an X below. 1 2 3 4 5 6 7 8 9 1|X| 2|O|X| 3|X|O|X| 4|X|X|X|X| 5|X|X|X|O|X| 6|O|X|X|X|O|X| 7|X|O|X|X|X|O|X| 8|O|X|O|X|X|X|O|X| 9|X|O|X|O|X|X|X|O|X In order to swap the values in a position between two fields with out violating ordering, there must be no relationship between these fields. Thus two can swap with 9...or can it? 6 and 9 have a three ordered relationship. 6 and two have a two ordered relationship. Swapping 2 and 9 violate the two ordered relationship between 2 and 6. What if we tried a three way swap? 2->6 6->9 9->2? No go, as 2 and 6 are still two ordered, and the original value in 9 would be greater than the original value in 6. How about 1 and 6? If we swap the values in these positions, 2 ordering between 1 and 3 will be violated. Answer is 1. Quote Link to comment Share on other sites More sharing options...
Payel Maity Posted May 8, 2014 Share Posted May 8, 2014 For Q2 , I think the correct answer is N. If we take an array of 2N elements where N=6. Now, A[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] be an array for eg. For 2-0rdered : 0 1 2 3 4 5 6 7 8 9 10 11 where 0 1 For 3-ordered : 0 1 2 3 4 5 6 7 8 9 10 11 where 0 1 2 now lets take the 10th element i.e. A[10]=9 . in 3 ordered its position is in 4th where as in 1 order its position is in 10th. so (10-4=6 ) ie. N position far . Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.