See :D

M

McAgnel

Disciple
TE lacks a bit in the programming front. I mean the discussions.. I request the members to contribute a bit more in this aspect... anyways, I will try to do my bit here... We can share code/logic/what ever and the person who cracks it is allowed to give the second question.

Ahhhh... Instead of calling them questions.. lets call then SNIP from here on..

here is the first SNIP i took from another group,

Take a look..

Code: 
Snip 1

Code: 
int main()

 {

   char *p = malloc(100);

   p = "india";  //assuming p is not null

   p++;

  free(p);

 }

1) How would free behave?

2) Will the program get executed properly?

PS : 'm sure, Josh will have a crack at this :D
 
I am guessing the program would choke. You can only free pointers that are obtained via a call to the (m)(c)(re)alloc functions.

Here's one from my side - Suppose you are given an array of random elements containing duplicates. Suggest the best possible way to eliminate the duplicates.

Eg: if you are given 6,3,1,8,3,7

the result should be 6,3,1,8,7 (order is irrelevant)
 
psynaps3 said:
I am guessing the program would choke. You can only free pointers that are obtained via a call to the (m)(c)(re)alloc functions.

Here's one from my side - Suppose you are given an array of random elements containing duplicates. Suggest the best possible way to eliminate the duplicates.

Eg: if you are given 6,3,1,8,3,7

the result should be 6,3,1,8,7 (order is irrelevant)
Click to expand...

Absolutely right! A better explanation would do no harm :)

The reason is that the address returned by malloc is overwritten by the address of the string literal. And that address gets incremented as well.

Take a look at this piece of code

Code: 
int main()

 {

   char *p = malloc(100);

   printf("Address in P : %d\n",p);

   p = "india";  //assuming p is not null

   printf("Address in P : %d\n",p);

   p++;

   printf("Address in P : %d\n",p);

  //free(p);

 }

this is the output you get

Code: 
Address in P : 4397968

Address in P : 432540[B]4[/B]

Address in P : 432540[B]5[/B]

Note the small increment in the address.

If the pointer is of data type integer, this is the output

Code: 
Address in P : 4397968

Address in P : 432540[B]4[/B]

Address in P : 432540[B]8[/B]

Difference 4 bytes. :)

Like psynaps3 said, you can't free the space which you have not allocated rather have control over. In this case, the behavior is unpredictable.

Okay now coming over to snip 2,

Answer:

create another array, retrieve each element from array1, check if it is present in array2? If not, store it there. :)
 
psynaps3 said:
I am guessing the program would choke. You can only free pointers that are obtained via a call to the (m)(c)(re)alloc functions.

Here's one from my side - Suppose you are given an array of random elements containing duplicates. Suggest the best possible way to eliminate the duplicates.
Eg: if you are given 6,3,1,8,3,7
the result should be 6,3,1,8,7 (order is irrelevant)
Click to expand...

Arrange the 2nd array in ascending order
6,3,1,8,3,7
1st element in the array1 is 6
so we put it in 2nd array
nxt is 3
so we shift 6 1 place and put 3 infront of it
it may be tiresome for this prob
but if the array is bigger then it'll decrease the time complexity
since tima cplxity of bin search< random 1
 
psynaps3 said:
That wouldn't be too efficient now, would it ;)
Click to expand...

Agreed, tot you just needed some solution :D
Anyways, if you don't want to create another array, then here it goes.

read the value from the position 0 in the first array into a variable, and search the array for that variable, where ever found, put a null, this way duplicates are removed. Once done with the entire array, push all the null to the end and numbers to one side, better sort it. ;)
 
scarsinme said:
Agreed, tot you just needed some solution :D
Anyways, if you don't want to create another array, then here it goes.

read the value from the position 0 in the first array into a variable, and search the array for that variable, where ever found, put a null, this way duplicates are removed. Once done with the entire array, push all the null to the end and numbers to one side, better sort it. ;)
Click to expand...

If u dont sort it the time cplxity will be very high.:mad:
2 b precise O(n)=n^2

So u've 2 sort it

& nowhere in ur snippet it was mentioned that 1 cant use a 2nd array
 
And how do you propose to sort it?

You do know that there is no comparison sort less than O(nlogn). Which is better than O(n^2), but do you really want to do a heapsort?

I agree that sorting is the most efficient method.
 
psynaps3 said:
I am guessing the program would choke. You can only free pointers that are obtained via a call to the (m)(c)(re)alloc functions.

Here's one from my side - Suppose you are given an array of random elements containing duplicates. Suggest the best possible way to eliminate the duplicates.
Eg: if you are given 6,3,1,8,3,7
the result should be 6,3,1,8,7 (order is irrelevant)
Click to expand...

If order is irrelevant, why bother too much about sorting? I am not sure about the types of sorting available, but you can have 2 pointers, one to point to the location of storage, one moving to find the next val to use/store null in its place.
 
I guess I should have explicitly mentioned that *memory* is not a constraint here. Apologies! All I am asking here is to see different solutions to this problem.
Let me rephrase the question a bit.

What is the most "time efficient" method to remove the duplicates?

Maybe, you people could also come up with the most space efficient way too? :)

PS: I do not know the answer, so please don't ask me to post the solution. I do have a few ideas though.
 
scarsinme said:
If order is irrelevant, why bother too much about sorting? I am not sure about the types of sorting available, but you can have 2 pointers, one to point to the location of storage, one moving to find the next val to use/store null in its place.
Click to expand...
Like atanuroy mentioned, your method would require a time complexity of O(n*n). I am pretty sure there are better solutions to this problem. Think think! :cool2:
 
create a 'set' and add the elements there

im sure the ppl who made java have already implemented the best algo's possible :p

set a=new set();

a.add(element);

or one can create a hashmap and add the key in it
 
nukeu666 said:
create a 'set' and add the elements there
im sure the ppl who made java have already implemented the best algo's possible :p
set a=new set();
a.add(element);
or one can create a hashmap and add the key in it
Click to expand...
haha, no shortcuts please :)
 
nukeu666 said:
create a 'set' and add the elements there
im sure the ppl who made java have already implemented the best algo's possible :p
set a=new set();
a.add(element);
or one can create a hashmap and add the key in it
Click to expand...

this is SEE (C) :bleh: No java :no: :hap5:

psynaps3
I am thinkin' :eek:hyeah:
 
Back
Top