#SOURCE 1. geeksforgeeks - top-10-algorithms-in-interview-questions

http://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/

Graph

Breadth First Search (BFS)
Depth First Search (DFS)
Shortest Path from source to all vertices Dijkstra
Shortest Path from every vertex to every other vertex Floyd Warshall
To detect cycle in a Graph Union Find
Minimum Spanning tree Prim
Minimum Spanning tree Kruskal
Topological Sort
Boggle (Find all possible words in a board of characters)
Bridges in a Graph

Linked List

Insertion of a node in Linked List (On the basis of some constraints)
Delete a given node in Linked List (under given constraints)
Compare two strings represented as linked lists
Add Two Numbers Represented By Linked Lists
Merge A Linked List Into Another Linked List At Alternate Positions
Reverse A List In Groups Of Given Size
Union And Intersection Of 2 Linked Lists
Detect And Remove Loop In A Linked List
Merge Sort For Linked Lists
Select A Random Node from A Singly Linked List

Dynamic Programming

Longest Common Subsequence
Longest Increasing Subsequence
Edit Distance
Minimum Partition
Ways to Cover a Distance
Longest Path In Matrix
Subset Sum Problem
Optimal Strategy for a Game
0-1 Knapsack Problem
Boolean Parenthesization Problem

Sorting And Searching

Binary Search
Search an element in a sorted and rotated array
Bubble Sort
Insertion Sort
Merge Sort
Heap Sort (Binary Heap)
Quick Sort
Interpolation Search
Find Kth Smallest/Largest Element In Unsorted Array
Given a sorted array and a number x, find the pair in array whose sum is closest to x

Tree / Binary Search Tree

Find Minimum Depth of a Binary Tree
Maximum Path Sum in a Binary Tree
Check if a given array can represent Preorder Traversal of Binary Search Tree
Check whether a binary tree is a full binary tree or not
Bottom View Binary Tree
Print Nodes in Top View of Binary Tree
Remove nodes on root to leaf paths of length < K
Lowest Common Ancestor in a Binary Search Tree
Check if a binary tree is subtree of another binary tree
Reverse alternate levels of a perfect binary tree

Number Theory

Modular Exponentiation
Modular multiplicative inverse
Primality Test | Set 2 (Fermat Method)
Euler�s Totient Function
Sieve of Eratosthenes
Convex Hull
Basic and Extended Euclidean algorithms
Segmented Sieve
Chinese remainder theorem
Lucas Theorem

BIT Manipulation

Maximum Subarray XOR
Magic Number
Sum of bit differences among all pairs
Swap All Odds And Even Bits
Find the element that appears once
Binary representation of a given number
Count total set bits in all numbers from 1 to n
Rotate bits of a number
Count number of bits to be flipped to convert A to B
Find Next Sparse Number

String / Array

Reverse an array without affecting special characters
All Possible Palindromic Partitions
Count triplets with sum smaller than a given value
Convert array into Zig-Zag fashion
Generate all possible sorted arrays from alternate elements of two given sorted arrays
Pythagorean Triplet in an array
Length of the largest subarray with contiguous elements
Find the smallest positive integer value that cannot be represented as sum of any subset of a given array
Smallest subarray with sum greater than a given value
Stock Buy Sell to Maximize Profit

#SOURCE 2. programcreek - top-10-algorithms-for-coding-interview

http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

Classic problems: --Two Pointers--

Rotate Array, Reverse Words in a String
Evaluate Reverse Polish Notation (Stack)
Isomorphic Strings
Word Ladder (BFS), Word Ladder II (BFS)
Median of Two Sorted Arrays
Kth Largest Element in an Array
Wildcard Matching, Regular Expression Matching
Merge Intervals, Insert Interval
Two Sum, Two Sum II, Two Sum III, 3Sum, 4Sum
3Sum Closest
String to Integer
Merge Sorted Array
Valid Parentheses
Longest Valid Parentheses
Implement strStr()
Minimum Size Subarray Sum
Search Insert Position
Longest Consecutive Sequence
Valid Palindrome
ZigZag Conversion
Add Binary
Length of Last Word
Triangle
Contains Duplicate: I, II, III
Remove Duplicates from Sorted Array: I, II, Remove Element , Move Zeroes
Longest Substring Without Repeating Characters
Longest Substring that contains 2 unique characters [Google]
Substring with Concatenation of All Words
Minimum Window Substring
Find Minimum in Rotated Sorted Array: I, II
Search in Rotated Array:I, II
Min Stack
Majority Element: I, II
Bulls and Cows
Largest Rectangle in Histogram
Longest Common Prefix [Google]
Largest Number
Simplify Path
Compare Version Numbers
Gas Station
Pascal's Triangle: I, II
Container With Most Water
Candy [Google]
Trapping Rain Water
Count and Say
Search for a Range
Basic Calculator, Basic Calculator II
Group Anagrams
Shortest Palindrome
Rectangle Area
Summary Ranges
Increasing Triplet Subsequence
Get Target Using Number List And Arithmetic Operations
Reverse Vowels of a String
Flip Game, Flip Game II
Missing Number, Find the duplicate number, First Missing Positive
Valid Anagram, Group Shifted Strings
Top K Frequent Elements
Find Peak Element
Word Pattern, Word Pattern II
H-Index , H-Index II
Palindrome Pairs
One Edit Distance
Scramble String
First Bad Version
Integer to English Words
Text Justification
Remove Invalid Parentheses
Intersection of Two Arrays, Intersection of Two Arrays II
Sliding Window Maximum, Moving Average from Data Stream
Guess Number Higher or Lower
Matrix

Common methods to solve matrix related problem include DFS, BFS, dynamic programming, etc.

Classic Problems:

Set Matrix Zeroes
Spiral Matrix
Spiral Matrix II
Search a 2D Matrix
Search a 2D Matrix II
Rotate Image [Palantir]
Valid Sudoku
Minimum Path Sum (DP. [Google]
Unique Paths (DP. [Google]
Unique Paths II (DP)
Number of Islands (DFS/BFS), Number of Islands II (Disjoint Set), Number of Connected Components in an Undirected Graph
Surrounded Regions (BFS)
Maximal Rectangle
Maximal Square
Word Search (DFS)
Word Search II
Range Sum Query 2D � Immutable
Longest Increasing Path in a Matrix (DFS)
Shortest Distance from All Buildings
Game of Life
Paint House, Paint House II
Sudoku Solver (DFS)
Walls and Gates (DFS/BFS)
Tic-Tac-Toe
Best Meeting Point
Linked List

The implementation of a linked list is pretty simple in Java. Each node has a value and a link to next node.

class Node { int val; Node next;

Node(int x. {
	val = x;
	next = null;
}

} Two popular applications of linked list are stack and queue.

Stack

class Stack{ Node top;

public Node peek(){
	if(top != null){
		return top;
	}

	return null;
}

public Node pop(){
	if(top == null){
		return null;
	}else{
		Node temp = new Node(top.val);
		top = top.next;
		return temp;	
	}
}

public void push(Node n){
	if(n != null){
		n.next = top;
		top = n;
	}
}

} Queue

class Queue{ Node first, last;

public void enqueue(Node n){
	if(first == null){
		first = n;
		last = first;
	}else{
		last.next = n;
		last = n;
	}
}

public Node dequeue(){
	if(first == null){
		return null;
	}else{
		Node temp = new Node(first.val);
		first = first.next;
		return temp;
	}	
}

} The Java standard library contains a class called "Stack". Another class from Java SDK is LinkedList, which can be used as a Queue (add(. and remove()). (LinkedList implements the Queue interface.. If a stack or queue is required to solve problems during your interview, they are ready to be used.

Classic Problems:

Implement a Stack Using an Array
Add Two Numbers
Reorder List
Linked List Cycle
Copy List with Random Pointer
Merge Two Sorted Lists
Odd Even Linked List
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Partition List
LRU Cache
Intersection of Two Linked Lists
Remove Linked List Elements
Swap Nodes in Pairs
Reverse Linked List, Reverse Linked List II, Print Linked List in Reversed Order
Remove Nth Node From End of List (Fast-Slow Pointers)
Implement Stack using Queues
Implement Queue using Stacks
Palindrome Linked List
Implement a Queue using an Array
Delete Node in a Linked List
Reverse Nodes in k-Group
Tree, Heap and Trie

A tree normally refers to a binary tree. Each node contains a left node and right node like the following:

class TreeNode{ int value; TreeNode left; TreeNode right; } Here are some concepts related with trees:

Binary Search Tree: for all nodes, left children <= current node <= right children Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less. Full Binary Tree: every node other than the leaves has two children. Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children. Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible Heap is a specialized tree-based data structure that satisfies the heap property. The time complexity of its operations are important (e.g., find-min, delete-min, insert, etc). In Java, PriorityQueue is important to know.

4.1 Tree

Binary Tree Traversal: Preorder, Inorder, Postorder, Level Order, Level Order II, Vertical Order
Invert Binary Tree
Kth Smallest Element in a BST
Binary Tree Longest Consecutive Sequence
Validate Binary Search Tree
Flatten Binary Tree to Linked List
Path Sum (DFS or BFS)
Path Sum II (DFS.
Construct Binary Tree from Inorder and Postorder Traversal
Construct Binary Tree from Preorder and Inorder Traversal
Convert Sorted Array to Binary Search Tree [Google]
Convert Sorted List to Binary Search Tree [Google]
Minimum Depth of Binary Tree
Binary Tree Maximum Path Sum *
Balanced Binary Tree
Symmetric Tree
Binary Search Tree Iterator
Binary Tree Right Side View
Lowest Common Ancestor of a Binary Search Tree
Lowest Common Ancestor of a Binary Tree
Verify Preorder Serialization of a Binary Tree
Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node II
Unique Binary Search Trees (DP)
Unique Binary Search Trees II (DFS)
Sum Root to Leaf Numbers (DFS)
Count Complete Tree Nodes
Closest Binary Search Tree Value
Binary Tree Paths
Maximum Depth of Binary Tree 27 Recover Binary Search Tree
Same Tree
Serialize and Deserialize Binary Tree
Inorder Successor in BST
Find Leaves of Binary Tree
Largest BST Subtree

4.2 Heap

Merge k sorted arrays [Google]
Merge k Sorted Lists *
Find Median from Data Stream
Meeting Rooms II, Meeting Rooms
Range Addition

4.3 Trie

Implement Trie (Prefix Tree)
Add and Search Word - Data structure design (DFS)

4.4 Segment Tree

Range Sum Query - Mutable
The Skyline Problem
Graph

Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node.

Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes.

breath-first-search

Define a GraphNode

class GraphNode{ int val; GraphNode next; GraphNode[] neighbors; boolean visited;

GraphNode(int x. {
	val = x;
}

GraphNode(int x, GraphNode[] n){
	val = x;
	neighbors = n;
}

public String toString(){
	return "value: "+ this.val; 
}

} 2. Define a Queue

class Queue{ GraphNode first, last;

public void enqueue(GraphNode n){
	if(first == null){
		first = n;
		last = first;
	}else{
		last.next = n;
		last = n;
	}
}

public GraphNode dequeue(){
	if(first == null){
		return null;
	}else{
		GraphNode temp = new GraphNode(first.val, first.neighbors);
		first = first.next;
		return temp;
	}	
}

} 3. Breath First Search uses a Queue

public class GraphTest {

public static void main(String[] args. {
	GraphNode n1 = new GraphNode(1); 
	GraphNode n2 = new GraphNode(2); 
	GraphNode n3 = new GraphNode(3); 
	GraphNode n4 = new GraphNode(4); 
	GraphNode n5 = new GraphNode(5); 

	n1.neighbors = new GraphNode[]{n2,n3,n5};
	n2.neighbors = new GraphNode[]{n1,n4};
	n3.neighbors = new GraphNode[]{n1,n4,n5};
	n4.neighbors = new GraphNode[]{n2,n3,n5};
	n5.neighbors = new GraphNode[]{n1,n3,n4};

	breathFirstSearch(n1, 5);
}

public static void breathFirstSearch(GraphNode root, int x){
	if(root.val == x)
		System.out.println("find in root");

	Queue queue = new Queue();
	root.visited = true;
	queue.enqueue(root);

	while(queue.first != null){
		GraphNode c = (GraphNode. queue.dequeue();
		for(GraphNode n: c.neighbors){

			if(!n.visited){
				System.out.print(n + " ");
				n.visited = true;
				if(n.val == x)
					System.out.println("Find "+n);
				queue.enqueue(n);
			}
		}
	}
}

} Output:

value: 2 value: 3 value: 5 Find value: 5 value: 4 Classic Problems:

Clone Graph
Course Schedule , Course Schedule II , Minimum Height Trees
Reconstruct Itinerary
Graph Valid Tree
Sorting

Time complexity of different sorting algorithms. You can go to wiki to see basic idea of them.

Algorithm Average Time Worst Time Space Bubble sort n^2 n^2 1 Selection sort n^2 n^2 1 Insertion sort n^2 n^2 Quick sort n log(n) n^2 Merge sort n log(n) n log(n) depends

BinSort, Radix Sort and CountSort use different set of assumptions than the rest, and so they are not "general" sorting methods. (Thanks to Fidel for pointing this out)

Here are some implementations/demos, and in addition, you may want to check out how Java developers sort in practice.

Mergesort
Quicksort
InsertionSort.
Maximum Gap (Bucket Sort)
Sort Colors (Counting Sort)
Dynamic Programming

Dynamic programming is a technique for solving problems with the following properties:

An instance is solved using the solutions for smaller instances. The solution for a smaller instance might be needed multiple times. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once. Additional space is used to save time. � The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.

public static int[] A = new int[100];

public static int f3(int n. { if (n <= 2) A[n]= n;

if(A[n] > 0)
	return A[n];
else
	A[n] = f3(n-1. + f3(n-2);//store results so only calculate once!
return A[n];

} Classic problems:

Edit Distance
Distinct Subsequences Total
Longest Palindromic Substring
Word Break
Word Break II
Maximum Subarray
Maximum Product Subarray
Palindrome Partitioning
Palindrome Partitioning II
House Robber [Google]
House Robber II
House Robber III
Jump Game
Jump Game II
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock IV
Dungeon Game
Minimum Path Sum
Unique Paths
Decode Ways
Longest Common Subsequence
Longest Common Substring
Longest Increasing Subsequence
Coin Change
Perfect Squares
Bit Manipulation

Bit operators:

OR (|) AND (&) XOR (^) Left Shift (<<) Right Shift (>>) Not (~) 1|0=1 1&0=0 1^0=1 0010<<2=1000 1100>>2=0011 ~1=0 Get bit i for a give number n. (i count from 0 and starts from right)

public static boolean getBit(int num, int i){ int result = num & (1<<i);

if(result == 0){
	return false;
}else{
	return true;
}

} For example, get second bit of number 10.

i=1, n=10 1<<1= 10 1010&10=10 10 is not 0, so return true;

Classic Problems:

Single Number
Single Number II
Maximum Binary Gap
Number of 1 Bits
Reverse Bits
Repeated DNA Sequences
Bitwise AND of Numbers Range
Sum of Two Integers
Counting Bits
Maximum Product of Word Lengths
Gray Code
Combinations and Permutations

The difference between combination and permutation is whether order matters.

Example 1:

Given 5 numbers - 1, 2, 3, 4 and 5, print out different sequence of the 5 numbers. 4 can not be the third one, 3 and 5 can not be adjacent. How many different combinations?

Example 2:

Given 5 banaba, 4 pear, and 3 apple, assuming one kind of fruit are the same, how many different combinations?

Class Problems:

Permutations
Permutations II
Permutation Sequence
Generate Parentheses
Combination Sum (DFS), II (DFS), III (DFS), IV (DP)
Combinations (DFS)
Letter Combinations of a Phone Number (DFS)
Restore IP Addresses
Factor Combinations (DFS)
Math

Solving math problems usually require us to find regularities or repeated pattern from the observations. List the results for a small set of numbers first, if you do not have any ideas.

Reverse Integer
Palindrome Number
Pow(x,n), Power of Two, Power of Three, Power of Four
Subsets
Subsets II
Fraction to Recurring Decimal [Google]
Excel Sheet Column Number
Excel Sheet Column Title
Factorial Trailing Zeroes
Happy Number
Count Primes
Plus One
Divide Two Integers
Multiply Strings
Max Points on a Line
Product of Array Except Self
Integer Break
Add Digits
Ugly Number, 9Ugly Number II, Super Ugly Number, Find K Pairs with Smallest Sums

UPDATE: I decided to add more categories below.

HashMap
Shortest Word Distance II

Additional Problems:

Self Crossing
Patching Array
Nim Game
Bulb Switcher
Pain Fence
Nested List Weight Sum

#SOURCE 3. javarevisited.blogspot.ca - top-15-data-structures-algorithm-interview-questions-answers-java-programming

http://javarevisited.blogspot.ca/2013/03/top-15-data-structures-algorithm-interview-questions-answers-java-programming.html

Question 1: How to find middle element of linked list in one pass? One of the most popular question from data structures and algorithm, mostly asked on telephonic interview. Since many programmer know that, in order to find length of linked list we need to first traverse through linked list till we find last node, which is pointing to null, and then in second pass we can find middle element by traversing only half of length. They get confused when interviewer ask him to do same job in one pass. In order to find middle element of linked list in one pass, you need to maintain two-pointer, one increment at each node while other increments after two nodes at a time, by having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list. See this trick to find middle element of linked list in single pass for more details.

Question 2: How to find if linked list has a loop ? This question has bit of similarity with earlier algorithm and data structure interview question. I mean we can use two pointer approach to solve this problem. If we maintain two pointers, and we increment one pointer after processing two nodes and other after processing every node, we are likely to find a situation where both the pointers will be pointing to same node. This will only happen if linked list has loop.

Question 3 : How to find 3rd element from end in a linked list in one pass? This is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has moved up to 3rd element, than when first pointer reaches to the end of linked list, second pointer will be pointing to the 3rd element from last in a linked list.

Question 4: In an integer array, there is 1 to 100 number, out of one is duplicate, how to find? This is a rather simple data structures question, especially for this kind of. In this case you can simply add all numbers stored in array, and total sum should be equal to n(n+1)/2. Now just subtract actual sum to expected sum, and that is your duplicate number. Of course there is a brute force way of checking each number against all other numbers, but that will result in performance of O(n^2. which is not good. By the way this trick will not work if array have multiple duplicates or its not numbers forming arithmetic progression. Here is example of one way to find duplicate number in array.

Question 6 : How to reverse String in Java ? This is one of my favorite question. Since String is one of the most important type of programming, you expect lot of question related to String any data structure interview. There are many ways to reverse Sting in Java or any other programming language, and interviewer will force you to solve this problem by using without API i.e. without using reverse(. method of StringBuffer. In follow-up he may ask to reverse String using recursion as well. See 3 ways to reverse String in Java to learn reversing String using both loops and recursion in Java.

Question 7: Write a Java program to sort an array using Bubble Sort algorithm? I have always send couple of questions from searching and sorting in data structure interviews. Bubble sort is one of the simplest sorting algorithm but if you ask anyone to implement on the spot it gives you an opportunity to gauge programming skills of a candidate. See How to sort array using Bubble Sort in Java for complete solution of this datastrucutre interview question.

Question 8: What is the difference between Stack and Queue data structure? One of the classical data structure interviews question. I guess every one know, No? Any way main difference is that Stack is LIFO(Last In First Out. data structure while Queue is a FIFO(First In First Out. data structure.

Question 9: How do you find duplicates in an array if there is more than one duplicate? Sometime this is asked as follow-up question of earlier data structure interview question, related to finding duplicates in Array. One way of solving this problem is using a Hashtable or HashMap data structure. You can traverse through array, and store each number as key and number of occurrence as value. At the end of traversal you can find all duplicate numbers, for which occurrence is more than one. In Java if a number already exists in HashMap then calling get(index. will return number otherwise it return null. this property can be used to insert or update numbers in HashMap.

Question 10 : What is difference between Singly Linked List and Doubly Linked List data structure? This is another classical interview question on data structure, mostly asked on telephonic rounds. Main difference between singly linked list and doubly linked list is ability to traverse. In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.

Question 11 : Write Java program to print Fibonacci series ? This is not a data structures question, but a programming one, which many times appear during data structure interview. Fibonacci series is a mathematical series, where each number is sum of previous two numbers e.g. 1,1, 2, 3, 5, 8, 13, 21. Interviewer is often interested in two things, a function which returns nth number in Fibonacci series and solving this problem using recursion in Java. Though, its easy question, recursion part often confuses beginners. See this link to find nth Fibonacci number in Java.

Question 12: Write Java program to check if a number is a palindrome or not? This is similar to previous question, not directly related to data structures, but quite popular along with other questions. A number is called palindrome, if reverse of number is equal to number itself. Interviewer ask to solve this problem without taking help from Java API or any open source library. Any way it’s simple question, you can use division operator (/. and remainder operator (%. to solve this question. Just remember, division operator can be used to get rid of last digit e.g. 1234/10 will give you 123, and modulus operator can give you last digit e.g. 1234%10 will return 4. By the way, here is a Java program check if number is palindrome or not.

Question 13 : What is binary search tree? This is a data structure question from Tree data structures. Binary Search Tree has some special properties e.g. left nodes contains items whose value is less than root , right sub tree contains keys with higher node value than root, and there should not be any duplicates in the tree. Apart from definition, interview can ask you to implement binary search tree in Java and questions on tree traversal e.g. IN order, preorder, and post order traversals are quite popular data structure question.

Question 14 : How to reverse linked list using recursion and iteration? This is another good question on data structures. There are many algorithms to reverse linked list and you can search for them using google. I am thinking of writing another blog post to explain linked list reversal and will share with you later.

Question 15: Write a Java program to implement Stack in Java? You can implement Stack by using array or linked list. This question expect you to implement standard method provided by stack data structure e.g. push(. and pop(). Both push(. and pop(. should be happen at top of stack, which you need to keep track. It’s also good if you can implement utility methods like contains(), isEmpty(. etc. By the way JDK has java.util.Stack class and you can check it’s code to get an idea. You can also check Effective Java book, where Josh Bloch has explains how an incorrect implementation of stack can cause memory leak in Java.

#SOURCE 4. wiki.dreamrunner.org - Programming Interviews Exposed

http://wiki.dreamrunner.org/public_html/BooksReview/Interview/Programming%20Interviews%20Exposed%20Secrets%20to%20Landing%20Your%20Next%20Job.html

Chapter 3: Approaches to Programming Problems

Interactivity Is Key

The code you write in the interview is probably the only example of your code that your interviewer will see. If you write ugly code, your interviewer will assume you always write ugly code. This is your chance to shine and show your best code. Take the time to make your code solid and pretty.

Tip Brush up on the languages you expect to use, and write your best code. Programming questions are designed to see both how well you can code and how you solve problems. If all the interviewer wanted to do were measure your coding ability, he could give you a piece of paper with problems and come back an hour later to evaluate how you did, just as they do in programming contests. What the interviewer wants is to see your thought processes as you work through each stage of the programming problem.

The problem-solving process in these interviews is very interactive, and if you’re having difficulty, the interviewer will generally guide you to the correct answer via a series of hints. Of course, the less help you need to solve the problem, the better you look, but showing an intelligent thought process and responding well to the hints you are given is also very important.

Even when you immediately know the answer to a problem, because it’s something you’ve already done before, don’t just blurt it out. Break the answer down into discrete steps and explain the thought processes behind each step. The point is to show the interviewer that you understand the underlying concepts, not that you’ve managed to memorize the answer to a programming puzzle.

If you know any additional information pertaining to the problem, you may want to mention it during the process to show your general knowledge of programming, even if it’s not directly applicable to the problem at hand. In answering these problems, show that you’re not just a propeller-head coder. Demonstrate that you have logical thought processes, are generally knowledgeable about computers, and can communicate well.

Tip Keep talking! Always explain what you are doing! Otherwise, the interviewer has no way of knowing how you tackle complex programming problems.

Solving the Questions

Now it’s time to solve the questions, but don’t just jump in. Instead, remember you want to fully understand the problem. You should try an example, and then focus on the algorithm that will solve the problem. You then want to explain your solution and code for the solution. The following steps walk you through the process:

The Basic Steps The best way to solve an interview problem is to approach it methodically. Here are the suggested steps:

Make sure you understand the problem. Your initial assumptions about the problem may be wrong, or the interviewer’s explanation may be very brief or difficult to follow. You can’t demonstrate your skills if you don’t understand the problem. Don’t hesitate to ask your interviewer questions about the problem, and don’t start solving it until you understand it. The interviewer may be deliberately obscuring things in order to determine whether you can find and understand the real problem. Once you understand the question, try an example. This example may lead to insights about how to solve the problem or bring to light any remaining misunderstandings that you have. Starting with an example also demonstrates a methodical, logical thought process. Examples are especially useful if you don’t see the solution right away. Tip Make sure you understand the problem before you start solving it, and then start with an example to solidify your understanding.

Focus on the algorithm you will use to solve the problem. Often, this will take a long time and require additional examples. This is to be expected. Interactivity is important during this process. If you stand quietly staring at the whiteboard, the interviewer has no way of knowing whether you’re making productive headway or are simply clueless. Talk to your interviewer and tell him or her what you are doing. For example, you might say something like, “I’m wondering whether I can store the values in an array and then sort them, but I don’t think that will work because I can’t quickly look up elements in an array by value.” This demonstrates your skill, which is the point of the interview, and may also lead to hints from the interviewer, who might respond, “You’re very close to the solution. Do you really need to look up elements by value, or could you …” It may take a long time to solve the problem, and you may be tempted to begin coding before you figure out an exact solution. Resist this temptation. Consider who you would rather work with: someone who thinks about a problem for a long time and then codes it correctly the first time or someone who hastily jumps into a problem, makes several errors while coding, and doesn’t have any idea where he or she is going. Not a difficult decision, is it?

After you’ve figured out your algorithm and how you will implement it, explain your solution to the interviewer. This gives him or her an opportunity to evaluate your solution before you begin coding. Your interviewer may say, “Sounds great, go ahead and code it,” or something like, “That’s not quite right because you can’t look up elements in a hash table that way.” In either case, you gain valuable information. While you code, it’s important to explain what you’re doing. For example, you might say, “Here, I’m initializing the array to all zeroes.” This narrative enables the interviewer to follow your code more easily. Tip Explain what you are doing to your interviewer before and while coding the solution. Keep talking!

Ask questions when necessary. You generally won’t be penalized for asking factual questions that you might otherwise look up in a reference. You obviously can’t ask a question like, “How do I solve this problem?” but it is acceptable to ask a question like, “I can’t remember - what format string do I use to print out a localized date?” While it’s better to know these things, it’s okay to ask this sort of question. After you’ve written the code for a problem, immediately verify that the code is correct by tracing through it with an example. This step demonstrates very clearly that your code works in at least one case. It also illustrates a logical thought process and your desire to check your work and search for bugs. The example may also help you flush out minor bugs in your solution. Make sure you check your code for all error and special cases, especially boundary conditions. Many error and special cases are overlooked by programmers; forgetting these cases in an interview indicates you may forget them on the job. For example, if you allocate memory dynamically, make sure you check that the allocation did not fail. (If time does not allow for extensive checking, at the very least explain that you should check for such failures.. Covering error and special cases will impress your interviewer and help you correctly solve the problem. Tip Try an example, and check all error and special cases.

Once you try an example and feel comfortable that your code is correct, the interviewer may ask you questions about what you wrote. Commonly, these questions focus on running time, alternative implementations, and complexity. If your interviewer does not ask you these questions, you should volunteer the information to show that you are cognizant of these issues. For example, you could say, “This implementation has linear running time, which is the best possible because I have to check all the input values. The dynamic memory allocation will slow it down a little, as will the overhead of using recursion.”

When You Get Stuck Getting stuck on a problem is expected and an important part of the interviewing process. Interviewers want to see how you respond when you don’t recognize the answer to a question immediately. Giving up or getting frustrated is the worst thing to do if this happens to you. Instead, show interest in the problem and keep trying to solve it:

Go back to an example. Try performing the task and analyzing what you are doing. Try extending from your specific example to the general case. You may have to use very detailed examples. This is okay, because it shows the interviewer your persistence in finding the correct solution. Tip When all else fails, return to a specific example. Try to move from the specific example to the general case and from there to the solution.

Try a different data structure. Perhaps a linked list, an array, a hash table, or a binary search tree will help. If you’re given an unusual data structure, look for similarities between it and more-familiar data structures. Using the right data structure often makes a problem much easier. Consider the less-commonly used or more-advanced aspects of a language. Sometimes the key to a problem involves one of these features. Tip Sometimes a different data structure or advanced language feature is key to the solution.

Even when you don’t feel stuck, you may be having problems. You may be missing an elegant or obvious way to implement something and writing too much code. Almost all interview coding questions have short answers. You rarely need to write more than 15 lines of code and almost never more than 30. If you start writing a lot of code, you may be heading in the wrong direction.

Chapter 4: Linked Lists

Linked List Problems

A C++ version looks like the following:

class Stack { public: Stack(); ~Stack(); void push( void *data ); void *pop(); protected: // Element struct needed only internally typedef struct Element { struct Element *next; void *data; } Element;

Element *head;

};

Stack::Stack(. { head = NULL; return; }

Stack::~Stack(. { while( head ){ Element *next = head->next; delete head; head = next; } return; }

void Stack::push( void *data ){ //Allocation error will throw exception Element *element = new Element; element->data = data; element->next = head; head = element; return; }

void *Stack::pop(. { Element *popElement = head; void *data;

/* Assume StackError exception class is defined elsewhere */
if( head == NULL )
    throw StackError( E_EMPTY );

data = head->data;
head = head->next;
delete popElement;
return data;

} Null or Cycle

Important You are given a linked list that is either NULL-terminated (acyclic), as shown in Figure 4-5, or ends in a cycle (cyclic), as shown in Figure 4-6.

Write a function that takes a pointer to the head of a list and determines whether the list is cyclic or acyclic. Your function should return false if the list is acyclic and true if it is cyclic. You may not modify the list in any way.Null or Cycle

Write a function that takes a pointer to the head of a list and determines whether the list is cyclic or acyclic. Your function should return false if the list is acyclic and true if it is cyclic. You may not modify the list in any way.

In outline form, this algorithm looks like this:

Start two pointers at the head of the list Loop infinitely If the fast pointer reaches a NULL pointer Return that the list is NULL terminated If the fast pointer moves onto or over the slow pointer Return that there is a cycle Advance the slow pointer one node Advance the fast pointer two nodes You can now implement this solution:

/* Takes a pointer to the head of a linked list and determines if

the list ends in a cycle or is NULL terminated */ bool determineTermination( Node *head ){ Node *fast, *slow; fast = slow = head; while( true ){ if( !fast || !fast->next ) return false; else if( fast == slow || fast->next == slow ) return true; else { slow = slow->next; fast = fast->next->next; } } } Chapter 5: Trees and Graphs

Following is some additional tree-related vocabulary:

Parent - A node that points to other nodes is the parent of those nodes. Every node except the root has one parent. In Figure 5-1, B is the parent of D, E, and F. Child - A node is the child of any node that points to it. In Figure 5-1, each of the nodes D, E, and F is a child of B. Descendant - All the nodes that can be reached by following a path of child nodes from a particular node are the descendants of that node. In Figure 5-1, D, E, F, H, I, J, and K are the descendants of B. Ancestor - An ancestor of a node is any other node for which the node is a descendant. For example, A, B, and D are the ancestors of I. Leaves - The leaves are nodes that do not have any children. G, H, I, and K are leaves. Common Searches

Breadth-First Search One way to search a tree is to do a breadth-first search (BFS). In a BFS you start with the root, move left to right across the second level, then move left to right across the third level, and so forth. You continue the search until either you have examined all of the nodes or you find the node you are searching for. The time to find a node is O(n), so this type of search is best avoided for large trees. A BFS also uses a large amount of memory because it is necessary to track the child nodes for all nodes on a given level while searching that level.

Depth-First Search Another common way to search for a node is by using a depth-first search (DFS). A depth-first search follows one branch of the tree down as many levels as possible until the target node is found or the end is reached. When the search can’t go down any farther, it is continued at the nearest ancestor with unexplored children. DFS has much lower memory requirements than BFS because it is not necessary to store all of the child pointers at each level. In addition, DFS has the advantage that it doesn’t examine any single level last (BFS examines the lowest level last). This is useful if you suspect that the node you are searching for will be in the lower levels. For example, if you were searching a job hierarchy tree looking for an employee who started less than three months ago, you would suspect that lower-level employees are more likely to have started recently. In this case, if the assumption were true, a DFS would usually find the target node more quickly than a BFS.

Traversals

Preorder traversal of a node performs the operation first on the node itself, then on its left descendants, and finally on its right descendants. In other words, a node is always visited before any of its children. Inorder traversal performs the operation first on the node’s left descendants, then on the node itself, and finally on its right descendants. In other words, the left subtree is visited first, then the node itself, and then the node’s right subtree. Postorder traversal performs the operation first on the node’s left descendants, then on the node’s right descendants, and finally on the node itself. In other words, all of a node’s children are visited before the node itself. Binary Tree Problems

Preorder Traversal, No Recursion Create the stack Push the root node on the stack While the stack is not empty Pop a node If the node is not null Print its value Push the node's right child on the stack Push the node's left child on the stack void preorderTraversal( Node root ){ NodeStack stack = new NodeStack(); stack.push( root ); while( true ){ Node curr = stack.pop(); if( curr == null . break; curr.printValue(); Node n = curr.getRight(); if( n != null . stack.push( n ); n = curr.getLeft(); if( n != null . stack.push( n ); } } Lowest Common Ancestor Chapter 6: Arrays and Strings

Arrays

An array is a sequence of variables of the same type arranged contiguously in a block of memory.

Strings

Strings are sequences of characters. However, what constitutes a character depends greatly on the language being used and the settings of the operating system on which the application runs.

Array and String Problems

Both hash tables and arrays provide constant-time lookup; you need to decide which one you will use. On the one hand, hash tables have a higher lookup overhead than arrays. On the other hand, an array would initially contain random values that you would have to take time to set to zero, whereas a hash table initially has no values. Perhaps the greatest difference is in memory requirements. An array would need an element for every possible value of a character. This would amount to a relatively reasonable 128 elements if you were processing ASCII strings, but if you had to process Unicode strings you would need more than 65,000 elements, assuming a 16-bit Unicode encoding. In contrast, a hash table would require storage for only the characters that actually exist in the input string. Therefore, arrays are a better choice for long strings with a limited set of possible character values; hash tables are more efficient for shorter strings or when there are many possible character values.

Chapter 7: Recursion

Although recursion is a very powerful technique, it is not always the best approach, and rarely is it the most efficient approach. This is due to the relatively large overhead for routine calls on most platforms. For a simple recursive routine like factorial, many computer architectures spend more time on call overhead than the actual calculation. Iterative routines, which use looping constructs instead of recursive routine calls, do not suffer from this overhead and are frequently more efficient.

Tip Iterative solutions are usually more efficient than recursive solutions.

This implementation is significantly more efficient than our previous recursive implementation because no routine calls are involved. Although it represents a different way of thinking about the problem, it’s not really any more difficult to write than the recursive implementation

Tip A recursive algorithm can be implemented without recursive calls by using a stack, but it’s usually more trouble than it’s worth.

In an interview, a working solution is of primary importance; an efficient solution is secondary. Unless you’ve been told otherwise, go with whatever type of working solution comes to you first. If it’s a recursive solution, you might want to mention the inefficiencies inherent in recursive solutions to your interviewer, so it’s clear that you know about them. In the rare instance that you see a recursive solution and an iterative solution of roughly equal complexity, you should probably mention them both to the interviewer, indicating that you’re going to work out the iterative solution because it’s likely to be more efficient.

Recursion Problems

Chapter 8: Concurrency

Basic Thread Concepts

Threads A thread is the fundamental unit of execution within an application: A running application consists of at least one thread. Each thread has its own stack and runs independently from the application’s other threads. Threads share the resources used by the application as it runs, such as file handles or memory, which is why problems can occur. Data corruption is a common side effect of having two threads simultaneously write data to the same block of memory, for example.

Monitors and Semaphores In order to avoid data corruption and other problems, applications must control how threads interact with shared resources, referred to as thread synchronization. The two fundamental thread synchronization constructs are monitors and semaphores. Which you use depends on what your system or language supports.

Concurrency Problems

Busy Waiting Producer/Consumer public class IntBuffer { private int index; private int[] buffer = new int[8];

public synchronized void add( int num ){
    while( index == buffer.length - 1 ){
        try {
            wait();
        }
        catch( InterruptedException e ){
        }
    }

    buffer[index++] = num;
    notifyAll();
}

public synchronized int remove(){
    while( index == 0 ){
        try {
            wait();
        }
        catch( InterruptedException e ){
        }
    }

    int ret = buffer[--index];
    notifyAll();
    return ret;
}

}

public class Producer extends Thread { private IntBuffer buffer;

public Producer( IntBuffer buffer ){
    this.buffer = buffer;
}

public void run(){
    Random r = new Random();
    while( true ){
        int num = r.nextInt();
        buffer.add( num );
        System.out.println( "Produced " + num );
    }
}

}

public class Consumer extends Thread { private IntBuffer buffer;

public Consumer( IntBuffer buffer ){
    this.buffer = buffer;
}

public void run(){
    while( true ){
        int num = buffer.remove();
        System.out.println( "Consumed " + num );
    }
}

}

IntBuffer b = new IntBuffer(); Producer p = new Producer( b ); Consumer c = new Consumer( b ); p.start(); c.start(); The Dining Philosophers This application deadlocks when all philosophers have simultaneously picked up their left fork: Because no right fork is available to any philosopher, no philosopher can eat.

One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again. The flaw with this solution is that it’s possible for one or more philosophers to starve because they never acquire both forks. This is referred to as livelock.

The best solution requires a very simple change to the application. Instead of having all the philosophers pick up the left fork first, have one of the philosophers pick up the right fork first:

Chapter 9: Object-Oriented Programming

Interfaces and Abstract Classes

Explain the difference between an interface and an abstract class in object-oriented programming.

An interface declares a set of related methods, outside of any class. An abstract class is an incomplete class definition that declares but does not define all of its methods. Conceptually, then, an interface defines an application programming interface (API. that is independent of any class hierarchy. In fact, interfaces can be used in non-OO programming models, such as componentbased models like COM and CORBA. However, you’re focusing on the use of interfaces in an object-oriented context, where they are useful in their own right. Interfaces are the ultimate encapsulators, because they hide all the details of the classes that implement their methods from the user of the interface. They’re particularly important - almost necessary, in fact - in languages that only support single inheritance (classes can only inherit from one base class). A class that exposes its members via an interface is said to implement the interface.

Unlike an interface, an abstract class is a proper class: It can have data members and can be a subclass of other classes. Unlike a concrete (nonabstract. class, however, some of its behaviors are deliberately left to be defined by its own subclasses. Abstract classes cannot be instantiated because of this - only instances of concrete subclasses can be created.

Virtual Methods

Describe what virtual methods are and why they are useful.

A virtual method is a method whose implementation is determined at run time based on the actual type (class. of the invoking object. Nonstatic Java methods are always virtual, so Java programmers may have trouble answering this one; but in C# and C++, methods are only virtual when declared with the virtual keyword - nonvirtual methods are the default.

Once you explain what virtual methods are and why they’re useful, talk about their advantages and disadvantages. The primary advantage was just described: the run-time method selection. Virtual methods are also used to declare abstract methods. The disadvantages are that it takes longer to invoke a virtual method (at a minimum, one lookup needs to be done in a table to find the right method - you can’t jump directly to the method as you can with nonvirtuals. and that extra memory is required to store the information needed for the lookup.

Multiple Inheritance

Why do C# and Java disallow the multiple inheritance of classes?

In C++ it’s legal for a class to inherit (directly or indirectly. from more than one class, which is referred to as multiple inheritance. C# and Java, however, limit classes to single inheritance - each class inherits from a single parent class.

Multiple inheritance is a useful way to create classes that combine aspects of two disparate class hierarchies, something that often happens when using different class frameworks within a single application. If two frameworks define their own base classes for exceptions, for example, you can use multiple inheritance to create exception classes that can be used with either framework.

The problem with multiple inheritance is that it can lead to ambiguity. The classic example is when a class inherits from two other classes, each of which inherits from the same class:

class A { protected: bool flag; };

class B : public A {};

class C : public A {};

class D : public B, public C { public: void setFlag( bool nflag ){ flag = nflag; // ambiguous } }; In this example, the flag data member is defined by class A. But class D descends from class B and class C, which both derive from A, so in essence two copies of flag are available because there are two instances of A in D’s class hierarchy. Which one do you want to set? The compiler will complain that the reference to flag in D is ambiguous. One fix is to explicitly disambiguate the reference:

B::flag = nflag;

Another fix is to declare B and C as virtual base classes, which means that only one copy of A will exist in the hierarchy, eliminating any ambiguity.

There are other complexities with multiple inheritance, such as the order in which the base classes are initialized when a derived object is constructed, or the way members can be inadvertently hidden from derived classes. Because of these complexities, some languages restrict themselves to the much simpler single inheritance model. On the other hand, single inheritance is also very restrictive, because only classes with a common ancestor can share behaviors. Interfaces mitigate this restriction somewhat by allowing classes in different hierarchies to expose common interfaces even if they’re not implemented by sharing code.

Chapter 10: Databases

Database Fundamentals

Data in a relational database is stored in tables, which consist of rows and columns. (A set of tables is referred to as a schema.. Each table has at least one column, but there may be no rows. Each column has a type associated with it, which limits the type of data that can be stored in the column, as well as additional constraints. Although the columns are ordered, the rows aren’t. Any ordering that is required is done when the data is fetched (via a query. from the database.

Most tables have keys, although it’s not a requirement (but it is good design). A key is a column or set of columns that uniquely identifies a particular row in the table. One of the keys is designated to be the primary key. For example, in a table of employees, you would use the employee identification number - guaranteed to be unique for each employee - as the primary key.

A table can be linked to another table using a foreign key. A foreign key is usually a primary key value taken from the other table. Foreign keys ensure that data isn’t deleted prematurely: You can’t delete a row from a table if the foreign key of another table references the row. This is known as referential integrity, and it ensures that related tables are always in a consistent state with respect to each other.

Structured Query Language (SQL)

Database Transactions

The integrity of the data stored in a database is paramount: If the data is ever corrupted, every application that depends on the database may fail or be in error. While referential integrity helps keep the data consistent, the best way to ensure data integrity is to use a database transaction.

A transaction groups a set of related database manipulations together into a single unit. If any operation within the transaction fails, the entire transaction fails and any changes made by the transaction are abandoned (rolled back). Conversely, if all the operations succeed, then all the changes are committed together as a group.

The four properties of a transaction are as follows:

Atomicity - The database system guarantees that either all operations with the transaction succeed or else they all fail. Consistency - The transaction must ensure that the database is in a correct, consistent state at the start and the end of the transaction. No referential integrity constraints can be broken, for example. Isolation - All changes to the database within a transaction are isolated from all other queries and transactions until the transaction is committed. Durability - Once committed, changes made in a transaction are permanent. The database system must have some way to recover from crashes and other problems so that the current state of the database is never lost. Database Problems

Simple SQL Given a database with the table

Olympics( city CHAR(16),

year INT(4)

) write a SQL statement to insert Montreal and 1976 into the database.

INSERT INTO Olympics VALUES( 'Montreal', 1976 ) Company and Employee Database Important You are given a database with the following tables:

Company ( companyName CHAR(30), id INT(4. PRIMARY KEY )

EmployeesHired ( id INT(4. PRIMARY KEY, numHired INT(4), fiscalQuarter INT(4), FOREIGN KEY id REFERENCES Company ) Write a SQL statement that returns the names of all the companies that hired employees in fiscal quarter 4. SELECT companyName FROM Company, EmployeesHired WHERE Company.id = EmpolyeesHired.id AND fiscalQuarter = 4 AND numHired > 0 Now, using the same schema, write a SQL statement that returns the names of all companies that did not hire anyone in fiscal quarters 1 through 4. SELECT companyName FROM Company WHERE id NOT IN (SELECT id from EmployeesHired WHERE numHired > 0) Finally, return the names of all companies and the total number of employees that each company hired during fiscal quarters 1 through 4. SELECT companyName, SUM(numHired) FROM Company, EmployeesHired WHERE Company.id = EmployeesHired.id GROUP BY companyName Max, No Aggregates Important Given the following SQL database schema

Test ( num INT(4)

) write a SQL statement that returns the maximum value from num without using an aggregate (MAX, MIN, etc.).

There is one minor bug in this query. If the maximum value is repeated in the Test table, it will be returned twice. To prevent this, use the DISTINCT keyword. This changes the query to the following:

SELECT DISTINCT num FROM Test WHERE num NOT IN (SELECT Lesser.num FROM Test AS Greater, Test AS Lesser WHERE Lesser.num < Greater.num) Three-Valued Logic Important Given the following table

Address ( street CHAR(30. NOT NULL, apartment CHAR(10),

city CHAR(40. NOT NULL,

) write a SQL statement that returns nonapartment addresses only.

The trick is in the use of the equality operator (‘=’. to test for a NULL column value. In most databases, a comparison to NULL returns UNKNOWN - even when comparing NULL to NULL. The proper way to check for a NULL or non-NULL column is to use the IS NULL or IS NOT NULL syntax. Thus, the original query should be restated as follows:

SELECT * FROM Address WHERE apartment IS NULL

Chapter 11: Other Programming Topics

Bit Manipulation

Graphics and Bit Operations Problems

Rectangle Overlap

The two rectangles do not overlap when

A’s UL’s x value is greater than B’s LR’s x value or A’s UL’s y value is less than B’s LR’s y value or A’s LR’s x value is less than B’s UL’s x value or A’s LR’s y value is greater than B’s UL’s y value. This solution is much simpler, requiring only four comparisons and one negation. You can implement the function as follows:

boolean overlap( Rect a, Rect b ){ return !( a.ul.x > b.lr.x || a.ul.y < b.lr.y || a.lr.x < b.ul.x || a.lr.y > b.ul.y ); } Working through these rules, you’ll get the following function:

boolean overlap( Rect a, Rect b){ return( a.ul.x <= b.lr.x && a.ul.y >= b.lr.y && a.lr.x >= b.ul.x && a.lr.y <= b.ul.y ); } To ensure that you didn’t make a mistake, it’s a good idea to verify that these conditions make sense. The preceding function determines that two rectangles overlap if

A’s left edge is to the left of B’s right edge and A’s upper edge is above B’s bottom edge and A’s right edge is to the right of B’s left edge and A’s bottom edge is below B’s upper edge. Big-endian or Little-endian

Write a function that determines whether a computer is big-endian or little-endian.

Endianness is important to know when reading or writing data structures, especially across networks, so that different applications can communicate with each other. Sometimes the endianness is hidden from the developer: Java uses a fixed endianness to store data, regardless of the underlying platform’s endianness, so data exchanges between two Java applications won’t normally be affected by endianness. But other languages, C in particular, don’t specify an endianness for data storage, leaving the implementation free to choose the endianness that works best for the platform. C is used to solve this problem.

If you set the value of the integer to 1, you can distinguish between the MSB and the LSB because in an integer with the value 1, the LSB has the value 1 and the MSB has the value 0.

The code for this test is as follows:

/* Returns true if the machine is little-endian, false if the

machine is big-endian */ bool endianness(){ int testNum; char *ptr;

testNum = 1; ptr = (char *. &testNum; return (ptr); / Returns the byte at the lowest address */ } This solution is sufficient for an interview. However, as the goal of an interview is not just to solve problems, but also to impress your interviewer, you may want to consider a slightly more elegant way to solve this problem. It involves using a feature of C/C++ called union types. A union is like a struct, except that all of the members are allocated starting at the same location in memory.

/* Returns true if the machine is little-endian, false if the

machine is big-endian */ bool endianness(){ union { int theInteger; char singleByte; } endianTest;

endianTest.theInteger = 1; return endianTest.singleByte; } Number of Ones

Write a function that determines the number of 1 bits in the computer’s internal representation of a given integer.

The number will be shifted to the right, but the new bit added on the left will depend on how the shift operator treats negative values. Let’s avoid the problem entirely and use Java’s >>> operator for our example. In the other C-like languages, you can also avoid the problem by reading the value as an unsigned integer. (That solution doesn’t work with Java because there are no unsigned integer types in Java.. Using either the >>> or an unsigned integer means that the shift operator will not sign extend, and the new bits that are added during the right shifting will be 0’s. The number will eventually become all 0’s. Finally, consider the case where you are given a positive integer. This is the sample case that you worked with, and the algorithm works correctly here.

The code for this algorithm is as follows:

int numOnesInBinary( int number ) { int numOnes = 0; while( number != 0 ){ if( ( number & 1 . == 1 ) numOnes++; number = number >>> 1; } return numOnes; } You can count the number of times that you can perform this process before the integer’s value reaches 0. This is the number of 1’s in the computer’s representation of the number. In outline form this algorithm is as follows:

Start with count = 0 While the integer is not zero AND the integer with the integer – 1 Increment count Return count Here is the code:

int numOnesInBinary( int number ){ int numOnes = 0; while( number != 0 ){ number = number & (number – 1); numOnes++; } return numOnes; } This solution has a running time of O(m), where m is the number of 1’s in the solution.

Chapter 12: Counting, Measuring, and Ordering Puzzles

Tackling Brainteasers

This property of brainteasers works most strongly to your advantage when you are faced with a problem that has only two possible answers (for example, any yes or no question). Whichever answer seems at first to be correct is probably wrong. Of course, it’s probably not a good idea to say, “The answer must be yes because if it were no this would be a very simple problem and you wouldn’t have bothered to ask it.” You can, however, use this knowledge to guide your thinking.

Tip Remember that the obvious answer is almost never the right answer.

Solve the Right Problem

For example, suppose you are given the problem of finding an arrangement that maximizes the number of oranges you can fit in the bottom of a square box. You would probably automatically assume that the oranges are small spherical fruit, that they are all about the same size, that “in the bottom” means in contact with the bottom surface of the box, and that the oranges must remain intact (you can’t puree them and pour them in). These assumptions may seem ridiculous - they are all rather obvious and they are all correct. The point is that assumptions are inherent in all communication or thought; you can’t begin to work on a problem without assumptions.

Tip If the solution that seems logical is wrong, you made a false assumption. Categorize your assumptions, and try to identify those that are false.

Don’t Be Intimidated

You don’t have to devise a plan for getting all the way to the solution before you start - things will come to you as you work:

Break a problem into parts - If you can identify a subproblem, try solving that, even if you’re not sure it’s critical to solving the main problem. Try a simplified problem - Try solving a simplified version of the problem; you may gain insights that will be useful in solving the full problem. Try specific examples - If the problem involves some sort of process, try working through a few specific examples. You may notice a pattern you can generalize to other cases. Above all, keep talking, keep thinking, and keep working. Estimation Problems

One estimation problem is “How many gas stations are there in the United States?” It has been so widely reported that this problem was posed by Microsoft that it seems almost certain to be apocryphal; nevertheless, it is a good example.

These problems are usually not difficult compared with the more common brainteasers. You’re not expected to know the actual statistic or fact. Instead, you are expected to do a rough order of magnitude calculation based on facts you do know. Because everything is an estimate anyway, try to adjust or round your figures so that any large numbers you use are powers (or at least multiples. of ten - this will significantly simplify your arithmetic.

Taking the gas station problem as an example, your calculation might go like this: “It takes me about six minutes to fill up my car. I go to the gas station about once a week, and there are usually two other cars there. If I assume this is average for Americans, each gas station services about 30 cars an hour. Suppose a gas station were open 12 hours a day, 7 days a week. That would be 84 hours a week. In reality, a gas station is probably open more than 12 hours a day, so I’ll say the average gas station is open 100 hours a week. That means it services 3,000 cars a week. There’s somewhere upwards of 250 million people in the United States. Not everyone has a car, so suppose there are 100 million cars on the road. If every car goes to the gas station once a week, like mine does, and each station sees 3,000 cars a week, there would have to be about 33,000 gas stations in the United States.” This figure is probably off by a lot, but it’s likely within an order of magnitude (that is, there are more than 3,300 gas stations and fewer than 330,000). It’s much more important that you are able to form a framework for the estimation and rapidly work through the calculations than that you accurately estimate the statistic. For more practice, try estimating the number of kindergarten teachers in your state, the circumference of the earth, and the weight of a ferry boat.

Brainteaser Problems

Chapter 13: Graphical and Spatial Puzzle

Tip Whenever possible, draw a picture.

Tip If the problem involves motion or change, draw multiple pictures of different points in time.

Tip Visualization may be more appropriate than diagramming for three-dimensional problems, but in either case, attack the problem spatially.

Graphical and Spatial Problems

Chapter 14: Knowledge-Based Questions

C++ versus Java

Important What are the differences between C++ and Java? C++ and Java are syntactically very similar. Java’s designers intended this to make it easy for C++ developers to learn Java. Apart from this area of similarity, Java and C++ differ in a variety of ways, largely because of their different design goals. Security, portability, and rapid development were of paramount importance in the design of Java, whereas C++ is more concerned with performance and backward compatibility with C. Java is compiled to virtual machine byte-code and requires a virtual machine to run; C++ is compiled to native machine code. This usually makes C++ faster, but it gives Java greater potential for portability and security.

C++ is a superset of C and maintains features such as programmer-controlled memory management, pointers, and a preprocessor for full backward compatibility with C. In contrast, Java eliminates these and other bug-prone features. Java replaces programmer memory deallocations with garbage collection. Java further dispenses with C++ features such as operator overloading and multiple inheritance. These choices are seen by some to make Java a better choice for rapid development and for projects where portability and security are more important than performance.

Tip A limited form of multiple inheritance can be simulated in Java using interfaces.

In Java, all objects are passed by reference, whereas in C++, the default behavior is to pass objects by value. Java does not perform automatic type casting as C++ does, though newer Java features such as generics and autoboxing now handle many common cases. In Java, all methods are virtual, meaning the implementation for a method is selected according to the type of the object as opposed to the type of the reference. In C++, methods must be explicitly declared as virtual. Java has defined sizes for primitive data types, while type sizes are implementation-dependent in C++ (and C).

In situations where there is legacy C code and a great need for performance, C++ has certain benefits, especially when low-level system access is required. In situations where portability, security, and speed of development are emphasized, Java (or a similar language such as C#. may be a better choice.

Garbage Collection

Important Discuss what garbage collection is and explain different ways it can be implemented.

Garbage collection is the process by which a program automatically finds and reclaims memory that is no longer used or no longer accessible by an application. This reclamation occurs without programmer assistance. C#, Java, Lisp, and Perl are examples of languages with garbage-collection facilities.

Garbage collection provides several advantages over having a programmer explicitly deallocate memory. It eliminates bugs due to dangling pointers and memory leaks. It also promotes greater simplicity in program and interface design because the complicated mechanisms traditionally used to ensure that memory is properly freed (such as “smart pointers” in C++. are unnecessary. In addition, because programmers don’t have to worry about memory deallocation, program development proceeds at a more rapid pace.

Garbage collection is not without its disadvantages, however. Garbage-collected programs often run more slowly because of the overhead needed for the system to determine when to deallocate and reclaim memory no longer needed. In addition, the system will occasionally over-allocate memory and may not free memory at the best possible time.

One method of garbage collection is to use reference counting. This involves tracking how many variables reference an object. Initially, there will be one reference to a piece of memory. The reference count will increase if the variable referencing it is copied. When a variable referencing an object changes value or goes out of scope, the object’s reference count is decremented. If a reference count ever goes to 0, the memory associated with the object is freed: If no one is keeping a reference to the object, then the object (and hence its memory. is no longer needed.

Reference counting is simple and relatively fast. However, it doesn’t handle circular references. Consider what happens in the case of a circularly linked list with nothing external pointing to it. Every element in the list has a nonzero reference count, yet the memory isn’t referenced by any object outside the list itself. Thus, the memory could safely be deallocated, but reference-based garbage collection won’t free it.

A second method of garbage collection is known as mark and sweep. In the first pass, the memory manager will mark all objects that can be accessed by any thread in the program. In the second pass, all unmarked objects are deallocated, or swept away.

Mark and sweep handles circular references, but it’s also less efficient. The garbage collector runs at different points in an application’s execution and may cause the application to pause while the garbage collecting occurs.

Network Performance

Important What are the two major issues in networking performance?

Any network can be measured by two major characteristics: latency and bandwidth. Latency refers to how long it takes a given bit of information to get through the network. Bandwidth refers to the rate at which data moves through the network once communication is established. The perfect network would have infinite bandwidth and no latency.

A pipe is a good analog for a network. The time it takes for a molecule of water to go through the whole pipe is determined by the length; this is analogous to the latency. The width of the pipe determines the bandwidth: how much water can pass in a given time.

Latency and bandwidth problems are often encountered when searching the Web. If you wait a long time for a page to display and then it appears quickly, this indicates good bandwidth but high latency. On the other hand, if a page starts loading right away but takes a long time to load, that is a symptom of a low-latency, low-bandwidth connection.

Hash Tables versus Binary Search Trees

Important Compare and contrast a hash table and a binary search tree. If you were designing the address book data structure for a personal digital assistant (PDA. with limited memory, which one would you use?

A binary search tree can insert and retrieve in O(log(n)). This is fast, though not as fast as a hash table’s O(1). A binary search tree, however, also maintains its data in sorted order.

In a PDA, you want to keep as much memory as possible available for data storage. If you use an unordered data structure such as a hash table, you need additional memory to sort the values, as you undoubtedly want to display the values in alphabetical order. Therefore, if you use a hash table, you have to set aside memory for sorting that could otherwise be used as storage space.

If you use a binary search tree, you won’t have to waste memory or processing time on sorting records for display. Although binary tree operations are slower than hash table operations, a device like this is likely to have no more than about 10,000 entries, so a binary search tree’s O(log(n). lookup will undoubtedly be fast enough. For these reasons, a binary search tree is better suited for this kind of task than a hash table.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

Graph

Linked List

Dynamic Programming

Sorting And Searching

Tree / Binary Search Tree

Number Theory

BIT Manipulation

String / Array

Files

README.md

Latest commit

History

README.md

File metadata and controls

Graph

Linked List

Dynamic Programming

Sorting And Searching

Tree / Binary Search Tree

Number Theory

BIT Manipulation

String / Array