Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes Java in General and the fly likes Java Code Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Java Code" Watch "Java Code" New topic
Author

Java Code

Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Hey guys.

I was recently assigned a homework problem by a company and based on my homework performance, I would have been selected for the subsequent interview process. However, I was rejected and the HR chap stated that I am not good enough to meet the technical standards of the company (which is kind of depressing). So, I was wondering if you guys could have a look at the assignment question and my solution and suggest valuable inputs that could be used to improve my chances in future job applications.

Thanks and Regards,
Vipin Anand


Here is the problem statement-->
QA Homework Assignment 4

Task

Implement the function described below. Include the test procedure you used to verify correctness of your solution. You may use Java or C#.

You will be evaluated on:

• Correctness of solution.
• Functional coverage of tests.
• Readability of code.
• Maintainability of code.
• Appropriate use of fundamental programming concepts.


Problem Description

You have a two-dimensional int array that is filled with the values -1,0,1. 0 indicates the cell is empty, -1 and 1 represent real values. Implement the following function

public static int FindSequence(int[][] grid, int length)

The purpose of FindSequence is to determine If a straight line sequence of either 1s or -1s of size "length" exists in grid. If such a sequence exists, return the value (either 1 or -1) that makes up the sequence. If no sequence is found, return 0.

Specifics
Sequences can wrap around array boundaries. That is, elements [0] and [length-1] are connected. Elements cannot be repeated within a sequence. Only adjacent elements can comprise a sequence. If more than 1 sequence exists in grid you should return the first you find (which it finds does not matter). Grids will never be larger than 10x10 Solutions in C# may use staggered or rectangular arrays.

Deliverables
For this assignment you should deliver documented source code (Java or C#) for FindSequence along with anything you used for testing (test case descriptions, unit tests...). We should be able to use your code in our unit tests without modification.

Example Grids
3x3 grid with 1 horizontal length=3 sequence:
[ 1, 1, 1]
[ 0, 0, 0]
[ 0, 1, 0]

3x3 grid with 1 vertical length=3 sequence:
[ 0,-1, 0]
[ 0,-1, 0]
[ 0,-1, 0]

3x3 grid with 1 diagonal length=3 sequence:
[-1, 0, 0]
[ 0,-1, 0]
[ 0, 0,-1]

5x5 grid with 1 horizontal length=4 sequence:
[ 0, 0, 0, 0, 0]
[ 0, 0, 0, 0, 0]
[ 1, 1, 0, 1, 1]
[ 0, 0, 0, 0, 0]
[ 0, 0, 0, 0, 0]

FAQ

Q: Are the length (i) and width (j) of the array equal? (i=j?)
A: Not necessarily. Your program should handle rectangular arrays.

Q: The problem states arrays will not be larger than 10x10, is this a condition I should enforce?
A: No, we will not test your solution with anything larger than 10x10. This limit is given simply so you can focus on an elegant solution rather than
a highly optimized and lengthy solution.

Q: Are values other than -1, 0, and 1 possible in the array?
A: No, the array will only contain those values.







Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 60774
    
  65

Doesn't look like a Servlets issue to me. I'll move this along to the Beginning Java forum...


[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Bear Bibeault wrote:Doesn't look like a Servlets issue to me. I'll move this along to the Beginning Java forum...


My apologies. Next time will make sure to keep things in the right section.
Stefan Evans
Bartender

Joined: Jul 06, 2005
Posts: 1016
First questions
- where are your test cases? How would you test this code? Thats a big part (or probably the larger part) of answering the question.
- I'm not a big fan of "static" I would probably have instantiated some objects to solve this problem.
- your 'equalize' method seems to do work that according to the spec is not needed. Maybe I'm making an assumption, but the question seemed to indicate you could expect a rectangular array. Checking and 'fixing' it to be rectangular seems to be extra unnecessary work I would mark you down on.


You call the method: AllWebLeads.searchSequence(i, j, -1, 1);
What does this -1 for angle mean? It is not documented.
I would suggest using an enumerated type for the angle to make it more readable.

Use JavaDoc for documenting your methods
Why does the method searchSequence return a value? Do you ever use it?
Using "Global variables" gets huge negative points from me.
I would suggest some JUnit test cases be written :-)



Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Stefan Evans wrote:First questions
- where are your test cases? How would you test this code? Thats a big part (or probably the larger part) of answering the question.
- I'm not a big fan of "static" I would probably have instantiated some objects to solve this problem.
- your 'equalize' method seems to do work that according to the spec is not needed. Maybe I'm making an assumption, but the question seemed to indicate you could expect a rectangular array. Checking and 'fixing' it to be rectangular seems to be extra unnecessary work I would mark you down on.


You call the method: AllWebLeads.searchSequence(i, j, -1, 1);
What does this -1 for angle mean? It is not documented.
I would suggest using an enumerated type for the angle to make it more readable.

Use JavaDoc for documenting your methods
Why does the method searchSequence return a value? Do you ever use it?
Using "Global variables" gets huge negative points from me.
I would suggest some JUnit test cases be written :-)






My Test case



angle = -1 implies very first time the loop enters into a row and encounters 1 or -1....its main purpose is to store the value of the location where 1 or -1 is found and use it in the modulus operation done at checkRepetition() to avoid elements that were already traversed before in the sequence. But yes, you are right I should have used Enumeration here.

I used static because of the problem definition. But yes I am not a big fan of static either.

Equalize method does not make an array rectangular. It basically solves a problem of unequal rows within the array.

For e.g. input array[] = {{1,0,1},{0,-1}}. Will output {{1,0,1},{0,-1,0}} so a 0 is appended at {0,-1} to make sure my program does not crash when I am traversing the array.


AllWebLeads.searchSequence(i, j, -1, 1); it does return the 'count' variable to check whether its equal to the expected length or not (its a recursive function).

Please, I would encourage you to further scrutinize my code and point out as many flaws as possible. What I see from your post is that I have issues with presentation of my code.
But from the operational perspective, I am very sure this code solves all possible input problems.



Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24183
    
  34

There is a method of 60 lines and one of 100 lines in the code; anything more than 10 lines is to be avoided, and methods of just a few lines are best. 100 lines is a huge red mark.


[Jess in Action][AskingGoodQuestions]
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Ernest Friedman-Hill wrote:There is a method of 60 lines and one of 100 lines in the code; anything more than 10 lines is to be avoided, and methods of just a few lines are best. 100 lines is a huge red mark.




Very good point from the code I see many repetitive operations must have been passed on to some servicing methods.....but one more thing doesnt that mean you are slowing down the operation? I mean the stack operations involved in function calls could be an overhead here.


But point taken. More inputs please!!
Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 60774
    
  65

Vipin Anand wrote:I mean the stack operations involved in function calls could be an overhead here.

That's like worrying if you have a fever while standing on the surface of the sun.

Besides always worry about code clarity first, then worry about performance if and only if you have a demonstrable performance issue.
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Bear Bibeault wrote:
Vipin Anand wrote:I mean the stack operations involved in function calls could be an overhead here.

That's like worrying if you have a fever while standing on the surface of the sun.

Besides always worry about code clarity first, then worry about performance if and only if you have a demonstrable performance issue.


Point taken. Functions give more flexibility to the code (easily maintainable).
Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 60774
    
  65

You might want to look up the term premature optimization.
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Bear Bibeault wrote:You might want to look up the term premature optimization.



Thanks. That is precisely what my problem is.....i will make sure that I wont commit the same mistake again in the future. Too bad I missed out a good opportunity (rare one for an international student like me) in spite of nailing the problem but not in a right way.
Stefan Evans
Bartender

Joined: Jul 06, 2005
Posts: 1016
angle = -1 implies ...[snip]

That is all very well. But it was not documented.
The comment for the method described the values of "angle" you could expect, and -1 wasn't one of them.
I had to visually inspect the internals of that method to figure out what was going on.
The point of my question wasn't so much "What does this do" but rather "Your code is harder to read because of this undocumented feature"


Equalize method does not make an array rectangular. It basically solves a problem of unequal rows within the array.

For e.g. input array[] = {{1,0,1},{0,-1}}. Will output {{1,0,1},{0,-1,0}} so a 0 is appended at {0,-1} to make sure my program does not crash when I am traversing the array.

Exactly. You fill in the gaps so that the matrix is fully populated - resulting in a 'rectangle' of values (a term they used in their question)
But where in the spec does it say you have to handle input like that?


AllWebLeads.searchSequence(i, j, -1, 1); it does return the 'count' variable to check whether its equal to the expected length or not (its a recursive function

Really? Look again.
I can see it RETURNS count. But where do you ever USE the value that it returns?
As far as I can tell the return value is redundant.

Stefan Evans
Bartender

Joined: Jul 06, 2005
Posts: 1016
Feedback on your test class

Why are the examples that they provided in the question not in your test cases? Those should be the first ones in.

Rather than one humongous test, each test case should be in a separate, well named method.
That way you can say at any point "x out of y test cases are working"
And you can also pinpoint exactly which ones you are having trouble with.
Currently all you can say is "the unit test fails somewhere"


It would have been nice to lay out your tests as a 2d array for easier reading, rather than all in one line.



Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Stefan Evans wrote:Feedback on your test class

Why are the examples that they provided in the question not in your test cases? Those should be the first ones in.

Rather than one humongous test, each test case should be in a separate, well named method.
That way you can say at any point "x out of y test cases are working"
And you can also pinpoint exactly which ones you are having trouble with.
Currently all you can say is "the unit test fails somewhere"


It would have been nice to lay out your tests as a 2d array for easier reading, rather than all in one line.






Cool will keep a track on this one.
Jared Malcolm
Ranch Hand

Joined: May 02, 2011
Posts: 54

Vipin Anand wrote:Too bad I missed out a good opportunity (rare one for an international student like me) in spite of nailing the problem but not in a right way.


It's always a long shot (but you have nothing to lose). Take the suggestions provided here and redo your work and submit again. Just mention to the HR person that you got some suggestions from fellow coders and implemented them on your own and without help. This in my mind shows that you can follow a standard if one is provided for you and that you really want the position....whats the worst thing they will say?

Your code worked correct? Do it another way and see if they like it better (if they will accept it).


SCJA 6 (Studying for SCJP 6)
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Jared Malcolm wrote:
Vipin Anand wrote:Too bad I missed out a good opportunity (rare one for an international student like me) in spite of nailing the problem but not in a right way.


It's always a long shot (but you have nothing to lose). Take the suggestions provided here and redo your work and submit again. Just mention to the HR person that you got some suggestions from fellow coders and implemented them on your own and without help. This in my mind shows that you can follow a standard if one is provided for you and that you really want the position....whats the worst thing they will say?

Your code worked correct? Do it another way and see if they like it better (if they will accept it).



That's a great idea...as a matter of fact I have the email of the QA developer who evaluated my code.....so I can modify it and make it look much better and send it again to him. Whats the worst he can write me back......"Good but you have already been rejected"......no problem I will email him but first, I will display it on this forum...so that you can scrutinize it again.
Yunnan Zhou
Ranch Hand

Joined: May 04, 2011
Posts: 31

come on.

I'am a Chinese.I like Java.Hello.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37958
    
  22
I think this question is too difficult for "beginning": moving.
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Alright, I have cleaned my code a bit. Took care of somethings mentioned in this forum. I still feel I can optimize "searchSequence" function further. Will work on it once I find time. So, guys what do you think about this now?

Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

Code seems way too verbose for what is required, hence unreadable and unmaintainable. I put this together in a few minutes:


If you want to improve your coding I would thoroughly recommend doing a bunch of TopCoder practice competitions. The problems are very similar to this one (in fact I wouldn't be surprised if this were "borrowed" from TopCoder ). It's great practice and you can see how everyone else tackled this problem, which is good for showing how you can write your code more efficiently.
Vipin Anand
Greenhorn

Joined: May 05, 2011
Posts: 10
Luigi Plinge wrote:Code seems way too verbose for what is required, hence unreadable and unmaintainable. I put this together in a few minutes:


If you want to improve your coding I would thoroughly recommend doing a bunch of TopCoder practice competitions. The problems are very similar to this one (in fact I wouldn't be surprised if this were "borrowed" from TopCoder ). It's great practice and you can see how everyone else tackled this problem, which is good for showing how you can write your code more efficiently.


Wow this can be done in 32 lines...I need to test this but I am pretty sure this will work. About TopCoder, I will do some problems from there.
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

Come to think of it, you don't need the boolean[][][] array, you just need to check if you're back at the starting point, so you can shorten the inner loop to
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Java Code
 
Similar Threads
I'm sure I'm doing something very dumb.... why can't I see my JLabel?
Grid Traversal
June Newsletter Puzzle
In Dire Need of Data Structure Advice
Newsletter Inverse