posted 4 years ago

For fun I am working through some algorithmic problems.

Worked on a problem this week for palindrome detection. Part of the problem is to give the time complexity. I don't know the answer for my implementation. Hoping you guys can clarify for me.

Supposedly this was given in an Amazon interview:

Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory.

Give the time complexity. The node structure is

Spoiler alert: I'm going to tell you how I solved this. But I'm guessing most of you have seen this before....I know I have, in the past. It's a pretty stock problem that gets put into a lot of algorithm books.

The basic idea for my implementation is the two pointer approach. One pointer at the start of the list, one pointer at the end. Compare the two elements. Then move each pointer in towards the middle and do it again, until you hit the middle.

For example "A car, a man, a maraca" (an awesome palindrome):

First time the method is called it compares "A" at the start with "a" at the end. Next "c" of car gets compared with "c" at the end of "maraca." The algorithm recurses toward the middle of the list.

As you can tell from the node structure provided, it's a singly-linked list though so in a poor implementation (not mine) every time a recursive call is made, the two pointers both start at the beginning of the list again and run them through the entire list up to the last value. When the first pointer hits "first" it stays there, but the second pointer continues advancing until it gets to "last."

This means that for N elements, it runs through all N elements, then N-1, then N-2, etc. I believe that is an O(N^2) time complexity.

BUT...

I optimized this by passing a copy of the first pointer into the recursive call. Now I can start one ahead of where I started last time. I don't have to run the pointer through the list from the beginning every time to catch up with where I was.

So here's my question because you guys know your time complexity analysis better than me. Given this algorithm what do you think is the time complexity?

I actually ran a few values into a table.

The poor implementation:

String length, total iterations+recursions

15, 91

17, 116

19, 144

21, 175

23, 209

My implementation:

String length, total iterations+recursions

15, 70

17, 116

19, 108

21, 130

23, 154

Basically it seems like what is happening here is that if N is the length of the string, the recursive method gets called N / 2 times. Inside that method, it iterates through an odd number of elements, that is 2 less each time.

1st call - N

2nd call - N-2

3rd call - N-4

...

(N / 2th-1)th call - 5

N / 2th call - 3

Any thoughts? Let me know if I did not explain myself clearly. I believe this falls into a standard O(log n) "divide and conquer" complexity but I could be wrong and I am really rusty on this.

Worked on a problem this week for palindrome detection. Part of the problem is to give the time complexity. I don't know the answer for my implementation. Hoping you guys can clarify for me.

Supposedly this was given in an Amazon interview:

Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory.

Give the time complexity. The node structure is

Spoiler alert: I'm going to tell you how I solved this. But I'm guessing most of you have seen this before....I know I have, in the past. It's a pretty stock problem that gets put into a lot of algorithm books.

The basic idea for my implementation is the two pointer approach. One pointer at the start of the list, one pointer at the end. Compare the two elements. Then move each pointer in towards the middle and do it again, until you hit the middle.

For example "A car, a man, a maraca" (an awesome palindrome):

First time the method is called it compares "A" at the start with "a" at the end. Next "c" of car gets compared with "c" at the end of "maraca." The algorithm recurses toward the middle of the list.

As you can tell from the node structure provided, it's a singly-linked list though so in a poor implementation (not mine) every time a recursive call is made, the two pointers both start at the beginning of the list again and run them through the entire list up to the last value. When the first pointer hits "first" it stays there, but the second pointer continues advancing until it gets to "last."

This means that for N elements, it runs through all N elements, then N-1, then N-2, etc. I believe that is an O(N^2) time complexity.

BUT...

I optimized this by passing a copy of the first pointer into the recursive call. Now I can start one ahead of where I started last time. I don't have to run the pointer through the list from the beginning every time to catch up with where I was.

So here's my question because you guys know your time complexity analysis better than me. Given this algorithm what do you think is the time complexity?

I actually ran a few values into a table.

The poor implementation:

String length, total iterations+recursions

15, 91

17, 116

19, 144

21, 175

23, 209

My implementation:

String length, total iterations+recursions

15, 70

17, 116

19, 108

21, 130

23, 154

Basically it seems like what is happening here is that if N is the length of the string, the recursive method gets called N / 2 times. Inside that method, it iterates through an odd number of elements, that is 2 less each time.

1st call - N

2nd call - N-2

3rd call - N-4

...

(N / 2th-1)th call - 5

N / 2th call - 3

Any thoughts? Let me know if I did not explain myself clearly. I believe this falls into a standard O(log n) "divide and conquer" complexity but I could be wrong and I am really rusty on this.

posted 4 years ago

I'm still seeing O(n^2). To get O(n log n), you have to be recursively breaking the original problem into chunks each with a fraction of the size of the previous recursion, not just a constant amount less. Another way to look at is the sum of 1 .. n is n(n+1)/2, which is better than n^2, but still is O(n^2).

posted 4 years ago

That last constraint is a huge one, and probably needs to be explained in detail because I suspect, if it's taken literally, that there

And a recursive solution, even though one may be possible without explicitly

Are you, for example, allowed to define a counter? Or a variable to hold a single character?

Winston

Scott Shipp wrote:Worked on a problem this week for palindrome detection. Part of the problem is to give the time complexity.

...

Given a string in the form of a Linked List, check whether the string is palindrome or not. Don’t use extra memory.

That last constraint is a huge one, and probably needs to be explained in detail because I suspect, if it's taken literally, that there

*is no*solution.

And a recursive solution, even though one may be possible without explicitly

*defining*any extra memory is actually likely to take the most memory of all.

Are you, for example, allowed to define a counter? Or a variable to hold a single character?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Piet Souris

Rancher

Posts: 1943

66

posted 4 years ago

The example given "A car, a man, a maraca", isn't a palindrome, because of the spaces and the commas.

My suggestion would be: let's do it the modern way! Create a proper LinkedList and check if

this list is equal to list.reverse()! That would give an O(n) complexity and saves a lot of programming...

But of course Winstons remarks are spot on. Problem with these kind of questions is always: what exactly is allowed?

Greetings,

Piet

My suggestion would be: let's do it the modern way! Create a proper LinkedList and check if

this list is equal to list.reverse()! That would give an O(n) complexity and saves a lot of programming...

But of course Winstons remarks are spot on. Problem with these kind of questions is always: what exactly is allowed?

Greetings,

Piet

posted 4 years ago

I came up with the exact formula for the time complexity:

(n-1)/2 * (((n+1)/2) +1)

So essentially (n/2)^2. So yes the Big-O is still O(N^2) although it is miles ahead performance-wise than the "poor implementation" I mentioned.

Winston--I agree but since there was no explanation given about that point on the site where I saw this posted, I decided it must mean not using any external data structure like a hashmap or whatever.

Piet--Generally in my experience palindromes are formed from the letters without the punctuation and the case is ignored. Case in point is the most famous palindrome, "A man, a plan, a canal, Panama!" In my solution I stripped all punctuation / spaces / etc. and lowercased everything before I did the comparison. If someone wants to define "palindrome" differently then the code can be modified to take that into account..

(n-1)/2 * (((n+1)/2) +1)

So essentially (n/2)^2. So yes the Big-O is still O(N^2) although it is miles ahead performance-wise than the "poor implementation" I mentioned.

Winston--I agree but since there was no explanation given about that point on the site where I saw this posted, I decided it must mean not using any external data structure like a hashmap or whatever.

Piet--Generally in my experience palindromes are formed from the letters without the punctuation and the case is ignored. Case in point is the most famous palindrome, "A man, a plan, a canal, Panama!" In my solution I stripped all punctuation / spaces / etc. and lowercased everything before I did the comparison. If someone wants to define "palindrome" differently then the code can be modified to take that into account..

posted 4 years ago

Well, two spring to mind:

1. It doesn't need to be recursive.

2. The first iteration (the one that finds the "last" element) is slightly different from the others, since it can also store the length of the "chain" (N), or the index of the last element, for subsequent iterations to use.

Indeed, if you're allowed to store both

loop.

That's why I said that what they mean by "extra memory" is very important.

Winston

Scott Shipp wrote:Any thoughts?

Well, two spring to mind:

1. It doesn't need to be recursive.

2. The first iteration (the one that finds the "last" element) is slightly different from the others, since it can also store the length of the "chain" (N), or the index of the last element, for subsequent iterations to use.

Indeed, if you're allowed to store both

`first`

*and*

`last`indices, all subsequent iterations can be done with a

`while(++first < --last)`

loop.

That's why I said that what they mean by "extra memory" is very important.

Winston

Articles by Winston can be found here

Consider Paul's rocket mass heater. |