InterviewStreet programming challenges discussion

[Desmond]

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.

Input:
The first line contains the number of test cases T. Each of the next T lines contains a string each.

Output:
Output T lines containing the answer for the corresponding test case.

Constraints:
1 <= T <= 10
The length of each string is at most 100000 and contains only lower case characters.

Sample Input:
2
ababaa
aa

Sample Output:
11
3

Explanation:
For the first case, the suffixes of the string are "ababaa", "babaa", "abaa", "baa", "aa" and "a". The similarities of each of these strings with the string "ababaa" are 6,0,3,0,1,1 respectively. Thus the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is 2 + 1 = 3.

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]

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]

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]

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

 

[Desmond]

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]

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]

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]

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]

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]

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]

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

One good site is gpl4you.com