Question

Write a program that breaks up a string of words with no spaces into a string with the appropriate spaces.

Follow the following process:

1. Clarify the problem
2. Refine the solution
3. Code it
4. Last words

Clarify the problem

1. Consider a general case, like “fastman”
2. Disambiguate expected result
3. State the key assumptions
4. clarify function signature

2 words? null input? where is the words from? We might use a dictionary.

Refine the solution

1. what if the dictionary cannot fit in RAM
2. how would you print the most likely of multiple choices
3. what if the words are not spelled correctly?
4. Testing

Code it

Write code now, skip.

Last words

Talk naive solution, then come up with a reasonably better one.

Time/Space tradeoff. (like pre-processing or something)

For very big/small input.

White-board practise is important!

First Word

A cookie is a small text file that is stored by a browser on the user’s machine. Cookies are plain text; they contain no executable code.

Every time the user loads the website, the browser sends the cookie back to the server to notify the website of the user’s previous activity.

1. Stateful information

   Such as shopping cart

2. browsing activity

   Such as log in, which button is clicked, and which page is visited

Security

A secure cookie will only be sent to the server when a request is made using SSL and the HTTPS protocol. However, the entire mechanism is inherently insecure.

The cookie just contains data and isn’t harmful in and of itself. However, tracking cookies and especially third-party tracking cookies are commonly used as ways to compile long-term records of individuals' browsing history, which is a potential privacy concern.

Types of HTTP Cookie

Common cookie types:

Session cookie

It’s while browsing. (Normally) deleted by browser when the user closes the browser.

Persistent cookie

Max-age 1 year. The value set in that cookie would be sent back to the server every time the user visited the server. Also called tracking cookies

Secure cookie

The secure attribute is enabled, and is only used via HTTPS.

Third-party cookie

First-party cookies are cookies that belong to the same domain that is shown in the browser’s address bar. Third-party cookies are cookies that belong to domains different from the one shown in the address bar.

It opens up the potential for tracking the user’s browsing history. An example of 3rd-party:

As an example, suppose a user visits www.example1.com. This web site contains an advert from ad.foxytracking.com, which, when downloaded, sets a cookie belonging to the advert’s domain (ad.foxytracking.com). Then, the user visits another website, www.example2.com, which also contains an advert from ad.foxytracking.com, and which also sets a cookie belonging to that domain (ad.foxytracking.com). Eventually, both of these cookies will be sent to the advertiser when loading their ads or visiting their website. The advertiser can then use these cookies to build up a browsing history of the user across all the websites that have ads from this advertiser.

One more thing

Nowadays ther'e a new kind of HttpOnly cookie (used only when transmitting HTTP (or HTTPS) requests, thus restricting access from other, non-HTTP APIs such as JavaScript).

source1

source2

Question

link

Given a permutation which contains numbers in the range [1, N], return the length of the largest cycle in the permutation.

A permutation cycle is a subset of a permutation whose elements trade places with one another.

Sample Testcases:

a) longestCycle([2 3 1]) returns 3, since only cycle is (1 2 3) whose length is 3

b) longestCycle([5 4 3 2 1]) returns 2, since the permutation can be decomposed into (1 5), (2 4), (3)

Solution

This is just an idea.

Now first of all, its important to understand what is a cycle in permutation.

Keeping that in mind, I take (5,4,3,2,1) as an example. First, we fetch 5, and we swap number 5 with the 5th element of the array (which is 1). After this swap, value 1 is in the 1st position, so this cycle is done, the length is 2.

We continue doing this until all numbers of value v is in the (v)th position, we should know the largest length of cycle during this process.

I did not write code, and I found very little relevant resources. If you did, please leave a comment below.

Question

link

Given API: int Read4096(char* buf);

It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file. The return is the number of chars read.

Use above API to Implement API “int Read(char* buf, int n)” which reads any number of chars from the file.

Solution

Since the nature of C++ and Java is different, I changed the api to:

GoogleApi.read4096(){}
GoogleRead4096.read(int n){}

As suggested, the solution is to keep one local buffer, and 1 pointer within the buffer.

Code

String buffer = null;
int p = 0;

public String read(int n) {
    if (n < 0) {
        return null;
    } else if (n == 0) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        // there is (LENGTH - p) chars left in the local buffer
        if (buffer == null || p == buffer.length()) {
            // no char left in buffer, update buffer
            buffer = GoogleApi.read4096();
            p = 0;
            if (buffer.length() == 0) {
                // finish reading the file (no more input chars)
                break;
            }
        } else {
            int numChars = buffer.length() - p;
            if (numChars >= n) {
                sb.append(buffer.substring(p, p + n));
                p = p + n;
                n = 0;
            } else {
                sb.append(buffer.substring(p));
                p = buffer.length();
                n -= numChars;
            }
        }
    }
    return sb.toString();
}

Question 1

link

Given a 2D array (n x m) of integers, find all duplicate rows and print their index.

Solution

This is a google question.

Use HashMap (but make your own). Computer hash value of each row and insert into HashMap as value pair of HashMap(hashValue, rowNumber). When there’s a collision, just check the rowNumber stored in HashMap with current row.

This requires O(n*m) time and O(n) space. Note that we’re not store the entire row into HashMap cuz it’ll take up too much space.

We (probably) can also use Trie.

Question 2

link

Given a binary matrix of N X N of integers, you need to return only unique rows of binary arrays.

input: 
0 1 0 0 1 
1 0 1 1 0 
0 1 0 0 1 
1 1 1 0 0 

ans: 
0 1 0 0 1 
1 0 1 1 0 
1 1 1 0 0

Solution

Different from Question 1, this input is only 0 and 1.

The solution is to use Trie. Each node only have 2 children (that’s why Trie is perfect solution here).

Code

Using binary trie node, refactored by me.

public int[][] getUniqueRows(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;

    TrieNode root = new TrieNode();
    TrieNode p;
    int uniqueCount = 0;
    boolean[] isUnique = new boolean[m];
    // isUnique is used to mark the lines that would appear in final result

    // start to build the trie
    for (int i = 0; i < m; i++) {
        // insert number matrix[i][] into the trie
        p = root;
        // root element would be an empty heading for all numbers
        for (int j = 0; j < n; j++) {
            int digit = matrix[i][j];
            if (p.kids == null) {
                p.kids = new TrieNode[2];
            }
            if (p.kids[digit] == null) {
                // this is a whole new branch, create a new node here
                p.kids[digit] = new TrieNode();
                if (j == n - 1) {
                    uniqueCount++;
                    isUnique[i] = true;
                }
            }
            p = p.kids[digit];
        }
    }
    System.out.println("uniqueCount is " + uniqueCount);
    int[][] result = new int[uniqueCount][];
    int k = 0;
    for (int w = 0; w < isUnique.length; w++) {
        if (isUnique[w]) {
            result[k++] = matrix[w];
        }
    }
    return result;
}

class TrieNode {
    TrieNode[] kids = null;
}

Question

link

In a binary tree, if in the path from root to the node A, there is no node with greater value than A’s, this node A is visible. We need to count the number of visible nodes in a binary tree. For example, in the following tree:

        5
     /     \
   3        10
  / \      /
20   21   1

There are four (4) visible nodes: 5, 20, 21, and 10.

Solution

This is an easy question. A solution is available here.

Code

written by me

public int countVisible(TreeNode root) {
    return helper(root, Integer.MIN_VALUE);
}

private int helper(TreeNode node, int ancesterMax) {
    if (node == null) {
        return 0;
    }
    int newMax = Math.max(ancesterMax, node.val);
    if (node.val > ancesterMax) {
        return 1 + helper(node.left, newMax) + helper(node.right, newMax);
    } else {
        return helper(node.left, newMax) + helper(node.right, newMax);
    }
}

Terminologies

Paging

Paging is a method of writing data to, and reading it from, secondary storage for use in primary storage, also known as main memory. Paging plays a role in memory management for a operating system.

Page table

A page table is the data structure used by a virtual memory system to store the mapping between virtual addresses and physical addresses.

Page fault

A page fault is a trap to the software raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. In the typical case the operating system tries to handle the page fault by making the required page accessible at a location in physical memory or terminates the program in the case of an illegal access.

An invalid page fault or page fault error occurs when the operating system cannot find the data in virtual memory. This usually happens when the virtual memory area, or the table that maps virtual addresses to real addresses, becomes corrupt.

Logical address

Logical address is the address at which an item (memory cell, storage element, network host) appears to reside from the perspective of an executing application program.

Physical address

Physical address (also real address, or binary address), is a memory address that is represented in the form of a binary number for accessing main memory.

In general, Logical address is the address generated by the CPU. Where as physical address is the actual address of the process in the memory. The CPU generates the logical address that is added with the offset value to get the actual address of the process inthe memory.

Thrashing

Thrashing or disk thrashing is a term used to describe when the hard drive is being overworked by moving information between the system memory and virtual memory excessively.

Demand Paging

Virtual memory is implemented (mostly) using demand paging. Demand Paging is a type of swapping in which pages of data are not copied from disk to RAM until they are needed. This is an example of a lazy loading technique.

Pros:

1. less RAM needed
2. more users
3. less I/O

When a pages is needed, if invalid referernce, abort the process. else if valid, it’s called page fault.

Page fault time:

1. servicing the page fault interrupt
2. read in new page (major part)
3. restart the process

Page Replacement

1. FIFO
2. Optimal Algorithm
3. LRU
4. LRU Approximation
   1. Additional-Reference-Bits algorithm
   2. Second-Chance (Clock) algorithm

Refer to another post “Cache and Page Replacement Algorithms”.

Solution to Thrashing

1. More RAM
2. Less program running together
3. Assign working priorities
4. Improve spatial locality#Solutions) by replacing loops, i.e.

Replace

// recall that in C, arrays use Row-major order
int m[256][256]; 
for (k=0; k<256; k++) { 
    for (i=0; i<256; i++) { 
        m[i][k] = something(); 
    }
}

with

int m[256][256]; 
for (i=0; i<256; i++) { 
    for (k=0; k<256; k++) {
        // consecutive values of k reside in adjacent memory locations 
        m[i][k] = something(); 
    }
}

So that the use of data elements is within relatively close storage locations.

Question

How to test hashCode() function? Example:

public int hashCode(){
    int result = 17 + hashDouble(re);
    result = 31 * result + hashDouble(im);
    return result;
}

Solution

We need to test that the hash function is reflexive, symmetric, and transitive.

Code

Not including ‘not equal’ test.

@Test
public void testEquals_Symmetric() {
    Person x = new Person("Foo Bar");  // equals and hashCode check name field value
    Person y = new Person("Foo Bar");
    Assert.assertTrue(x.equals(y) && y.equals(x));
    Assert.assertTrue(x.hashCode() == y.hashCode());
}

Question

link

Object Oriented design for Elevator in a multi-storied apartment

A Single Elevator

Use Case:

1. User
   1. press a button to summon the lift
   2. press a button to get to a specific floor
2. Button
   1. floor button and level button
   2. illuminates when pressed
   3. place an ‘elevator request’ when pressed
3. Elevator
   1. moves up/down
   2. open/close the door

ElevatorRequests Class

Each button press results in an elevator request which has to be served. Each of these requests is tracked at a global place. ElevatorRequests, the class which stores elevator requests can use different strategies to schedule the elevator requests.

ElevatorController

The elevator is controlled by a controller class which we call ElevatorController. The elevator controller instructs the elevator what to do and also can shutdown/start up the elevator of the building. The elevator controller reads the next elevator request to be processed and serves it.

Button (Abstract) Class

Button is abstract class defining common behavior like illuminate, doNotIlluminate. FloorButton, ElevatorButton extend Button type and define placeRequest() which is invoked when the button is pressed.

In conclusion, ElevatorController runs the show by reading the ElevatorRequests to process and instructing the Elevator what to do. User send request by pressing Buttons.

Extend the answer to multiple elevators

1. Each elevator have 1 controller.

2. Floor based requests can be served by any elevator, thus these requests are added to a common area accessible by all controllers.

3. Each elevator controller runs as a separate thread and checks if it can process a floor request. Mind synchronization issues.

Question

Design a Parking Lot.

Solution

Class hierarchy:

1. A parking lot has multiple Levels.
2. A Level has multiple Parking Spot.
3. A Spot can park motorcycle, car or bus, which all belongs to Vehicle.

Implement methods:

1. Vehicle.parkInSpot(Spot s)
2. Vehicle.leaveSpot(Spot s)
3. Vehicle.canFitIn(Spot s)
4. ParkingLot.parkVehicle(Vehicle v)
5. Level.parkVehicle(Vehicle v)
6. Level.parkVehicleAtSpot(Vehicle v, Spot s)
7. Level.findAvailableSpot(VehicleType vt)

ParkingLot Class is just a wrapper class of Levels. By doing this, we seperated out parking logic from other broader actions (like Spot management).

The code below is from CC150v5. Its design is a bit strange (a car can occupy multiple spots), so just use this code as a guide but not a reference.

Code

ParkingLot.java

public class ParkingLot {
    private Level[] levels;
    private final int NUM_LEVELS = 5;

    public ParkingLot() {
        levels = new Level[NUM_LEVELS];
        for (int i = 0; i < NUM_LEVELS; i++) {
            levels[i] = new Level(i, 30);
        }
    }

    /* Park the vehicle in a spot (or multiple spots). Return false if failed. */
    public boolean parkVehicle(Vehicle vehicle) {
        for (int i = 0; i < levels.length; i++) {
            if (levels[i].parkVehicle(vehicle)) {
                return true;
            }
        }
        return false;
    }

    public void print() {
        for (int i = 0; i < levels.length; i++) {
            System.out.print("Level" + i + ": ");
            levels[i].print();
            System.out.println("");
        }
        System.out.println("");
    }
}

Level.java

/* Represents a level in a parking garage */
public class Level {
    private int floor;
    private ParkingSpot[] spots;
    private int availableSpots = 0; // number of free spots
    private static final int SPOTS_PER_ROW = 10;

    public Level(int flr, int numberSpots) {
        floor = flr;
        spots = new ParkingSpot[numberSpots];
        int largeSpots = numberSpots / 4;
        int bikeSpots = numberSpots / 4;
        int compactSpots = numberSpots - largeSpots - bikeSpots;
        for (int i = 0; i < numberSpots; i++) {
            VehicleSize sz = VehicleSize.Motorcycle;
            if (i < largeSpots) {
                sz = VehicleSize.Large;
            } else if (i < largeSpots + compactSpots) {
                sz = VehicleSize.Compact;
            }
            int row = i / SPOTS_PER_ROW;
            spots[i] = new ParkingSpot(this, row, i, sz);
        }
        availableSpots = numberSpots;
    }

    public int availableSpots() {
        return availableSpots;
    }

    /* Try to find a place to park this vehicle. Return false if failed. */
    public boolean parkVehicle(Vehicle vehicle) {
        if (availableSpots() < vehicle.getSpotsNeeded()) {
            return false;
        }
        int spotNumber = findAvailableSpots(vehicle);
        if (spotNumber < 0) {
            return false;
        }
        return parkStartingAtSpot(spotNumber, vehicle);
    }

    /* Park a vehicle starting at the spot spotNumber, and continuing until vehicle.spotsNeeded. */
    private boolean parkStartingAtSpot(int spotNumber, Vehicle vehicle) {
        vehicle.clearSpots();
        boolean success = true;
        for (int i = spotNumber; i < spotNumber + vehicle.spotsNeeded; i++) {
             success &= spots[i].park(vehicle);
        }
        availableSpots -= vehicle.spotsNeeded;
        return success;
    }

    /* find a spot to park this vehicle. Return index of spot, or -1 on failure. */
    private int findAvailableSpots(Vehicle vehicle) {
        int spotsNeeded = vehicle.getSpotsNeeded();
        int lastRow = -1;
        int spotsFound = 0;
        for (int i = 0; i < spots.length; i++) {
            ParkingSpot spot = spots[i];
            if (lastRow != spot.getRow()) {
                spotsFound = 0;
                lastRow = spot.getRow();
            }
            if (spot.canFitVehicle(vehicle)) {
                spotsFound++;
            } else {
                spotsFound = 0;
            }
            if (spotsFound == spotsNeeded) {
                return i - (spotsNeeded - 1);
            }
        }
        return -1;
    }

    public void print() {
        int lastRow = -1;
        for (int i = 0; i < spots.length; i++) {
            ParkingSpot spot = spots[i];
            if (spot.getRow() != lastRow) {
                System.out.print("  ");
                lastRow = spot.getRow();
            }
            spot.print();
        }
    }

    /* When a car was removed from the spot, increment availableSpots */
    public void spotFreed() {
        availableSpots++;
    }
}