Cracking the Coding interview Object Oriented Design: October 2015

Friday, October 2, 2015

[11.4] Find duplicate in N = 32,000

1. Example

Bit Vector STORE number into corresponding position
Multiple int
int[] array => array[0] ,array[1], .......
32 bit 32 bit
int wordNumber = numberPos >> 5; ==> array Index

int bitNumber = (numberPos & 0x1F); // mod by 32 ==> array element int bit
// NOTE: divide by 32 is because each int is 32 bit
// divide by 8 is because each byte is 8 bit1~ N = 1 ~ 32000 = 32 *1000 = 2^4 * 2^10 = 2 ^14
4KB = 4*2^10*8 btis = 2 ^ 15 bits
2 ^ 15 > 2 ^14
each bit represents a integer

2. Implementation

public static void checkDuplicates(int[] array)
{


     BitSet bs = new BitSet(32000);
     for (int i =0 ; i < array.length; i++)
     {
          int num = array[i];
          int index = num-1;
          if ( bs.get(index) )
               System.out.println(num);
          else 
               bs.set(index);
     }
}


class BitSet
{
    // NOTE: divide by 32 is because each int  is 32 bit
    //       divide by 8  is because each byte is  8 bit
    
    // Field
    int[] bitSet;
    // Constructor
    public BitSet(int size)
    {
            bitSet = new int[size >> 5]; // divide by 32
    }




    boolean get(int pos)
    {
           int wordNumber = (pos >> 5);  // divide by 32
           int bitNumber = (pos & 0x1F); // mod 32 1F=1 1111 = 2^4*1+2^3*1+...+2^0
           return ( bitSet[wordNumber] & (1>>bitNumber) ) != 0;
    }
  

  

    void set(int numberPos)
    {
           int wordNumber = numberPos >> 5;
           int bitNumber = (numberPos & 0x1F); // mod by 32
           bitsSet[wordNumber] |= (1<< bitNumber);
    }

}

3. Silmilar Ones

[11.3] find ONE missing number within four billion integers

1.Example

Bit Vector

byte[] => byte[0] byte[1]......

int arrayIndex = n / 8; => byte array index

int bitIndex = n % 8; => byte array element bit

s= {0,1,3,6}

index 0 1 2 3 4 5 6 7
bit array 1 1 0 1 0 0 1 0

bitArray | 1 << (0%8) = 1 0 0 0 0 0 0 0
bitArray | 1 << (1%8) = 1 1 0 0 0 0 0 0
bitArray | 1 << (3%8) = 1 1 0 1 0 0 0 0
bitArray | 1 << (6%8) = 1 1 0 1 0 0 1 0

bitArray & 1 << (6%8) =
1 1 0 1 0 0 "1" 0 & 0 0 0 0 0 0 "1" 0 = 1 ==> 6 exists in bitArray

2. Implementation

// 0                    Store 0
// 1                    Store 1
// .
// .
// .
// 2147483647 = 2^32    Store 2^32
// Assuming we are taking about 32-bit integers. 
// There are 2^32 = 4*10^9 distinct integers.






// Case1: 1GB memory = 1 * 10^9 * 8 bits = 8 billion bits.
// It is enough to use one bit correpresening one distinct integer. 
// We don't need sort 
int radix = 8;
byte[] bitField = new byte[0xffff ffff / radix];// 
void F() throws FileNotFoundException // method had sth to cause this e
{



     Scanner in = new Scanner (new FileReader("a.txt") );
     while (in.hasNextInt())
     {
           int  n = in.hasNextInt();
           int arrayIndex = n / 8;
           int bitIndex = n % 8;
           int setOnePos = 1 << bitIndex;
           bitField[ arrayIndex ] | = setOnePos;
     }



     int arrayLength = bitField.length;
     int bitLength = 8; 





     for (int i = 0 ; i < bitfield.length; i++) {
        for (int j = 0; j < 8; j++) 
        {
           // Retrieves the individual bits of each byte. When 0 bit
           // is found, finds the corresponding value. 
           if ((bitfield[i] & (1 << j)) == 0) {
              System.out.println (i * 8 + j);
              return;
           }
        }
     }

// 0          store integer 0 ~ 2^20      = 0       ~ 1048576*1
// 1          store integer 2^20+1 ~ 2^21 = 1048577 ~ 1048576*2
// .
// .
// .
// 4095       store integer ~ 2^32   =              ~ 1048576*4096 = //                                                  2147483647
// There are 4 billion =2^32 distinct integers 
// one map to one
// >= 2 ^32 bit array = 2^32 / 8 = 2 ^29 byte array


// many map to one

int bitSize  = 1048576;  // 2^20 bits (2^17 bytes)
int blockNum = 4096;    // 2^12
byte[] bitField = new byte[bitSize/8];
int[] blocks    = new int[blockNum];


// function have FileNotFOundExcpetion possibility and throws ... but don't have try and catch
// function have Exception possibility and use try catch 
void findOpenNumber() throws FileNotFoundException
{




     int stating = -1;
     Scanner in = new Scanner ( new FileReader("input_file_q11_4.txt") );

     


     // NOTE: first pass, check which block
     while (in.hasNextInt())
     { 
          int n = in.nextInt();
          blocks[ n / (bitField.length*8)]++;// n/2^20
     }




     for ( int i = 0 ; i < blocks.length ; i++ )
     {
         // Block not fill up, means probably missing a number 
         if (  block[i]  < bitField.length *8 ) // < 2^20
         {
               // If value < 2^20, then at least 1 number is missing
               // in this section
               // In last section: 4095*2^17*8 = 2^32 - 2^20
               // NOTE: ***count the starting integer in that section
               starting = i* bitField.length * 8;
               break;
         }
     }



     // NOTE: second pass, check which specific number from those 2^20 numbers
     in = new Scanner(new FileReader("input_file_q11_4.txt") );
     while (in.hasNextInt())
     {
         int n = in.nextInt();
         // If the number is inside the block that's missing 
         // numbers, we record it
         if ( n >= starting && n < starting + bitField.length *8 )
              bitField[ (n -starting) / 8] |= 1 << ((n-starting)%8) ;
         
     }




     // Find the missing number within those 2^20 integers
     // 2^20 -1 = (2^17-1)*8+7+ 0 = 2^20 -8 +7 +0 
     for (int i = 0; i < bitField.length; i++ )
     {
         for (int j = 0 ; j < 8 ; j++ )
         {
               // Retrieves the individual bits of each byte
               // When 0 bit is found, finds the corresponding value
               if (  bitField[i]  &  (1<





// Bit-vector to store integers
public class BitArray
{
     


    // Field
    private byte[] set;
    // Constructor
    public BitArray (int length)
    {
         arraySize = (length % 8 =! = 0) ? (length / 8 )+1:length / 8;
         this.set = new byte[ arraySize ];
    }




    // Set given number in the bit-array. i.e., make corresponding bit as 1
    public void storeNumber(int number)
    {


         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;

         // so bit at postiion needs to made 1
         this.set[arrayIndex] = (byte)  (this.set[arrayIndex] |  pos );

    }
    private int getArrayIndex(int number )
    {
         return number / 8;
    }
    private int getbitIndex(int number)
    {
         return number % 8;
    }




    // check if the number exists in the array if the corresponding bit is 1, then it exist
    public boolean numberExists(int number)
    {

         // validate the input
         if ( number < 0 || number > (set.length * 8 )  )
             throw new IllegalArgumentException("number out of range");

         
         int arrayIndex = this.getArrayIndex(number);
         int bitIndex = this.getBitIndex(number);
  

         // MAKE bit index value is 1 (shift 1 to the bit index), default is 0
         int pos = 1 << bitIndex;
         return ( this.set[arrayIndex] & pos ) > 0 ? true:false;       
    }



    private void printSet()
    {
           
    }



    public static void main (String[] args)
    {
           BitArray array = new BitArray(1000);
           System.out.println("length of array:" + array.set.length );


           int num1 = 17;
           array.storeNumber(num1);
           int num2 = 171;
           array.storeNumber(num2);
           int num3 = 400;
           array.storeNumber(num3);


           System.out.println("val "+ num1 + " exists ? " + array.numberExists(num1) );
           System.out.println("val" + num2 + " exists ? " + array.numberExists(num2) );
           System.out.println( "val" + num3 + " exists ? " + array.numberExists(num3) );
           
    }





3. Similar Ones
http://question.ikende.com/question/2D373139353434383837
http://geekrai.blogspot.com/2014/09/bit-array-or-vector.html

[7.10] Garbage collector

1. Example
1. reference counting
2. mark and sweep
3. copy

2. implementation

In C++, garbage collection with reference counting is almost always implemented with
smart pointers, which perform reference counting.
The main reason for using smart pointers over raw ordinary pointers is the conceptual
simplicity of implementation and usage.

With smart pointers, everything related to garbage collection is performed behind the scenes - typically in constructors / destructors / assignment operator / explicit object mangement functions.

There are two types of functions, both of which are very simple:





RefCountPointer::type1()
{
  //implements depends on reference counting organization
  // this can also be no ref. counter at all
  incrementRefCounter();
}
RefCountPointer::type2()
{
  // Implementation depends on reference counting organization
  // there can also be no ref. coutner at all
  decrementRefcounter();
  if ( referenceCounterIsZero() )
      destructObject();
}




// NOTE Method 1. Simple Reference Counting ( )
struct Object
{
};
struct RefCount
{
    int count;
};
struct RefCountPtr
{
    Object *pointee;
    RefCount *refCOunt;
};
Advantages: performance
Disadvantages: memory overhead because of two poitners





// NOTE Method 2: Alternative Reference Counting  ( )
struct Object
{
};
struct RefCountPtrImp1
{
   int count;
   Object *object;
};
struct RefCountPtr
{
   RefCountPtrImp1 * pointee;
};
Advantages:no memory overhead because of two pointers
Disadvantages: performance penalty extra level of indirection




// NOTE Method 3: Intrusive Reference Counting ( )
struct Object
{
};
struct ObjectIntrusiveReferenceCounting
{
   Object object;
   int count;
};
struct RefCountPtr
{
   ObjectIntrusiveReferenceCounting * pointee;
};
Advantages: no previous disadvantage (no overhead due to pointers)
Disadvantages: class for intrusive reference counting should be modified




// NOTE Method 4: Ownership List Reference Counting (LinkedList)
// Ownership list reference counting. It is an alternative for approach // 1-3. For 1-3 it is only important to determine that counter is zero -// its actual is not important. This is the main idea of approached #4

// 1. all smart pointers for given objects are stored in doubly-linked 
// lists. 
// 2. The constructor of a smart pointer adds the new node to a list.  
// 3. The destructor removes a node from the list.
// 4. checked if the list is empty or not. If it is empty, the object is //    deleted.

struct object
{
};
struct ListNode
{
    Object *pointee;
    ListNode *next;
};

3. Similar ones

[7.9] in-memory file system

1. Example

For datablock allocation, we can use bitmask vector and linear search or B+ tree
1. bitmask vector and linear search
2. B+ tree

2.Implementation
http://www.farhadsaberi.com/linux_freebsd/image/unix_file_system.gif

//NOTE: 1. "Datablock" -> INode -> File -> Direcotry
struct DataBlock 
{  
  char data[DATA_BLOCK_SIZE]; 
};
DataBlock dataBlocks[NUM_DATA_BLOCKS];



//NOTE: 2. Datablock -> "INode" -> File -> Direcotry
struct INode 
{
  std::vector datablocks;
};



//NOTE: 3. Datablock -> INode -> "File" -> Direcotry
std::mapmapFromName;
struct MetaData
{
   int size;
   Date last_modified, created;
   char extra_attributes;
}
struct FSBase;
struct File : public FSBase
{
   private:
     std::vector * nodes; 
     MetaData metaData;
};




//NOTE: 4. Datablock -> INode -> File -> "Direcotry"
Srtuct Directory :public FSBase
{
    std::vector content;
};








std::vector dataBlockUsed();






struct FileSystem
{




    init();
    mount( FileSystem* );
    unmount( FileSystem* );

    

    File createFile( const char* name ){ ... }
    Directory createDirectory( const char* name ) { ... }
    



    // mapFromName to find INode corresponding to file
    void openFile( File *file, FileMode mode){ ... }




    void closeFile( File *file){ ... }
    void writeToFile( File* file, void *data , int num ) { ... }
    void readFromFile( File* file, void *res, int numBytes, int position ){ ... }




};

.3 Similar Ones

[7.8] Othello

1. Example

Game:
1.strat
2.run
3.check rule
4.add result

   A B C D E F G H
8
7
6
5 W B
4 B W
3
2
1

Start: B W
W B
Flip1: W B W --> W W W
Flip2: W W
B --> W
W W

Rule1: Each othello piece is white on one side and black on the other(see start).

Rule2: When a piece is surrounded by its opponents on both the left and right sides(see Flip 1), or both the top and bottom(see Flip 2), it is said to be captures and its color is flipped.

Rule3: On your turn, you must capture at least one of your opponent's pieces(at least flip1 or flip2 happen).

Rule4: The game ends when wither user has no more valid moves, and the win is assigned to the person with the most pieces.

2. Implementation
Othello has three major steps:
1. Game() which would be the main function to manage all the activity in the game:
2. Initialize the game which will be done by constructor
3. Get first user input
4. Validate the input
5. Change board configuration
6. Check if someone has won the game
7. Get second input
8. Validate the input
9. Change the board configuration
10.Check if someone has won the game
private void getMove( int color ) throws Exception{...}
try

{

getMove(black); valid = true;

}

catch (Exception e)

{

System.out.println("Enter a valid coordinate!");

}

public class Question
{



     private final int white = 1;
     private final int black = 2;
     private int[][] board;


  

     // Set up the board in the standard othello starting positions, 
     // and starts the game
     public void start() {....}
     

     


     // The actual game runs continuously until a player wins
     public void game()
     {

         printBoard();


         while ( won() == 0 )
         {
              boolean valid = false;
              while ( !valid )
              {
                    try
                    {
                        getMove(black);
                        valid = true;
                    }
                    catch (Exception e)
                    {
                        System.out.println("Enter a valid coordinate!");
                    }
              }
              valid = false;
              while (  !valid ) 
              {
                    try
                    {
                        getMove(white);
                        valid = true;
                    }
                    catch
                    {
                        System.out.println("Enter a valid coordinate !");
                    }
              }
              
              printBoard(); 
             
         }


         if ( won() != 3 )
            System.out.println( won() ==1 ? "white": "black" + " won !");
         else 
            System.out.println("It's a draw !");


     }






     // NOTE(GET INPUT): Get the input - a move
     // Prompts the player for a move and the coordinates for the move. 
     // throws an exception if the input is not valid or if the entered 
     // coordinates do not make a valid move
     private void getMove( int color ) throws Exception{...}

     


     // NOTE(CHECK RULE): 1. Validate the move
     // returns if a move at coordinate (x,y) is a valid move for the specified player
     private boolean isValid(int color, int x, int y){...}



     // NOTE(ADD SUB RESULT): 2. Configure the board
     // Adds the move onto the board, and the pieces gained from that 
     // move. Assume the move is valid
     public void add(int x, int y, int color){...}




     // NOTE(CHECK RULE): 3. Check if someone Won
     // Check which color has more pieces on the board, count the pieces
     // Returns the winner, if any. If there are no winners, returns 0
     private int won()
     {
          if ( !canGo(white) && !canGo(black) )
          {


                int count = 0;
                for (int i = 0 ; i < 8 ; i++ )
                {
                     for (int j = 0 ; j < 8; j ++)
                     {
                          if (board[i][j] == white)
                          {
                                count++;
                          }
                          if (board[i][j] == black)
                          {
                               count--;
                          }
                     }
                }


   
                if ( count > 0 ) return white; 
                if ( count < 0 ) return black;
                // count == 0 --> draw
                return 3; 
                

          }


          // Still canGo()
          return 0;


     }
     



     // NOTE(CHECK RULE): 
     // Returns whether the player of the specified color has a valid 
     //  move in his turn. This will return false when 
     //  1. none of his pieces are present (no piece remaining)
     //  2. none of his moves result in him gaining new pieces
     //  3. the board is filled up
     private boolean canGo(int color){...}



}

3. Similar ones

[7.7] chat server

1. Example

A online --msg--> B online
A online --add friend-> B offline
A offline<--see-- B online

What is our chat server?
1. support a small number of users
2. ppl have a contact list to see who is online vs offline

What specifies actions does it need to support?
- User A signs online

- User A ask for their contact list, with each person's current status
- Friends of User A now see User A as online
- User A add User B to contact list
- User A sends text-based message to User B
- User A changes status message and/or status type
- User A removes User B

- User A signs offline

What can we learn about these requirements?
- We must have
1.a concept of users,
2. add request status,
3.online status,
4. messages.

What are the core components?
1. Database
2. Server
3. XML
We' ll need a database to store items and an "always online" application as the server.
We might recommend using XML for the communication between the chat server and the clients, as it's easy for a person and a machine to read.

What are the key objects and methods?
hidden details such as how to actually push the data to a client

2. Implementation

enum StatusType
{
   online, offline, away
}
class Status
{
    StatusType status_type;
    String status_message;
}
class User
{


   // Field: my ID
   String username;
   String display_name;

   // Field: my friend list
   User[] contact_list;
   // Field: my ongoing friend list
   AddRquest[] requests;



   // Method: modify status and short description
   boolean updateStatus(  StatusType stype, Strign message ){....;}
   // Method: add people
   boolean addUserWithUsername(String name);
   // Method: I aprove someone
   boolean approveRequest(String username);
   // Method: I reject someone
   boolean denyRequest(String username);
   // Mehtod: I remove some friends
   boolean removeContact(String username);
   // Method: CHAT MAIN FUNCTION - I CHAT, send message
   boolean sendMessage(String usernname, String message);
}

/* Hold data that from_user would like to add to_user */
class AddRequest
{
    User from_user;
    User to_user;
}
class Server
{
   User getUserByUsername(String username);
}

3. Similar Ones

What problems would be the hardest to solve(or the most interesting)?
Q1 How do we know if someone is online- I mean, really ,really know?

While we would like users to tell us when they sign off, we can't know for sure. A user's connection might have died, for example. To make sure that we know when a user has signed off. we might try regularly pining the client to male sure it's still there.

Q2 How do we deal with conflicting information ?

We have some information stored in the computer's memory and some in the database. What happens if they got out of sync? which one is "right"?

Q3 How do we make our server scale?

While we designed out chat sever without worrying -- too much --- about scalability, in real life this would be a concern. We'd need to split our data across many servers, which would increase our concern about out of sync data.

Q4 How do we prevent denial of service(DOS) attacks?

Clients can push data to us -- what if they try to DOS us? How do we prevent that?
https://msdn.microsoft.com/en-us/library/cc750213.aspx
http://static.planetminecraft.com/files/resource_media/screenshot/1306/Cisco-what-is-ddos-attack_4812859_lrg.jpg

http://docs-legacy.fortinet.com/cb/html/index.html#page/FOS_Cookbook/UTM/cb_utm_ip_dos.html

A DOS attack really shouldn't be handled by your HTTP server. Once a request has reached it the attacker has 'won' by taking up a connection (no matter how short). Even if they are short they can just slam it with thousands/sec and prevent anyone else from connecting. Also, they might not attempt to 'connect' via TCP and just flood the server with all sorts of requests.

Block/detect DOS attacks at a lower level or via a firewall, which I'm sure many software and hardware versions support some basic types of DOS detection and prevention.

http://corporatecomplianceinsights.com/what-is-a-ddos-attack-and-how-can-you-prevent-one/

While there are many varieties of DoS and DDoS attacks, they can generally be categorized as one of two types: network‐based, or application‐based. In a network‐based attack, the attacker floods the victim computer with information, clogging up the victim computer’s communication lines and overwhelming the victim computer’s ability to process the flood of information. Some of the historically more common techniques include:

Ping Floods: In this relatively simple type of attack, the attacking computer sends a flood of requests (or “pings”) to the victim computer that ask the victim computer to acknowledge that the victim computer is able to communicate with the attacker. If enough of these ping requests are sent, it can overwhelm the victim.
Smurf or Fraggle Attacks: In these attacks, the attacking computer falsifies (or “spoofs”) its Internet Protocol address so that it appears to be the same as the victim’s computer. The attacker, posing as the victim, then sends requests to an entire network of computers seeking an acknowledgment. The entire network then sends its acknowledgment to the victim’s computer, flooding it with information.
SYN/ACK Flood: These attacks exploit the way computers acknowledge each other when they first communicate over the Internet. The attacking computer introduces itself, pursuant to standard Internet protocol, with a “SYN” message. The computer responds with the standard “SYN‐ACK” message and waits for the attacking computer to issue the standard “ACK” acknowledgement. The attacker never issues this acknowledgement, which has the effect of making the victim computer expend its resources waiting. A flood of these mismatched communications can take the victim computer out of commission.

The second broad category of DoS and DDoS attacks is application‐based attacks. While conceptually similar in some ways to network‐based flooding attacks, application‐based attacks, as the name suggests, focus on exploiting software programs or applications on the victim computer in an attempt to make the computer crash or slow to a crawl. An attacker carrying out such a request may seek, for example, to repeatedly run resource‐intensive search requests on a victim’s search engine or database, or to repeatedly request complex and feature‐rich web pages from a server, either of which may severely tax or exceed the victim server’s capacity.

The organized group of attacking computers used in a DDoS attack is often called a “botnet” (as in “robot network”). To assemble a botnet, an attacker often will infect the computers of unsuspecting users with malicious software that allows the attacker to remotely control those computers. The user of the infected computer often will be completely unaware that the computer has been infected. Less enterprising or technically adept attackers can simply rent botnets from the web’s black market. There also have been occasions in which botnets have consisted of volunteers who willingly allow their computers to be controlled by the DDoS attacker. This often occurs in politically‐motivated attacks, as in the Wikileaks‐related attacks coordinated by the “Anonymous” organization. The recruiting and coordination of such voluntary botnets often occurs on social media sites such as Twitter, as well as in online chat rooms.

Hardware and Structural Defense: Of course, monitoring and having a response plan alone will do nothing to stop DoS and DDoS attacks, or lessen their severity. For that, you will need to consider hardware and structural defenses. For example, most modern network hardware can be configured to prevent Ping, Smurf/Fraggle, SYN/ACK, and similar DoS network flood attacks by rejecting or limiting the Internet traffic that characterizes those types of attacks (i.e., an unusually high number of “ping” requests from one computer, or a computer that refuses to issue the “ACK” message). Hardware‐implemented access control lists can also be used to filter out traffic from particular attacking computers.

These “limiting” or “filtering” solutions, however, are less useful in defending against DDoS attacks. Because DDoS attacks are perpetrated through several different computers acting in concert (often hundreds or thousands of them), they can confuse or circumvent measures taken to limit or filter the requests coming from a small number of specifically identified computers. Planning an adequate DDoS defense therefore should involve considering structural defenses as well – in other words, defenses that involve the manner in which a computer network, and the information it contains, is organized. Even these structural defenses, however, may have limited effectiveness in preventing or remediating the attacks.

Perhaps the simplest structural solution is to have an extraordinary amount of network capacity and processing power, so that your entity can withstand nearly any DDoS “flood.” While some larger entities can do this, for most it is simply not cost effective. More practical structural solutions can include: outsourcing to a large and well‐established hosting provider that is likely to have a larger amount of capacity and in‐house methods of addressing DDoS attacks; having a backup “mirror” website hosted at a different location that can be substituted if the primary site is under attack; implementing caching systems that substitute simpler web pages in place of complex feature‐rich pages if application resources become strained; and having a system architecture that clearly separates the “front‐end” web‐facing system from the “back end” processing systems to minimize the business effects of attacks on the web server.

Reporting: It is indisputably difficult to investigate and hold accountable those who perpetrate DoS and DDoS attacks – but it does happen. As of the date of this article, for example, there are news reports that persons suspected of being involved in the Wikileaks-related attacks have been arrested and their residences searched for evidence. If your business is victimized by such an attack, you therefore should consider forensic preservation of the system logs and related documentation. It just may be that this information could lead to the perpetrator being prosecuted.

Thursday, October 1, 2015

[7.6] Jigsaw puzzle

1. Example

every piece has four edges with different type: inner, outer or flat
every piece can rotate , we called orientation here
_ _
___| |___
| |
| |
|________|

___ ___
| |__| |
| |
|________|

_______
| |
| |
|________|

2. Implementation

//
//We grounded the edges by their type. Because inners with outers, and //vice versa, this enables us to go straight to the potential matches.


//We keep track of the inner perimeter of the puzzle (Exposed_Edges) as //we work our way inwards. Exposed_Edges is initialized to be the //corner's edges.



class Edge 
{
   enum Type {inner, outer, flat}
   Piece parent; // NOTE : this edge belong to which piece, it must be some piece's lateral[left, right,top, bottom]
   Type type;
   bool fitsWith(Edge type){...}// Inners & outer fit together
}
class Piece
{
   Edge left, right, top, bottom;
   Orientation solvedOrientation = ....;// 90,180,etc
}



class Puzzle
{




   Piece[][] pieces;// Remaining pieces left to put away 
   Piece[][] solution;
   Edge[] inners, outers, flats;




   
   // NOTE: they are the outmost layer pieces with flat edge outside. 
   // we're going to solve this by working our way in-wards, starting   
   //with the corners. This is a list of the inside edges. 
   
    Edge[] exposed_edges;




   void sort() 
   {
        
        // Iterate through all edges, adding each to inners, outers, 
        // etc. as appropriate. Look for the corners-add those to  
        // solution. Add each non-flat edge of the corner to 
        // exposed_edges.
        
   }




   void solve()
   {
        // NOTE: edge1 here refers the edge inside 
        foreach edge1 in exposed_edges
        {
             // Look for a match to edge1 
             if (  edge.type == Edge.type.inner  )
             {
                   // NOTE: outers refers to those remaining pieces 
                   foreach edge2 in outers
                   {
                       if edge1.fitsWith(edges)
                       {
                             
//we found a match ! 
//1. Remove edge1 from exposed_edges. 
//2. Add edges2'piece to solution. 
//3. Check which edges of edge2 are exposed , and add those to exposed //edges.
                             
                       }
                   }
                   // Do the same thing, swapping inner & outer 
             }
        }
   }



}

3. Similar ones

[7.5] Online book reader system

1. Example

1.User membership creation and extension
2. Searching the database of books
3. Reading the books

2. Implementation





//
//keep all the book's information
//Method - add books
//Method - delete books
//Method - update books
//
public class Book
{
    private long ID;
    private String details;
    private static Set books;


    // Constructor
    public Book(long ID, Stirng details){...}


    // Class Method
    public static void addBook(long ID, String detials)
    {
         books.add(new Book(ID, details));
    }
    public static Book find(long ID)
    {
         for ( Book b: books)
             if (b.getID() == ID) return b
         return null;
    }
    public static  void delete (Book b)
    {
         books.remvoe(b);
    }


    // Object methods
    public void update (){}
}






//
//Keep all the information regarding the user ,and an identifier to //identify each user uniquely.
//We can add functionality like 
//Method - registering the user, 
//Method - charging a membership amount,
//Method - monthly / daily quota
//
public class User
{
     private long ID;
     private String details;
     private int accountType;
     private static Set users;

    
     // Constructor
     public User(long ID, Stirgn details, int accountType){...}



     // Class Method
     public static User find(long ID)
     {
          for (User u:users)
               if (u.getID() == ID) return u;
          return null;
     }
     public static void addUser()
     {
          users.add(  new User(ID, details, accountType));
     }



     // Object methods
     public Book searchLibrary(long ID) {return Book.find(id);}
     public void renewMembership(){...}    
}





//
//Manager class for managing the online book reader system which would //have a listen function to listen for any incoming requests to log in.
//It also provides 
//Method  - book search functionality and 
//Method  - display functionality.
//Because the end user interacts through this class, 
//SEARCH must be implemented
//
public class OnlineReaderSystem
{


       private Book b;
       private User u;



       // Constructor
       public OnlineReaderSystem(Book b, User u){...}
       


       // Object methods
       public void listenRequest(){}
       public Book searchBook(long ID){return book.find(ID);}
       public User searchUser(long ID){return user.find(ID);}
       public void display(){}


}

3. Similar Ones

[7.4] Chess Design

1. Example

A B C D E F G H
8 Br Bn Bb Bq Bk Bb Bn Br
7 Bp Bp Bp Bp Bp Bp Bp Bp
6
5
4
3
2 Wp Wp Wp Wp Wp Wp Wp Wp
1 Wr Wp Wb Wq Wk Wb Wn Wr

2. implementation

// 0. GameManager : Game run
public class GameManager 
{
     void processTurn(PlayerBase player){};
     boolean acceptTurn(ChessPieceTurn turn){ return true};
     Position currentPosition;
}
public class chessPieceTurn{};





// 1. PlayerBase
public abstract class PlayerBase
{
    public abstract ChessPieceTurn getTurn(Position p); 
}
class ComputerPlayer extends PlayerBase
{
    public ChessPieceTurn getTurn(Position p){return null;}
    public setDifficulty(){};
    public PositionEstimator estimator;
    public PositionBackTracker backtracker; 
}
public class HumanPalyer extends PlayerBase
{
    public chessPieceTurn getTurn (Position p){return null;}
}



// 2. ChessPieceBase
public abstract class chessPieceBase
{
    abstract boolean canBeChecked();
    abstract boolean isSupportCastle();
}
public class King extends ChessPieceBase{...}
public class Queen extends ChessPieceBase{...}






// 3. Represent chess position in compact form
public class Position
{ 
   ArrayList black;
   ArrayList white;
}




public class PositionBackTracker 
{
    public static Position getNext(Position p){return null;}
}




// PositionPotentialValue
public abstract class PositionPotentialValue
{
    abstract boolean lessThan(PositionPotentialValue pv);
}
public class PositionEstimator
{
    public static PositionPotentialValue estimate(Position p){...}
}

3. Similar Ones
http://rangerway.com/way/object-oriented-chess-game/#tfbml-data%7B%22close_iframe%22%3Atrue%2C%22location_url%22%3A%22http%3A%2F%2Frangerway.com%2Fway%2Fobject-oriented-chess-game%2F%22%7D

[7.3] music juke box

1 Example
Music Jukebox
________
/ O (|) \
| ===== |
| _ _ _ |
| |_| |_| |_| |
| _ _ _ |
| |_| |_| |_| |
|________ |
| |
JukeBox
- CDPlayer
- User
- Set<CD>
- TRackSelector
- Song getCurrentTrack()
- void processOneUser(User u)
CDPlayer

TRackSelector
- Song currentSong
- void setTrack(Song s)
- getCurrentSong()
Playlist
- ~~ArrayList<song>~~
- Queue<Song>
- Song track
~~- add~~
- getNextTrackToPlay()
- void queueUpTrack(Song s)
User
- name
- ID
- getID, setID
- getName. setName
- addUser(String n, long id)
Song
-name

2. implementation
CD album
a Collection of all CD in a matrix form
matrix[][]
CD class
- name
- number of songs
- album price
- album published year
Song class
-song name
- song duration
- song price
- song singer
- song published year
PLAY class
- play
- delete
-

*********************
class CDPlayer VS class Playlist
Let's first understand the basic system components:
=>CD player
=>CD
=>Display() (display length of song, remaining time and playlist)

Now, let's break this down further:
-playlist creation (includes add, delete, shuffle etc sub functionalities)
- CD selector
-Queueing up a song
- Get next song from playlist
-Track selector

A user can be introduced:
-Adding
- Deleting
-credit information

public class CD{}
public class CDPlayer
{
    private Playlist p;
    private CD c;
    
    public Playlist getPlaylist() {return p;}
    public void setPlaylist() {this.p = p;}
    
    public CD getCD(){return c;}
    public void setCD(CD c ){ this.c = c;}
    


    // 3 Constructors
    public CDPlayer(Playlist p){this.p = p;}
    public CDPlayer(CD c, Playlist p){...}
    public CDPlayer(CD c){this.c = c;}
 

    
    public void playTrack(Song s){...}
}

//*** The Machine
public class JukeBox 
{
    private CDPlayer cdPlayer;
    private User user;
    private Set cdCollection;
    private TrackSelector ts;

  

    // Constructor
    public JukeBox(CDPlayer cdPlayer, User user, Set cdCollection, TrackSelector ts){...}



    public Song getCurrentTrack() {return ts.getCurrentSong();}
    public void processOneUser(User u){this.user = u;}
}

// a collection of songs, add a song and pop up a song
public class Playlist 
{
    private Song track;
    private Queue queue;



    // Constructor
    public Playlist(Song track, Queue queue){...}



    public Song getNextTrackToPlay() {return queue.peek();}
    public void queueUpTrack(Song s){queue.add(s);}
}
public class Song
{
    private String songName;
}

public class TrackSelector
{
    private Song currentSong;
    


    // Constructor
    public TrackSelector(Song s ){currentSong = s;}



    public void setTrack(Song s ){currentSong = s; }
    public Song getCurrentSong() {return currentSong;}
}

public class User
{
    private String name;
    private long ID; 
  
    
    // Constructor
    public User(String name, long ID){...}
    public User getUser(){return this;}


    public String getName() {return name;} 
    public void setName(String name) {this.name = name;}
    
    public long getID() {return ID;}
    public void setID(long ID){ ID = ID;}


    public static User addUser(String name, long ID){...}
    

}

.3 similar Ones

[7.2] getCallHandler()

1. Example

------------------>PM
| |
|-----------------? TL <-----------------------
| |
fresher1 fresher2 fresher3 fresher4 fresher5 fresher6

X X X X X O ->?

Call coming in districute call.rank=0 -> Emp check every level employee to see availability
Emp.receive(call)
Emp.cannotHandle(call)
- call.rank +1
- distribute call.rank+1 again
- find next level available Emp
-> Queue, no one is available
Employee
- free
- rank
- CallHandler instance
- void ReceiveCall(Call call)
- void CallHandled(Call call)
- void CannontHandle(Call call)
Call
- rank
- void reply()
- void disconnect()
CallHandler
- Employee callHandler(Call call)
- void dispatchCall(Call call)
- void getNextCall(Employee emp)

2. Implementation
Q1: getHandler() check available and check canHandle or not
A1: If not handle ==> call CallHanlder class to do the distribute job
AND callHandler call next level people to Handle call
if handled, complete, otherwise, call CallHandler class again
A1: available -> every ppl has a field called free, ==> Employee has 3 types
Employee class
fresher class
TL class
PM class
CallHandler class hook up call and Employee
Call class ??

public class CallHandler  // Hook up call and employee
{
  static final int LEVELS = 3;// we have 3 level of employees
    static final int NUM_FRESHERS = 5;// we have 5 freshers
    // Use ArrayList[] instead of ArrayList> since we know the size
    ArrayList[] employeeLevels = new ArrayList[LEVELS];
    // queue for each call's rank
    Queue[]  callQueues = new LinkedList[LEVELS];



    public CallHandler(){...}




    // *** check every level employee to see who is free now
    // @Return: Employee - the one it is free
    Employee getCallHandler(Call call)
    {
         //for (int i = 0 ; employeeLevels[call.rank].size())
         for (int level = call.rank; level < LEVELS -1; level++) 
         {
              ArrayList employeeLevel = employeeLevels[level];
              for (Employee emp: employeeLevel)
              {
                  if (emp.free)
                  {
                     return emp;
                  }
              }
         }
         return null;
    }
    



    // ** route the call to an available employee, or adds to a queue
    void dispatchCall(Call call)
    {
          // try to route the call to an employee with minimal rank
          Employee emp = getCallHandler(call);
          // Someone is free
          if (emp != null)
               emp.ReceiveCall(call);
          // No one is free
          else
              // place the call into queue according to its rank
              callQueues[call.rank].add(call);
    } 



    void getNextCall(Employee e){...}// look for call for e's rank, put this as parameter



}

class Call
{
    int rank = 0;
    public void reply(String message){...}
    public void disconnect(){...}
}
class Employee
{
    CallHandler callHandler;


    // Fields
    int rank;// 0 - fresher, 1- technical lead, 2 - product manager
    boolean free; // availability


    // Constructor 
    Employee(int rank) {this.rank = rank;}


    // Function
    void ReceiveCall(Call call){...}
    void CallHandled(Call call){...}// call is complete
    void CannotHandle(Call call)// escalate call
    {
         call.rank = rank + 1;
         CallHandler.dispatchCall(call);
         free =  = true;
         CallHandler.getNextCall(this);// look for waiting call
    }
}
class Fresher extends Employee
{
     public Fresher(){super(0);}
}
class TechLead extends Employee
{
     public TechLead() {super(1);}
}
class ProductManager extends Employee
{
     public ProductManager(){super(2);}
}

3. Similar Ones