Only 48 hours left in the trailboss' kickstarter!

New rewards and stretch goals. CLICK HERE!



  • Post Reply Bookmark Topic Watch Topic
  • New Topic

i can't find the reason of a interview question  RSS feed

 
leon ting
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The following program fails with a class cast exception. No one before you could find out why. Someone did put in some debug statements to try to find out why.

Unfortunately, you do not have access to the program and you need to find out why the program immediately, by only looking at the source code and the execution output.


1.Why did the program fail?

2.What would you do to fix the program?


class ThreadTest
{
public static void main (String[] args)
{
Data globalData = new Data();
Thread threadA = new LongDataThread(globalData);
Thread threadB = new ShortDataThread(globalData);

threadB.start();
threadA.start();
}
}

class ShortDataThread extends Thread
{
Data m_data;

public ShortDataThread(Data data) {
m_data = data;
}

public void run ()
{
for (int idx = 0; idx < 100; idx++) {
m_data.initShortData();
m_data.putInShortData("short", new Integer(idx));
m_data.printShortData();
}
}

}

class LongDataThread extends Thread
{
Data m_data;

public LongDataThread(Data data) {
m_data = data;
}

public void run ()
{
for (int idx = 0; idx < 100; idx++) {
m_data.initLongData();
m_data.putInLongData("long", "address1", new Integer(idx));
m_data.printLongData();
}
}

}

(Please do not write on this page)

class Data
{
int m_indexName;
int m_indexAddress;
int m_indexAmount;

Object [] m_data = new Object[3];

public void initLongData ()
{
m_indexName = 0;
m_indexAddress = 1;
m_indexAmount = 2;
}

public void initShortData ()
{
m_indexName = 0;
m_indexAmount = 1;
}

public void putInLongData (String name, String address, Integer amt)
{
m_data[m_indexName] = name;
m_data[m_indexAddress] = address;
m_data[m_indexAmount] = amt;
}

public void putInShortData (String name, Integer amt)
{
m_data[m_indexName] = name;
m_data[m_indexAmount] = amt;
}

public void printLongData ()
{
System.out.println("DEBUG: indexName = " + new Integer(m_indexName));
System.out.println("DEBUG: indexAddr = " + new Integer(m_indexAddress));
System.out.println("DEBUG: indexAmt = " + new Integer(m_indexAmount));

String name = (String)m_data[m_indexName];
String address = (String)m_data[m_indexAddress];
Integer amount = (Integer)m_data[m_indexAmount];
System.out.println("printLongData: name is " + name);
System.out.println("printLongData: addr is " + address);
System.out.println("printLongData: amount is " + amount);
}

public void printShortData ()
{
System.out.println("DEBUG: indexName = " + new Integer(m_indexName));
System.out.println("DEBUG: indexAmt = " + new Integer(m_indexAmount));

String name = (String)m_data[m_indexName];
Integer amount = (Integer)m_data[m_indexAmount];
System.out.println("printShortData: name is " + name);
System.out.println("printShortData: amount is " + amount);
}

}

(Please do not write on this page)


Execution of the program:

C:\AribaDev\jdk1.3.1\tmp>..\bin\java ThreadTest
DEBUG: indexName = 0
DEBUG: indexAmt = 2
printShortData: name is long
printShortData: amount is 0
DEBUG: indexName = 0
DEBUG: indexAddr = 1
DEBUG: indexAmt = 1
java.lang.ClassCastException: java.lang.Integer
at Data.printLongData(ThreadTest.java:55)
at LongDataThread.run(ThreadTest.java:119)
DEBUG: indexName = 0
DEBUG: indexAmt = 1
printShortData: name is short
printShortData: amount is 1
DEBUG: indexName = 0
DEBUG: indexAmt = 1
printShortData: name is short
printShortData: amount is 2
DEBUG: indexName = 0
DEBUG: indexAmt = 1
printShortData: name is short
printShortData: amount is 3
DEBUG: indexName = 0
DEBUG: indexAmt = 1
printShortData: name is short
 
Henry Wong
author
Sheriff
Posts: 22817
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As seems to be the Java Ranch policy, I am supposed to hint at the answer, but quite frankly, I am not sure how to give a good hint here... Here is an attempt at the first question...

1. Why did the program fail?

Take a look at the few lines right before the cast exception...


DEBUG: indexName = 0
DEBUG: indexAddr = 1
DEBUG: indexAmt = 1
java.lang.ClassCastException: java.lang.Integer


You will noticed that both the address index and the amount index are the same. One is a String, the other is a Integer. One will definitely fail when casted.

Question: is the configuration (index) correct? And if it is not, what should they be? And furthermore, what do you think caused them to be wrong?

Anyway, that should be a good start... I'll let you figure out the rest.

Henry
 
Paul Santa Maria
Ranch Hand
Posts: 236
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, Leon -

Actually, this question had me stumped at first, too - it's not as easy as it might appear.

I think the point of the question is to get you to recognize a "race condition".

Specifically, you have two different threads accessing "global data". With no synchronization whatsoever.

Re-read Henry's post.

Do you know the answer yet? It's perfectly OK to say "No". But please post back and let us know your thoughts on the problem.

Thank you in advance .. PSM
[ September 23, 2005: Message edited by: Paul Santa Maria ]
 
leon ting
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong:

thank your hints!let me try to answer your question:
1.is the configuration (index) correct?
no
2. And if it is not, what should they be?
the index is set by ShortDataThread, alough it's value is same with index set by LongDataThread. it's not correct.

3.what do you think caused them to be wrong?
i guess the reason is that m_data[m_indexAddress] is set to String by threadB(ShortDataThread) When threadA(LongDataThread) do Integer cast to m_data[m_indexAddress],this situation happens on before the sentence:Integer amount = (Integer)m_data[m_indexAmount],threadB(ShortDataThread) has done the method:m_data.putInShortData("short", new Integer(idx)),then threadA execute controlled by cpu.

and it's lucky that the author of <<java thread>> answered me this question.
eager to have your guide with the question again.

[ September 24, 2005: Message edited by: leon ting ]
[ September 24, 2005: Message edited by: leon ting ]
 
leon ting
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
about question 2. What would you do to fix the program?

i modified code as below:
public class ShortDataThread extends Thread {
Data m_data;

public ShortDataThread(Data data) {
m_data = data;
}

public void run() {
for (int idx = 0; idx < 100; idx++) {
synchronized (this) {
m_data.initShortData();
m_data.putInShortData("short", new Integer(idx));
m_data.printShortData();
}

}
}

}

public class LongDataThread extends Thread {
Data m_data;

public LongDataThread(Data data) {
m_data = data;
}

public void run() {
for (int idx = 0; idx < 100; idx++) {
synchronized(this){
m_data.initLongData();
m_data.putInLongData("long", "address1", new Integer(idx));
m_data.printLongData();
}
}
}

}

and i run the ThreadTest, the problem still exists! how can i do ?
[ September 24, 2005: Message edited by: leon ting ]
 
Henry Wong
author
Sheriff
Posts: 22817
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by leon ting:

3.what do you think caused them to be wrong?
i guess the reason is that m_data[m_indexAddress] is set to String by threadB(ShortDataThread) When threadA(LongDataThread) do Integer cast to m_data[m_indexAddress],this situation happens on before the sentence:Integer amount = (Integer)m_data[m_indexAmount],threadB(ShortDataThread) has done the method:m_data.putInShortData("short", new Integer(idx)),then threadA execute controlled by cpu.


Yup, that is definitely one of the problems. With "race conditions" you can have many problems at the same time.

In this case, the cause is most likely caused by the fact that the initShort() method happening between the initLong() and printLong() methods. The initialization of the short corrupted the inner working for the long.

Henry
 
Henry Wong
author
Sheriff
Posts: 22817
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by leon ting:
about question 2. What would you do to fix the program?

i modified code as below:

and i run the ThreadTest, the problem still exists! how can i do ?


My answer would have been for each thread to have its own copy of the data -- as it is small and self contained... but I don't think that is the answer they are looking for in an interview...

You are correct in that certain "blocks" of code need to run uninterrupted. So how do you protect them? Correct. Use synchronization.
Unfortunately, you chose the "this" object. The problem here is that the "this" object is different for each thread. The two threads are using different locks, and hence, won't stop each other from stepping on the common data object.

More hints... You need to choose a common lock (ie. a common object to synchronize with). Does such a common object exist?

And BTW, I might have gone a bit too quick. You really need to understand why a lock was chosen for synchronization. (and in this case, why a common object) Finding the right one will only get you pass the interview -- not help you on your next thread problem.

Henry
 
Paul Santa Maria
Ranch Hand
Posts: 236
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Actually, Leon, there are (at least!) three possible solutions (each with its own merits and disadvantages), and not necessarily any "one correct answer".

Let's break it down:
1. The basic problem is that you've got two threads (ShortDataThread and LongDataThread) each sharing a common object (object "globalData", an instance of class "Data"). That fact alone usually cries out for some kind of "lock".

2. Unfortunately, each thread type has a different "view" of the data.

Class ShortDataThread thinks "Data" has two items: the first being a "name", the second an "amount". Class LongDataThread, on the other hand, thinks data has three items: name, address, and amount. Moreover, they "disagree" about the meaning of the second item: ShortDataThread treats it as an "amount", LongDataThread as an "address".

That's precisely the conflict that's causing the cast exception: shortDataThread wrote an integer "amount" into exactly the same spot that longDataThread was expecting to read a string "address". Ker-boom!

3. One solution is to apply a lock. And, in general, ANYtime you have multiple threads potentially updating shared data, you should almost ALWAYS have a lock.

Golden rule: lock DATA, not "code". Java's "synchronized" syntax makes it much easier to adhere to this rule than other mechanisms in other languages.

But that doesn't really apply here. You need a lock that extends from one thread's first "initXXXData()" to that same thread's last "printXXXData()". The other thread must be *locked out* that whole time. Not a happy prospect...

3. Another solution is to create a separate instance of "Data" for each different thread (or make data a "static member", so there's one instance of Data for each different thread *type*).

The problem with this solution is that the data isn't really global
any more: it's private to the thread. This may or may not be what you want.

4. A third solution is to get rid of the (bogus) methods "initLongData ()" and "initShortData()", and replace them with a single, coherent "initData()":



Voila! You've just solved the cast error, and you've still got your global data.

5. You still, however, have the problem of what happens if one thread is updating the data while the other is trying to read it. This third solution still calls for a lock - but now it's much easier to "apply the golden rule" to figure out where the lock goes.

'Hope that helps .. PSM

PS:
The part about:
No one before you could find out why. Someone did put in some debug statements to try to find out why.
is significant. It's the nature of race conditions like this that instrumenting the code ... or stepping through the debugger ... changes the timing and MASKS the problem. Making it EXTREMELY difficult to track down and resolve!
 
leon ting
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
henry:
with your hint, i found out the lock m_data and it's run ok now.
your conclusion give me big help.

Paul:
in reading your analyis, my tousy thoughts is cleared a lot,it's very "abstract to concrete".

and through this question,i feel a lot.
I assure i have little imagation gifts. i think it's the same mean that I'm not smart. although this couldn't be a execuse, I trust it's the original reason i can't resolve this question by myself.
because I'm the kind of need henry's hint step by step but not spred thoughts like the kind of Paul's way resolving problem(consecutively).
I feel sad with this, and should i insist to learn java or computer? do you have any guide with my big question?
[ September 24, 2005: Message edited by: leon ting ]
 
Paul Santa Maria
Ranch Hand
Posts: 236
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Leon -

You are obviously *very* smart and *very* creative. And persistent and curious. And motivated. Otherwise you wouldn't have followed up on the original interview question. And our followups.

On the contrary, you are *exactly* the kind of developer I'd want working with me on my team! I predict you're going to be very successful - and that you're going to accomplish a lot over the course of your career.

Sincerely .. PSM
 
Henry Wong
author
Sheriff
Posts: 22817
119
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The issues related to Threads is really a unique. Experience is sometimes more important than anything else. As long as you stay curious, and strive to understand "why" to problems, you should be okay.

Basically, you will eventually learn to smell the smoke, after you have been burn many times.

Henry
 
leon ting
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i guess the reason is that <<m_data[m_indexAddress] is set to String by
threadB(ShortDataThread) When threadA(LongDataThread) do Integer cast to m_data[m_indexAddress]>>,this situation happens on before the sentence:Integer amount = (Integer)m_data[m_indexAmount],threadB(ShortDataThread) has done the method:m_data.putInShortData("short", new Integer(idx)),then threadA execute controlled by cpu.

the code in <<>> should be: m_data[m_indexAddress] is set to Integer by
threadB(ShortDataThread) When threadA(LongDataThread) do String cast to m_data[m_indexAddress].

to henry and paul:

thanks a lot! i get a big encourage.

i'll study more hard!
[ September 26, 2005: Message edited by: leon ting ]
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!