Software Support

Genuine questions you can ask.

- How many meetings do you have every week?

- What is ratio of testers to developers to product managers?

- What is interaction like?

- How does project planning happen on the team?

- I am very interested in scalability. Did you come in with background in this, or what opportunities are there to learn about it?

- I am not familiar with technology X, but it sounds like very interesting solution. Could you tell me bit more about how it works?

How to prepare for technical questions?

- Ask yourself if you could improve the time efficiency by reducing space efficiency or vice versa.

- Write code for algo on paper.

Must know:

- DS: LinkedLists, Binary Trees, Trees, Stacks, Queues, Vectors/ArrayLists, Hash tables

- Algos: BFS, DFS, Binary search, Merge sort, Quick sort, Tree Insert/Find etc.

- Concepts: Bit Manipulation, Singleton design pattern, Memory(stack vs heap), factory design pattern, recursion, Big O notation

Structure answers using SAR:

- Situation: On my SE project, I was assigned to work with three other people. While two were great, third member didn’t contribute much. He stayed quiet in meetings, rarely chipped in during email discussions and struggled to complete his components.

- Action: One day after class, I pulled him aside to speak about the course and then move discussion into talking about project. I asked him open ended questions on how he felt it was going, and which components he was excited about tackling. He suggested all easiest components, and yet offered to do the write up. I realized that he was not lazy - he was actually just really confused about the project and lacked confidence. I worked with him after that to break down components into smaller pieces, and made sure to complement him a lot in his work to boost his confidence.

- Result: He was still weakest member of team, but he got a lot better. He was able to finish all his work on time and he contributing more in discussions. We were happy to work with him on future project.

Five steps to technical questions:

- Ask your interviewer questions to resolve ambiquity

- Design an algorithm

- Write pseudo code first but make sure to tell your interviewer that you are writing pseudo code.

- Write your code, not too slow and not too fast.

- Test your code and carefully fix any mistakes.

Ask questions:

- What are the data types?

- How much data is there?

- What assumptions do you need to solve the problem?

- Who is the user?

1) Design algorithm to sort a list?

- What sort of list? An array? A linked list? : Array

- What does the array hold? Numbers? Characters? Strings? : Numbers

- And are the numbers integers? : Yes

- Where did the numbers come from? Are they IDs? Values of something? : They are ages of customers

- And how many customers are there? : About a million

- We now have a different problem: sort an array containing million integers between 0 and 130. How do we solve this? Just create an array with 130 elements and count the number of ages at each value.

2) Design an algorithm?

- What are the space and time complexities?

- What happens if there is a lot of data?

- Does your design cause other issues?

- If there are other issues, did you make right tradeoffs?

- If they gave you specific data, have you leveraged that information?

3) Pseudo code:

- Writing pseudo code can help you outline your thoughts clearly and reduce number of mistakes you commit.

- Make sure you tell your interviewer that you are writing pseudocode and that you will follow it up with real code.

4) Code:

- Don’t rush through your code.

- Use DS generously. Use good DS or define your own. If you are asked problem involving finding minimum age for group of people, consider defining data structure to represent a person.

- Don’t crowd your coding:

5) Test:

- Consider testing for:

- Extreme cases: 0, negative, null, maximums etc.

- User error: what happens if user passes in null or negative value?

- General cases: Test the normal case.

DS brainstorming:

Example: Numbers are randomly generated and stored into an array. How would you keep track of the median?

- LinkedList: Probably not – linkedlist tend not to do very well with accessing and sorting numbers

- Array? : may be, but you already have an array. Could you somehow keep elements sorted? That’s probably expensive.

- Binary tree? : This is possible, since binary tree do fairly wall with ordering. If binary search tree is perfectly balanced, top might be median. If it is even number, median is actually average of middle two elements. The middle two elements cant both be at top. This is probably workable algorithm.

- Heap? : Heap is really good at basic ordering and keeping track of max and mins. This is actually interesting – if you had two heaps, you could keep track of biggest half and smallest half of the elements. Biggest half is kept in the min heap, such that smallest element in biggest half is at the root. The smallest half is kept in max heap, such that biggest element of smallest half is root. Now with these DS, you have potential median elements at the roots. If the heaps are no longer the same size, you can quickly rebalance the heaps by popping an element off the one heap and pushing it onto the other.

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

- Public static Boolean isUniqueChars2(String str) {

- Boolean[] char_set = new Boolean[256];

- For(int i=0;i<str.length();i++) {

- Int val = str.charAt(i);

- If(char_Set[val]) return false;

- Char_Set[val] = true;

- }

- Return true;

- }

- Time complexity is O(n) where n is the length of the string, and space complexity is O(n).

Design an algorithm and write code to remove duplicate characters in a string without using additional buffer.

- For each character, check if it is a duplicate of already found characters.

- Skip duplicate characters and update the non duplicate characters.

- Time complexity is O(N2).

- Code

- Code…

- Test cases:

- String does not contain any duplicates e.g abcd

- String contains all duplicates e.g aaaa

- Null string

- String with all continuous duplicates. E.g aaaabbbb

- String with non contiguous duplicate. Eg. Abababab

Write method to replace all spaces in string with ‘%20’.

- Count a number of spaces during first scan of the string

- Parse the string again from end and for each character:

- If space is encountered, store ‘%20’.

- Else, store the character as it is in the newly shifted location.

- Public static void replaceFun(char[] str, int length) {

- For(I = 0; i<length; i++) {

- If (str[i] ==’’) {

- spaceCount++;

- }

- NewLength = length+spaceCount *2;

- Str[newLength] = ‘\0’;

- For(i=length-1;i>=0;i--) {

- If(str[i]==’’){

- Str[newLength-1] = ‘0’;

- Str[newLength-2] = ‘2’;

- Str[newLength-3] = ‘%’;

- newLength = newLength – 3;

- }

- Else

- {

- Str[newLength – 1] = str[i];

- newLength = newLength – 1;

- }

Assume you have method is SubString which checks if one word is a substring of another.

Given two strings, s1 and s2, write code to check is s2 is a rotation of s1 using only one call to isSubstring

- Check is length(S1)==length(s2). If not, return false.

- Else concatenate s1 with itself and see whether s2 is substring of the result.

- Input s1=apple, s2=pleap

- Input s1=apple, s2=ppale

- Public static Boolean isRotation(String s1, String s2) {

- Int len = s1.length();

- /* check that s1 and s2 are equal length and not empty */

- If (len ==s2.length() && len>0){

- /*concatenate s1 and s1 within new buffer */

- String s1s1 = s1+s1;

- Return isSubstring(s1s1,s2);

- }

- Return false;

- }

Write an algorithm to delete a node in the middle of single linked list, given only access to that node.

- Ex: Input: node c form linkedlist a->b->c->d->e

- Result: nothing is returned, but new linkedlist looks like a->b->d->e

- Public static Boolean deleteNode(LinkedListNode n){

- If(n==null ||n.next==null){

- Return false;

- }

- LinkedListNode next=n.next;

- N.data=next.data;

- N.next=next.next;

- Return true;

}

You have two very large binary trees: T1, with millions of nodes and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

boolean containsTree(TreeNode t1, TreeNode t2) {

if (t2 == null) return true; // The empty tree is always a subtree

else return subTree(t1, t2);

}

boolean subTree(TreeNode r1, TreeNode r2) {

if (r1 == null)

return false; // big tree empty & subtree still not found.

if (r1.data == r2.data) {

if (matchTree(r1,r2)) return true;

}

return (subTree(r1.left, r2) || subTree(r1.right, r2));

}

boolean matchTree(TreeNode r1, TreeNode r2) {

if (r2 == null && r1 == null)

return true; // nothing left in the subtree

if (r1 == null || r2 == null)

return false; // big tree empty & subtree still not found

if (r1.data != r2.data)

return false; // data doesn’t match

return (matchTree(r1.left, r2.left) &&

matchTree(r1.right, r2.right));

}

Design musical jukebox using object oriented principles.

Let’s first understand basic system components:

- CD Player

- CD

- Display() (display length of song, remaining time and playlist)

- Lets break this down further:

- Playlist creation (includes add, delete, shuffle etc sub functionalities)

- CD selector

- Track selector

- Queueing up of song

- Get next song from playlist

- User can also 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(Playlist p) { this.p = p; }

public CD getCD() { return c; }

public void setCD(CD c) { this.c = c; }

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) { ... }

}

public class JukeBox {

private CDPlayer cdPlayer;

private User user;

private Set<CD> cdCollection;

private TrackSelector ts;

public JukeBox(CDPlayer cdPlayer, User user, Set<CD> cdCollection, TrackSelector ts) { ... }

public Song getCurrentTrack() { return ts.getCurrentSong(); }

public void processOneUser(User u) { this.user = u; }

}

public class Playlist {

private Song track;

private Queue<Song> queue;

public Playlist(Song track, Queue<Song> 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;

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

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

public Song getCurrentSong() { return currentSong; }

}

public class User {

private String name;

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; }

private long ID;

public User(String name, long iD) { ... }

public User getUser() { return this; }

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

}

Design chess game using object oriented principles:

public class ChessPieceTurn { };

public class GameManager {

void processTurn(PlayerBase player) { };

boolean acceptTurn(ChessPieceTurn turn) { return true; };

Position currentPosition;

}

public abstract class PlayerBase {

public abstract ChessPieceTurn getTurn(Position p);

}

class ComputerPlayer extends PlayerBase {

public ChessPieceTurn getTurn(Position p) { return null; }

public void setDifficulty() { };

public PositionEstimator estimater;

public PositionBackTracker backtracter;

}

public class HumanPlayer extends PlayerBase {

public ChessPieceTurn getTurn(Position p) { return null; }

}

public abstract class ChessPieceBase {

abstract boolean canBeChecked();

abstract boolean isSupportCastle();

}

public class King extends ChessPieceBase { ... }

public class Queen extends ChessPieceBase { ... }

public class Position { // represents chess positions in compact form

ArrayList<ChessPieceBase> black;

ArrayList<ChessPieceBase> white;

}

public class PositionBackTracker {

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

}

public class PositionEstimator {

public static PositionPotentialValue estimate(Position p) { ... }

}

public abstract class PositionPotentialValue {

abstract boolean lessThan(PositionPotentialValue pv);

}

Design data structure for online book reader system.

Since the problem doesn’t describe much about the functionality, let’s assume we want to

design a basic online reading system which provides the following functionality:

» User membership creation and extension

» Searching the database of books

» Reading the books

To implement these we may require many other functions, like get, set, update, etc Objects

required would likely include User, Book, and Library

The following code / object oriented design describes this functionality:

public class Book {

private long ID;

private String details;

private static Set<Book> books;

public Book(long iD, String details) { ... }

public static void addBook(long iD, String details){

books.add(new Book(iD, details));

}

public void update() { }

public static void delete(Book b) { books.remove(b); }

public static Book find(long id){

for (Book b : books)

if(b.getID() == id) return b;

return null;

}

public class User {

private long ID;

private String details;

private int accountType;

private static Set<User> users;

public Book searchLibrary(long id) { return Book.find(id); }

public void renewMembership() { ... }

public static User find(long ID) {

for (User u : users) {

if (u.getID() == ID) return u;

}

return null;

}

public static void addUser(long ID, String details, int accountType) {

users.add(new User(ID, details, accountType));

}

public User(long iD, String details, int accountType) { ... }

}

public class OnlineReaderSystem {

private Book b;

private User u;

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

public void listenRequest() { }

public Book searchBook(long ID) { return Book.find(ID); }

public User searchUser(long ID){ return User.find(ID); }

public void display() { }

}

This design is a very simplistic implementation of such a system.

We have a class for User to keep all the information regarding the user, and an identifier to identify each user uniquely. We can add functionality like registering the user, charging a membership amount and monthly / daily quota, etc.

Next, we have Book class where we will keep all the book’s information. We would also im-

plement functions like add / delete / update books.

Finally, we have a 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 book

search functionality and display functionality Because the end user interacts through this

class, search must be implemented here.

Implement jigsaw puzzle. Design the data structure and explain an algorithm to solve puzzle.

class Edge {

enum Type { inner, outer, flat }

Piece parent;

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;

/* 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() {

foreach edge1 in exposed_edges {

/* Look for a match to edge1 */

if (edge1.type == Edge.Type.inner) {

foreach edge2 in outers {

if edge1.fitsWith(edge2) {

/* We found a match! Remove edge1 from

* exposed_edges. Add edge2’s piece to

* solution. Check which edges of edge2 are

* exposed, and add those to exposed_edges. */

}

/* Do the same thing, swapping inner & outer. */

}

How would you design a chat server? Provide details about various backend components, classes and methods. What would be the hardest problem to solve? What is our chat server?

This is something you should discuss with your interviewer, but let’s make a couple of as-

sumptions: imagine we’re designing a basic chat server that needs to support a small num-

ber of users People have a contact list, they see who is online vs offline, and they can send

text-based messages to them We will not worry about supporting group chat, voice chat,

etc We will also assume that contact lists are mutual: I can only talk to you if you can talk to

me Let’s keep it simple

What specific actions does it need to support?

» User A signs online

» User A asks for their contact list, with each person’s current status

» Friends of User A now see User A as online

» User A adds 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 a concept of users, add request status, online status, and messages

What are the core components?

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?

We have listed the key objects and methods below Note that we have hidden many of the

details, such as how to actually push the data out to a client

enum StatusType {

online, offline, away;

}

class Status {

StatusType status_type;

String status_message;

}

class User {

String username;

String display_name;

User[] contact_list;

AddRequest[] requests;

boolean updateStatus(StatusType stype, String message) { … };

boolean addUserWithUsername(String name);

boolean approveRequest(String username);

boolean denyRequest(String username);

boolean removeContact(String username);

boolean sendMessage(String username, String message);

}

/* Holds data that from_user would like to add to_user */

class AddRequest {

User from_user;

User to_user;

}

class Server {

User getUserByUsername(String username);

}

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 pinging the client to make 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 get out of sync? Which one is “right”?

Q3 How do we make our server scale?

While we designed out chat server 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 we do prevent denial of service attacks?

Clients can push data to us—what if they try to DOS us? How do we prevent that?

Write method to generate nth Fibonacci number.

There are three potential approaches: (1) recursive approach (2) iterative approach (3) using

matrix math We have described the recursive and iterative approach below, as you would

not be expected to be able to derive the matrix-based approach in an interview

Recursive Solution:

int fibo(int n) {

if (n == 0) {

return 0; // f(0) = 0

} else if (n == 1) {

return 1; // f(1) = 1

} else if (n > 1) {

return fibo(n-1) + fibo(n-2); // f(n) = f(n—1) + f(n-2)

} else {

return –1; // Error condition

}

Iterative Solution:

int fibo(int n) {

if (n < 0) return -1; // Error condition.

if (n == 0) return 0;

int a = 1, b = 1;

for (int i = 3; i <= n; i++) {

int c = a + b;

a = b;

b = c;

}

return b;

}

Write algo to print all ways of arranging eight queens on chess board so none of them share same row, column or diagonal.

We will use a backtracking algorithm For each row, the column where we want to put the

queen is based on checking that it does not violate the required condition

1 For this, we need to store the column of the queen in each row as soon as we have finalized

it Let ColumnForRow[] be the array which stores the column number for each row

2 The checks that are required for the three given conditions are:

» On same Column : ColumnForRow[i] == ColumnForRow[j]

» On same Diagonal: (ColumnForRow[i] - ColumnForRow[j] ) == ( i- j) or

(ColumnForRow[j] - ColumnForRow[i]) == (i - j)

int columnForRow[] = new int [8];

boolean check(int row) {

for (int i = 0; i < row; i++) {

int diff = Math.abs(columnForRow[i] - columnForRow[row]);

if (diff == 0 || diff == row - i) return false;

}

return true;

}

void PlaceQueen(int row){

if (row == 8) {

printBoard();

return;

}

for (int i = 0; i < 8; i++) {

columnForRow[row]=i;

if(check(row)){

PlaceQueen(row+1);

}

You are given two sorted arrays, A and B, and A has a large enough buffer at the end

to hold B Write a method to merge B into A in sorted order

SOLUTION

This code is a part of the standard merge-sort code We merge A and B from the back, by

comparing each element

public static void merge(int[] a, int[] b, int n, int m) {

int k = m + n - 1; // Index of last location of array b

int i = n - 1; // Index of last element in array b

int j = m - 1; // Index of last element in array a

// Start comparing from the last element and merge a and b

while (i >= 0 && j >= 0) {

if (a[i] > b[j]) {

a[k--] = a[i--];

} else {

a[k--] = b[j--];

}

while (j >= 0) {

a[k--] = b[j--];

}

Write a method to sort an array of strings so that all the anagrams are next to each other

SOLUTION

The basic idea is to implement a normal sorting algorithm where you override the com-

pareTo method to compare the “signature” of each string In this case, the signature is the

alphabetically sorted string

public class AnagramComparator implements Comparator<String> {

public String sortChars(String s) {

char[] content = s.toCharArray();

Arrays.sort(content);

return new String(content);

}

public int compare(String s1, String s2) {

return sortChars(s1).compareTo(sortChars(s2));

}

If you have a 2 GB file with one string per line, which sorting algorithm would you use

to sort the file and why?

SOLUTION

When an interviewer gives a size limit of 2GB, it should tell you something - in this case, it

suggests that they don’t want you to bring all the data into memory

So what do we do? We only bring part of the data into memory

Algorithm:

How much memory do we have available? Let’s assume we have X MB of memory available

1 Divide the file into K chunks, where X * K = 2 GB Bring each chunk into memory and

sort the lines as usual using any O(n log n) algorithm Save the lines back to the file

2 Now bring the next chunk into memory and sort

3 Once we’re done, merge them one by one

The above algorithm is also known as external sort Step 3 is known as N-way merge

The rationale behind using external sort is the size of data Since the data is too huge and we

can’t bring it all into memory, we need to go for a disk based sorting algorithm.

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string

Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4

Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

SOLUTION

Use ordinary binary search, but when you hit an empty string, advance to the next non-

empty string; if there is no next non-empty string, search the left half

public int search(String[] strings, String str, int first, int last) {

while (first <= last) {

// Ensure there is something at the end

while (first <= last && strings[last] == “”) {

--last;

}

if (last < first) {

return -1; // this block was empty, so fail

}

int mid = (last + first) >> 1;

while (strings[mid] == “”) {

++mid; // will always find one

}

int r = strings[mid].compareTo(str);

if (r == 0) return mid;

if (r < 0) {

first = mid + 1;

} else {

last = mid - 1;

}

return -1;

}

public int search(String[] strings, String str) {

if (strings == null || str == null) return -1;

if (str == “”) {

for (int i = 0; i < strings.length; i++) {

if (strings[i] == “”) return i;

}

return -1;

}

return search(strings, str, 0, strings.length - 1);

}

Given a matrix in which each row and each column is sorted, write a method to find

an element in it

SOLUTION

Assumptions:

» Rows are sorted left to right in ascending order Columns are sorted top to bottom in

ascending order

» Matrix is of size MxN

This algorithm works by elimination Every move to the left (--col) eliminates all the elements

below the current cell in that column Likewise, every move down eliminates all the elements

to the left of the cell in that row

boolean FindElem(int[][] mat, int elem, int M, int N) {

int row = 0;

int col = N-1;

while (row < M && col >= 0) {

if (mat[row][col] == elem) {

return true;

} else if (mat[row][col] > elem) {

col--;

} else {

row++;

}

return false;

}

Given two lines on a Cartesian plane, determine whether the two lines would intersect

SOLUTION

There are a lot of unknowns in this problem (what format are the lines in? What if they are the

same line?), but let’s assume:

» If two lines are the same (same line = same slope and y-intercept), they are considered

to intersect

» We get to decide the data structure

1 public class Line {

2 static double epsilon = 0.000001;

3 public double slope;

4 public double yintercept;

6 public Line(double s, double y) {

7 slope = s;

8 yintercept = y;

9 }

11 public boolean intersect(Line line2) {

12 return Math.abs(slope - line2.slope) > epsilon ||

13 Math.abs(yintercept - line2.yintercept) < epsilon;

14 }

15 }

OBSERVATIONS AND SUGGESTIONS:

» Ask questions This question has a lot of unknowns—ask questions to clarify them Many

interviewers intentionally ask vague questions to see if you’ll clarify your assumptions

» When possible, design and use data structures It shows that you understand and care

about object oriented design

» Think through which data structures you design to represent a line There are a lot of

options, with lots of trade offs Pick one and explain your choice

» Don’t assume that the slope and y-intercept are integers

» Understand limitations of floating point representations Never check for equality with

Write a method to implement *, - , / operations You should use only the + operator

SOLUTION

With an understanding of what each operation (minus, times, divide) does, this problem can

be approached logically

» Subtraction should be relatively straightforward, as we all know that a - b is the same

thing as a + (-1)*b

» Multiplication: we have to go back to what we learned in grade school: 21 * 3 = 21 + 21

+ 21 It’s slow, but it works

» Division is the trickiest, because we usually think of 21 / 3 as something like “if you divide

a 21 foot board into 3 pieces, how big is each piece?” If we think about it the other way

around, it’s a little easier: “I divided a 21 foot board in x pieces and got pieces of 3 feet

each, how many pieces were there?” From here, we can see that if we continuously sub-

tract 3 feet from 21 feet, we’ll know how many pieces there are That is, we continuously

subtract b from a and count how many times we can do that

1 /* Flip a positive sign to negative, or a negative sign to pos */

2 public static int FnNegate(int a) {

3 int neg = 0;

4 int d = a < 0 ? 1 : -1;

5 while (a != 0) {

6 neg += d;

7 a += d;

8 }

9 return neg;

10 }

12 /* Subtract two numbers by negating b and adding them */

13 public static int FnMinus(int a, int b) {

14 return a + FnNegate(b);

15 }

17 /* Check if a and b are different signs */

18 public static boolean DifferentSigns(int a, int b) {

19 return ((a < 0 && b > 0) || (a > 0 && b < 0)) ? true : false;

20 }

22 /* Return absolute value */

23 public static int abs(int a) {

24 if (a < 0) return FnNegate(a);

25 else return a;

26 }

28 /* Multiply a by b by adding a to itself b times */

29 public static int FnTimes(int a, int b) {

30 if (a < b) return FnTimes(b, a); // algo is faster if b < a

31 31 int sum = 0;

32 for (int iter = abs(b); iter > 0; --iter) sum += a;

33 if (b < 0) sum = FnNegate(sum);

34 return sum;

35 }

37 /* Divide a by b by literally counting how many times does b go into

38 * a. That is, count how many times you can subtract b from a until

39 * you hit 0. */

40 public static int FnDivide(int a, int b) throws

41 java.lang.ArithmeticException {

42 if (b == 0) {

43 throw new java.lang.ArithmeticException(“Divide by 0.”);

44 }

45 int quotient = 0;

46 int divisor = FnNegate(abs(b));

47 int divend; /* dividend */

48 for (divend = abs(a); divend >= abs(divisor); divend += divisor) {

49 ++quotient;

50 }

51 if (DifferentSigns(a, b)) quotient = FnNegate(quotient);

52 return quotient;

53 }

OBSERVATIONS AND SUGGESTIONS

» A logical approach of going back to what exactly multiplication and division do comes

in handy Remember that All (good) interview problems can be approached in a logi-

cal, methodical way!

» The interviewer is looking for this sort of logical work-your-way-through-it approach

» This is a great problem to demonstrate your ability to write clean code—specifically,

to show your ability to re-use code For example, if you were writing this solution and

didn’t put FnNegate in its own method, you should move it out once you see that you’ll

use it multiple times

» Be careful about making assumptions while coding Don’t assume that the numbers are

all positive, or that a is bigger than b

Given two squares on a two dimensional plane, find a line that would cut these two

squares in half

SOLUTION

Any line that goes through the center of a rectangle must cut it in half Therefore, if you drew

a line connecting the centers of the two squares, it would cut both in half

1 public class Square {

2 public double left;

3 public double top;

4 public double bottom;

5 public double right;

6 public Square(double left, double top, double size) {

7 this.left = left;

8 this.top = top;

9 this.bottom = top + size;

10 this.right = left + size;

11 }

13 public Point middle() {

14 return new Point((this.left + this.right) / 2,

15 (this.top + this.bottom) / 2);

16 }

18 public Line cut(Square other) {

19 Point middle_s = this.middle();

20 Point middle_t = other.middle();

21 if (middle_s == middle_t) {

22 return new Line(new Point(left, top),

23 new Point(right, bottom));

24 } else {

25 return new Line(middle_s, middle_t);

26 }

27 }

28 }

How would you design the DS for a very large social network (Facebook, LinkedIn etc)? Describe how you would design an algorithm to show the connection, or path between two people

Approach:

Forget that we’re dealing with millions of users at first Design this for the simple case

We can construct a graph by assuming every person is a node and if there is an edge be-

tween two nodes, then the two people are friends with each other

class Person {

Person[] friends;

// Other info

}

If I want to find the connection between two people, I would start with one person and do a

simple breadth first search

But... oh no! Millions of users!

When we deal with a service the size of Orkut or Facebook, we cannot possibly keep all of our

data on one machine That means that our simple Person data structure from above doesn’t

quite work—our friends may not live on the same machine as us Instead, we can replace our

list of friends with a list of their IDs, and traverse as follows:

1 For each friend ID: int machine_index = lookupMachineForUserID(id);

2 Go to machine machine_index

3 Person friend = lookupFriend(machine_index);

There are more optimizations and follow up questions here than we could possibly discuss,

but here are just a few thoughts

Optimization: Reduce Machine Jumps

Jumping from one machine to another is expensive Instead of randomly jumping from ma-

chine to machine with each friend, try to batch these jumps—e g , if 5 of my friends live on

one machine, I should look them up all at once

Optimization: Smart Division of People and Machines

People are much more likely to be friends with people who live in the same country as them

Rather than randomly dividing people up across machines, try to divvy them up by country,

city, state, etc This will reduce the number of jumps.

Usually, in BFS, we mark a node as visited by setting a flag visited in its node class Here, we

don’t want to do that (there could be multiple searches going on at the same time, so it’s bad

to just edit our data) In this case, we could mimic the marking of nodes with a hash table to

lookup a node id and whether or not it’s been visited

Other Follow-Up Questions:

» In the real world, servers fail How does this affect you?

» How could you take advantage of caching?

» Do you search until the end of the graph (infinite)? How do you decide when to give up?

» In real life, some people have more friends of friends than others, and are therefore

more likely to make a path between you and someone else How could you use this data

to pick where you start traversing?

The following code demonstrates our algorithm:

public class Server {

ArrayList<Machine> machines = new ArrayList<Machine>();

}

public class Machine {

public ArrayList<Person> persons = new ArrayList<Person>();

public int machineID;

}

public class Person {

private ArrayList<Integer> friends;

private int ID;

private int machineID;

private String info;

private Server server = new Server();

public String getInfo() { return info; }

public void setInfo(String info) {

this.info = info;

}

public int[] getFriends() {

int[] temp = new int[friends.size()];

for (int i = 0; i < temp.length; i++) {

temp[i] = friends.get(i);

}

return temp;

}

public int getID() { return ID; }

public int getMachineID() { return machineID; }

public void addFriend(int id) { friends.add(id); }

// Look up a person given their ID and Machine ID

public Person lookUpFriend(int machineID, int ID) {

for (Machine m : server.machines) {

if (m.machineID == machineID) {

for (Person p : m.persons) {

if (p.ID == ID){

return p;

}

return null;

}

// Look up a machine given the machine ID

public Machine lookUpMachine(int machineID) {

for (Machine m:server.machines) {

if (m.machineID == machineID)

return m;

}

return null;

}

public Person(int iD, int machineID) {

ID = iD;

this.machineID = machineID;

}

If you were designing web crawler, how would you avoid getting into infinite loops?

First, how does the crawler get into a loop? The answer is very simple: when we re-parse an

already parsed page This would mean that we revisit all the links found in that page, and this

would continue in a circular fashion

Be careful about what the interviewer considers the “same” page Is it URL or content? One

could easily get redirected to a previously crawled page

So how do we stop visiting an already visited page? The web is a graph-based structure,

and we commonly use DFS (depth first search) and BFS (breadth first search) for traversing

graphs We can mark already visited pages the same way that we would in a BFS/DFS

We can easily prove that this algorithm will terminate in any case We know that each step

of the algorithm will parse only new pages, not already visited pages So, if we assume that

we have N number of unvisited pages, then at every step we are reducing N (N-1) by 1 That

proves that our algorithm will continue until they are only N steps

SUGGESTIONS AND OBSERVATIONS

» This question has a lot of ambiguity Ask clarifying questions!

» Be prepared to answer questions about coverage

» What kind of pages will you hit with a DFS versus a BFS?

» What will you do when your crawler runs into a honey pot that generates an infinite

subgraph for you to wander about?

You have billion URLs, where each is a huge page. How do you detect the duplicate documents?

SOLUTION

Observations:

1 Pages are huge, so bringing all of them in memory is a costly affair We need a shorter

representation of pages in memory A hash is an obvious choice for this

2 Billions of urls exist so we don’t want to compare every page with every other page

(that would be O(n^2))

Based on the above two observations we can derive an algorithm which is as follows:

1 Iterate through the pages and compute the hash table of each one

2 Check if the hash value is in the hash table If it is, throw out the url as a duplicate If it

is not, then keep the url and insert it in into the hash table

This algorithm will provide us a list of unique urls But wait, can this fit on one computer?

» How much space does each page take up in the hash table?

» Each page hashes to a four byte value

» Each url is an average of 30 characters, so that’s another 30 bytes at least

» Each url takes up roughly 34 bytes

» 34 bytes * 1 billion = 31 6 gigabytes We’re going to have trouble holding that all in

memory!

What do we do?

We could split this up into files We’ll have to deal with the file loading / unloading—ugh

» We could hash to disk Size wouldn’t be a problem, but access time might A hash table

on disk would require a random access read for each check and write to store a viewed

url This could take msecs waiting for seek and rotational latencies Elevator algorithms

could elimate random bouncing from track to track

» Or, we could split this up across machines, and deal with network latency Let’s go with

this solution, and assume we have n machines

» First, we hash the document to get a hash value v

» v%n tells us which machine this document’s hash table can be found on

» v / n is the value in the hash table that is located on its machine

You have to design a database that can store terabytes of data It should support ef-

ficient range queries How would you do it?

SOLUTION

Construct an index for each field that requires range queries Use a B+ tree to implement

the index A B+ tree organizes sorted data for efficient insertion, retrieval and removal of

records Each record is identified by a key (for this problem, it is the field value) Since it is a

dynamic, multilevel index, finding the beginning of the range depends only on the height

of the tree, which is usually quite small Record references are stored in the leaves, sorted by

the key Additional records can be found by following a next block reference Records will be

sequentially available until the key value reaches the maximum value specified in the query

Thus, runtimes will be dominated by the number of elements in a range

Avoid using trees that store data at interior nodes, as traversing the tree will be expensive

since it won’t be resident in memory

How would you load test a webpage without using any test tools?

SOLUTION

Load testing helps to identify a web application’s maximum operating capacity, as well as

any bottlenecks that may interfere with its performance Similarly, it can check how an ap-

plication responds to variations in load

To perform load testing, we must first identify the performance-critical scenarios and the

metrics which fulfill our performance objectives Typical criteria include:

» response time

» throughput

» resource utilization

» maximum load that the system can bear

Then, we design tests to simulate the load, taking care to measure each of these criteria

In the absence of formal testing tools, we can basically create our own For example, we

could simulate concurrent users by creating thousands of virtual users We would write a

multi-threaded program with thousands of threads, where each thread acts as a real-world

user loading the page For each user, we would programmatically measure response time,

data I/O, etc

We would then analyze the results based on the data gathered during the tests and compare

it with the accepted values

We have the following method used in a chess game: boolean canMoveTo(int x, int y)

x and y are the coordinates of the chess board and it returns whether or not the piece

can move to that position Explain how you would test this method

SOLUTION

There are two primary types of testing we should do:

Validation of input/output:

We should validate both the input and output to make sure that each are valid This might

entail:

1 Checking whether input is within the board limit

» Attempt to pass in negative numbers

» Attempt to pass in x which is larger than the width

» Attempt to pass in y which is larger than the width

Depending on the implementation, these should either return false or throw an excep-

tion

2 Checking if output is within the valid set of return values (Not an issue in this case,

since there are no “invalid” boolean values )

Functional testing:

Ideally, we would like to test every possible board, but this is far too big We can do a reason-

able coverage of boards however There are 6 pieces in chess, so we need to do something

like this:

1 foreach piece a:

2 for each other type of piece b (6 types + empty space)

3 foreach direction d

4 Create a board with piece a.

5 Place piece b in direction d.

6 Try to move – check return value.

Find the mistake(s) in the following code:

1 unsigned int i;

2 for (i = 100; i <= 0; --i)

3 printf(“%d\n”, i);

SOLUTION

The printf will never get executed, as “i” is initialized to 100, so condition check “i <= 0” will fail

Suppose the code is changed to “i >= 0 ” Then, it will become an infinite loop, because “i” is an

unsigned int which can’t be negative

The correct code to print all numbers from 100 to 1, is “i > 0”

1 unsigned int i;

2 for (i = 100; i > 0; --i)

3 printf(“%d\n”, i);

One additional correction is to use %u in place of %d, as we are printing unsigned int

1 unsigned int i;

2 for (i = 100; i > 0; --i)

3 printf(“%u\n”, i);

How would you test a pen?

SOLUTION

This problem is largely about understand the constraints: what exactly is the pen? You

should ask a lot of questions to understand what exactly you are trying to test To illustrate

the technique in this problem, let us guide you through a mock-conversation

Interviewer: How would you test a pen?

Candidate: Let me find out a bit about the pen Who is going to use the pen?

Interviewer: Probably children

Candidate: Ok, that’s interesting What will they be doing with it? Will they be writing, draw-

ing, or doing something else with it?

Interviewer: Drawing

Candidate: Ok, great On what? Paper? Clothing? Walls?

Interviewer: On clothing

Candidate: Great What kind of tip does the pen have? Felt? Ball point? Is it intended to

wash off, or is it intended to be permanent?

Interviewer: It’s intended to wash off

… many questions later

Candidate: Ok, so as I understand it, we have a pen that is being targeted at 5—10 year olds

The pen has a felt tip and comes in red, green, blue and black It’s intended to wash off cloth-

ing Is that correct?

…

The candidate now has a problem that is significantly different from what it initially seemed

to be Thus, the candidate might now want to test:

1 Does the pen wash off with warm water, cold water, and luke warm water?

2 Does the pen wash off after staying on the clothing for several weeks? What happens if

you wash the clothing while the pen is still wet?

3 Is the pen safe (e g —non-toxic) for children?

How to test an ATM in a distributed banking system?

SOLUTION

The first thing to do on this question is to clarify assumptions Ask the following questions:

» Who is going to use the ATM? Answers might be “anyone,” or it might be “blind people”

- or any number of other answers

» What are they going to use it for? Answers might be “withdrawing money,” “transferring

money,” “checking their balance,” or many other answers

» What tools do we have to test? Do we have access to the code, or just the ATM machine?

Remember: a good tester makes sure she knows what she’s testing!

Here are a few test cases for how to test just the withdrawing functionality:

» Withdrawing money less than the account balance

» Withdrawing money greater than the account balance

» Withdrawing money equal to the account balance

» Withdrawing money from an ATM and from the internet at the same time

» Withdrawing money when the connection to the bank’s network is lost

» Withdrawing money from multiple ATMs simultaneously

Compare and contrast a hash table vs an STL map How is a hash table implemented?

If the number of inputs is small, what data structure options can be used instead of the hash table?

SOLUTION

Compare and contrast Hash Table vs. STL map

In a hash table, a value is stored by applying hash function on a key Thus, values are not

stored in a hash table in sorted order Additionally, since hash tables use the key to find the

index that will store the value, an insert/lookup can be done in amortised O(1) time (assum-

ing only a few collisions in the hashtable) One must also handle potential collisions in a

hashtable

In an STL map, insertion of key/value pair is in sorted order of key It uses a tree to store

values, which is why an O(log N) insert/lookup is required There is also no need to handle

collisions An STL map works well for things like:

» find min element

» find max element

» print elements in sorted order

» find the exact element or, if the element is not found, find the next smallest number

How is a hash table implemented?

1 A good hash function is required (e g : operation % prime number) to ensure that the

hash values are uniformly distributed

2 A collision resolving method is also needed: chaining (good for dense table entries),

probing (good for sparse table entries), etc

3 Implement methods to dynamically increase or decrease the hash table size on a given

criterion For example, when the [number of elements] by [table size] ratio is greater

than the fixed threshold, increase the hash table size by creating a new hash table and

transfer the entries from the old table to the new table by computing the index using

new hash function

What can be used instead of a hash table, if the number of inputs is small?

You can use an STL map Although this takes O(log n) time, since the number of inputs is

small, this time is negligible

What is the difference between deep copy and shallow copy? Explain how you would

use each

SOLUTION

1 struct Test {

2 char * ptr;

3 };

4 void shallow_copy(Test & src, Test & dest) {

5 dest.ptr = src.ptr;

6 }

7 void deep_copy(Test & src, Test & dest) {

8 dest.ptr = malloc(strlen(src.ptr) + 1);

9 memcpy(dest.ptr, src.ptr);

10 }

Note that shallow_copy may cause a lot of programming run-time errors, especially with the

creation and deletion of objects Shallow copy should be used very carefully and only when

a programmer really understands what he wants to do In most cases shallow copy is used

when there is a need to pass information about a complex structure without actual duplica-

tion of data (e g , call by reference) One must also be careful with destruction of shallow

copy

In real life, shallow copy is rarely used There is an important programming concept called

“smart pointer” that, in some sense, is an enhancement of the shallow copy concept

Deep copy should be used in most cases, especially when the size of the copied structure is

Small.

In terms of inheritance, what is the effect of keeping a constructor private?

SOLUTION

Declaring the constructor private will ensure that no one outside of the class can directly instantiate the class In this case, the only way to create an instance of the class is by providing a static public method, as is done when using the Factory Method Pattern

Additionally, because the constructor is private, the class also cannot be inherited

In Java, does the finally block gets executed if we insert a return statement inside the

try block of a try-catch-finally?

SOLUTION

Yes, it will get executed

The finally block gets executed when the try block exists However, even when we attempt

to exit within the try block (normal exit, return, continue, break or any exception), the finally

block will still be executed

Note: There are some cases in which the finally block will not get executed: if the

virtual machine exits in between try/catch block execution, or the thread which

is executing try/catch block gets killed.

What is the difference between final, finally, and finalize?

SOLUTIONS

Final

When applied to a variable (primitive): The value of the variable cannot change

When applied to a variable (reference): The reference variable cannot point to any other object on the heap

When applied to a method: The method cannot be overridden

When applied to a class: The class cannot be subclassed

Finally

There is an optional finally block after the try block or after the catch block. Statements in the

finally block will always be executed (except if JVM exits from the try block) The finally block

is used to write the clean up code.

Finalize

This is the method that the JVM runs before running the garbage collector

Explain what object reflection is in Java and why it is useful?

SOLUTION

Object Reflection is a feature in Java which provides a way to get reflective information about

Java classes and objects, such as:

1 Getting information about methods and fields present inside the class at run time

2 Creating a new instance of a class

3 Getting and setting the object fields directly by getting field reference, regardless of

what the access modifier is

import java.lang.reflect.*;

public class Sample {

public static void main(String args[]) {

try {

Class c = Class.forName(“java.sql.Connection”);

Method m[] = c.getDeclaredMethods();

for (int i = 0; i < 3; i++) {

System.out.println(m[i].toString());

}

} catch (Throwable e) {

System.err.println(e);

}

This code’s output is the names of the first 3 methods inside the “java sql Connection” class

(with fully qualified parameters)

Why it is useful:

1 Helps in observing or manipulating the runtime behavior of applications

2 Useful while debugging and testing applications, as it allows direct access to methods,

constructors, fields, etc

Suppose you are using a map in your program, how would you count the number of

times the program calls the put() and get() functions?

SOLUTION

One simple solution is to put count variables for get() and put() methods and, whenever they

are called, increment the count We can also achieve this by extending the existing library

map and overriding the get() and put() functions

At first glance, this seems to work However, what if we created multiple instances of the

map? How would you sum up the total count for each map object?

The simplest solution for this is to keep the count variables static We know static variables

have only one copy for all objects of the class so the total count would be reflected in count

variables

Write a method to find the number of employees in each department

SOLUTION

This problem uses a straight-forward join of Departments and Employees Note that we use a

left join instead of an inner join because we want to include Departments with 0 employees

select Dept_Name, Departments.Dept_ID, count(*) as ‘num_employees’

from Departments

left join Employees

on Employees.Dept_ID = Departments.Dept_ID

group by Departments.Dept_ID, Dept_Name

What are the different types of joins? Please explain how they differ and why certain

types are better in certain situations

SOLUTION

JOIN is used to combine the results of two tables To perform a join, each of the tables must

have at least one field which will be used to find matching records from the other table The

join type defines which records will go into the result set

Let’s take for example two tables: one table lists “regular” beverages, and another lists the

calorie-free beverages Each table has two fields: the beverage name and its product code

The “code” field will be used to perform the record matching.

1 INNER JOIN: Result set will contain only those data where the criteria match In our ex-

ample we will get 3 records: 1 with COCACOLA and 2 with PEPSI codes

2 OUTER JOIN: OUTER JOIN will always contain the results of INNER JOIN, however it can

contain some records that have no matching record in other table OUTER JOINs are divided

to following subtypes:

2 1 LEFT OUTER JOIN, or simply LEFT JOIN: The result will contain all records from the left

table If no matching records were found in the right table, then its fields will contain the

NULL values In our example, we would get 4 records In addition to INNER JOIN results,

BUDWEISER will be listed, because it was in the left table

2 2 RIGHT OUTER JOIN, or simply RIGHT JOIN: This type of join is the opposite of LEFT

JOIN; it will contain all records from the right table, and missing fields from the left table will

contain NULL If we have two tables A and B, then we can say that statement A LEFT JOIN B

is equivalent to statement B RIGHT JOIN A

In our example, we will get 5 records In addition to INNER JOIN results, FRESCA and WATER

records will be listed

2 3 FULL OUTER JOIN

This type of join combines the results of LEFT and RIGHT joins All records from both tables

will be part of the result set, whether the matching record exists in the other table or not If

no matching record was found then the corresponding result fields will have a NULL value

In our example, we will get 6 records

What is denormalization? Explain the pros and cons

SOLUTION

Denormalization is the process of attempting to optimize the performance of a database by

adding redundant data or by grouping data In some cases, denormalization helps cover up

the inefficiencies inherent in relational database software A relational normalized database

imposes a heavy access load over physical storage of data even if it is well tuned for high

performance

A normalized design will often store different but related pieces of information in separate

logical tables (called relations) If these relations are stored physically as separate disk files,

completing a database query that draws information from several relations (a join operation)

can be slow If many relations are joined, it may be prohibitively slow There are two strate-

gies for dealing with this The preferred method is to keep the logical design normalized, but

allow the database management system (DBMS) to store additional redundant information

on disk to optimize query response In this case, it is the DBMS software’s responsibility to

ensure that any redundant copies are kept consistent This method is often implemented

in SQL as indexed views (Microsoft SQL Server) or materialized views (Oracle) A view rep-

resents information in a format convenient for querying, and the index ensures that queries

against the view are optimized

The more usual approach is to denormalize the logical data design With care, this can

achieve a similar improvement in query response, but at a cost—it is now the database de-

signer’s responsibility to ensure that the denormalized database does not become inconsis-

tent This is done by creating rules in the database called constraints, that specify how the

redundant copies of information must be kept synchronized It is the increase in logical com-

plexity of the database design and the added complexity of the additional constraints that

make this approach hazardous Moreover, constraints introduce a trade-off, speeding up

reads (SELECT in SQL) while slowing down writes (INSERT, UPDATE, and DELETE) This means

a denormalized database under heavy write load may actually offer worse performance than

its functionally equivalent normalized counterpart

A denormalized data model is not the same as a data model that has not been normalized,

and denormalization should only take place after a satisfactory level of normalization has

taken place and that any required constraints and/or rules have been created to deal with

the inherent anomalies in the design For example, all the relations are in third normal form and any relations with join and multivalued dependencies are handles appropriately.

Draw an entity-relationship diagram for a database with companies, people, and pro-

fessionals (people who work for companies)

SOLUTION

People who work for companies are Professionals So there is an ISA (is a) relationship be-

tween People and Professionals (or we could say that a Professional is derived from People)

Each Professional has additional information such as degree, work experiences, etc, in addi-

tion to the properties derived from People

A Professional works for one company at a time, but Companies can hire many Professionals,

so there is a Many to One relationship between Professionals and Companies This “Works

For” relationship can store attributes such as date of joining the company, salary, etc These

attributes are only defined when we relate a Professional with a Company

A Person can have multiple phone numbers, which is why Phone is a multi-valued attribute

Imagine a simple database storing information for students’ grades Design what this

database might look like, and provide a SQL query to return a list of the honor roll

students (top 10%), sorted by their grade point average

SOLUTION

In a simplistic database, we’ll have at least these three objects: Students, Courses, and Cour-

seEnrollment Students will have at least the student name and ID, and will likely have other

personal information Courses will contain the course name and ID, and will likely contain

the course description, professor, etc CourseEnrollment will pair Students and Courses, and

will also contain a field for CourseGrade We will assume that CourseGrade is an integer

Our SQL query to get the list of honor roll students might look like this:

SELECT StudentName, GPA

FROM (

SELECT top 10 percent Avg(CourseEnrollment.Grade) AS GPA,

CourseEnrollment.StudentID

FROM CourseEnrollment

GROUP BY CourseEnrollment.StudentID

ORDER BY Avg(CourseEnrollment.Grade)) Honors

INNER JOIN Students ON Honors.StudentID = Students.StudentID

This database could get arbitrarily more complicated if we wanted to add in professor infor-

mation, billing, etc

Explain the following terms: virtual memory, page fault, thrashing

SOLUTION

Virtual memory is a computer system technique which gives an application program the im-

pression that it has contiguous working memory (an address space), while in fact it may be

physically fragmented and may even overflow on to disk storage Systems that use this tech-

nique make programming of large applications easier and use real physical memory (e g

RAM) more efficiently than those without virtual memory

http://en.wikipedia.org/wiki/Virtual_memory

Page Fault: A page is a fixed-length block of memory that is used as a unit of transfer be-

tween physical memory and external storage like a disk, and a page fault is an interrupt (or

exception) to the software raised by the hardware, when a program accesses a page that is

mapped in address space, but not loaded in physical memory

http://en.wikipedia.org/wiki/Page_fault

Thrash is the term used to describe a degenerate situation on a computer where increas-

ing resources are used to do a decreasing amount of work In this situation the system is

said to be thrashing Usually it refers to two or more processes accessing a shared resource

repeatedly such that serious system performance degradation occurs because the system is

spending a disproportionate amount of time just accessing the shared resource Resource

access time may generally be considered as wasted, since it does not contribute to the ad-

vancement of any process In modern computers, thrashing may occur in the paging system

(if there is not ‘sufficient’ physical memory or the disk access time is overly long), or in the

communications system (especially in conflicts over internal bus access), etc

Write a step by step execution of things that happen after a user presses a key on the

keyboard Use as much detail as possible

SOLUTION

1 The keyboard sends a scan code of the key to the keyboard controller (Scan code for

key pressed and key released is different)

2 The keyboard controller interprets the scan code and stores it in a buffer

3 The keyboard controller sends a hardware interrupt to the processor This is done by

putting signal on “interrupt request line”: IRQ 1

4 The interrupt controller maps IRQ 1 into INT 9

5 An interrupt is a signal which tells the processor to stop what it was doing currently

and do some special task

6 The processor invokes the “Interrupt handler” CPU fetches the address of “Interrupt

Service Routine” (ISR) from “Interrupt Vector Table” maintained by the OS (Processor

use the IRQ number for this)

7 The ISR reads the scan code from port 60h and decides whether to process it or pass

the control to program for taking action

Explain what happens, step by step, after you type a URL into a browser Use as much

detail as possible

SOLUTION

There’s no right, or even complete, answer for this question This question allows you to go

into arbitrary amounts of detail depending on what you’re comfortable with Here’s a start

though:

1 Browser contacts the DNS server to find the IP address of URL

2 DNS returns back the IP address of the site

3 Browser opens TCP connection to the web server at port 80

4 Browser fetches the html code of the page requested

5 Browser renders the HTML in the display window

6 Browser terminates the connection when window is closed

One of the most interesting steps is Step 1 and 2 - “Domain Name Resolution ” The web ad-

dresses we type are nothing but an alias to an IP address in human readable form Mapping

of domain names and their associated Internet Protocol (IP) addresses is managed by the

Domain Name System (DNS), which is a distributed but hierarchical entity

Each domain name server is divided into zones A single server may only be responsible for

knowing the host names and IP addresses for a small subset of a zone, but DNS servers can

work together to map all domain names to their IP addresses That means if one domain

name server is unable to find the IP addresses of a requested domain then it requests the

information from other domain name servers

Explain any common routing protocol in detail For example: BGP, OSPF, RIP

SOLUTION

Depending on the reader’s level of understanding, knowledge, interest or career aspirations,

he or she may wish to explore beyond what is included here Wikipedia and other websites

are great places to look for a deeper understanding We will provide only a short summary

BGP: Border Gateway Protocol

BGP is the core routing protocol of the Internet “When a BGP router first comes up on the

Internet, either for the first time or after being turned off, it establishes connections with

the other BGP routers with which it directly communicates The first thing it does is down-

load the entire routing table of each neighboring router After that it only exchanges much

shorter update messages with other routers

BGP routers send and receive update messages to indicate a change in the preferred path

to reach a computer with a given IP address If the router decides to update its own routing

tables because this new path is better, then it will subsequently propagate this information

to all of the other neighboring BGP routers to which it is connected, and they will in turn

decide whether to update their own tables and propagate the information further ”

Borrowed from http://www livinginternet com/i/iw_route_egp_bgp htm

RIP: Routing Information Protocol

“RIP provides the standard IGP protocol for local area networks, and provides great network

stability, guaranteeing that if one network connection goes down the network can quickly

adapt to send packets through another connection “

“What makes RIP work is a routing database that stores information on the fastest route

from computer to computer, an update process that enables each router to tell other rout-

ers which route is the fastest from its point of view, and an update algorithm that enables

each router to update its database with the fastest route communicated from neighboring

routers ”

OSPF: Open Shortest Path First

“Open Shortest Path First (OSPF) is a particularly efficient IGP routing protocol that is faster

than RIP, but also more complex ”

The main difference between OSPF and RIP is that RIP only keeps track of the closest router

for each destination address, while OSPF keeps track of a complete topological database of

all connections in the local network The OSPF algorithm works as described below

Compare and contrast the IPv4 and IPv6 protocols

SOLUTION

IPv4 and IPv6 are the internet protocols applied at the network layer IPv4 is the most widely

used protocol right now and IPv6 is the next generation protocol for internet

» IPv4 is the fourth version of Internet protocol which uses 32 bit addressing whereas IPv6

is a next generation internet protocol which uses 128 bits addressing

» IPv4 allows 4,294,967,296 unique addresses where as IPv6 can hold 340-undecillion (34,

000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000, 000) unique IP addresses

» IPv4 has different class types: A,B,C,D and E Class A, Class B, and Class C are the three

classes of addresses used on IP networks in common practice Class D addresses are

reserved for multicast Class E addresses are simply reserved, meaning they should not

be used on IP networks (used on a limited basis by some research organizations for

experimental purposes)

» IPv6 addresses are broadly classified into three categories:

1 Unicast addresses: A Unicast address acts as an identifier for a single interface An

IPv6 packet sent to a Unicast address is delivered to the interface identified by

that address

2 Multicast addresses: A Multicast address acts as an identifier for a group / set of

interfaces that may belong to the different nodes An IPv6 packet delivered to a

multicast address is delivered to the multiple interfaces

3 Anycast addresses: Anycast addresses act as identifiers for a set of interfaces that

may belong to the different nodes An IPv6 packet destined for an Anycast ad-

dress is delivered to one of the interfaces identified by the address

» IPv4 address notation: 239 255 255 255, 255 255 255 0

IPv6 addresses are denoted by eight groups of hexadecimal quartets separated by co-

lons in between them

» An example of a valid IPv6 address: 2001:cdba:0000:0000:0000:0000:3257:9652

Because of the increase in the population, there is a need of Ipv6 protocol which can provide

solution for:

1 Increased address space

2 More efficient routing

3 Reduced management requirement

Improved methods to change ISP

5 Better mobility support

6 Multi-homing

7 Security

8 Scoped address: link-local, site-local and global-address space

What is a network / subnet mask? Explain how host A sends a message / packet to

host B when: (a) both are on same network and (b) both are on different networks

Explain which layer makes the routing decision and how

SOLUTION

A mask is a bit pattern used to identify the network/subnet address The IP address consists

of two components: the network address and the host address

The IP addresses are categorized into different classes which are used to identify the network

address

Example: Consider IP address 152 210 011 002 This address belongs to Class B, so:

Network Mask: 11111111.11111111.00000000.00000000

Given Address: 10011000.11010101.00001011.00000010

By ANDing Network Mask and IP Address, we get the following network address:

10011000.11010101.00000000.00000000 (152.210.0.0)

Host address: 00001011.00000010

Similarly, a network administrator can divide any network into sub-networks by using subnet

mask To do this, we further divide the host address into two or more subnets

For example, if the above network is divided into 18 subnets (requiring a minimum of 5 bits

to represent 18 subnets), the first 5 bits will be used to identify the subnet address

Subnet Mask: 11111111 11111111 11111000 00000000 (255 255 248 0)

Given Address: 10011000 11010101 00001011 00000010

So, by ANDing the subnet mask and the given address, we get the following subnet address:

10011000 11010101 00001000 00000000 (152 210 1 0)

How Host A sends a message/packet to Host B:

When both are on same network: the host address bits are used to identify the host within

the network

Both are on different networks: the router uses the network mask to identify the network and

route the packet The host can be identified using the network host address

The network layer is responsible for making routing decisions A routing table is used to

store the path information and the cost involved with that path, while a routing algorithm

uses the routing table to decide the path on which to route the packets

Routing is broadly classified into Static and Dynamic Routing based on whether the table is

fixed or it changes based on the current network condition

What are the differences between TCP and UDP? Explain how TCP handles reliable

delivery (explain ACK mechanism), flow control (explain TCP sender’s / receiver’s win-

dow) and congestion control

SOLUTION

TCP (Transmission Control Protocol): TCP is a connection-oriented protocol A connection can

be made from client to server, and from then on any data can be sent along that connection

» Reliable - when you send a message along a TCP socket, you know it will get there unless

the connection fails completely If it gets lost along the way, the server will re-request

the lost part This means complete integrity; data will not get corrupted

» Ordered - if you send two messages along a connection, one after the other, you know

the first message will get there first You don’t have to worry about data arriving in the

wrong order

» Heavyweight - when the low level parts of the TCP “stream” arrive in the wrong order, re-

send requests have to be sent All the out of sequence parts must be put back together,

which requires a bit of work

UDP(User Datagram Protocol): UDP is connectionless protocol With UDP you send messages

(packets) across the network in chunks

» Unreliable - When you send a message, you don’t know if it’ll get there; it could get lost

on the way

» Not ordered - If you send two messages out, you don’t know what order they’ll arrive in

» Lightweight - No ordering of messages, no tracking connections, etc It’s just fire and

forget! This means it’s a lot quicker, and the network card / OS have to do very little work

to translate the data back from the packets

Explain how TCP handles reliable delivery (explain ACK mechanism), flow control (explain TCP

sender’s/receiver’s window).

For each TCP packet, the receiver of a packet must acknowledge that the packet is received

If there is no acknowledgement, the packet is sent again These guarantee that every single

packet is delivered ACK is a packet used in TCP to acknowledge receipt of a packet A TCP

window is the amount of outstanding (unacknowledged by the recipient) data a sender can

send on a particular connection before it gets an acknowledgment back from the receiver

that it has gotten some of it

What’s the difference between a thread and a process?

SOLUTION

Processes and threads are related to each other but are fundamentally different

A process can be thought of as an instance of a program in execution Each process is an in-

dependent entity to which system resources (CPU time, memory, etc ) are allocated and each

process is executed in a separate address space One process cannot access the variables

and data structures of another process If you wish to access another process’ resources,

inter-process communications have to be used such as pipes, files, sockets etc

A thread uses the same stack space of a process A process can have multiple threads A key

difference between processes and threads is that multiple threads share parts of their state

Typically, one allows multiple threads to read and write the same memory (no processes can

directly access the memory of another process) However, each thread still has its own regis-

ters and its own stack, but other threads can read and write the stack memory

A thread is a particular execution path of a process; when one thread modifies a process

resource, the change is immediately visible to sibling threads

You are given a class with synchronized method A, and a normal method C If you

have two threads in one instance of a program, can they call A at the same time? Can

they call A and C at the same time?

SOLUTION

Java provides two ways to achieve synchronization: synchronized method and synchronized

statement

Synchronized method: Methods of a class which need to be synchronized are declared with

“synchronized” keyword If one thread is executing a synchronized method, all other threads

which want to execute any of the synchronized methods on the same objects get blocked

Syntax: method1 and method2 need to be synchronized

public class SynchronizedMethod {

// Variables declaration

public synchronized returntype Method1() {

// Statements

}

public synchronized returntype method2() {

// Statements

}

// Other methods

}

Synchronized statement: It provides the synchronization for a group of statements rather

than a method as a whole It needs to provide the object on which these synchronized state-

ments will be applied, unlike in a synchronized method

Syntax: synchronized statements on “this” object

1 synchronized(this) {

2 /* statement 1

3 * ...

4 * statement N */

5 }

i) If you have two threads in one instance of a program, can they call A at the same time?

Not possible; read the above paragraph

ii) Can they call A and C at the same time?

Yes Only methods of the same object which are declared with the keyword synchronized

can’t be interleaved

Write a function to swap a number in place without temporary variables

SOLUTION

This is a classic interview problem If you haven’t heard this problem before, you can ap-

proach it by taking the difference between a and b:

public static void swap(int a, int b) {

a = b - a; // 9 - 5 = 4

b = b - a; // 9 - 4 = 5

a = a + b; // 4 + 5 = 9

System.out.println(“a: “ + a);

System.out.println(“b: “ + b);

}

You can then optimize it as follows:

public static void swap_opt(int a, int b) {

a = a^b;

b = a^b;

a = a^b;

System.out.println(“a: “ + a);

System.out.println(“b: “ + b);

}

Write an algorithm which computes the number of trailing zeros in n factorial

SOLUTION

Trailing zeros are contributed by pairs of 5 and 2, because 5*2 = 10 To count the number of

pairs, we just have to count the number of multiples of 5 Note that while 5 contributes to

one multiple of 10, 25 contributes two (because 25 = 5*5)

public static int numZeros(int num) {

int count = 0;

if (num < 0) {

System.out.println(“Factorial is not defined for < 0”);

return 0;

}

for (int i = 5; num / i > 0; i *= 5) {

count += num / i;

}

return count;

}

walk through an example to see how this works: Suppose num = 26 In the first loop, we

count how many multiples of five there are by doing 26 / 5 = 5 (these multiples are 5, 10, 15,

20, and 25) In the next loop, we count how many multiples of 25 there are: 26 / 25 = 1 (this

multiple is 25) Thus, we see that we get one zero from 5, 10, 15 and 20, and two zeros from

25 (note how it was counted twice in the loops) Therefore, 26! has six zeros.

Write a method which finds the maximum of two numbers You should not use if-else

or any other comparison operator

Input: 5, 10

Output: 10

SOLUTION

Let’s try to solve this by “re-wording” the problem We will re-word the problem until we get

something that has removed all if statements

Rewording 1: If a > b, return a; else, return b

Rewording 2: If (a - b) is negative, return b; else, return a

Rewording 3: If (a - b) is negative, let k = 1; else, let k = 0 Return a - k * (a - b)

Rewording 4: Let c = a - b Let k = the most significant bit of c Return a - k * c

We have now reworded the problem into something that fits the requirements The code

for this is below

1 int getMax(int a, int b) {

2 int c = a - b;

3 int k = (c >> 31) & 0x1;

4 int max = a - k * c;

5 return max;

6 }

You are given an array of integers (both positive and negative) Find the continuous

sequence with the largest sum Return the sum

EXAMPLE

Input: {2, -8, 3, -2, 4, -10}

Output: 5 (i e , {3, -2, 4} )

SOLUTION

A simple linear algorithm will work by keeping track of the current subsequence sum If that

sum ever drops below zero, that subsequence will not contribute to the subsequent maximal

subsequence since it would reduce it by adding the negative sum

public static int getMaxSum(int[] a) {

int maxsum = 0;

int sum = 0;

for (int i = 0; i < a.length; i++) {

sum += a[i];

if (maxsum < sum) {

maxsum = sum;

} else if (sum < 0) {

sum = 0;

}

return maxsum;

}

NOTE: If the array is all negative numbers, what is the correct behavior? Con-

sider this simple array {-3, -10, -5}. You could make a good argument that the

maximum sum is either: (A) -3 (if you assume the subsequence can’t be empty)

(B) 0 (the subsequence has length 0) or (C) MINIMUM_INT (essentially the error

case). We went with option B (max sum = 0), but there’s no “correct” answer. This

is a great thing to discuss with your interviewer to show how careful you are.

Design a method to find the frequency of occurrences of any given word in a book

SOLUTION

The first question – which you should ask your interviewer – is if you’re just asking for a

single word (“single query”) or if you might, eventually, use the same method for many dif-

ferent words (“repetitive queries”)? That is, are you simply asking for the frequency of “dog”,

or might you ask for “dog,” and then “cat,” “mouse,” etc?

Solution: Single Query

In this case, we simply go through the book, word by word, and count the number of times

that a word appears This will take O(n) time We know we can’t do better than that, as we

must look at every word in the book

Solution: Repetitive Queries

In this case, we create a hash table which maps from a word to a frequency Our code is then

like this:

Hashtable<String, Integer> setupDictionary(String[] book) {

Hashtable<String, Integer> table = new Hashtable<String, Integer>();

for (String word : book) {

word = word.toLowerCase();

if (word.trim() != “”) {

if (!table.containsKey(word)) table.put(word, 0);

table.put(word, table.get(word) + 1);

}

return table;

}

int getFrequency(Hashtable<String, Integer> table, String word) {

if (table == null || word == null) return -1;

word = word.toLowerCase();

if (table.containsKey(word)) {

return table.get(word);

}

return 0;

}

Note: a problem like this is relatively easy. Thus, the interviewer is going to be

looking heavily at how careful you are. Did you check for error condition?

Write a method to generate a random number between 1 and 7, given a method

that generates a random number between 1 and 5 (i e , implement rand7() using

rand5())

SOLUTION

First, observe that we cannot do this in a guaranteed finite amount of time Why? Let’s see by

a parallel example: How would you use rand2() to create rand3()?

Observe that each call of rand2() and the corresponding decision you make can be repre-

sented by a decision tree On each node, you have two branches You take the left one when

rand2() equals 0 (which happens with 1/2 probability) You take the right one when rand2()

equals 1 (which happens with 1/2 probability) You continue branching left and right as you

continue to call 1/2 When you reach a leaf, you return a result of 1, 2 or 3 (your rand3() re-

sults)

» What’s the probability of taking each branch? 1/2

» What’s the probability to reach a particular leaf node? 1/2^j (for some j)

» What the probability of returning 3 (for example)? We could compute this by summing

up the probabilities of reaching each leaf node with value 3 Each of these paths has

probability 1/2^j, so we know that the total probability of returning 3 must be a series

of terms of reciprocal powers of 2 (e g , 1/2^x + 1/2^y + 1/2^z + …)

We also know, however, that the probability of returning 3 must be 1/3 (because rand3()

should be perfectly random) Can you find a series of reciprocal powers of 2 that sum to 1/3?

No, because 3 and 2 are relatively prime

We can similarly conclude that to solve this problem, we will need to accept a small (infini-

tesimally small) chance that this process will repeat forever That’s ok

So, how do we solve this?

In order to generate a random number between 1 and 7, we just need to uniformly generate

a larger range than we are looking for and then repeatedly sample until we get a number that

is good for us We will generate a base 5 number with two places with two calls to the RNG

public static int rand7() {

while (true) {

int num = 5 * (rand5() - 1) + (rand5() - 1);

if (num < 21) return (num % 7 + 1);

}

Write a function that adds two numbers You should not use + or any arithmetic op-

erators

SOLUTION

To investigate this problem, let’s start off by gaining a deeper understanding of how we add

numbers We’ll work in Base 10 so that it’s easier to see To add 759 + 674, I would usually add

digit[0] from each number, carry the one, add digit[1] from each number, carry the one, etc

You could take the same approach in binary: add each digit, and carry the one as necessary

Can we make this a little easier? Yes! Imagine I decided to split apart the “addition” and

“carry” steps That is, I do the following:

1 Add 759 + 674, but “forget” to carry I then get 323

2 Add 759 + 674 but only do the carrying, rather than the addition of each digit I then

get 1110.

Add the result of the first two operations (recursively, using the same process de-

scribed in step 1 and 2): 1110 + 323 = 1433

Now, how would we do this in binary?

1 If I add two binary numbers together but forget to carry, bit[i] will be 0 if bit[i] in a and

b are both 0 or both 1 This is an XOR

2 If I add two numbers together but only carry, I will have a 1 in bit[i] if bit[i-1] in a and b

are both 1’s This is an AND, shifted

3 Now, recurse until there’s nothing to carry

int add_no_arithm(int a, int b) {

if (b == 0) return a;

int sum = a ^ b; // add without carrying

int carry = (a & b) << 1; // carry, but don’t add

return add_no_arithm(sum, carry); // recurse

}

OBSERVATIONS AND SUGGESTIONS:

The Approach: There are a couple of suggestions for figuring out this problem:

1 Our first instinct in problems like these should be that we’re going to have to work

with bits Why? Because when you take away the + sign, what other choice do we

have? Plus, that’s how computers do it.

Write a method to shuffle a deck of cards It must be a perfect shuffle - in other words,

each 52! permutations of the deck has to be equally likely Assume that you are given

a random number generator which is perfect
SOLUTION

This is a very well known interview question, and a well known algorithm If you aren’t one

of the lucky few to have already know this algorithm, read on

Let’s start with a brute force approach: we could randomly selecting items and put them into

a new array We must make sure that we don’t pick the same item twice though by somehow

marking the node as dead

Array: [1] [2] [3] [4] [5]

Randomly select 4: [4] [?] [?] [?] [?]

Mark element as dead: [1] [2] [3] [X] [5]

The tricky part is, how do we mark [4] as dead such that we prevent that element from be-

ing picked again? One way to do it is to swap the now-dead [4] with the first element in the

array:

Array: [1] [2] [3] [4] [5]

Randomly select 4: [4] [?] [?] [?] [?]

Swap dead element: [X] [2] [3] [1] [5]

Array: [X] [2] [3] [1] [5]

Randomly select 3: [4] [3] [?] [?] [?]

Swap dead element: [X] [X] [2] [1] [5]

By doing it this way, it’s much easier for the algorithm to “know” that the first k elements are

dead than that the third, fourth, nineth, etc elements are dead We can also optimize this by

merging the shuffled array and the original array

Randomly select 4: [4] [2] [3] [1] [5]

Randomly select 3: [4] [3] [2] [1] [5]

This is an easy algorithm to implement iteratively:

public static void shuffleArray(int[] cards) {

int temp, index;

for (int i = 0; i < cards.length; i++){

index = (int) (Math.random() * (cards.length - i)) + i;

temp = cards[i];

cards[i] = cards[index];

cards[index] = temp;

}

1) The parameter weekday is true if it is a weekday, and parameter vacation is true if we are on vacation.

We sleep if it is a weekday or we are on vacation. Return true if we sleep in.

public boolean sleepIn(boolean weekday, boolean vacation) {

if (!weekday || vacation) {

return true;

} else {

return false;

}

// This can be shortened to: return(!weekday || vacation);

}

2) We have two monkeys, a and b, and the parameters aSmile and bSmile indicate if each is smiling. We are in trouble if they both are smiling or if neither of them is smiling. Return true if we are in trouble.

public boolean monkeyTrouble(boolean aSmile, boolean bSmile) {

  if (aSmile && bSmile) {

    return true;

  if (!aSmile && !bSmile) {

    return true;

  return false;

  // The above can be shortened to:

  //   return ((aSmile && bSmile) || (!aSmile && !bSmile));

  // Or this very short version (think about how this is the same as the above)

  //   return (aSmile == bSmile);

3) Given two int values, return their sum. Unless the two values are same, then return double their sum.

-       Store the sum in a local variable

- Double it if a and b are the same

public int sumDouble(int a, int b) {

  // Store the sum in a local variable

  int sum = a + b;

  // Double it if a and b are the same

  if (a == b) {

    sum = sum * 2;

  return sum;

4) Given an int n, return absolute difference between n and 21, except return double the absolute difference if n is over 21.

public int diff21(int n) {

if (n <= 21) {

return 21 - n;

} else {

return (n - 21) * 2;

}

5) We have a loud talking parrot. The hour parameter is the current hour time in the range 0…23. We are in trouble if parrot is talking and hour is before 7 or after 20. Return true if we are in trouble.

public boolean parrotTrouble(boolean talking, int hour) {

return (talking && (hour < 7 || hour > 20));

}

6) Given 2 ints, a and b, return true if one of them is 10 or if their sum is 10.

public boolean makes10(int a, int b) {

  return (a == 10 || b == 10 || a+b == 10);

7) Given an int n, return true if it is within 10 of 100 or 200. Note: Math.abs(num) computes the absolute value of the number.

public boolean nearHundred(int n) {

return ((Math.abs(100 - n) <= 10) || (Math.abs(200 - n) <= 10));

}

8) Given 2 int values, return true if one is negative and one is positive. Except if the parameter “negative” is true, then return true only if both are negative.

public boolean posNeg(int a, int b, boolean negative) {

if (negative) {

return (a < 0 && b < 0);

}

else {

return ((a < 0 && b > 0) || (a > 0 && b < 0));

}

9) Given a string, return a new string where “not” has been added to the front. However, if the string already begins with “not”, return the string unchanged.

public String notString(String str) {

if (str.length() >= 3 && str.substring(0, 3).equals("not")) {

return str;

}

return "not " + str;

}

10) Given a non-empty string and an int n, return a new string where the char at index n has been removed. The value of n will be a valid index of a char in the original string (i.e. n will be in the range 0..str.length()-1 inclusive).

public String missingChar(String str, int n) {

String front = str.substring(0, n);

// Start this substring at n+1 to omit the char.

// Can also be shortened to just str.substring(n+1)

// which goes through the end of the string.

String back = str.substring(n+1, str.length());

return front + back;

}

11) Given a string, return a new string where the first and last chars have been exchanged.

public String frontBack(String str) {

if (str.length() <= 1) return str;

String mid = str.substring(1, str.length()-1);

// last + mid + first

return str.charAt(str.length()-1) + mid + str.charAt(0);

}

Expected	This Run
frontBack("code") → "eodc"	"eodc"	OK
frontBack("a") → "a"	"a"	OK
frontBack("ab") → "ba"	"ba"	OK

12) Given a string, we'll say that the front is the first 3 chars of the string. If the string length is less than 3, the front is whatever is there. Return a new string which is 3 copies of the front.

public String front3(String str) {

int frontEnd = 3;

if (str.length() < frontEnd) {

frontEnd = str.length();

}

String front = str.substring(0, frontEnd);

return front + front + front;

}

13) Given a string, take the last char and return a new string with the last char added at the front and back, so "cat" yields "tcatt". The original string will be length 1 or more.

public String backAround(String str) {

String back = str.substring(str.length()-1, str.length());

return back + str + back;

}

14) Given a string, take the first 2 chars and return the string with the 2 chars added at both the front and back, so "kitten" yields"kikittenki". If the string length is less than 2, use whatever chars are there.

- // First figure the number of chars to take

public String front22(String str) {

// First figure the number of chars to take

int take = 2;

if (take > str.length()) {

take = str.length();

}

String front = str.substring(0, take);

return front + str + front;// First figure the number of chars to take

}

15) Given a string, return true if the string starts with "hi" and false otherwise.

- First test if the string is not at least length 2 (so the substring() below does not go past the end

- Pull out the string of the first two chars

- Test if it is equal to "hi"

public boolean startHi(String str) {

// First test if the string is not at least length 2

// (so the substring() below does not go past the end).

if (str.length() < 2) return false;

// Pull out the string of the first two chars

String firstTwo = str.substring(0, 2);

// Test if it is equal to "hi"

if (firstTwo.equals("hi")) {

return true;

} else {

return false;

}

16) Given two temperatures, return true if one is less than 0 and the other is greater than 100.

public boolean icyHot(int temp1, int temp2) {

if ((temp1 < 0 && temp2 > 100) || (temp1 > 100 && temp2 < 0)) {

return true;

} else {

return false;

}

17) Given 2 int values, return true if either of them is in the range 10..20 inclusive.

public boolean in1020(int a, int b) {

return ((a >= 10 && a <= 20) || (b >= 10 && b <= 20));

}

18) We'll say that a number is "teen" if it is in the range 13..19 inclusive. Given 3 int values, return true if 1 or more of them are teen.

public boolean hasTeen(int a, int b, int c) {

// Here it is written as one big expression,

// vs. a series of if-statements.

return (a>=13 && a<=19) ||

(b>=13 && b<=19) ||

(c>=13 && c<=19);

}

19) We'll say that a number is "teen" if it is in the range 13..19 inclusive. Given 2 int values, return true if one or the other is teen, but not both.

public boolean loneTeen(int a, int b) {

boolean aTeen = (a>=13 && a<=19);

boolean bTeen = (b>=13 && b<=19);

return (aTeen && !bTeen) || (!aTeen && bTeen);

}

20) Given a string, if the string "del" appears starting at index 1, return a string where that "del" has been deleted. Otherwise, return the string unchanged.

- First char + rest of string starting at 4

- Otherwise return the original string

public String delDel(String str) {

  if (str.length()>=4 && str.substring(1, 4).equals("del")) {

    // First char + rest of string starting at 4

    return str.substring(0, 1) + str.substring(4);

  // Otherwise return the original string.

  return str;

Expected	This Run
delDel("adelbc") → "abc"	"abc"	OK
delDel("adelHello") → "aHello"	"aHello"	OK
delDel("adedbc") → "adedbc"	"adedbc"	OK
delDel("abcdel") → "abcdel"	"abcdel"	OK
delDel("add") → "add"	"add"	OK
delDel("ad") → "ad"	"ad"	OK
delDel("a") → "a"	"a"	OK
delDel("") → ""	""	OK
delDel("del") → "del"	"del"	OK
delDel("adel") → "a"	"a"	OK
delDel("aadelbb") → "aadelbb"	"aadelbb"	OK

21) Return true if the given string begins with "mix", except the 'm' can be anything, so "pix", "9ix" .. all count.

- Check if string is too small.

- Pull out the length 2 string for the ix part (i.e. substring starting at index 1 and stopping just before 3).

public boolean mixStart(String str) {

// Check if string is too small

// (so substring() below does not go off the end)

if (str.length() < 3) return false;

// Pull out length 2 string for the "ix" part

// (i.e. substring starting at index 1 and stopping just before 3).

String two = str.substring(1, 3);

if (two.equals("ix")) {

return true;

} else {

return false;

}

// This last part can be shortened to just:

// return(two.equals("ix"));

}

Expected	This Run
mixStart("mix snacks") → true	True	OK
mixStart("pix snacks") → true	True	OK
mixStart("piz snacks") → false	False	OK
mixStart("nix") → true	True	OK
mixStart("ni") → false	False	OK
mixStart("n") → false	False	OK
mixStart("") → false	False	OK

22) Given a string, return a string made of the first 2 chars (if present), however include first char only if it is 'o' and include the second only if it is 'z', so "ozymandias" yields "oz".

public String startOz(String str) {

String result = "";

if (str.length() >= 1 && str.charAt(0)=='o') {

result = result + str.charAt(0);

}

if (str.length() >= 2 && str.charAt(1)=='z') {

result = result + str.charAt(1);

}

return result;

}

Expected	This Run
startOz("ozymandias") → "oz"	"oz"	OK
startOz("bzoo") → "z"	"z"	OK
startOz("oxx") → "o"	"o"	OK
startOz("oz") → "oz"	"oz"	OK
startOz("ounce") → "o"	"o"	OK
startOz("o") → "o"	"o"	OK
startOz("abc") → ""	""	OK
startOz("") → ""	""	OK
startOz("zoo") → ""	""	OK
startOz("aztec") → "z"	"z"	OK
startOz("zzzz") → "z"	"z"	OK
startOz("oznic") → "oz"	"oz"	OK

24) Given three int values, A B C, return the largest.

- First check between a and b

- Now check between max and c

public int intMax(int a, int b, int c) {

int max;

// First check between a and b

if (a > b) {

max = a;

} else {

max = b;

}

// Now check between max and c

if (c > max) {

max = c;

}

return max;

}

Expected	This Run
intMax(1, 2, 3) → 3	3	OK
intMax(1, 3, 2) → 3	3	OK
intMax(3, 2, 1) → 3	3	OK
intMax(9, 3, 3) → 9	9	OK
intMax(3, 9, 3) → 9	9	OK
intMax(3, 3, 9) → 9	9	OK
intMax(8, 2, 3) → 8	8	OK
intMax(-3, -1, -2) → -1	-1	OK

25) Given 2 int values, return whichever value is nearest to the value 10, or return 0 in the event of a tie. Note that Math.abs(n) returns the absolute value of a number.

public int close10(int a, int b) {

int aDiff = Math.abs(a - 10);

int bDiff = Math.abs(b - 10);

if (aDiff < bDiff) return a;

else if (bDiff < aDiff) return b;

else return 0;

}

Expected	This Run
close10(8, 13) → 8	8	OK
close10(13, 8) → 8	8	OK
close10(13, 7) → 0	0	OK
close10(7, 13) → 0	0	OK
close10(5, 21) → 5	5	OK
close10(0, 20) → 0	0	OK
close10(10, 10) → 0	0	OK

26) Given 2 int values, return true if they are both in the range 30..40 inclusive, or they are both in the range 40..50 inclusive.

public boolean in3050(int a, int b) {

if (a >= 30 && a <= 40 && b >= 30 && b <= 40) {

return true;

}

if (a >= 40 && a <= 50 && b >= 40 && b <= 50) {

return true;

}

return false;

// This could be written as one very large expression,

// connecting the two main parts with ||

}


Expected	This Run
in3050(30, 31) → true	true	OK
in3050(30, 41) → false	false	OK
in3050(40, 50) → true	true	OK
in3050(40, 51) → false	false	OK
in3050(39, 50) → false	false	OK
in3050(50, 39) → false	false	OK
in3050(40, 39) → true	true	OK
in3050(49, 48) → true	true	OK
in3050(50, 40) → true	true	OK
in3050(50, 51) → false	false	OK
in3050(35, 36) → true	true	OK
in3050(35, 45) → false	false	OK

27) Given 2 positive int values, return the larger value that is in the range 10..20 inclusive, or return 0 if neither is in that range.

- First make it so the bigger value is in a

- Knowing a is bigger, just check a first
public int max1020(int a, int b) {

// First make it so the bigger value is in a

if (b > a) {

int temp = a;

a = b;

b = temp;

}

// Knowing a is bigger, just check a first

if (a >= 10 && a <= 20) return a;

if (b >= 10 && b <= 20) return b;

return 0;

}

Expected	This Run
max1020(11, 19) → 19	19	OK
max1020(19, 11) → 19	19	OK
max1020(11, 9) → 11	11	OK
max1020(9, 21) → 0	0	OK
max1020(10, 21) → 10	10	OK
max1020(21, 10) → 10	10	OK
max1020(9, 11) → 11	11	OK
max1020(23, 10) → 10	10	OK
max1020(20, 10) → 20	20	OK
max1020(7, 20) → 20	20	OK
max1020(17, 16) → 17	17	OK

28) Return true if the given string contains between 1 and 3 'e' chars.

public boolean stringE(String str) {

int count = 0;

for (int i=0; i<str.length(); i++) {

if (str.charAt(i) == 'e') count++;

// alternately: str.substring(i, i+1).equals("e")

}

return (count >= 1 && count <= 3);

}

Expected	This Run
stringE("Hello") → true	true	OK
stringE("Heelle") → true	true	OK
stringE("Heelele") → false	false	OK
stringE("Hll") → false	false	OK
stringE("e") → true	true	OK
stringE("") → false	false	OK

29) Given two non-negative int values, return true if they have the same last digit, such as with 27 and 57. Note that the % "mod" operator computes remainders, so 17 % 10 is 7.

public boolean lastDigit(int a, int b) {

  return(a % 10 == b % 10);

Expected	This Run
lastDigit(7, 17) → true	true	OK
lastDigit(6, 17) → false	false	OK
lastDigit(3, 113) → true	true	OK
lastDigit(114, 113) → false	false	OK
lastDigit(114, 4) → true	true	OK
lastDigit(10, 0) → true	true	OK
lastDigit(11, 0) → false	false	OK

30) Given a string, return a new string where the last 3 chars are now in upper case. If the string has less than 3 chars, uppercase whatever is there. Note that str.toUpperCase() returns the uppercase version of a string.

public String endUp(String str) {

  if (str.length() <= 3) return str.toUpperCase();

  int cut = str.length() - 3;

  String front = str.substring(0, cut);

  String back  = str.substring(cut);  // this takes from cut to the end

  return front + back.toUpperCase();

Expected	This Run
endUp("Hello") → "HeLLO"	"HeLLO"	OK
endUp("hi there") → "hi thERE"	"hi thERE"	OK
endUp("hi") → "HI"	"HI"	OK
endUp("woo hoo") → "woo HOO"	"woo HOO"	OK
endUp("xyz12") → "xyZ12"	"xyZ12"	OK
endUp("x") → "X"	"X"	OK
endUp("") → ""	""	OK

31) Given a non-empty string and an int N, return the string made starting with char 0, and then every Nth char of the string. So if N is 3, use char 0, 3, 6, ... and so on. N is 1 or more.

public String everyNth(String str, int n) {

  String result = "";

  // Look at every nth char

  for (int i=0; i<str.length(); i = i + n) {

    result = result + str.charAt(i);

  return result;

Expected	This Run
everyNth("Miracle", 2) → "Mrce"	"Mrce"	OK
everyNth("abcdefg", 2) → "aceg"	"aceg"	OK
everyNth("abcdefg", 3) → "adg"	"adg"	OK
everyNth("Chocolate", 3) → "Cca"	"Cca"	OK
everyNth("Chocolates", 3) → "Ccas"	"Ccas"	OK
everyNth("Chocolates", 4) → "Coe"	"Coe"	OK
everyNth("Chocolates", 100) → "C"	"C"	OK

32) Given a string and a non-negative int n, return a larger string that is n copies of the original string.

public String stringTimes(String str, int n) {

  String result = "";

  for (int i=0; i<n; i++) {

    result = result + str;  // could use += here

  return result;

Expected	This Run
stringTimes("Hi", 2) → "HiHi"	"HiHi"	OK
stringTimes("Hi", 3) → "HiHiHi"	"HiHiHi"	OK
stringTimes("Hi", 1) → "Hi"	"Hi"	OK
stringTimes("Hi", 0) → ""	""	OK
stringTimes("Hi", 5) → "HiHiHiHiHi"	"HiHiHiHiHi"	OK
stringTimes("Oh Boy!", 2) → "Oh Boy!Oh Boy!"	"Oh Boy!Oh Boy!"	OK
stringTimes("x", 4) → "xxxx"	"xxxx"	OK
stringTimes("", 4) → ""	""	OK
stringTimes("code", 2) → "codecode"	"codecode"	OK
stringTimes("code", 3) → "codecodecode"	"codecodecode"	OK

33) Given a string and a non-negative int n, we'll say that the front of the string is the first 3 chars, or whatever is there if the string is less than length 3. Return n copies of the front;

public String frontTimes(String str, int n) {

   int frontLen = 3;

  if (frontLen > str.length()) {

    frontLen = str.length();

  String front = str.substring(0, frontLen);

  String result = "";

  for (int i=0; i<n; i++) {

    result = result + front;

  return result;

Expected	This Run
frontTimes("Chocolate", 2) → "ChoCho"	"ChoCho"	OK
frontTimes("Chocolate", 3) → "ChoChoCho"	"ChoChoCho"	OK
frontTimes("Abc", 3) → "AbcAbcAbc"	"AbcAbcAbc"	OK
frontTimes("Ab", 4) → "AbAbAbAb"	"AbAbAbAb"	OK
frontTimes("A", 4) → "AAAA"	"AAAA"	OK
frontTimes("", 4) → ""	""	OK
frontTimes("Abc", 0) → ""	""	OK

34) Given a string, return a new string made of every other char starting with the first, so "Hello" yields "Hlo".

public String stringBits(String str) {

  String result = "";

  // Note: the loop increments i by 2

  for (int i=0; i<str.length(); i+=2) {

    result = result + str.substring(i, i+1);

    // Alternately could use str.charAt(i)

  return result;

Expected	This Run
stringBits("Hello") → "Hlo"	"Hlo"	OK
stringBits("Hi") → "H"	"H"	OK
stringBits("Heeololeo") → "Hello"	"Hello"	OK
stringBits("HiHiHi") → "HHH"	"HHH"	OK
stringBits("") → ""	""	OK
stringBits("Greetings") → "Getns"	"Getns"	OK
stringBits("Chocoate") → "Coot"	"Coot"	OK
stringBits("pi") → "p"	"p"	OK
stringBits("Hello Kitten") → "HloKte"	"HloKte"	OK
stringBits("hxaxpxpxy") → "happy"	"happy"	OK

35) Given a non-empty string like "Code" return a string like "CCoCodCode".

public String stringSplosion(String str) {

  String result = "";

  // On each iteration, add the substring of the chars 0..i

  for (int i=0; i<str.length(); i++) {

    result = result + str.substring(0, i+1);

  return result;

Expected	This Run
stringSplosion("Code") → "CCoCodCode"	"CCoCodCode"	OK
stringSplosion("abc") → "aababc"	"aababc"	OK
stringSplosion("ab") → "aab"	"aab"	OK
stringSplosion("x") → "x"	"x"	OK
stringSplosion("fade") → "ffafadfade"	"ffafadfade"	OK
stringSplosion("There") → "TThTheTherThere"	"TThTheTherThere"	OK
stringSplosion("Kitten") → "KKiKitKittKitteKitten"	"KKiKitKittKitteKitten"	OK
stringSplosion("Bye") → "BByBye"	"BByBye"	OK
stringSplosion("Good") → "GGoGooGood"	"GGoGooGood"	OK
stringSplosion("Bad") → "BBaBad"	"BBaBad"	OK

36) Given a string, return the count of the number of times that a substring length 2 appears in the string and also as the last 2 chars of the string, so "hixxxhi" yields 1 (we won't count the end substring).

public int last2(String str) {

   // Screen out too-short string case.

  if (str.length() < 2) return 0;

  String end = str.substring(str.length()-2);

  // Note: substring() with 1 value goes through the end of the string

  int count = 0;

  // Check each substring length 2 starting at i

  for (int i=0; i<str.length()-2; i++) {

    String sub = str.substring(i, i+2);

    if (sub.equals(end)) {  // Use .equals() with strings

      count++;

  return count;

Expected	This Run
last2("hixxhi") → 1	1	OK
last2("xaxxaxaxx") → 1	1	OK
last2("axxxaaxx") → 2	2	OK
last2("xxaxxaxxaxx") → 3	3	OK
last2("xaxaxaxx") → 0	0	OK
last2("xxxx") → 2	2	OK
last2("13121312") → 1	1	OK
last2("11212") → 1	1	OK
last2("13121311") → 0	0	OK
last2("1717171") → 2	2	OK
last2("hi") → 0	0	OK
last2("h") → 0	0	OK
last2("") → 0	0	OK

37) Given an array of ints, return the number of 9's in the array.

public int arrayCount9(int[] nums) {

  int count = 0;

  for (int i=0; i<nums.length; i++) {

    if (nums[i] == 9) {

      count++;

  return count;

Expected	This Run
arrayCount9({1, 2, 9}) → 1	1	OK
arrayCount9({1, 9, 9}) → 2	2	OK
arrayCount9({1, 9, 9, 3, 9}) → 3	3	OK
arrayCount9({1, 2, 3}) → 0	0	OK
arrayCount9({}) → 0	0	OK
arrayCount9({4, 2, 4, 3, 1}) → 0	0	OK
arrayCount9({9, 2, 4, 3, 1}) → 1	1	OK

38) Given an array of ints, return true if one of the first 4 elements in the array is a 9. The array length may be less than 4.

public boolean arrayFront9(int[] nums) {

  // First figure the end for the loop

  int end = nums.length;

  if (end > 4) end = 4;

  for (int i=0; i<end; i++) {

    if (nums[i] == 9) return true;

  return false;

Expected	This Run
arrayFront9({1, 2, 9, 3, 4}) → true	true	OK
arrayFront9({1, 2, 3, 4, 9}) → false	false	OK
arrayFront9({1, 2, 3, 4, 5}) → false	false	OK
arrayFront9({9, 2, 3}) → true	true	OK
arrayFront9({1, 9, 9}) → true	true	OK
arrayFront9({1, 2, 3}) → false	false	OK
arrayFront9({1, 9}) → true	true	OK
arrayFront9({5, 5}) → false	false	OK
arrayFront9({2}) → false	false	OK
arrayFront9({9}) → true	true	OK
arrayFront9({}) → false	false	OK
arrayFront9({3, 9, 2, 3, 3}) → true	true	OK

39) Given an array of ints, return true if .. 1, 2, 3, .. appears in the array somewhere.

public boolean array123(int[] nums) {

   // Note: iterate < length-2, so can use i+1 and i+2 in the loop

  for (int i=0; i < (nums.length-2); i++) {

    if (nums[i]==1 && nums[i+1]==2 && nums[i+2]==3) return true;

  return false;

Expected	This Run
array123({1, 1, 2, 3, 1}) → true	true	OK
array123({1, 1, 2, 4, 1}) → false	false	OK
array123({1, 1, 2, 1, 2, 3}) → true	true	OK
array123({1, 1, 2, 1, 2, 1}) → false	false	OK
array123({1, 2, 3, 1, 2, 3}) → true	true	OK
array123({1, 2, 3}) → true	true	OK
array123({1, 1, 1}) → false	false	OK
array123({1, 2}) → false	false	OK
array123({1}) → false	false	OK
array123({}) → false	false	OK

40) Given 2 strings, a and b, return the number of the positions where they contain the same length 2 substring. So "xxcaazz" and "xxbaaz" yields 3, since the "xx", "aa", and "az" substrings appear in the same place in both strings.

public int stringMatch(String a, String b) {

  // Figure which string is shorter.

  int len = Math.min(a.length(), b.length());

  int count = 0;

  // Look at both substrings starting at i

  for (int i=0; i<len-1; i++) {

    String aSub = a.substring(i, i+2);

    String bSub = b.substring(i, i+2);

    if (aSub.equals(bSub)) {  // Use .equals() with strings

      count++;

  return count;

Expected	This Run
stringMatch("xxcaazz", "xxbaaz") → 3	3	OK
stringMatch("abc", "abc") → 2	2	OK
stringMatch("abc", "axc") → 0	0	OK
stringMatch("hello", "he") → 1	1	OK
stringMatch("he", "hello") → 1	1	OK
stringMatch("h", "hello") → 0	0	OK
stringMatch("", "hello") → 0	0	OK
stringMatch("aabbccdd", "abbbxxd") → 1	1	OK
stringMatch("aaxxaaxx", "iaxxai") → 3	3	OK
stringMatch("iaxxai", "aaxxaaxx") → 3	3	OK

41) Given a string, return a version where all the "x" have been removed. Except an "x" at the very start or end should not be removed.

public String stringX(String str) {

  String result = "";

  for (int i=0; i<str.length(); i++) {

    // Only append the char if it is not the "x" case

    if (!(i > 0 && i < (str.length()-1) && str.substring(i, i+1).equals("x"))) {

      result = result + str.substring(i, i+1); // Could use str.charAt(i) here

  return result;

Expected	This Run
stringX("xxHxix") → "xHix"	"xHix"	OK
stringX("abxxxcd") → "abcd"	"abcd"	OK
stringX("xabxxxcdx") → "xabcdx"	"xabcdx"	OK
stringX("xKittenx") → "xKittenx"	"xKittenx"	OK
stringX("Hello") → "Hello"	"Hello"	OK
stringX("xx") → "xx"	"xx"	OK
stringX("x") → "x"	"x"	OK
stringX("") → ""	""	OK

42) Given a string, return a string made of the chars at indexes 0,1, 4,5, 8,9 ... so "kittens" yields "kien".

public String altPairs(String str) {

  String result = "";

  // Run i by 4 to hit 0, 4, 8, ...

  for (int i=0; i<str.length(); i += 4) {

    // Append the chars between i and i+2

    int end = i + 2;

    if (end > str.length()) {

      end = str.length();

    result = result + str.substring(i, end);

  return result;

Expected	This Run
altPairs("kitten") → "kien"	"kien"	OK
altPairs("Chocolate") → "Chole"	"Chole"	OK
altPairs("CodingHorror") → "Congrr"	"Congrr"	OK
altPairs("yak") → "ya"	"ya"	OK
altPairs("ya") → "ya"	"ya"	OK
altPairs("y") → "y"	"y"	OK
altPairs("") → ""	""	OK
altPairs("ThisThatTheOther") → "ThThThth"	"ThThThth"	OK

43) Suppose the string "yak" is unlucky. Given a string, return a version where all the "yak" are removed, but the "a" can be any char. The "yak" strings will not overlap.

public String stringYak(String str) {

   String result = "";

  for (int i=0; i<str.length(); i++) {

    // Look for i starting a "yak" -- advance i in that case

    if (i+2<str.length() && str.charAt(i)=='y' && str.charAt(i+2)=='k') {

      i =  i + 2;

    } else { // Otherwise do the normal append

      result = result + str.charAt(i);

  return result;

Expected	This Run
stringYak("yakpak") → "pak"	"pak"	OK
stringYak("pakyak") → "pak"	"pak"	OK
stringYak("yak123ya") → "123ya"	"123ya"	OK
stringYak("yak") → ""	""	OK
stringYak("yakxxxyak") → "xxx"	"xxx"	OK
stringYak("HiyakHi") → "HiHi"	"HiHi"	OK
stringYak("xxxyakyyyakzzz") → "xxxyyzzz"	"xxxyyzzz"	OK

44) Given an array of ints, return the number of times that two 6's are next to each other in the array. Also count instances where the second "6" is actually a 7.

public int array667(int[] nums) {

  int count = 0;

  // Note: iterate to length-1, so can use i+1 in the loop

  for (int i=0; i < (nums.length-1); i++) {

    if (nums[i] == 6) {

      if (nums[i+1] == 6 || nums[i+1] == 7) {

        count++;

  return count;

Expected	This Run
array667({6, 6, 2}) → 1	1	OK
array667({6, 6, 2, 6}) → 1	1	OK
array667({6, 7, 2, 6}) → 1	1	OK
array667({6, 6, 2, 6, 7}) → 2	2	OK
array667({1, 6, 3}) → 0	0	OK
array667({6, 1}) → 0	0	OK
array667({}) → 0	0	OK
array667({3, 6, 7, 6}) → 1	1	OK
array667({3, 6, 6, 7}) → 2	2	OK
array667({6, 3, 6, 6}) → 1	1	OK
array667({6, 7, 6, 6}) → 2	2	OK
array667({1, 2, 3, 5, 6}) → 0	0	OK
array667({1, 2, 3, 6, 6}) → 1	1	OK

45) Given an array of ints, we'll say that a triple is a value appearing 3 times in a row in the array. Return true if the array does not contain any triples.

public boolean noTriples(int[] nums) {

  // Iterate < length-2, so can use i+1 and i+2 in the loop.

  // Return false immediately if every seeing a triple.

  for (int i=0; i < (nums.length-2); i++) {

    int first = nums[i];

    if (nums[i+1]==first && nums[i+2]==first) return false;

  // If we get here ... no triples.

  return true;

Expected	This Run
noTriples({1, 1, 2, 2, 1}) → true	true	OK
noTriples({1, 1, 2, 2, 2, 1}) → false	false	OK
noTriples({1, 1, 1, 2, 2, 2, 1}) → false	false	OK
noTriples({1, 1, 2, 2, 1, 2, 1}) → true	true	OK
noTriples({1, 2, 1}) → true	true	OK
noTriples({1, 1, 1}) → false	false	OK
noTriples({1, 1}) → true	true	OK
noTriples({1}) → true	true	OK
noTriples({}) → true	true	OK

46) Given an array of ints, return true if it contains a 2, 7, 1 pattern -- a value, followed by the value plus 5, followed by the value minus 1. Additionally the 271 counts even if the "1" differs by 2 or less from the correct value.

public boolean has271(int[] nums) {

  // Iterate < length-2, so can use i+1 and i+2 in the loop.

  // Return true immediately when seeing 271.

  for (int i=0; i < (nums.length-2); i++) {

    int val = nums[i];

    if (nums[i+1] == (val + 5) &&

      Math.abs(nums[i+2] - (val-1)) <= 2)  return true;

  // If we get here ... none found.

  return false;

Expected	This Run
has271({1, 2, 7, 1}) → true	true	OK
has271({1, 2, 8, 1}) → false	false	OK
has271({2, 7, 1}) → true	true	OK
has271({3, 8, 2}) → true	true	OK
has271({2, 7, 3}) → true	true	OK
has271({2, 7, 4}) → false	false	OK
has271({2, 7, -1}) → true	true	OK
has271({2, 7, -2}) → false	false	OK
has271({4, 5, 3, 8, 0}) → true	true	OK
has271({2, 7, 5, 10, 4}) → true	true	OK
has271({2, 7, -2, 4, 9, 3}) → true	true	OK
has271({2, 7, 5, 10, 1}) → false	false	OK
has271({2, 7, -2, 4, 10, 2}) → false	false	OK

Question:

Senior member of technical staff:

How do you reverse print a string? What if it does not exist?

static String reverseMe(String s) {

   StringBuilder sb = new StringBuilder();

   for(int i = s.length() - 1; i >= 0; --i)

     sb.append(s.charAt(i));

   return sb.toString();

 }

Member of technical staff intern at Vmware

Simple algo for intersection of two arrays

For example, if the input arrays are:
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Intersection as {3, 5}.

Algorithm:
For Intersection of two arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

a1 = [1,3,4,5,7]

a2 = [2,3,5,6]

i,j = 0,0

#Get length of the larger array as the count

count = (max(len(a1), len(a2)))

for x in range(0,count):

        if (a1[i]  a2[j]):

                j = j+1

        elif (a1[i] == a2[j]):

                print a1[i]

                i = i+1

                j = j+1

Member of technical staff:

String manipulations

Scalability: How does Java Affects both Performance and Scalability?

- Java does not scale any better or worse than any other general purpose language.

- Javas culture encourages practices that scale only to medium size system as it encourages techniques that do not scale well:

- 1) Favors multi threading

- 2) Shared state

- 3) Vertical scaling

- 4) Large monolithic components

- 5) Multiple tiers, lots of layers

- Java is less scalable as

- During garbage collection all threads are blocked and the garbage collection time can expand to minutes. These huge latencies effectively limit memory which limits scalability.

- Real time Java APIs extensions were developed as a way to addressing garbage collection problems.

Scalability testing;

Performance testing focused on ensuring the application under test gracefully handles increase in work load.

Tools: LoadRunner, Winrunner, Astra, Rational Robot etc.

It is performed as series of load tests with different server hardware or software configurations while keeping other test environment characteristics unchanged.

Purpose:

Scalability is closely related with performance as its purpose is to get higher performance.

It is property of a system, network or process which indicates its ability to either handle growing amounts of work in graceful manner.

Vertical Scaling:

To scale vertically or scale up means to add resources to single node in a system, typically involving addition of CPUs or memory to single computer.

Such vertical scaling of existing systems also enables them to leverage virtualization technology more effectively, as it provides more resources for hosted set of OS and application modules to share.

Horizontal Scaling:

To scale horizontally or scale out means to add more nodes to a system, such as adding new computer to distributed software application.

How to scale Java applications vertically?

Java technology based applications embrace threading in fundamental way. Not only Java language facilitates multithreaded applications, but the JVM is multithreaded process that provides scheduling and memory management for Java applications. Java applications that can benefit directly from multi CPU resources include applications servers such as BEA weblogic, IBM Websphere or open source glassfish and tomcat application server.

Hot lock is key enemy for scalability

- Coordination between threads is achieved using synchronized keyword.

- Synchronized block In Java is generally more expensive that critical section facilities offered by many platforms.

- Synchronized keyword forces the scheduler to serialize operations on the synchronized block.

- If many threads compete for the contended synchronizations, and only one thread is executing synchronized block, then any other threads waiting to enter that block are stalled.

- If no other threads are available for execution, then processors may sit idle. In such situations, more CPUs can help little with performance.

- Hotlock may involve multiple thread switches and system calls.

- When multiple threads contend for the same monitor, JVM has to maintain queue of threads waiting for that monitor which means more time spent in JVM or OS code and less time spent in program code.

- To avoid hot lock problem:

- 1) Make synchronized blocks as short as possible.

- 2) Reducing lock granularity: When you are using synchronized marker, you have two choices on its granularity method locks or block locks. If you put synchronized on method, you are locking on this object implicitly.

- 3) Avoid lock on static methods: worst solution is to put the synchronized keywords on the static methods, which means it will lock on all instances of this class.

- 4) Race condition can also cause the scalability problems: Too many synchronized keywords will cause scalability problems. But in some special cases, lack of synchronized can also cause system fail to scale vertically. The lack of synchronized can cause race conditions, allowing more than two threads to modify shared resource at the same time and may corrupt some shared data.

- Use concurrentHashMap instead of hashmap while building a scalable system.

Multithreading

- Java provides built in support for multithreaded programming.

- A multithreaded program contains two or more parts that can run concurrently.

- Each part of such a program is called thread and each thread defines separate path of execution.

- Multithreading is specialized form of multitasking. Multitasking threads need less over head than multitasking processes.

- Process contains one or more threads.

- Thread cannot exists on its own, it must be part of the process.

- Multithreading enables you to write very efficient programs that make maximum use of the CPU, because idle time can be kept to minimum.

- Thread stages:

- New: A new thread begins its life cycle in new state. It remains in this state until program starts the thread.

- Runnable: Thread enters runnable state when start method is invoked.

- Running: Scheduler chooses thread from runnable pool.

- Waiting/blocked/Sleeping: Sometimes thread transitions to the waiting state while the thread waits for another thread to perform a task.

- Dead: It is considered dead when its run method completes.

- Yield: Makes running thread to runnable

- Join: Lets one thread join on to end of another thread.

- Thread created by implementing runnable:

-       // Create a new thread.

-       class NewThread implements Runnable {

-          Thread t;

-          NewThread() {

-             // Create a new, second thread

-             t = new Thread(this, "Demo Thread");

-             System.out.println("Child thread: " + t);

-             t.start(); // Start the thread

-          }

-          // This is the entry point for the second thread.

-          public void run() {

-             try {

-                for(int i = 5; i > 0; i--) {

-                   System.out.println("Child Thread: " + i);

-                   // Let the thread sleep for a while.

-                   Thread.sleep(500);

-                }

-            } catch (InterruptedException e) {

-                System.out.println("Child interrupted.");

-            }

-            System.out.println("Exiting child thread.");

-          }

-       }

-       class ThreadDemo {

-          public static void main(String args[]) {

-             new NewThread(); // create a new thread

-             try {

-                for(int i = 5; i > 0; i--) {

-                  System.out.println("Main Thread: " + i);

-                  Thread.sleep(1000);

-                }

-             } catch (InterruptedException e) {

-                System.out.println("Main thread interrupted.");

-             }

-             System.out.println("Main thread exiting.");

-          }

-       }

Thread created by extending thread:

// Create a second thread by extending Thread

class NewThread extends Thread {

   NewThread() {

      // Create a new, second thread

      super("Demo Thread");

      System.out.println("Child thread: " + this);

      start(); // Start the thread

   // This is the entry point for the second thread.

   public void run() {

      try {

         for(int i = 5; i > 0; i--) {

            System.out.println("Child Thread: " + i);

                          // Let the thread sleep for a while.

            Thread.sleep(500);

      } catch (InterruptedException e) {

         System.out.println("Child interrupted.");

      System.out.println("Exiting child thread.");

class ExtendThread {

   public static void main(String args[]) {

      new NewThread(); // create a new thread

      try {

         for(int i = 5; i > 0; i--) {

            System.out.println("Main Thread: " + i);

            Thread.sleep(1000);

      } catch (InterruptedException e) {

         System.out.println("Main thread interrupted.");

      System.out.println("Main thread exiting.");

This would produce following result:

Child thread: Thread[Demo Thread,5,main]

Main Thread: 5

Child Thread: 5

Child Thread: 4

Main Thread: 4

Child Thread: 3

Child Thread: 2

Main Thread: 3

Child Thread: 1

Exiting child thread.

Main Thread: 2

Main Thread: 1

Main thread exiting.

Thread methods:

- Public void start()

- Public void run()

- Public final void join(long millisec)

- Public static void yield()

- Public static void sleep(long millisec)

- Public static thread currentThread()

- Public static void dumpStack()

- Public final void setName(String name)

- Public final void setPriority(int priority)

- Public final void setDeamon(Boolean on)

- Public void interrupt()

Ex:

// File Name : DisplayMessage.java

// Create a thread to implement Runnable

public class DisplayMessage implements Runnable

   private String message;

   public DisplayMessage(String message)

      this.message = message;

   public void run()

      while(true)

         System.out.println(message);

// File Name : GuessANumber.java

// Create a thread to extentd Thread

public class GuessANumber extends Thread

   private int number;

   public GuessANumber(int number)

      this.number = number;

   public void run()

      int counter = 0;

      int guess = 0;

do

          guess = (int) (Math.random() * 100 + 1);

          System.out.println(this.getName()

                       + " guesses " + guess);

          counter++;

      }while(guess != number);

      System.out.println("** Correct! " + this.getName()

                       + " in " + counter + " guesses.**");

// File Name : ThreadClassDemo.java

public class ThreadClassDemo

   public static void main(String [] args)

      Runnable hello = new DisplayMessage("Hello");

      Thread thread1 = new Thread(hello);

      thread1.setDaemon(true);

      thread1.setName("hello");

      System.out.println("Starting hello thread...");

      thread1.start();

      Runnable bye = new DisplayMessage("Goodbye");

      Thread thread2 = new Thread(hello);

      thread2.setPriority(Thread.MIN_PRIORITY);

      thread2.setDaemon(true);

      System.out.println("Starting goodbye thread...");

      thread2.start();

      System.out.println("Starting thread3...");

      Thread thread3 = new GuessANumber(27);

      thread3.start();

try

         thread3.join();

      }catch(InterruptedException e)

         System.out.println("Thread interrupted.");

      System.out.println("Starting thread4...");

      Thread thread4 = new GuessANumber(75);

           thread4.start();

      System.out.println("main() is ending...");

This would produce following result. You can try this example again and again and you would get different result every time.

Starting hello thread...

Starting goodbye thread...

Hello

Thread-2 guesses 27

Hello

** Correct! Thread-2 in 102 guesses.**

Hello

Starting thread4...

Hello

..........remaining result produced.

Design patterns

What is a software design pattern?

A design pattern is a solution to a general software problem within a particular context.

· Context : A recurring set of situations where the pattern applies.

· Problem : A system of forces (goals and constraints) that occur repeatedly in this context.

· Solution : A description of communicating objects and classes (collaboration) that can be applied to resolve those forces.

Why is the study of patterns important?

- make the designs more adaptable to change

- reuse knowledge or experienced software designers.

- common vocabulary for communication and documentation

- framework for evolution and improvement of existing patterns.

- raise the level of abstraction when discussing and documenting software designs.

As initial software designs are implemented and deployed, programmers often discover improvements which make the designs more adaptable to change. Design patterns capture solutions that have evolved over time as developers strive for greater flexibility in their software, and they document the solutions in a way which facilitates their reuse in other, possibly unrelated systems. Design patterns allow us to reuse the knowledge of experienced software designers.

Moreover, the study of design patterns provides a common vocabulary for communication and documentation, and it provides a framework for evolution and improvement of existing patterns. As an analogy, consider that during a discussion among programmers, the words “stack” and “tree” can be used freely without explanation. Software developers understand fundamental data structures such as a “stack” because these data structures are well-documented in textbooks and are taught in computer science courses. The study of design patterns will have a similar (but more profound) effect by allowing designers to say “composite pattern” or “observer pattern” in a particular design context, without having to describe all classes, relationships, and collaborations which make up the pattern. Patterns raise the level of abstraction when discussing and documenting software designs.

How do I document a design pattern?

A pattern description must address the following major points:

· Pattern Name and Classification : A short, meaningful name for the pattern, usually only one or two words. Names provide a vocabulary for patterns, and they have implied semantics – choose names carefully. Following the GoF book, we can also group patterns into higher level classifications such as creational, structural, and behavioral patterns.

· Problem : A general description of the problem context and the goals and constraints that occur repeatedly in that context. A concrete motivational scenario can be used to help describe the problem. The problem description should provide guidance to assist others in recognizing situations where the pattern can be applied.

· Solution : The classes and/or objects that participate in the design pattern, their structure (e.g., in terms of a UML class diagram), their responsibilities, and their collaborations. The solution provides an abstract description that can be applied in many different situations. Sample Code in an object-oriented language can be used to illustrate a concrete realization of the pattern.

· Consequences : A discussion of the results and tradeoffs of applying the pattern. Variations and language-dependent alternatives should also be addressed.

· Known Uses : Examples of the pattern in real systems. Look for applications of the pattern in language libraries and frameworks, published system descriptions, text books, etc. Not every good solution represents a pattern. A general rule of thumb is that a candidate pattern (also called a “proto-pattern”) should be discovered in a minimum of three existing systems before it can rightfully be called a pattern

What is an example of a design pattern?

Following the lead of the “Gang of Four” (GoF), design pattern descriptions usually contain multiple sections including

· Intent

· Motivation

· Applicability

· Structure

· Participants

· Collaborations

· Consequences

· Implementation

· Sample Code

· Known Uses

· Related Patterns

A complete discussion of even a small pattern is beyond the scope of a simple FAQ entry, but it is possible to get the idea by examining an abbreviated discussion of one of the simplest and most easily understood patterns

Consider the Singleton pattern, whose intent reads as follows:

Intent: Ensure that a class has one instance, and provide a global point of access to it.

Almost every programmer has encountered this problem and formulated an approach for solving it in a general way – some solutions are better than others. The solution offered by the GoF would look something like the following when coded in Java.

public class Singleton {

private static Singleton instance = null;

public static Singleton getInstance() {

if (instance == null)

instance = new Singleton();

return instance;

}

protected Singleton() { ... }

// possibly another constructor form

public void someMethod() { ... }

//... other methods }

The programmer would access the single instance of this class by writing something similar to

1	Singleton.getInstance().someMethod()

or similar to

Singleton s = Singleton.getInstance();

s.method1(); ...

s.method2(); ...

Calendar is an abstract class. The getInstance() method tries to instantiate GregorianCalendar() i.e., parent instantiating a derived class. This looks Non-OO? Ex: Calendar a=Calendar.getInstance(); Can somebody explain why is it so?

The Calender class is an abstact class, true, however,the point you missed is that the getInstance() returns the ” Calendar using the default timezone and locale. ” , in your case, the GregorianCalender a class that IS a Calender (a Suzuki IS a car, a 747 IS a plane..the standard OO terminology. So what you get is a class that does some specialized work based on the default locale. Other methods

public static synchronized Calendar

          getInstance(TimeZone
  zone,Locale aLocale)

public static synchronized Calendar

          getInstance(TimeZone
  zone)

return Calenders for specific timezones and locales. The closest parallel is possibly the Factory Method design pattern.

What major patterns do the Java APIs utilize?

Design patterns are used and supported extensively throughout the Java APIs. Here are some examples: MVC Pattern, Factory method design pattern(getInstance() method in java.util.Calendar class), Singleton pattern (java.lang.system and java.sql.DriverManager), Protoype pattern(clone()), Command pattern(Action interface and abstract action class), Proxy pattern(RMI and IDL features), Composite pattern (Component and container class in java.awt), Bridge pattern(separation of components in java.awt(Button and list)

· The Model-View-Controller design pattern is used extensively throughout the Swing API.

· The getInstance() method in java.util.Calendar is an example of a simple form of the Factory Method design pattern.

· The classes java.lang.System and java.sql.DriverManager are examples of the Singleton pattern, although they are not implemented using the approach recommended in the GoF book but with static methods.

· The Prototype pattern is supported in Java through the clone() method defined in class Object and the use of java.lang.Cloneable interface to grant permission for cloning.

· The Java Swing classes support the Command pattern by providing an Action interface and an AbstractAction class.

The Java 1.1 event model is based on the observer pattern. In addition, the interface java.util.Observable and the class java.util.Observer provide support for this pattern.
The Adapter pattern is used extensively by the adapter classes in java.awt.event.
The Proxy pattern is used extensively in the implementation of Java’s Remote Method Invocation (RMI) and Interface Definition Language (IDL) features.
The structure of Component and Container classes in java.awt provide a good example of the Composite pattern.
The Bridge pattern can be found in the separation of the components in java.awt (e.g., Button and List), and their counterparts in java.awt.peer.

How can I make sure at most one instance of my class is ever created?

This is an instance where the Singleton design pattern would be used. You need to make the constructor private (so nobody can create an instance) and provide a static method to get the sole instance, where the first time the instance is retrieved it is created:

public class Mine {

private static Mine singleton; private Mine() { }

public static synchronized Mine getInstance() {

if (singleton == null) {

     singleton =
  new

Mine();

} return singleton;

}

// other stuff... }

When would I use the delegation pattern instead of inheritence to extend a class’s behavior?

Both delegation and inheritance are important concepts in object-oriented software design, but not everyone would label them as patterns. In particular, the seminal book on design patterns by the “Gang of Four” contains a discussion of inheritance and delegation, but the authors do not treat these topics as specific patterns. It is reasonable to think of them as design concepts which are more general than specific design patterns.

Inheritance is a relationship between two classes where one class, called a subclass in this context, inherits the attributes and operations of another class, called its superclass. Inheritance can be a powerful design/reuse technique, especially when it is used in the context of the Liskov Substitution Principle. (The article by Robert Martin athttp://www.objectmentor.com/publications/lsp.pdf provides an excellent explanation of the ideas behind Barbara Liskov’s original paper on using inheritance correctly.) The primary advantages of inheritance are

1. it is directly supported by object-oriented languages, and

2. it provides the context for polymorphism in strongly-typed object-oriented languages such as C++ and Java.

But since the inheritance relationship is defined at compile-time, a class can’t change its superclass dynamically during program execution. Moreover, modifications to a superclass automatically propagate to the subclass, providing a two-edged sword for software maintenance and reuse. In summary, inheritance creates a strong, static coupling between a superclass and its subclasses.

Delegation can be viewed as a relationship between objects where one object forwards certain method calls to another object, called its delegate. Delegation can also a powerful design/reuse technique. The primary advantage of delegation is run-time flexibility – the delegate can easily be changed at run-time. But unlike inheritance, delegation is not directly supported by most popular object-oriented languages, and it doesn’t facilitate dynamic polymorphism.

What is an analysis pattern?

An analysis pattern is a software pattern not related to a language or implementation problem, but to a business domain, such as accounting or health care. For example, in health care, the patient visit activity would be subject to a number of patterns.

What are the differences between analysis patterns and design patterns?

Analysis pattern are for domain architecture, design pattern are for implementation mechanism for some aspect of the domain architecture. In brief, analysis pattern are more high level and more (end-user) functional oriented.

What is the disadvantage of using the Singleton pattern? It is enticing to use this pattern for all the classes as it makes it easy to get the reference of the singleton object.

The intent of the Singleton pattern is to ensure a class has only one instance and to provide a global point of access to it. True, the second part about providing a global point of access is enticing, but the primary disadvantage of using the Singleton pattern for all classes is related to the first part of the intent; i.e., that it allows only one instance of the class. For most classes in an application, you will need to create multiple instances. What purpose would a Customer class serve if you could create only one Customer object?

How do you write a Thread-Safe Singleton?

I have written plenty of non-thread-safe Singletons but it wasn’t until recently when I tracked it down that I realized that thread-safety could be a big problem.

The problem is that in the typical Singleton implementation (at least the ones I’ve seen) there is the ability to create multiple versions of the single instance…I know, “But How?”.

Well, in the _{getInstance()} call the instance is checked for null, and then immediately constructed if it is null, and then the instance is returned.

The problem is that the thread (Ta) making the call could swap-out immediately after checking for a null. A subsequent thread (Tb) could then make a call to get the instance and construct an instance of the Singleton. When the original thread (Ta) is then swapped back in, it would construct and return a completely separate object. BAD KITTY!

The following code snippet shows an example of a thread-safe Singleton.

package com.jgk.patterns.singleton;

public class JGKSingleton {

/* Here is the instance of the Singleton */

private static JGKSingleton instance_;

/* Need the following object to synchronize */

/* a block */

private static Object syncObject_;

/* Prevent direct access to the constructor

private JGKSingleton() { super(); }

public static JGKSingleton getInstance() {

/* in a non-thread-safe version of a Singleton */

/* the following line could be executed, and the */

/* thread could be immediately swapped out */

if (instance_ == null) {

synchronized(syncObject_) {

if (instance_ == null) {

instance_ = new JGKSingleton();

}

return instance_;

}

What are Collaboration Patterns?

Collaboration Patterns are repeatable techniques used by teams of people to help them work together (collaborate). Ellen Gottesdiener of EBG Consulting has created these patterns in order to help facilitate good teamwork. These patterns really have nothing to do with object-oriented development or Java, besides the fact that they can help with requirements gathering or CRC design sessions.
In a nutshell, Collaboration Patterns are techniques to help make meetings useful.

Is it correct from a design point of view to make an object both an _Observer and _Observable at the same time?

Yes, and this can be the preferred pattern in some cases.

For example, suppose you were writing a supply chain management system for a retail chain. Each store object in your system generates item-sold events; when the chain generates enough of these for a particular product, a buyer object generates a purchase order for more of the product. However, the buyer object has no particular interest in individual item sold events. Instead, the buyer (Observer) registers to receive out-of-stock events from the warehouse (Observable); the warehouse, as Observer, registers with the individual stores (Observables) to receive item-sold events. Thus, the warehouse is both Observer and Observable. (Please note that this is a synthetic example, and probably not the way to organize a supply chain.)

Another reason to use one or more central Observer-Observable object in between ultimate Observers and Observables is to fully decouple the two. In some cases, Observer and Observable may exist on different machines, and may rely on the central Observer-Observable to hide this complication.

A good source for more details is the Publisher-Subscriber section of Buschmann et al., Pattern-Oriented Software Architecture: A System of Patterns.

Is there some kind of Design pattern which would make it possible to use the Same code base in EJB and non EJB context?

class PieceOfCode {

public

Object
  myMethod() {}

}

class EJBImpl ... {

PieceOfCode poc = new PieceOfCode();

public

Object
  myMethod() {

return poc.myMethod();

}

This should not be a violation of EJB specs, since EJBs can use simple java classes for their use. Think about Dependant Objects and so on.

What is session facade?

Session facade is one design pattern that is often used while developing enterprise applications.

It is implemented as a higher level component (i.e.: Session EJB), and it contains all the iteractions between low level components (i.e.: Entity EJB). It then provides a single interface for the functionality of an application or part of it, and it decouples lower level components simplifying the design.

Think of a bank situation, where you have someone that would like to transfer money from one account to another.

In this type of scenario, the client has to check that the user is authorized, get the status of the two accounts, check that there are enough money on the first one, and then call the transfer. The entire transfer has to be done in a single transaction otherwise is something goes south, the situation has to be restored.

As you can see, multiple server-side objects need to be accessed and possibly modified. Multiple fine-grained invocations of Entity (or even Session) Beans add the overhead of network calls, even multiple transaction. In other words, the risk is to have a solution that has a high network overhead, high coupling, poor reusability and mantainability.

The best solution is then to wrap all the calls inside a Session Bean, so the clients will have a single point to access (that is the session bean) that will take care of handling all the rest.

Obviously you need to be very careful when writing Session Facades, to avoid the abusing of it (often called “God-Bean”).

How can I implement the MVC design pattern using JSP?

The MVC (Model View Controller) design pattern is a pattern/architecture that can be used by GUI’s. It seperates the application’s data, user interface and control logic into three separate entities. This ensures the system will be more maintainable in the future as changes to one component will not have an affect on the others.

The MVC pattern also conforms with the JSP Model 2 architecture.

The MVC pattern can be easily implemented in web applications using JSTL core, JSP, Servlets and JavaBeans.

JSTL makes it easy for HTML designers to use dynamic data in their pages without having to learn in depth java. The tags are in a recognizable HTML like format meaning a smaller learning curve than taking on the JSP specification after taking on the Java specification.

JSTL also makes it easy for web developers who are developing all aspects of the application in helping you keep the content separate from the display by keeping your JSP clean from any Java code. Since JSTL and its EL (expression Language) are really only suited for accessing data, it forces you to use a MVC pattern so long as you keep all JSP and Java syntax/code out of the JSP pages.

A common scenario might look like this, a user sends a request to a server. The request is handled by a Servlet (the controller) which will initialize any JavaBeans (the model) required to fulfill the user’s request. The Servlet (the controller) will then forward the request, which contains the JavaBeans (the model), to a JSP (the view) page which contains only HTML and JSTL syntax. The JSTL will format the data into a human readable format before being sent back to the user. Thus completing the full MVC process.

JSTL also has a tag library for XML processing, this could be used in an MVC environment as you could replace the JavaBeans with an XML document to describe your data, so long as the XML is still constructed in a controller such as a Servlet before being passed to the JSP (the view).

Member of technical staff:

Write a function that takes an array of integers and outputs the array with all odd integers followed by even integers.

int[] input = {5, 12, 3, 21, 8, 7, 19, 102, 201};

List<Integer> evens = new ArrayList<Integer>();

List<Integer> odds = new ArrayList<Integer>();

for (int i : input) {

    if (i % 2 == 0) {

        evens.add(i);

    } else {

        odds.add(i);

    }

}

int[] array_sort = {5, 12, 3, 21, 8, 7, 19, 102, 201 };



List<Integer> odd = new ArrayList<Integer>();

List<Integer> even = new ArrayList<Integer>();

for (int i : array_sort) {

    if ((i & 1) == 1) {

        odd.add(i);

    } else {

        even.add(i);

    }

}

Collections.sort(odd);

Collections.sort(even);

System.out.println("Odd:" + odd);

System.out.println("Even:" + even);

Debugging question on reversing linked list. Code given and was asked to find error.

public void reverse()

{

   Node currentNode, nextNode, loopNode;

   if(first==null)

      return;



   currentNode=first;

   nextNode= first.next;

   loopNode=null;





   while(nextNode != null)

   {

        currentNode.next = loopNode;

        loopNode= currentNode;

        currentNode=nextNode;

        nextNode =nextNode.next;

   }



   first = currentNode;

   first.next = loopNode;



}

Given a series of strings, find the biggest common prefix.

public String greatestCommonPrefix(String a, String b) {

    int minLength = Math.min(a.length(), b.length());

    for (int i = 0; i < minLength; i++) {

        if (a.charAt(i) != b.charAt(i)) {

            return a.substring(0, i);

        }

    }

    return a.substring(0, minLength);

}

public class Test{

 public static void main(String[] args){

    String s1 = "Mary Had a Little Lamb";

    String s2 = "Mary Had a Big Lamb";

    int minStrLen = s1.length();

    if ( minStrLen > s2.length()){

        minStrLen = s2.length();

    }



    StringBuilder output = new StringBuilder();

    for(int i=0; i<minStrLen; i++){

        if ( s1.charAt(i) ==  s2.charAt(i)){

         output.append(s1.charAt(i));

        }else{

          break;

        }

    }       

    System.out.println(output.toString());

  }

}

Senior member of technical staff:

Merge 2 sorted single linked lists into the brand new list(no pointer copy allowed). The resulting list should have the data from both lists all correctly sorted.

1. Check to see if both lists NULL - return NULL in that case.
2. Check to see if list 1 is NULL - return list 2
3. Check to see if list 2 is NULL - return list 1
4. Both list non-empty:
     Pick lowest of first element of list 1 and 2 - put that into head element
     Initialize two pointers into the the 2 lists and a pointer into the head of the new list
     while there are elements left in either of the two lists
         append the lowest of the two elements to the new list using new pointer's next field

Linux

1) For displaying the list of the directories: ls

2) Changing the directory: cd

3) present working directory: pwd

4) Absolute path: /

5) changing directory to One level up: cd..

6) Previous working directory (cd - )

7) Listing directory: list

8) System Directories: 22

9) checking Free space for directories as well as Hard drive:

# df --> show info files system use space and mount

# df -h --> same as "df" but showing file in G.B

# df -H --> exact size********

# df -T =-> IT SHOWS DISK SPACE AND FILE TYPES

# du --> display info of files & total size

# du -sh --> display total size of directories

10) Creating directories : mkdir

11) Making touch files in a directory # touch file1 file2

12) Editing touch files: # cat > file1 # cat file1

13) Adding more lines in touch files: # cat >> file1

14) for seeing how much line, how much words & how much characters in file

# wc -l file

# wc -w file

# wc -c file

15) Use spelling dictionary

# look symbolic

16) moving file

# mv doc /root/doc

17) MOVING MULTIPLES FILES FROM ONE DIR TO ANOTHER DIR: # mv text1 text2 text3 text4 text5 /root

18) REMOVING (del) FILE/dir: # rm text1 # rmdir

19) Removing multiple files/dir: # rm * # rmdir *

20) Copying files and directory: # cp file /root/idris

21) Copying multiple files: # cp * /root/idris

22) Copying dir from one to other: cp -r jawed jabbar

cp -r MEANS COPY WITH PRESENTE TIME DATE

cp -p MEANS COPY WITH PRESERVE TIME DATE

# cp -p install.log /mnt

# cp -r install.log /home

23) MOUNTING CDROM/CDRECORDER/FLOPPY/USB_DISK

# mount /media/cdrecorder

# mount /media/floppy

# mount /media/USB_DISK

# mount /media/cdrom

24) Creating users

# useradd jawed

# useradd jabbar

# passwd jawed

25) Show all logged users:

# users

# who

# w

# adduser jabbar

26) Deleting users:

# userdel jawed

27) Creating groups with users:

# groupadd account

# useradd idris

# passwd idris

28) renaming group

# groupmod -n sequrity account

29) Deleting group

# groupdel sequrity

30) date and time

# date

# clock

# cal

31) History commands

# history |less

32) searching file or directory through locate

# locate urdu

# slocate urdu

33) aliases for making short cut commands

# alias c=clear

# alias mk=mkdir

34) viewing process

# ps -alx

35) Process monitoring

# kill 1766 (portmap)

# kill 0 1766 (portmap)

# top

Automating test cases consideration

- Scope: Pick areas very carefully that are to be automated

- Preparation timeframe:

- Return on investment

- Choose benefits to be gained

- Degree of change: best use of test automation is for regression testing

- Test integrity

- Test Independence

- Debugging or testing of actual test script themselves

- Record and playback

- Maintainence of scripts

1. What automating testing tools are you familiar with?

Win Runner , Load runner, QTP , Silk Performer, Test director, Rational robot, QA run.

{mosgoogle left}

2. How did you use automating testing tools in your job?

1. For regression testing

2. Criteria to decide the condition of a particular build

3. How do you plan test automation?

1. Prepare the automation Test plan

2. Identify the scenario

3. Record the scenario

4. Enhance the scripts by inserting check points and Conditional Loops

5. Incorporated Error Hnadler

6. Debug the script

7. Fix the issue

8. Rerun the script and report the result.

4. Can test automation improve test effectiveness?

Yes, Automating a test makes the test process:

1.Fast

2.Reliable

3.Repeatable

4.Programmable

5.Reusable

6.Comprehensive

5. What is data - driven automation?

Testing the functionality with more test cases becomes laborious as the functionality grows. For multiple sets of data (test cases), you can execute the test once in which you can figure out for which data it has failed and for which data, the test has passed. This feature is available in the WinRunner with the data driven test where the data can be taken from an excel sheet or notepad.

{mosgoogle left}

6. What are the main attributes of test automation?

software test automation attributes :

Maintainability - the effort needed to update the test automation suites for each new release

Reliability - the accuracy and repeatability of the test automation

Flexibility - the ease of working with all the different kinds of automation test ware

Efficiency - the total cost related to the effort needed for the automation

Portability - the ability of the automated test to run on different environments

Robustness - the effectiveness of automation on an unstable or rapidly changing system

Usability - the extent to which automation can be used by different types of users

7. Does automation replace manual testing?

There can be some functionality which cannot be tested in an automated tool so we may have to do it manually. therefore manual testing can never be repleaced. (We can write the scripts for negative testing also but it is hectic task).When we talk about real environment we do negative testing manually.

8. How will you choose a tool for test automation?

choosing of a tool deends on many things ...

1. Application to be tested

2. Test environment

3. Scope and limitation of the tool.

4. Feature of the tool.

5. Cost of the tool.

6. Whether the tool is compatible with your application which means tool should be able to interact with your appliaction

7. Ease of use

9. How you will evaluate the tool for test automation?

We need to concentrate on the features of the tools and how this could be benficial for our project. The additional new features and the enhancements of the features will also help.

10. What are main benefits of test automation?

FAST ,RELIABLE,COMPREHENSIVE,REUSABLE

11. What could go wrong with test automation?

1. The choice of automation tool for certain technologies

2. Wrong set of test automated

12. How you will describe testing activities?

Testing activities start from the elaboration phase. The various testing activities are preparing the test plan, Preparing test cases, Execute the test case, Log teh bug, validate the bug & take appropriate action for the bug, Automate the test cases.

13. What testing activities you may want to automate?

Automate all the high priority test cases which needs to be exceuted as a part of regression testing for each build cycle.

14. Describe common problems of test automation.

The commom problems are:

1. Maintenance of the old script when there is a feature change or enhancement

3. The change in technology of the application will affect the old scripts

15. What types of scripting techniques for test automation do you know?

5 types of scripting techniques:

Linear

Structured

Shared

Data Driven

Key Driven

16. What are principles of good testing scripts for automation?

1. Proper code guiding standards

2. Standard format for defining functions, exception handler etc

3. Comments for functions

4. Proper errorhandling mechanisms

5. The apprpriate synchronisation techniques

17. What tools are available for support of testing during software development life cycle?

Testing tools for regressiona and load/stress testing for regression testing like, QTP, load runner, rational robot, winrunner, silk, testcomplete, Astra are availalbe in the market. -For defect tracking BugZilla, Test Runner are availalbe.

18. Can the activities of test case design be automated?

As I know it, test case design is about formulating the steps to be carried out to verify something about the application under test. And this cannot be automated. IHowever, I agree that the process of putting the test results into the excel sheet.

19. What are the limitations of automating software testing?

Hard-to-create environments like ?out of memory?, ?invalid input/reply?, and ?corrupt registry entries? make applications behave poorly and existing automated tools can?t force these condition - they simply test your application in ?normal? environment.

20. What skills needed to be a good test automator?

1.Good Logic for programming.

2. Analytical sklls.

3.Pessimestic in Nature.

21. How to find that tools work well with your existing system?

1. Discuss with the support officials

2. Download the trial version of the tool and evaluate

3. Get suggestions from peopel who are working on the tool

22. Describe some problem that you had with automating testing tool.

1. The inabality of winrunner to identify the third party control like infragistics controls

2. The change of the location of the table object will cause object not found error.

3. The inability of the winrunner to execute the script against multiple langauges

23. What testing activities you may want to automate in a project?

Testing tools can be used for :

* Sanity tests(which is repeated on every build),

* stress/Load tests(U simulate a large no of users,which is manually impossibele) &

* Regression tests(which are done after every code change)

26. How to find that tools work well with your existing system?

To find this, select the suite of tests which are most important for your application. First run them with automated tool. Next subject the same tests to careful manual testing. If the results are coinciding you can say your testing tool has been performing.

27. How will you test the field that generates auto numbers of AUT when we click the button 'NEW" in the application?

We can create a textfile in a certain location, and update the auto generated value each time we run the test and compare the currently generated value with the previous one will be one solution.

28. How will you evaluate the fields in the application under test using automation tool?

We can use Verification points(rational Robot) to validate the fields .Ex.Using objectdata,objectdata properties VP we can validate fields.

29. Can we perform the test of single application at the same time using different tools on the same machine?

No. The Testing Tools will be in the ambiguity to determine which browser is opened by which tool.

30. Difference between Web application Testing and Client Server Testing. State the different types for Web application Testing and Client Server Testing types?

which winrunner 7.2 versioncompatiable with internet explorer, firefox,n.n

31. What is 'configuration management'?

Configuration management is a process to control and document any changes made during the life of a project. Revision control, Change Control, and Release Control are important aspects of Configuration Management.

32. How to test the Web applications?

The basic differnce in webtesting is here we have to test for URL's coverage and links coverage. Using WinRunner we can conduct webtesting. But we have to make sure that Webtest option is selected in "Add in Manager". Using WR we cannot test XML objects.

33. what are the problems encountered during the testing the application compatibility on different browsers and on different operating systems

Font issues,alignment issues

35. How testing is proceeded when SRS or any other docccument is not given?

If SRS is not there we can perfom Exploratory testing. In Exporatory testing the basic moduole is executed and depending on its results, the next plan is executed.

36. How do we test for severe memory leakages ?

By using Endurance Testing .

Endurance Testing means checking for memory leaks or other problems that may occur with prolonged execution.

37. what is the difference between quality assurance and testing?

Quality assurance involves entire software development process and testing involves operation of a system or application to evaluate the results under certain conditions. QA is oriented to prevention and Testing is oriented to detection.

38. why does software have bugs?

1. miscommunication

2. programming errors

3. time pressures.

4. changing requirements

5. software complexity

40. What is memory leaks and buffer overflows ?

Memory leaks means incomplete deallocation - are bugs that happen very often. Buffer overflow means data sent as input to the server that overflows the boundaries of the input area, thus causing the server to misbehave. Buffer overflows can be used.

what are the major differences between stress testing,load testing,Volume testing?

Stress testing means increasing the load ,and checking the performance at each level. Load testing means at a time giving more load by the expectation and checking the performance at that level. Volume testing means first we have to apply initial.

Tuesday, August 19, 2014

What is a software design pattern?

Why is the study of patterns important?

How do I document a design pattern?

What is an example of a design pattern?

Calendar is an abstract class. The getInstance() method tries to instantiate GregorianCalendar() i.e., parent instantiating a derived class. This looks Non-OO? Ex: Calendar a=Calendar.getInstance(); Can somebody explain why is it so?

What major patterns do the Java APIs utilize?

How can I make sure at most one instance of my class is ever created?

When would I use the delegation pattern instead of inheritence to extend a class’s behavior?

What is an analysis pattern?

What are the differences between analysis patterns and design patterns?

What is the disadvantage of using the Singleton pattern? It is enticing to use this pattern for all the classes as it makes it easy to get the reference of the singleton object.

How do you write a Thread-Safe Singleton?

What are Collaboration Patterns?

Is it correct from a design point of view to make an object both an Observer and Observable at the same time?

Is there some kind of Design pattern which would make it possible to use the Same code base in EJB and non EJB context?

What is session facade?

How can I implement the MVC design pattern using JSP?

Given a series of strings, find the biggest common prefix.

Is it correct from a design point of view to make an object both an _Observer and _Observable at the same time?