Get All Possible Substrings of A String

I had to write this by hand at an interview with a local company. Pretty sure I aced it.

Given a string, write a method to return all possible substrings of the string.

Solution: Complexity O(n^2).

Find An Index In Array Such That A[i] = i

Book: Cracking the Coding Interview
Question: 9.3 (page 109)

A magic index in array A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted array, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if values are not distinct?

Solution: Complexity - O(log(n))

Swap Numbers In Place

Book: Cracking the Coding Interview
Question: 17.1 (page 163)

Write a function to swap [two numbers] in place (that is, without temporary variables)

Solution: Simple arithmetic trick. Also could be done using XOR (not sure if works with negative values, though.).

Longest Increasing Sequence with Pairs

Book: Cracking the Coding Interview
Question: 11.7 (page 122)

A circus is designing a tower routine consisting of people standing top one another's shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom:
(56, 90) (60, 95) (65, 100) (68, 110) (70, 150) (75, 190)

Solution: Complexity - O(n^2)

Find String in Array Interspersed with Empty Strings

Book: Cracking the Coding Interview
Question: 11.5 (page 121)

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
EXAMPLE:
Input: find "ball" in {"at", "", "", "", "ball", "", "car", "", "", "dad", "", ""}
Output: 4

Solution: Average case: O(log(n)), Worst case: O(n/2) => O(n)

Sort by Anagrams

Book: Cracking the Coding Interview
Question: 11.2 (page 121)

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

Solution: Complexity - O(nlogn) [because of TreeMap]

Merge B into A

Book: Cracking the Coding Interview
Question: 11.1 (page 121)

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

Solution: Complexity - O(n)

Find Successor Of a Node

Book: Cracking the Coding Interview
Question: 4.6 (page 86)

Write an algorithm to find the 'next' node (i.e, in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

Solution: Complexity - O(n) in the worst case. Did not test the below code; it makes sense and it should work fine.

Sorted Array to Binary Search Tree

Book: Cracking the Coding Interview
Question: 4.3 (page 86)

Given a sorted (increasing order) array, write an algorithm to create a binary search tree with minimal height.

Solution: Complexity - O(n)

Find Out Whether There Is a Route Between Two Nodes

Book: Cracking the Coding Interview
Question: 4.2 (page 86)

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Solution: Complexity - O(V+E)

Set Row and Column to Zero if Element is Zero

Book: Cracking the Coding Interview
Question: 1.7 (page 73)

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

Solution: Complexity - O(M*N), Space - O(M+N)

String Compression

Book: Cracking the Coding Interview
Question: 1.5 (page 73)

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string "aabcccccaaa" would become "a2b1c5a3". If the "compressed" string would not become the smaller than the original string, your method should return the original string.

Solution: Complexity - O(n)

String Permutations

Book: Cracking the Coding Interview
Question: 1.3 (page 73)

Give two strings, write a method to decide if one is a permutation of the other.

Solution: Complexity - O(n), Space - O(n)

Determine If String Has All Unique Characters

Book: Cracking the Coding Interview
Question: 1.1 (page 73)

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

Solution 1: Complexity - O(n), Space - O(1)
Solution 2: Complexity - O(n), Space - O(n)