File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Jobs Discussion and the fly likes Interview Questions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Careers » Jobs Discussion
Bookmark "Interview Questions" Watch "Interview Questions" New topic
Author

Interview Questions

Rovart Shrivastava
Greenhorn

Joined: Feb 13, 2009
Posts: 4
Write functions for the following programs :
1. compress string "AAAABBBCCDEFHHH" to "4A3B2CDEG3H"
2. decompress string "4A3B2CDEG3H" to "AAAABBBCCDEFHHH"

please suggest some optimized approach to do it.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39828
    
  28
Welcome to JavaRanch
I am not convinced you have asked that in the correct forum.
We don't give out that sort of answer; please tell us what you thought the correct answer was, and we'll tell you what we think of it.
Srikanth Basa
Ranch Hand

Joined: Jun 06, 2005
Posts: 241
An obvious solution with nothing specified points to time complexity of O(n).

Any constraints mentioned by interviewer ? If there are constraints/assumptions provided then the solution possibly could be O ( log n)
Don Solomon
Ranch Hand

Joined: Jul 20, 2008
Posts: 48
I can't figure this logic out....went from "F" to "G" and "G" to "F". I would have asked for a requirements document.


Software development is an exercise in thinking not coding.
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375

Srikanth Basavaraju wrote:An obvious solution with nothing specified points to time complexity of O(n).

Any constraints mentioned by interviewer ? If there are constraints/assumptions provided then the solution possibly could be O ( log n)

I don't think you can compress/decompress the whole string without going through all the characters in the input, hence you can't do better than O(n) ... Or I'm missing something?


Gabriel
Software Surgeon
Srikanth Basa
Ranch Hand

Joined: Jun 06, 2005
Posts: 241
You are correct Gabriel. I also couldn't think of any better than O(n) but interviewers in general, don't ask a question where complexity is evident. I guess he/she might have provided more inputs which are missing from this post .
Andrew Monkhouse
author and jackaroo
Marshal Commander

Joined: Mar 28, 2003
Posts: 11508
    
  95

Note that Rovart did not give us any real information to go on, so asking for the "optimized" approach is not really useful. However, on the theory that optimized could imply elapsed time optimization (different from complexity), then there could be a divide and conquer optimization for both compression and decompression on a multi-cpu system. Whether this would be valuable or not would depend on a lot of other factors, and I would think that a good interviewer would probably be really interested in hearing what factors the candidate came up with that might make a difference.

As for the complexity of the code - a valid interview question can be asking if a provided solution can be optimized better even when the interviewer knows that it cannot. Personally I would only ask such a question if I was face to face with a person who is doing well in the interview - I would want to be able to judge how stressed they are before asking the question (if they are stressed then the question is a big no-no) and I would want to watch for any signs of stress and be able to pull them away from going down a rabbit hole. But if they are good then they may be able to see that there are no improvements possible. (I did get asked how I could improve a solution one time where the interviewer wanted to see if I would jump to a JNI solution).


The Sun Certified Java Developer Exam with J2SE 5: paper version from Amazon, PDF from Apress, Online reference: Books 24x7 Personal blog
Deepak Bala
Bartender

Joined: Feb 24, 2006
Posts: 6662
    
    5

Depending on whether the characters can repeat or not, your solution would vary a little. You cannot however compress / decompress better than O(N) since you need to go through the entire string to understand how to build the output string.


SCJP 6 articles - SCJP 5/6 mock exams - More SCJP Mocks
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 30929
    
158

This could also depend on the level of the job. If it is a basic job, maybe the question is really just on how to write an algorithm and we are reading into the word "optimal."


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Gabriel Claramunt
Ranch Hand

Joined: May 26, 2007
Posts: 375

Just for fun, here's a shot at the first problem in Scala
(hey!, it's an interview, is the chance to "show off")

Rovart Shrivastava
Greenhorn

Joined: Feb 13, 2009
Posts: 4
Yes it was a basic interview question to check the algorithm.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Interview Questions