• Post Reply Bookmark Topic Watch Topic
  • New Topic

Programming with Strings  RSS feed

 
Ranch Hand
Posts: 109
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If a string is given as below :
"Every day I want to play the game table tennis"  , we need to find the substring "I want to " from the main string, and if it exists it should be removed  to produce the sentence : "Every day  play the game table tennis" .

This should be done without using any String functions like indexOf(), substring(), etc. Only charAt() can be used. Asked in an interview.
How to do it ? And why do they not allow these functions to be used ? Then what is the point of learning these advanced features and doing Java certifications adn learning Java in depth?




 
author & internet detective
Marshal
Posts: 37693
575
Eclipse IDE Java VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Lilou Laure wrote:This should be done without using any String functions like indexOf(), substring(), etc. Only charAt() can be used.


I imagine you can also use length().

Lilou Laure wrote:How to do it ?


Give it a try. Can you describe it in English first? You'd loop through each character and keep track of what?

Lilou Laure wrote:And why do they not allow these functions to be used ? Then what is the point of learning these advanced features and doing Java certifications adn learning Java in depth?


They are trying to test your understanding of loops and your logic. They wouldn't have you do this once they hired you. It's hard to come up with interview questions that are simple enough to code at an interview and non trivial. So sometimes that comes with adding constraints such as this one.
 
Sheriff
Posts: 22949
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's how I would do it: First I would write the code in the normal way, using whatever String methods are necessary. Then for every String method I wasn't allowed to use, I would write my own version (as a method in my code) using only allowed methods and modify the original code to use that version instead.
 
Ranch Hand
Posts: 207
3
Java MySQL Database Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have done this question quite a bit, but what I am not getting is that in the final String how to remove the string "I want to". I have removed it, but I am getting boxes in place of the blank.





Here is my approach.
Please guide me how to get rid of those boxes and get only single space. Basically I have performed subtraction but, don't know how to avoid those boxes and get only single space.
Please correct me wherever I am wrong, since I followed very naive approach

Also, what I am getting is->

Space complexity-> O(n)
Time Complexity-> O(n^2) // little big

Please guide me how to improve the above approach to get less time complexity as compared to O(n^2).

Thanks Lilou, for such a great question.

Well, can you tell me that in which company's interview, this question was asked?

 
Marshal
Posts: 56820
173
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have had to do that sort of thing in Forth, where I could only implement the equivalent of charAt (Forth=C@ pronounced C‑fetch). You can find the char the same in both places, then continue until you reach the end of the String or a different char. If the end of the shorter String comes first, you have an included String (=substring).
I only had to implement prefix and suffix rather than an included substring, but you can repeatedly test for prefix at successive starting positions along the larger String.

Have you considered directly copying chars from the source String's toCharArray to another char[]? You can create a new String easily from that char[].

Don't mention the name of the company you were applying to.
 
Lilou Laure
Ranch Hand
Posts: 109
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

O Shea wrote:I have done this question quite a bit, but what I am not getting is that in the final String how to remove the string "I want to". I have removed it, but I am getting boxes in place of the blank.





Here is my approach.
Please guide me how to get rid of those boxes and get only single space. Basically I have performed subtraction but, don't know how to avoid those boxes and get only single space.
Please correct me wherever I am wrong, since I followed very naive approach

Also, what I am getting is->

Space complexity-> O(n)
Time Complexity-> O(n^2) // little big

Please guide me how to improve the above approach to get less time complexity as compared to O(n^2).

Thanks Lilou, for such a great question.

Well, can you tell me that in which company's interview, this question was asked?



You have kind of hard coded it for the fragment "I want to" . Thats what even i did. But they want it to work for any fragment that they give. like for eg : " play the game" or anything else.
 
Lilou Laure
Ranch Hand
Posts: 109
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Jeanne wrote:They are trying to test your understanding of loops and your logic. They wouldn't have you do this once they hired you. It's hard to come up with interview questions that are simple enough to code at an interview and non trivial. So sometimes that comes with adding constraints such as this one.



Oh but sometimes it gets dfficult to code it within the given time duration as well as show a perfect output.   
 
O Shea
Ranch Hand
Posts: 207
3
Java MySQL Database Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, it is hardcoded, this is a problem.
and yes, time is also a problem, we have to do it in quick and efficiently.
 
Lilou Laure
Ranch Hand
Posts: 109
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have come up with this solution :
Please let me know if its fine. As far as i have tested it, it is working fine.


 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!