check the unique URL

[nitin1]

i have thought a lot on this. but not getting O(n) solution. given n URL's and you have to find the unique URL in that (if there is any). you have to print that URL. thanks. O(n2) solution is a stupid solution, some O(n) is acheivable, but not getting how can it be O(n). i have lastly thoguht about tries. can it be like this ? some related to tries ? thanks alot in advance.

[Moschops]

You need to think of a way that you only look at each entry in the list once, and at the end of it know the answer, or at least can find it very quickly.

How would you do this on paper? If I read out a list of words to you, and you have to tell me which one I only said once. This is programming. Thinking about the problem in a way that lends itself to a programatic solution. All the rest is just memorising syntax. We'll make it really simple. There are only three words in my list, so one of them I'll say twice, and one of them I'll say once. How will you know which I only said once?

[deceptikon]

some O(n) is acheivable, but not getting how can it be O(n)

I can immediately think of an O(mn) solution where m represents the length of these strings, but strictly O(n) kind of ignores the fact that you're dealing with collections of characters or assumes that some constant form of identity for each URL already exists. Otherwise you have to calculate the identity of a URL and that factors into the time complexity.

[Moschops]

Perhaps we use different notations. I class O(n) and O(mn) and indeed O(any multiple of n at all) as all being O(n).

[nitin1]

ohh... @moschops! your answer give me very nice approach to go for any answer!. too good.. thanks. i would mark something or have some mnemonic to identify any word which u have said and when u will say it again , i will put cross ahead of it. at last , i will check my mnemocs which dont have cross on it, and that is my answer.

@james sir, what is that solution u talking about ? is that trie related or what ? can you exemplify it litlle bit ? thanks from heart to both of you.

[deceptikon]

Perhaps we use different notations.

It seems we do. Mine is correct. ;)

I class O(n) and O(mn) and indeed O(any multiple of n at all) as all being O(n).

What happens when the growth of m reaches or exceeds the growth of n? You're assuming that m is insignificant, which isn't a safe assumption. It's not unreasonable for O(mn) to be equivalent to O(n*n), which as I'm sure you're aware equates to O(n^2). It could be even worse than that, and saying that the complexity is O(n) for such cases would be woefully inaccurate.

In complexity analysis you're allowed to discard constants from the equation, not independent variables that have their own asymptotic growth.

@james sir, what is that solution u talking about ? is that trie related or what ?

The O(mn) solution I was thinking of was a simple frequency table or map. One pass through the URL collection to build the table and another pass to look for frequencies equal to 1. The m part of the equation accounts for comparing URL strings when building the table.

[nitin1]

which table are you talking about ? can you tell me in context of C++ or C ? i mean are you talking about this :

map<string,int> m;

or what ? in this map, it is red-black tree and it is logn complexity. OR are you talking about hashmap in which we use some hash function in O(1) ? if latter is the case, then why O(m) is there with that, because in hash map we hash the strings in O(1). please make me correct at any point if i am wrong. thanks a lot to you.

[Moschops]

What happens when the growth of m reaches or exceeds the growth of n?

I took m to be a big constant, or at least something that would in practical terms be trusted not to exceed some definable constant.

[deceptikon]

can you tell me in context of C++ or C ?

unordered_map<string, int> freq;
string line;

// O(mn) complexity
while (getline(in, line))
{
    ++freq[line];
}

// O(n) complexity
for (auto x : freq)
{
    if (x.second == 1)
    {
        cout << x.first << '\n';
    }
}

i mean are you talking about this : map<string,int> m;

Yes, that's a suitable option for implementing a frequency table. Though building a frequency table based on a balanced tree is O(nlogn).

in this map, it is red-black tree and it is logn complexity.

Search in a red black tree is O(logn).

then why O(m) is there with that, because in hash map we hash the strings in O(1).

Search in a hash map is amortized O(1). Did you think hashing strings of unknown length is an O(1) operation? ;) The O(m) part of the equation is to account for the management of your string data: copies, comparisons, etc... If you were working with integers or fixed length strings then that would all be constant time, but last I checked, URLs weren't fixed length.

[nitin1]

okay boss! that means hashing in unordered_map will take o(m) time for each string . i was wrong because hashing the strings will i think scan the string atleast once. right ? that why it is now O(mn). am i right ? thanks.

[deceptikon]

hashing the strings will i think scan the string atleast once. right ?

Yes.