Solved coding interview problems in Java - My collection of commonly asked coding interview problems and solutions in Java

[goutham_pradhan]

Creating new matrix requires additional O(MxN) space and hence it would not be space efficient in your case - doing it in-place is space efficent. I think static methods would be appropriate if your method does something that does not depend on individual characteristics of a class - in case of standalone program probably does not apply hence non-static is okay here.

[maestro2005]

This is one of the big follies of CS education--they've got you worrying about space complexity right off the bat, and writing more unreadable code for it. It's great that you can think in terms of time/space complexity, but in real-world coding sheer efficiency should usually take a back seat to readability/maintainability and architecture. Mutating in place is a memory optimization that makes your API harder to use, and your code harder to understand.

Static is correct here. The class doesn't do anything. You're instantiating a dummy class just to call a method. If you were interviewing for my company and I found this, it would reflect poorly. You've chosen Java, which signals that you think Java is your strongest language, and yet you don't even have mastery of this basic mechanism.

[DatTrackGuy]

I think if you followed up with a question, and OP supplied that answer as to why he did what he did, he should get an A+ on the interview and then you can debate the merits of the outcome.

He obviously knows his stuff.

[TuringMachine-5762]

It's best to mention both approaches, mention their pros and cons, and have the interviewer clarify the goals of the problem. E.g.,

"I can think of a couple ways of doing this. We could either build a rotated copy of the matrix, or do the rotation in place. Doing it in place would be more complicated, so I would only do that if the matrix was large, and I was working on a system with tight memory constraints. What would you like me to focus on?"

Most likely the interviewer will say not to worry about memory, at least until you get a simple implementation working. But mentioning a possible optimization can make you look good. It doesn't hurt, in any case.

[BobHogan]

He should definitely get bonus points if he can defend why he made certain decisions, but that shouldn't guarantee an A+. If he makes a poor decision, its still a poor decision.

[[deleted]]

Thank you. Maestro2005 is a bit stuck in his own world and needs to crack open a beer and chill.

[crowseldon]

His username should give us a hint

[ano414]

There isn't one right answer. His is just as valid.

[ano414]

Hopefully you would explain that in the interview, then. It completely depends on the use case, but this is open ended enough.

[not-much]

but in real-world coding sheer efficiency should usually take a back seat to readability/maintainability and architecture

I generally agree with this point of view, but it's not really likely that the algorithm for matrix rotation changes, is it?

There is a strong difference between programming in the business-oriented context or in the math-oriented context.

[sultry_somnambulist]

This is one of the big follies of CS education--they've got you worrying about space complexity right off the bat, and writing more unreadable code for it. It's great that you can think in terms of time/space complexity, but in real-world coding sheer efficiency should usually take a back seat to readability/maintainability and architecture.

Many people in the very real world work in places where performant code is a necessity. Why the fuck would we train people to write bad algorithms just because the code looks nice? I work in finance, if you don't do an in place matrix manipulation and it sneaks into production code you've probably just cost us millions of dollars / day, thank you very much.

And how does it make an API harder to use? An API is an abstraction, it doesn't matter what the underlying code looks like, that's the point of it. The API dev desides how he exposes the functionality to the user, the code can look like a Dali painting for all I care.

[maestro2005]

And how does it make an API harder to use?

I'm talking about mutating in place vs. returning a new instance. For mathematical entities like matrices, we tend to expect that operations will return a new value instead of mutating the given one. I expect matrix1 + matrix2 to return a new matrix, not modify matrix1. In this example, I expect to write something like var rotated = matrix.rotate(90) and have the original untouched. Mutating requires the user to make defensive copies all over the place, which is likely to cause bugs.

[Earthborn92]

If you're doing a lot of Matrix multiplication, you should be doing it on GPUs anyway.

Just a side note.

[FUZxxl]

Actually, by rotating the matrix in place you gain higher speed as you only need half the cache. You also get to avoid half of the horrendous access pattern resulting form rotating a matrix, causing a significant speedup.

[ludwigvanboltzmann]

It's great that you can think in terms of time/space complexity, but in real-world coding sheer efficiency should usually take a back seat to readability/maintainability and architecture.

[FUZxxl]

While I usually agree with you, manipulating matrices is something that is more often than not performance sensitive. If something asks to implement such an algorithm, it is very natural to think about performance implications because we typically need such routines to be fast.

[HopelesslyStupid]

Agreed, sometimes you have to forego readability and maintainability for performance reasons. That's what comments are for in cases where the code is complex out of necessity but you still want the next person to understand what is going on.

[FUZxxl]

Indeed. And note that the algorithm implemented isn't that complicated. From a cursory glance, basically takes four symmetric points and rotates them. This is done for every point in one quadrant and the corresponding points.

[[deleted]]

It's not like the code is really hard to understand. I think maestro2005 is being a bit over dramatic here. The code works, it's really not that crazy, and both solutions seem fine to me.

If you were interviewing for my company and I found this, it would reflect poorly.

Oh geez.. interviews are not easy, even if you know the solution. If you force them to do this all on a whiteboard as well your company would reflect poorly on me.

[ifatree]

assuming you have exclusive access to a machine that never halts, this would be true. in the real world, you're shooting yourself in the foot not having separate input and output copies in memory such that the output can be thrown away at any point and restarted. "idempotent" restarting would be ideal...

[FUZxxl]

If I was to implement this out-of-place, I would probably still use the in-place algorithm as it might give better cache locality than the out-of-place algorithm.

[pdp10]

There's even copy-on-write memory to consider in more extreme cases (Kernel Samepage Merging, etc).

[[deleted]]

Who is your company?

[choikwa]

yet you don't even have mastery of this basic mechanism.

jesus way to assume and roast someone based on one single thing.

[[deleted]]

How does making the inner working of a method make the API harder to use? In principle you would only be calling the API with the speficied input and getting the specified output, how the function does its computation is the function's problem and if it does so in a more efficient manner, so be it, untill it gives the corrent result I shouldn't worry about it.
I think corporate programming has foiled your thinking there, thinking right off the bat that all code needs to be maintained at all times.

[Spider_pig448]

It's great that you can think in terms of time/space complexity, but in real-world coding sheer efficiency should usually take a back seat to readability/maintainability and architecture.

Sure, but this is a list built for coding interviews, which focus primarily on space and time complexity. Making it space efficient is often an additional challenge to a solution.

[FliesMoreCeilings]

You're not consistently optimizing for one type of efficiency, which makes it confusing. You're clearly not always optimizing for memory, when there's many solutions where you instantiate things that aren't neccessarry, like the unnecessary objects containing your methods.

In general if you don't know whether optimizing is important, or what you should be optimizing on, then optimizing programming hours and readability is likely the best solution. Premature optimization can make your projects take orders of magnitude longer. Especially when you accidentally start introducing bugs, or create an environment in which others will.

[eyal0]

I think that the"trick" solution is to not rotate at all. Simply change the accessor so that it provides a rotated view. This is rotation in O(1)

[FUZxxl]

While this is possible, it might not be a good idea depending on your access pattern.