• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Interview Questions

 
Rovart Shrivastava
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 49472
64
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 241
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can't figure this logic out....went from "F" to "G" and "G" to "F". I would have asked for a requirements document.
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Srikanth Basa
Ranch Hand
Posts: 241
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 11893
203
C++ Firefox Browser IntelliJ IDE Java Mac Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
Deepak Bala
Bartender
Posts: 6663
5
Firefox Browser Linux MyEclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34695
367
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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."
 
Gabriel Claramunt
Ranch Hand
Posts: 375
Monad Scala
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes it was a basic interview question to check the algorithm.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic