Friday, October 22, 2010

Deleting a middle node from a single linked list when pointer to the previous node is not available

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/delete-non-tail-node-in-linked-list-given-only-access-to-that-node/.
Problem
Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

Solution
If we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following:
We have a list looking like:

......... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... 

and we need to delete Node(i).

  1. Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
  2. delete the second Node(i+1), it doesn't require pointer to the previous node.
Pseudocode:
As the solution given here:
void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}


Here the problem is we are not actually deleting the node, but just replacing the value from the next node. Hence it is sort of quiz. Moreover, if some node is already referring to pointer(i+1) (not data), then it may be problem.

Wednesday, October 20, 2010

Array implementation of stack

Here will discuss the array implementation of stack.

Problems with array implementation
Underflow - Array may be empty but people may try to pop the element
Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html
Null items - Can nulls be added - Yes in this case, nulls can be added in stack
Loitering (java specific) - Holding a reference to an object wen it is no longer needed. To over come this we should explicitly set array index to null. For eg.
public string pop() //stack of string
{
  String item = stackArray[--top];
  stackArray[top] = null;
  return item;
}
Doing so, makes your program less of memory consumer.

Stack in java
Following is the implementation of stack in java:
public class MyStack {
   private int maxSize;
   private long[] stackArray;
   private int top;
   public MyStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
   }
   public long pop() {
      return stackArray[top--];
   }
   public long peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == maxSize - 1);
   }
   public static void main(String[] args) {
      MyStack theStack = new MyStack(10); 
      theStack.push(10);
      theStack.push(20);
      theStack.push(30);
      theStack.push(40);
      theStack.push(50);
      while (!theStack.isEmpty()) {
         long value = theStack.pop();
         System.out.print(value);
         System.out.print(" ");
      }
      System.out.println("");
   }
}
CPP implementation (without classes)
Following is the implementation in cpp:
#include <stdio .h>  
 #include <conio .h>  
 #define MAX 20  
 int top=-1,ch;  
 int a[MAX];  
 int main(){  
   void menu();  
   void push();  
   void pop();  
   void display();  
   menu();  
   while(ch!=3){  
      switch(ch){  
           case 1:  
               push();  
               display();  
               break;  
           case 2:  
               pop();  
               display();  
               break;  
           }  
      menu();       
      }  
 }  
 void push()  
 {  
    if(top==MAX-1)  
     printf("Stack is full\nStack overflow\n");  
    else  
    {  
     printf("Enter element:");  
     scanf("%d",&a[++top]);  
    }  
 }  
 void pop()  
 {  
    if(top==-1)  
    printf("Stack is emplty\nSTACK UNDERFLOW\n");  
    else  
    {  
      top--;  
      printf("Deleted %d\n",a[top+1]);  
    }  
 }  
 void display()  
 {  
    int i=0;  
    printf("\nStack is :\n");  
    for(i=top;i>=0;i--)  
    printf("%d\n",a[i]);  
 }  
 void menu()  
 {  
    printf("\n1.Push\n2.Pop\n3.Exit\n");  
    scanf("%d",&ch);  
    while(ch < 1 ch=>3)  
    {  
     printf("Enter valid choice 1,2 or 3\n");  
     scanf("%d",&ch);  
    }  
 }  


Stack Implementation in CPP (using classes)
#include <iostream>
using namespace std;
#define STACKSIZE 10
class stack
{
        private:
                int arr[STACKSIZE+1];
                int tos;
        public:
                stack();
                void push(int x);
                int  pop();
                bool is_empty();
                bool is_full();
                int  size();
                void display();
};
stack::stack()
{
        tos = 0;
}
void stack::push(int x)
{
        if(!is_full())
                arr[tos++] = x;
        else
                cout << "Stack is full, Can not push " << x << endl;
}
int stack::pop()
{
        if(!is_empty())
                return arr[--tos];
        else
                cout << "Stack is empty, cannot pop" << endl;
        return -1;
}
bool stack::is_empty()
{
        if(tos == 0)
                return true;
        else
                return false;
}
bool stack::is_full()
{
        if(tos == STACKSIZE)
                return true;
        else
                return false;
}
int stack::size()
{
        return tos;
}
void stack::display()
{
        if(tos == 0)
        {
                cout << "No elements to display" << endl;
                return;
        }
        for(int i=0;i
                cout << arr[i] << " ";
        cout << endl;
}
int main()
{
        stack mystack;
        cout << mystack.size() << endl;
        mystack.push(1);
        if(mystack.is_full())
                cout << "stack is full" << endl;
        mystack.pop();
        if(mystack.is_empty())
                cout << "stack is empty" << endl;
}


Thanks.

Tuesday, October 19, 2010

5 Pirates Problem

Problem :

Five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

Solution :

(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )

Most of the time i get people who give answers like “the most senior pirate takes half and divides the rest up among the least senior pirates.” um, you missed the whole point to begin with. sorry.

any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don’t say “because he’s nice”.

now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.

lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.

if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he’s obviously going to keep all the money for himself.

if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. pirate 3 realizes that if his plan is not adopted he will be executed and they will be left with 2 pirates. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don’t vote for pirate 3, i get nothing, i should vote for this plan.

now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3’s scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn’t want to die and we just showed that 3 has a winning proposal.

so lets sum up at this point
Pirate 1  2  3  4  5
    5. ?  ?  ?  ?  ?
    4. 0  1  0 99  -
    3. 1  0 99  -  -
    2. 0 100 -  -  -
    1.100

once you see the pattern it becomes very clear. you have to realize that when a pirate’s plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.
Pirate 1  2  3  4  5
    5. 1  0  1  0 98

what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.

hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves. 

100 Programmers Problem

Problem :

100 programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?

Solution :

this is a very difficult problem to solve during an interview (especially if you’ve already taxed the candidate’s brain). look for obvious solutions first, and the reasoning behind them and then try to lead them to the ultimate solution.

a logical answer could be all the programmers would just say “red” and that way about half of them would survive on average, assuming the hats were distributed randomly.

this is a good start and should naturally lead to having every other programmer say the color of the hat in front of them. the first programmer would say the color of the hat in front of him, then the next programmer would just say that color that was just said. so we can guarantee that half survive - the even numbered programmers (since the person behind them told them the answer). and potentially if the hats were distributed randomly some of the programmers would get lucky and the hat in front of them would be the same color as their own. so this strategy should save more than half, and on average 75% of them would live.

at this point, if the solution is not clear, the candidate may give answers like, “they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color”. this is definitely good and on the correct track. another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number, (red = 1, blue = 0). another interesting answer. there are many others like these that “bend” the rules and come to a solution.

but the real solution acknowledges that the programmers can only say “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. a good way to get this point across, is simply to change the problem slightly by saying “the assassin gets to hear their plan before she puts the hats on, and so will try to thwart the plan however she can.”

so if they decide to all say “red”, she’ll put blue hats on all of them. if they decide to all say the color of the hat in front of them, she’ll alternate the hats on every head, guaranteeing half will die. even with the assassin hearing their plan, there is still a way to save almost everyone.

we know that the first person is never going to have any information about the color of their hat, so they cannot be guaranteed to survive. but, i’ll give you a hint to the solution: i can save every other person for sure.

solution: they agree that if the number of red hats that the back person can see is even, that programmer will say “red”. if they add up to an odd number, they will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.

sample:
100  99  98  97  96  95  94 ... facing ->
 R    B   B   R   B   R   B ... -> 45 R and 48 B

this shows #100 wearing a red hat, 99 a blue, 98 a blue, 97 a red, 96 a blue, 95 a red, 94 a blue and 45 red hats - 48 blue hats on the people in front of them.

100 counts up the red hats: 47 total. so 100 says “blue”. the assassin kills 100. 99 counts up the red hats in front: 47. 100 said blue, so 100 saw an odd number. 99 sees an odd number, so 99 says “blue” and lives. 98 had counted 47 red hats, and 99 didn’t say “red” so thats still the total. 98 says “blue”. 97 counts up and finds 46 red hats. 99 and 98 didn’t say “red”, so his count is missing a red hat (its on his head, he realizes). he says “red”. 96 heard the “red” and now knows that there are an even number of “red” hats in front of 95. 96 sees 46, so he knows he has a “blue” hat. etc…

even if the assassin knows the plan, she can’t thwart it. she hears the plan, but she still has to put the hats on their heads. the plan doesn’t rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage she can do.

Sum it Up

Problem: 

you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)?
what if there are two repeating numbers (and the same memory constraint?)

Solution:

as a programmer, my first answer to this problem would be make a bit vector of size n, and every time you see the number, set its correspond index bit to 1. if the bit is already set, then that’s the repeater. since there were no constraints in the question, this is an ok answer. its good because it makes sense if you draw it for someone, whether they are a programmer, mathemetician, or just your grandpa. its not the most efficient answer though.

now, if i add the constraint that you can only use a fixed amount of memory (i.e. not determined by n) and it must run in O(n) time… how do we solve it. adding all the numbers up from 1 to n-1 would give us a distinct sum. subtracting the total sum of all the numbers from the sum of n to n-1 ( which is (n)(n-1)/2 ) would give us the secret extra number.

what if you can only use a fixed amount of memory, and two of the numbers are repeated? we know that the numbers have a distinct sum, and the difference would be equal to the sum of our unknowns
c = a + b
where c is the sum and a and b are the unknowns - c is a constant
if we had another similar formula we could solve the two unknown equations. my first thought was that the numbers would have a distinct product - (n-1)!
if we divide the total product by the (n-1)! product, we would get another equation
c2 = ab
we could then solve the two equations to get them into quadratic formula notation
0 = ax^2 + bx + c
and solve for the two values of x. this answer is correct but factorial grows really fast.

some sort of sum would be better. the sum of the squares from n-1 to 1 would work. that would yield a function of the form
c2 = a^2 + b^2
which could also be solved by using the quadratic equation.

i think its fine to remind someone of the quadratic equation… (maybe only because i myself had to look it up to solve the problem) i mean really though, the last time i used it was probably in 10th grade. as long as they get the idea that given two unknowns and two equations you can solve for the unknowns - thats the point.

Palindromes

Problem: 

This year on October 2, 2001, the date in MM/DD/YYYY format will be a palindrome (same forwards as backwards).
10/02/2001
when was the last date that this occurred on? (see if you can do it in your head!)


Solution:

we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can’t be any year in 1900 because that would result in a day of 91. same for 1800 down to 1400. it could be a year in 1300 because that would be the 31st day. so whats the latest year in 1300 that would make a month? at first i thought it would be 1321, since that would give us the 12th month, but we have to remember that we want the maximum year in the 1300 century with a valid month, which would actually be 1390, since 09/31 is a valid date.

but of course, a question like this wouldn’t be complete without an aha factor. and of course, there are not 31 days in september, only 30. so we have to go back to august 08 which means the correct date would be 08/31/1380.

palindromes also offer another great string question.
write a function that tests for palindromes
bool isPalindrome( char* pStr )

if you start a pointer at the beginning and the end of the string and keep comparing characters while moving the pointers closer together, you can test if the string is the same forwards and backwards. notice that the pointers only have to travel to the middle, not all the way to the other end (to reduce redundancy).
bool isPalindrome( char* pStr )
{
  if ( pStr == NULL )
   return false;

  char* pEnd = pStr;
  while ( *pEnd != '\0' )
    pEnd++;

  pEnd--;

  while(pEnd > pStr)
  {
    if ( *pEnd != *pStr )
      return false;

    pEnd--;
    pStr++;
  }

  return true;
}

thanks to tom for sending me this one! congrats on the wedding…

Daughters’ Ages

Problem :

Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years.

the first grad says to the second: “how have you been?”
second: “great! i got married and i have three daughters now”
first: “really? how old are they?”
second: “well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”
first: “right, ok.. oh wait.. hmm, i still don’t know”
second: “oh sorry, the oldest one just started to play the piano”
first: “wonderful! my oldest is the same age!”

How old are the daughters?

Solution :

Start with what you know. you know there are 3 daughters whose ages multiply to 72. let’s look at the possibilities…
Ages:            Sum of ages:
1 1 72            74
1 2 36            39
1 3 24            28
1 4 18            23
1 6 12            19
1 8 9             18
2 2 18            22
2 3 12            17
2 4 9             15
2 6 6             14
3 3 8             14
3 4 6             13

after looking at the building number the man still can’t figure out what their ages are (we’re assuming since he’s an MIT math grad, he can factor 72 and add up the sums), so the building number must be 14, since that is the only sum that has more than one possibility.

finally the man discovers that there is an oldest daughter. that rules out the “2 6 6” possibility since the two oldest would be twins. therefore, the daughters ages must be “3 3 8”.

(caveat: an astute reader pointed out that it is possible for two siblings to have the same age but not be twins, for instance one is born in january, and the next is conceived right away and delivered in october. next october both siblings will be one year old. if a candidate points this out, extra credit points to him/her.)

this question is pretty neat, although there is certainly a bit of an aha factor to it. the clues are given in such a way that you think you are missing information (the building number), but whats important isn’t the building number, but the fact that the first man thought that it was enough information, but actually wasn’t.


int atoi( char* pStr )

Problem: 

Write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about.

Solution :


string manipulation functions are great programming questions. they test whether the user can understand and translate into code simple algorithms. string functions test pointer arithmetic which usually shows a knowledgeable programmer. also there are usually multiple solutions, some more efficient than others. plus people use them all the time so they should understand how they work. my favorite is atoi and i start the problem like this:

int atoi( char* pStr )

write the definition for this function without using any built-in functions. if pStr is null, return 0. if pStr contains non-numeric characters, either return 0 (ok) or return the number derived so far (better) (e.g. if its “123A”, then return 123). assume all numbers are positive. plus or minus signs can be considered non-numeric characters. in order to solve this program, the programmer must understand the difference between the integer 0 and the character ‘0’, and how converting ‘0’ to an int, will not result in 0. in other words, they have to understand what ascii is all about. if they are stuck solving this problem, just ask them first to write:

charToInt(char c)

if they can’t do that then they basically missed half the problem. any moderately talented programmer who has a CS degree knows how to convert a char to an int. (note i said convert, not cast. charToInt('9') should return 9.)

when they start to solve the problem you will notice that they must make a choice in how they will process the string - from left to right or right to left. i will discuss both methods and the difficulties encountered in each.

“right to left” - this method starts at the right hand letter of the string and converts that character to an int. it then stores this value after promoting it to its correct “tens” place.
int atoi( char* pStr )
{
  int iRetVal = 0;
  int iTens = 1;

  if ( pStr )
  {
    char* pCur = pStr;
    while (*pCur)
      pCur++;

    pCur--;

    while ( pCur >= pStr && *pCur <= '9' && *pCur >= '0' )
    {
      iRetVal += ((*pCur - '0') * iTens);
      pCur--;
      iTens *= 10;
    }
  }
  return iRetVal;
}

“left to right” - this method keeps adding the number and multiplying the result by ten before continuing to the next number. e.g. if you had “6234” and you processed from left to right you’d have 6, then if you kept reading you’d multiply your result by 10 (6*10) to add a zero for where the next number would go. 60, and then you’d slide the 2 into the zero place you just made. 62. do it again, 620, slide the next number in, 623.
int atoi( char* pStr )
{
  int iRetVal = 0;

  if ( pStr )
  {
    while ( *pStr && *pStr <= '9' && *pStr >= '0' )
    {
      iRetVal = (iRetVal * 10) + (*pStr - '0');
      pStr++;
    }
  }
  return iRetVal;
}

i think the “left to right” method is a little bit cleaner, or maybe its just cooler. but both are “correct”.

remember that debugging code on paper is somewhat hard. most programmers aren’t used to studying code that much when you can just hit F-7, compile and see if the compiler barfs or not. if you notice an error, just ask them to step through a sample string drawing out what is happening with all the variables and the pointers in every step. they should find their mistake then and fix it (no points deducted).

Bumblebee

Problem: 

two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one. as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle of the tunnel (the bee survives). how far did the bee travel?

Solution: 

This puzzle falls pretty high on my aha scale. my first inclination when i heard it was to think “ok, so i just need to sum up the distances that the bee travels…” but then you quickly realize that its a difficult (not impossible) summation which the interviewer could hardly expect you to answer (unless i guess if you are looking for a job as a quant). “there must be a trick” you say. eh, sort of i guess, enough to say that this question is a stupid interview question.

the tunnel is 200 miles long. the trains meet in the middle travelling at 100 mph, so it takes them an hour to reach the middle. the bee is travelling 1000 mph for an hour (since its flying the whole time the trains are racing toward one another) - so basically the bee goes 1000 miles.

there is no process to explain, so this question can’t possibly teach you anything about the person. they either know it or they don’t and if they already knew it before you asked, you’re not going to be able to tell when they give you the answer. so don’t ask this question. and if someone asks you this question, just tell them you’ve already heard it before.

100 Doors in a Row - Solution

Problem: 

you have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.
What state are the doors in after the last pass? which are open which are closed?

 

Solution :


For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..

you can figure out that for any given door, say door #42, you will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 i will open the door, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close. for every pair of divisors the door will just end up back in its initial state. so you might think that every door will end up closed? well what about door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.

Reverse a String

Problem:

A typical programming interview question is “reverse a string, in place”. if you understand pointers, the solution is simple. even if you don’t, it can be accomplished using array indices. i usually ask candidates this question first, so they get the algorithm in their head. then i play dirty by asking them to reverse the string word by word, in place. for example if our string is “the house is blue”, the return value would be “blue is house the”. the words are reversed, but the letters are still in order (within the word).
 

Solution:


Solving the initial problem of just reversing a string can either be a huge help or a frustrating hinderance. most likely the first attempt will be to solve it the same way, by swapping letters at the front of the string with letters at the back, and then adding some logic to keep the words in order. this attempt will lead to confusion pretty quickly.

for example, if we start by figuring out that “the” is 3 letters long and then try to put the “t” from “the” where the “l” from “blue” is, we encounter a problem. where do we put the “l” from “blue”? hmm… well we could have also figured out how long “blue” was and that would tell us where to put the “l” at… but the “e” from “blue” needs to go into the space after “the”. argh. its getting quite confusing. in fact, i would be delighted to even see a solution to this problem using this attack method. i don’t think its impossible, but i think it is so complex that it’s not worth pursuing.

here’s a hint. remember before when we just reversed “the house is blue”? what happened?
initial: the house is blue
reverse: eulb si esuoh eht

look at the result for a minute. notice anything? if you still don’t see it, try this.
initial: the house is blue
reverse: eulb si esuoh eht
wanted : blue is house the

the solution can be attained by first reversing the string normally, and then just reversing each word.

The Circular Lake Monster Problem

Problem:

For #1, how about row in a circle a bit smaller 1/4r in size. Since he won't be able to keep up with you, when he is on the opposite shore you can make a brake for it. You have r*3/4 to travel, but 4*3/4 is less then pi, so he won't be able to catch you in time

Solution:

Assume x is the monster's speed. Then to get the circle trick to work, you row a circle a little less than 1/x of the radius, leaving you 1 - 1/x to row when he is opposite of you. If the monster can travel pi times the radius faster than you can travel the radius, you're hosed. In the time you travel 1 - 1/x, he'll travel x times that. Set that equal to pi, and you x * (1 - 1/x) = pi, which solves to x = pi + 1.

pi + 1 would be my guess for the speed that impossible to escape from, but I could be making an easy mistake.

Monday, October 18, 2010

Some terms and their synonyms in programming languages

Scope/Visibility
Nested/Inner Class
Instance/Member 
Class/Static
Local/Automatic variable

Arrays tip : Ignoring the zeroth row

This trick can be used in any language but is shown in java right now.
Sometimes you want to use natural input values as an index, the real values that that data has instead of starting with zero. Let's take the case of data that starts with the value 1, like the day of the month. The standard approach is to subtract one from every day value that's used as an index. This is annoying and error prone. Another way to do handle this case is to declare the array with an extra element, eg, 32 if dealing with the days in the month, then ignoring the zeroth element. If you're dealing with a two dimensional array, for example the accidents array from the previous page, you can even deallocate the first row so there won't be any possibility of referencing the zeroth day. For example,
static final int DAYS  = 32;
static final int HOURS = 24;
. . .
int[][] accidents = new int[DAYS][HOURS];
accidents[0] = null;
Because two-dimensional arrays are stored by row, you can do this. You can use the trick of allocating more columns to use the natural data, but you can't deallocate a column.
Enhanced by Zemanta

Tuesday, September 21, 2010

Enums in java

In prior releases, the standard way to represent an enumerated type was the int Enum pattern:
// int Enum Pattern - has severe problems!
public static final int SEASON_WINTER = 0;
public static final int SEASON_SPRING = 1;
public static final int SEASON_SUMMER = 2;
public static final int SEASON_FALL   = 3;
But these are not type safe, and clearly naming them is bit of a problem. So in Java 5, they introduced Enums.

Eg.
enum Season { WINTER, SPRING, SUMMER, FALL } 
public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX,
        SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }

    public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES } 
  
Note on Semicolon ( ; )
Enum embedded inside a class. Outside the enclosing class, elements are referenced as Outter.Color.RED, Outter.Color.BLUE, etc.
public class Outter {
 public enum Color {
   WHITE, BLACK, RED, YELLOW, BLUE
 }
}
Enum that overrides toString method. A semicolon after the last element is required to be able to compile it. More details on overriding enum toString method can be found.
public enum Color {
 WHITE, BLACK, RED, YELLOW, BLUE;  //; is required here.

 @Override public String toString() {
   //only capitalize the first letter
   String s = super.toString();
   return s.substring(0, 1) + s.substring(1).toLowerCase();
 }
}
Iterating enum through Value method...

for ( Color c :Color.values() ) {
         System.out.print( c + " " );
}


Enum constants may act as case labels in switch 
 enum Grade A, B, C, D, F, INCOMPLETE };
class Student {

  private String firstName;
  private String lastName;
  private Grade grade;

  public Student(String firstName, String lastName) ;

//getters and setters of grade
 public void assignGrade(Grade grade) {
    this.grade = grade;
  }

  public Grade getGrade() {
    return grade;
  }
 

Now we can have switch block as :
switch (student1.getGrade()) {
      case A: 
        outputText.append(" excelled with a grade of A");
        break;   
      case B: // fall through to C
      case C: 
        outputText.append(" passed with a grade of ")
                  .append(student1.getGrade().toString());
        break;
      case D: // fall through to F
      case F:
        outputText.append(" failed with a grade of ")
                  .append(student1.getGrade().toString());
        break;
      case INCOMPLETE:
        outputText.append(" did not complete the class.");
        break;
      default:
        outputText.append(" has a grade of ")
                  .append(student1.getGrade().toString());
        break;
    }



Enum with additional fields and custom constructor. Enum constructors must be either private or package default, and protected or public access modifier is not allowed. When custom constructor is declared, all elements declaration must match that constructor.
public enum Color { //Color is of type enum
 WHITE(21), BLACK(22), RED(23), YELLOW(24), BLUE(25);

 private int code;

 private Color(int c) {
   code = c;
 }

 public int getCode() {
   return code;
 }
Enum that implements interfaces. Enum can implement any interfaces. All enum types implicitly implements java.io.Serializable, and java.lang.Comparable.
public enum Color implements Runnable {
 WHITE, BLACK, RED, YELLOW, BLUE;

 public void run() {
   System.out.println("name()=" + name() +
       ", toString()=" + toString());
 }
}
A sample test program to invoke this run() method:
for(Color c : Color.values()) {
 c.run();
}
Or,
for(Runnable r : Color.values()) {
 r.run();
}
Enum and their super-class
All java enum E implicitly extends java.lang.Enum. Since java doesn't allow multiple inheritance, enum types can't have superclass. They can't even extend from java.lang.Enum, nor java.lang.Object. It also means enum A can't inherit or extend enum B.

For example, the following is an invalid enum declaration:
public enum MyType extends Object {
ONE, TWO
}
Compiler error:
MyType.java:3: '{' expected
public enum MyType extends Object {
MyType.java:6:  expected
2 errors
 
The correct form should be:
public enum MyType {
ONE, TWO
}

Custom string values for enums
The default string value for java enum is its face value, or the element name. However, you can customize the string value by overriding toString() method. For example,
public enum MyType {
ONE {
    public String toString() {
        return "this is one";
    }
},

TWO {
    public String toString() {
        return "this is two";
    }
}
}
Running the following test code will produce this:
public class EnumTest {
public static void main(String[] args) {
    System.out.println(MyType.ONE);
    System.out.println(MyType.TWO);
}
}
-------------
this is one
this is two
Another interesting fact is, once you override toString() method, you in effect turn each element into an anonymous inner class. So after compiling the above enum class, you will see a long list of class files:
MyType.class
MyType$1.class
MyType$2.class

Saturday, September 18, 2010

Modifying Java Variables (w.r.t c and c++)

Modifying Simple Variable
The only mechanism for changing the value of a simple Java variable is an assignment statement. Java assignment syntax is identical to C assignment syntax. As in C, an assignment replaces the value of a variable named on the left- hand side of the equals sign by the value of the expression on the right- hand side of the equals sign.

Modifying Object Variable 
Java object variables can be changed in two ways. Like simple variables, you can make assignments to object variables. When this is done the object referenced by the variable is not changed. Instead, the reference is replaced by a reference to a different object.
With a few exceptions, the only other thing that you can do with an object variable is to send it a message. This is an important part of any Java program, allowing communication between objects.


Friday, September 17, 2010

Constructor in java 1

Constructors

When you create a new instance (a new object) of a class using the new keyword, a constructor for that class is called. Constructors are used to initialize the instance variables (fields) of an object. Constructors are similar to methods, but with some important differences.
  • Constructor name is class name. A constructors must have the same name as the class its in.
  • Default constructor. If you don't define a constructor for a class, a default parameterless constructor is automatically created by the compiler. The default constructor calls the default parent constructor (super()) and initializes all instance variables to default value (zero for numeric types, null for object references, and false for booleans).
  • Default constructor is created only if there are no constructors. If you define any constructor for your class, no default constructor is automatically created.
  • Differences between methods and constructors.
    • There is no return type given in a constructor signature (header). The value is this object itself so there is no need to indicate a return value.
    • There is no return statement in the body of the constructor.
    • The first line of a constructor must either be a call on another constructor in the same class (using this), or a call on the superclass constructor (using super). If the first line is neither of these, the compiler automatically inserts a call to the parameterless super class constructor.
    These differences in syntax between a constructor and method are sometimes hard to see when looking at the source. It would have been better to have had a keyword to clearly mark constructors as some languages do.
  • this(...) - Calls another constructor in same class. Often a constructor with few parameters will call a constructor with more parameters, giving default values for the missing parameters. Use this to call other constructors in the same class.
  • super(...). Use super to call a constructor in a parent class. Calling the constructor for the superclass must be the first statement in the body of a constructor. If you are satisfied with the default constructor in the superclass, there is no need to make a call to it because it will be supplied automatically.

Example of explicit this constructor call

public class Point {
    int m_x;
    int m_y;

    //============ Constructor
    public Point(int x, int y) {
        m_x = x;
        m_y = y;
    }

    //============ Parameterless default constructor
    public Point() {
        this(0, 0);  // Calls other constructor.
    }
    . . .
}

super(...) - The superclass (parent) constructor

An object has the fields of its own class plus all fields of its parent class, grandparent class, all the way up to the root class Object. It's necessary to initialize all fields, therefore all constructors must be called! The Java compiler automatically inserts the necessary constructor calls in the process of constructor chaining, or you can do it explicitly.
The Java compiler inserts a call to the parent constructor (super) if you don't have a constructor call as the first statement of you constructor. The following is the equivalent of the constuctor above.
//============ Constructor (same as in above example)
    public Point(int x, int y) {
        super();  // Automatically done if you don't call constructor here.
        m_x = x;
        m_y = y;
    }

Why you might want to call super explicitly

Normally, you won't need to call the constructor for your parent class because it's automatically generated, but there are two cases where this is necessary.
  1. You want to call a parent constructor which has parameters (the automatically generated super constructor call has no parameters).
  2. There is no parameterless parent constructor because only constructors with parameters are defined in the parent class.

Common naming convention : Coding Style

Variable names must be in mixed case starting with lower case. 
Common practice in the Java development community and also the naming convention for variables used by Sun for the Java core packages. Makes variables easy to distinguish from types, and effectively resolves potential naming collision as in the declaration
eg.
int state;

Names representing constants (final variables) must be all uppercase using underscore to separate words.
MAX_ITERATIONS, COLOR_RED
Common practice in the Java development community and also the naming convention used by Sun for the Java core packages.

In general, the use of such constants should be minimized. In many cases implementing the value as a method is a better choice:

int getMaxIterations() // NOT: MAX_ITERATIONS = 25
{
return 25;
}

This form is both easier to read, and it ensures a uniform interface towards class values.

Names representing methods must be verbs and written in mixed case starting with lower case. getName(), computeTotalWidth() 

Abbreviations and acronyms should not be uppercase when used as name.
exportHtmlSource(); // NOT: exportHTMLSource();
openDvdPlayer(); // NOT: openDVDPlayer();

Using all uppercase for the base name will give conflicts with the naming conventions given above. A variable of this type whould have to be named dVD, hTML etc. which obviously is not very readable. Another problem is illustrated in the examples above; When the name is connected to another, the readability is seriously reduced; The word following the acronym does not stand out as it should.

Private class variables should have underscore suffix.
class Person { 
               private String name_; 
... }
Apart from its name and its type, the scope of a variable is its most important feature. Indicating class scope by using underscore makes it easy to distinguish class variables from local scratch variables. This is important because class variables are considered to have higher significance than method variables, and should be treated with special care by the programmer.

A side effect of the underscore naming convention is that it nicely resolves the problem of finding reasonable variable names for setter methods:

void setName(String name)
{
name_ = name;
}

An issue is whether the underscore should be added as a prefix or as a suffix. Both practices are commonly used, but the latter is recommended because it seem to best preserve the readability of the name.

It should be noted that scope identification in variables have been a controversial issue for quite some time. It seems, though, that this practice now is gaining acceptance and that it is becoming more and more common as a convention in the professional development community.

Generic variables should have the same name as their type.
void setTopic(Topic topic) // NOT: void setTopic(Topic value) 
                                        // NOT: void setTopic(Topic aTopic) 
                                         // NOT: void setTopic(Topic t) 
void connect(Database database) // NOT: void connect(Database db) 
                                                   // NOT: void connect(Database oracleDB)
Reduce complexity by reducing the number of terms and names used. Also makes it easy to deduce the type given a variable name only.

If for some reason this convention doesn't seem to fit it is a strong indication that the type name is badly chosen.

Non-generic variables have a role. These variables can often be named by combining role and type:

Point startingPoint, centerPoint;
Name loginName;
All names should be written in English.English is the preferred language for international development.

Variables with a large scope should have long names, variables with a small scope can have short names
Scratch variables used for temporary storage or indices are best kept short. A programmer reading such variables should be able to assume that its value is not used outside a few lines of code. Common scratch variables for integers are i, j, k, m, n and for characters c and d.

The name of the object is implicit, and should be avoided in a method name.
line.getLength(); // NOT: line.getLineLength();
The latter might seem natural in the class declaration, but proves superfluous in use, as shown in the example.


The terms get/set must be used where an attribute is accessed directly.
employee.getName(); 
employee.setName(name); 
matrix.getElement(2, 4);
matrix.setElement(2, 4, value);

is prefix should be used for boolean variables and methods.
isSet, isVisible, isFinished, isFound, isOpen
This is the naming convention for boolean methods and variables used by Sun for the Java core packages.

Using the is prefix solves a common problem of choosing bad boolean names like status or flag. isStatus or isFlag simply doesn't fit, and the programmer is forced to chose more meaningful names.

Setter methods for boolean variables must have set prefix as in:

void setFound(boolean isFound);

There are a few alternatives to the is prefix that fits better in some situations. These are has, can and should prefixes:

boolean hasLicense();
boolean canEvaluate();
boolean shouldAbort = false;


The term compute can be used in methods where something is computed.
valueSet.computeAverage(); matrix.computeInverse()
Give the reader the immediate clue that this is a potential time consuming operation, and if used repeatedly, he might consider caching the result. Consistent use of the term enhances readability.


 Iterator variables should be called i, j, k etc.
for (Iterator i = points.iterator(); i.hasNext(); ) { : } for (int i = 0; i < nTables; i++) { : } 

The notation is taken from mathematics where it is an established convention for indicating iterators. Variables named j, k etc. should be used for nested loops only. 

Complement names must be used for complement entities 
get/set, add/remove, create/destroy, start/stop, insert/delete, increment/decrement, old/new, begin/end, first/last, up/down, min/max, next/previous, old/new, open/close, show/hide, suspend/resume, etc. 
Reduce complexity by symmetry. 

Abbreviations in names should be avoided
computeAverage(); // NOT: compAvg(); 
ActionEvent event; // NOT: ActionEvent e; 
catch (Exception exception) { // NOT: catch (Exception e) { 
There are two types of words to consider. First are the common words listed in a language dictionary. These must never be abbreviated.  
Never write
cmd instead of command 
comp instead of compute cp
instead of copy 
e instead of exception 
init instead of initialize
pt instead of point etc. 
Then there are domain specific phrases that are more naturally known through their acronym or abbreviations. These phrases should be kept abbreviated. Never write: HypertextMarkupLanguage instead of html CentralProcessingUnit instead of cpu PriceEarningRatio instead of pe etc. 

Negated boolean variable names must be avoided. 
bool isError; // NOT: isNoError 
bool isFound; // NOT: isNotFound 
The problem arise when the logical not operator is used and double negative arises. It is not immediately apparent what !isNotError means.

Associated constants (final variables) should be prefixed by a common type name.

final int COLOR_RED = 1; 
final int COLOR_GREEN = 2; 
final int COLOR_BLUE = 3; 
This indicates that the constants belong together, and what concept the constants represents. 
An alternative to this approach is to put the constants inside an interface effectively prefixing their names with the name of the interface: interface Color { final int RED = 1; final int GREEN = 2; final int BLUE = 3; }


Exception classes should be suffixed with Exception. 

class AccessException extends Exception { : } 
Exception classes are really not part of the main design of the program, and naming them like this makes them stand out relative to the other classes. This standard is followed by Sun in the basic Java library.


Default interface implementations can be prefixed by Default. 

class DefaultTableCellRenderer implements TableCellRenderer { : } 
It is not uncommon to create a simplistic class implementation of an interface providing default behaviour to the interface methods. The convention of prefixing these classes by Default has been adopted by Sun for the Java library.


Singleton classes should return their sole instance through method getInstance

class UnitManager { private final static UnitManager instance_ = new UnitManager(); private UnitManager() { ... } public static UnitManager getInstance() // NOT: get() or instance() or unitManager() etc. { return instance_; } } Common practice in the Java community though not consistently followed by Sun in the JDK. The above layout is the preferred pattern.

Classes that creates instances on behalf of others (factories) can do so through method new[ClassName]

class PointFactory { public Point newPoint(...) { ... } } 
Indicates that the instance is created by new inside the factory method and that the construct is a controlled replacement of new Point().

 Functions (methods returning an object) should be named after what they return and procedures (void methods) after what they do. Increase readability. Makes it clear what the unit should do and especially all the things it is not supposed to do. This again makes it easier to keep the code clean of side effects. 4 Files

Classes should be declared in individual files with the file name matching the class name. 

Secondary private classes can be declared as inner classes and reside in the file of the class they belong to. Enforced by the Java tools.

 File content must be kept within 80 columns. 80 columns is the common dimension for editors, terminal emulators, printers and debuggers, and files that are shared between several developers should keep within these constraints. It improves readability when unintentional line breaks are avoided when passing a file between programmers.

Special characters like TAB and page break must be avoided. 

 These characters are bound to cause problem for editors, printers, terminal emulators or debuggers when used in a multi-programmer, multi-platform environment.
  

The incompleteness of split lines must be made obvious 
totalSum = a + b + c + 
                   d + e; 
method(param1, param2, 
                  param3);
setText ("Long line split" +
                "into two parts."); 
 for (int tableNo = 0; tableNo < nTables; 
           tableNo += tableStep) { ... } 

Split lines occurs when a statement exceed the 80 column limit given above. It is difficult to give rigid rules for how lines should be split, but the examples above should give a general hint. In general: 
Break after a comma. 
Break after an operator. 
Align the new line with the beginning of the expression on the previous line. 5 Statements


Type conversions must always be done explicitly. Never rely on implicit type conversion.
floatValue = (int) intValue; // NOT: floatValue = intValue;
By this, the programmer indicates that he is aware of the different types involved and that the mix is intentional.
 

Variables should be initialized where they are declared and they should be declared in the smallest scope possible.
This ensures that variables are valid at any time. Sometimes it is impossible to initialize a variable to a valid value where it is declared. In these cases it should be left uninitialized rather than initialized to some phony value.

Improving coding style into classes

Class and Interface declarations should be organized in the following manner: 
1. Class/Interface documentation. 
2. class or interface statement. 
3. Class (static) variables in the order public, protected, package (no access modifier), private. 
4. Instance variables in the order public, protected, package (no access modifier), private.
5. Constructors. 
6. Methods (no specific order). Reduce complexity by making the location of each class element predictable. 


Imported classes should always be listed explicitly.
import java.util.List; // NOT: import java.util.*; 
import java.util.ArrayList; 
import java.util.HashSet; 
Importing classes explicitly gives an excellent documentation value for the class at hand and makes the class easier to comprehend and maintain. Appropriate tools should be used in order to always keep the import list minimal and up to date.

Improving coding style into functions or methods

Method modifiers should be given in the following order: static abstract synchronized final native
The modifier (if present) must be the first modifier.
public static double square(double a);
// NOT: static public double square(double a);
is one of public, protected or private while includes volatile and transient. The most important lesson here is to keep the access modifier as the first modifier. Of the possible modifiers, this is by far the most important, and it must stand out in the method declaration. For the other modifiers, the order is less important, but it make sense to have a fixed convention.
 

Specific cases of naming enhancing naming style

The term find can be used in methods where something is looked up.
vertex.findNearestVertex(); matrix.findSmallestElement(); node.findShortestPath(Node destinationNode);
Give the reader the immediate clue that this is a simple look up method with a minimum of computations involved. Consistent use of the term enhances readability.

The term initialize can be used where an object or a concept is established.
printer.initializeFontSet();
The American initializeshould be preferred over the English initialise. Abbreviation init must be avoided.




Plural form should be used on names representing a collection of objects.
Collection points; int[] values;
Enhances readability since the name gives the user an immediate clue of the type of the variable and the operations that can be performed on its elements.
 

n prefix should be used for variables representing a number of objects.
nPoints, nLines
The notation is taken from mathematics where it is an established convention for indicating a number of objects.

Note that Sun use num prefix in the core Java packages for such variables. This is probably meant as an abbreviation of number of, but as it looks more like number it makes the variable name strange and misleading. If "number of" is the preferred phrase, numberOf prefix can be used instead of just n. num prefix must not be used.

No suffix should be used for variables representing an entity number.
tableNo, employeeNo
The notation is taken from mathematics where it is an established convention for indicating an entity number.

An elegant alternative is to prefix such variables with an i: iTable, iEmployee. This effectively makes them named iterators.

Java specific naming convention

JFC (Java Swing) variables should be suffixed by the element type.
widthScale, nameTextField, leftScrollbar, mainPanel, fileToggle, minLabel, printerDialog
Enhances readability since the name gives the user an immediate clue of the type of the variable and thereby the available resources of the object.

Array specifiers must be attached to the type not the variable.
int[] a = new int[20]; // NOT: int a[] = new int[20]
The arrayness is a feature of the base type, not the variable. It is not known why Sun allows both forms.

Java source files should have the extension .java. Point.java Enforced by the Java tools.


The import statements must follow the package statement. import statements should be sorted with the most fundamental packages first, and grouped with associated packages together and one blank line between groups. 
 import java.io.IOException; 
import java.net.URL;
import java.rmi.RmiServer; 
import java.rmi.server.Server; 
import javax.swing.JPanel; 
import javax.swing.event.ActionEvent; 
import org.linux.apache.server.SoapServer; 
The import statement location is enforced by the Java language. The sorting makes it simple to browse the list when there are many imports, and it makes it easy to determine the dependiencies of the present package The grouping reduce complexity by collapsing related information into a common unit.


The package statement must be the first statement of the file.
All files should belong to a specific package. The package statement location is enforced by the Java language. Letting all files belong to an actual (rather than the Java default) package enforces Java language object oriented programming techniques.