# InterviewStreet programming challenges discussion



## Desmond (Jun 13, 2012)

Hi,

One of my friends pointed me towards this site: *www.interviewstreet.com/challenges

It is like a programming leaderboard, wherein you solve problems and get ranked. So, I have started this thread to discuss challenges, their algorithms, your rank/score, what you tackled lately etc.

I would ask you to avoid putting up your code so that everyone can rack their brains 


*EDIT:* I've tackled this problem today:



> For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.
> 
> Calculate the sum of similarities of a string S with each of it's suffixes.
> 
> ...



However, the code I wrote in Java seems to pass only 4 out of 10 test cases. Since they have not shown what extra testcases they are using to test, I cannot know what went wrong. So, referring to the above problem, what else, according to you guys, should I test for? 

PS: The code passes the above mentioned test cases successfully.


----------



## nims11 (Jun 13, 2012)

good thread! I practice in SPOJ. Better Change this thread to "Online Judge Discussion Thread"

*EDIT:* solved that string similarity problem and got accepted. What is your approach?


----------



## Desmond (Jun 14, 2012)

How many test cases did your code solve?

I wrote a recursive method to get the total number of similarities, the original string and a start index passed as arguments. Created suffixes of the the original string beginning at the passed index and compared it to the original string character by character and obtained the similarity for that iteration. Every new iteration, I incremented the start index until the index matched the length of the original string. 

What was your approach?

PS: Just checked, my code got accepted. My rank is now 5691 and score 90.


----------



## nims11 (Jun 14, 2012)

all.
i proceeded iteratively, comparing the suffixes. O(n^2) solution.


----------



## Desmond (Jun 14, 2012)

So, what I cannot understand is what are test nos. 5-10 and why my code is failing. 

The challenge also states that the length of the string should be 100000 max, did you check this constraint? I tried entering a string of this length but got a stack overflow error.

PS: I need a crash course on time complexity. Any resources?


----------



## nims11 (Jun 14, 2012)

i just reserved space for 100000 characters. No need to check the constraints, just make sure your code can store it. btw a recursive solution for this problem is quite overboard and unnecessary. maybe you are getting stack overflow error in worst case due to recursion.

I read time complexity from "Introduction to Algorithm" (Cormen) book. Just get the idea of time complexity, you will keep getting comfortable as you keep solving questions.


----------



## Desmond (Jun 14, 2012)

What language you used?

I was checking the string length constraint, the problem was that I had set the constraint to 10000 instead of 100000. Corrected it, now it is passing 7 test cases and failing 3 because of exceeding time limit.

Edit: I am using Java, there is no way of reserving space that I know of, any way to go about this?


----------



## nims11 (Jun 14, 2012)

i used C++. by reserving space i meant *char str[100001];* since i prefer it over using std::string.

No idea about java. Just make sure that your string can hold 100000 characters. Also change your approach from recursive to iterative.


----------



## Desmond (Jun 14, 2012)

Yup, optimized my code and used two loops this time. Passed 8 test cases this time, but still failing in two test cases due to excessive time.

I just found out that a String class in java can hold a char array of 4 bytes, which I think is more than enough.

Edit: I've been wondering whether it is a problem with Java, since Java is known to be pretty slow.


----------



## nims11 (Jun 14, 2012)

DeSmOnD dAvId said:


> Edit: I've been wondering whether it is a problem with Java, since Java is known to be pretty slow.



this is true as most competitive coders prefer C++. But this doesn't make much difference in most cases. Java submissions are popular and only cause problems in some extreme problems.


----------



## mitraark (Aug 4, 2012)

Can anyone suggest some good sites where I can give mock exams [ preferably technical and not aptitude ]

One good site is gpl4you.com


----------

