someone
BAN USERRead question again.
"5 gates to race".. it clearly specifies that for one race you can race only 5 horses. Each gate will have one horse and when gun is shot they start running.
Moreover, I dont think 5 horses from one direction and 5 from another is called a race. Have not seen one like that.
Even if this type of race is allowed, how can you mark middle of racetrack as the destination? A horse who completes the racetrack of half length in best time, may not complete entire racetrack in best time.
let me explain in detail.
race1: a1 a2 a3 a4 a5, winner: a1
race2: b1 b2 b3 b4 b5, winner: b1
race3: c1 c2 c3 c4 c5, winner: c1
race4: d1 d2 d3 d4 d5, winner: d1
race5: e1 e2 e3 e4 e5, winner: e1
race6: a1 b1 c1 d1 e1, winner: a1
lets arrange horses of 6th race in their final standing. lets say a1>b1>c1>d1>e1
a1 has beaten winners of all group winners so he is the fastest.
d1 and e1 could not make to top 3 so how can any other horse of their initial group make to top 3 (since we already know d1 and e1 were winners of their groups)? so we reject 2 groups d1 and e1. and b1 c1 are sent back to their respective groups because they have chances to be amongst top 3.
our job is to find ONLY 2nd and 3rd fastest because we already have a1 as the fastest horse. so who all can be the candidate for those 2 positions?
a2 and a3 (2nd and 3rd in 1st group, they are top two)
b1 and b2 (1st and 2nd of 2nd group, they are top two)
c1 (why only one from this? because even the winner of this group which was c1, had 2 horses above him in 6th race. so it cant come 1st or 2nd ever so this group is candidate for 3rd place only)
rest 2 groups were already rejected (i described above why)
race 7: a2 a3 b1 b2 c1.
"You assume there is only 1 occurrence of each char of string 2 in string 1"
-> Not at all. I am initializing all elements of hash array as zero and for each occurrence of an alphabet in string1 i am INCREMENTING corresponding index of hash by 1 (i am not marking it as 1 but incrementing by 1). in example string1, 'r' occurs twice so my corresponding hash index hash['r'-'a'] would be 2. after i delete one occurrence of 'r' from string2 (car) there would still remain one 'r' in hash array.
if i understood 'reordering' concept of this question..
assuming all letters are small.
1) hash[26] = {0};
2) hash 1st string as:
i = 0;
while(string1[i])
hash[string1[i] - 'a']++, i++;
3) for each letter in string2, print it and decrease from hash this way
i = 0;
while(string2[i])
hash[string2[i] - 'a']--, i++;
4) for remaining letters in hash table, print any permutation. for best complexity just print the hash array from beginning to end.
- someone June 29, 20117 races.
1) divide 25 horses in 5 groups and you have 5 winners.
2) race these 5 winners and the winner of this race is the fastest horse, 2nd and 3rd horse (along with their respective groups) are candidate for remaining 2 positions while we can plainly reject remaining 10 horses belonging to horses who stood 4th n 5th in 6th race.
3) for final race we choose following horse
-> those who came 2nd and 3rd in 1st group
-> those who came 1st and 2nd in 2nd group
-> the one that came 2nd in 3rd group.
It seems same as its trivial counterpart. Start merging arrays from the back, means start comparing from the highest elements of both arrays.
1) i = m-1 and j = k = n-1.
while(A[j]==-1) j--
2) run loop till k>=0
3) if(A[j] == B[i]) A[k] = A[k-1] = A[j];
k = k-2; i--; while(A[j]==-1) j--;
4) else if(A[j] > B[j]) A[k] = A[j];
k--; while(A[j]==-1) j--;
5) else A[k] = B[i];
k--; i--;
suppose length[i] is the length of the longest increasing subsequence ending at index i.
length[0] = 1
for all index from 1 to n-1
if array[i] > array[i-1] then length[i] = length[i-1]+1 because we are extending the sequence ended at index (i-1) by 1
else length[i] = 1 because we are starting new sequence from ith index.
find greatest length[i] for all i and is the answer required. similarly can be done for decreasing subsequence. time O(n)
you know that in a singly linked list there is only one pointer associated with each node which is called 'next' pointer. but here, each node additionally has one more pointer which is called 'arbit' and this pointer can point to any node of the linked list. you are to create another singly linked list which is copy of this original list having both next and arbit pointers.
- someone June 25, 2011
The easiest would be to swap data. But if reference of nodes are stored already then swapping data would create chaos, In that case one should swap nodes itself.
- someone September 20, 2012Lets say list is a->b->c->d->e and we want to swap c with d,
lets take two pointers p and q, where p points to b and q points to c. Following three lines will swap the nodes.
p->next = q->next (so now b points to d)
q->next = p->next->next (now c points to e)
p->next->next = q (now d points to c)
this will result in a->b->d->c->e