Interview Questions

[Rovart Shrivastava]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

  def rleLst(xs:List[(Int,Char)],x:Char)=
    if (xs==Nil) (1,x)::Nil else if (x==xs.head._2) (xs.head._1+1,x)::xs.tail else (1,x)::xs
  
  def rleLstToStr(xs:String, s:(Int,Char))=
    ((if (s._1>1) s._1.toString else "")+s._2 )+xs
  
  def rle(s:String)=
    s.foldLeft(Nil:List[(Int,Char)])(rleLst(_,_)).foldLeft("")(rleLstToStr(_,_))
  
  
  def main(args: Array[String])={
    println(rle(""))
    println(rle("a"))
    println(rle("aaacdddmmmmmmr"))
   }

[Rovart Shrivastava]

Yes it was a basic interview question to check the algorithm.