# Category Archives: Technical Interviews

Posts about technical interviews and prep.

# Objective

Given an array of distinct integers, use them to build a balanced binary search tree.

# Observations

1. The number of nodes in the left and right subtrees of a binary tree differ by at most 1.
2. Every node in the left subtree of a binary search tree is less than or equal to the value of the parent (root) node.
3. Every node in the right subtree of a binary search tree is greater than the value of the parent (root) node.
4. The root node of a balanced binary search tree is the middle value in the tree’s set of values.
5. The middle element of a sorted array corresponds to the root node of a binary search tree.
Code
``````import java.util.*;

/*
*	Given an array of distinct integers, use them to build a balanced binary search tree.
*/
class Solution {
/*
*	Node class for constructing a binary tree of integers.
*/
class Node {
private int data;
public Node left;
public Node right;

public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

/*
*	Build a binary search tree for a given range of indices. Called by {@link Solution#arrayToBalancedBST}.
*
*	@param int[] numbers An array of distinct integers sorted in ascending order.
*	@param int start The starting index for the smallest element in the BST.
*	@param int end The ending index for the largest element in the BST.
*
*	@return Node The root of the BST constructed from the given range of indices.
*/
private Node build(int[] numbers, int start, int end) {
System.err.println("Called build for range " + start + " to " + end);

Node root = null;

// If we can create at least one new node for the given range of indices
if (start <= end) {
// Get index of new parent/root node
int mid = (start + end) / 2;
root = new Node(numbers[mid]);
System.err.println("Created Node: " + root.data);

// This isn't super necessary but it saves 2 extra function
// calls for each leaf node that would return null
if (start != end) { // Comment this out to see the unnecessary calls
root.left = build(numbers, start, mid - 1);
root.right = build(numbers, mid + 1, end);
}
}

// Return the new root
return root;
}

/*
*	@return The root of a balanced binary search tree
*/
public Node arrayToBalancedBST(int[] numbers) {
// Sort numbers in ascending order
Arrays.sort(numbers);

return build(numbers, 0, numbers.length - 1);
}

/*
*	Prints an in-order tree traversal.
*/
public void inOrder(Node root) {
// Traverse all the way left
if (root.left != null) {
inOrder(root.left);
}

// Print current node
System.out.println("Traversed Node: " + root.data);

// Continue traversal with right subtree
if (root.right != null) {
inOrder(root.right);
}
}

/*
*	Driver function
*/
public static void run() {
Solution solution = new Solution();
int[] numbers = {5, 4, 7, 3, 2, 1, 6};
Node root = solution.arrayToBalancedBST(numbers);
solution.inOrder(root);
}

public static void main(String[] args) {
Solution.run();
}
}``````

# Objective

Given an array of integers, find the maximal sum of any subarray (contiguous block of integers) of the array.

# Observations

1. We want to find the largest sum of any contiguous sequence of integers in the array.
2. When calculating the running sum of a contiguous block of numbers, we don’t want to include a previously-calculated contiguous block that sums to a value that is less than the value stored at the current index. For example, if we have `nums = [1, -4, 1, 2]`, the sum of `nums0 + nums1 = 1 + -4 = -3` is less than the value of `nums2 = 1`, so we would not include a block consisting of indices `0` through `1` in our maximal contiguous block.
3. A subarray can sum to a maximal value but still contain negative values in its middle elements. For example, if we have `nums = [2, -1, 1, 2]`, our maximal sum comes from a subarray containing all elements of the array (`2 + -1 + 1 + 2 = 4`), which includes the negative value `nums1 = -1`.
Code
``````class Solution {
public int maximumSubarraySum(int[] nums) {
/* Case: Empty array */
if (nums.length == 0) {
return 0;
}

/* Case: One or more elements */
// Maximum sum of any subarray
int totalMax = nums[0];
// Maximum sum of current subarray
int currentMax = nums[0];

// This only runs if the array contains more than one element
// Note that this starts at index 1, because 'totalMax' and 'currentMax' were initialized to nums[0]
for (int i = 1; i < nums.length; i++) {
// Update running maximum for current subarray
currentMax = Math.max(
// If this is larger, new value simulates possible beginning of new subarray
nums[i],
// If this is larger, new value simulates continuing to sum existing subarray
currentMax + nums[i]
);

// Update maximum value of any subarray
totalMax = Math.max(currentMax, totalMax);
}

// Maximum subarray sum
}
}

public class MaximumSubarraySum {

public static void main(String[] args) {
Solution s = new Solution();
int[] nums = {-1, 5, 7, -20, 8, 4, -1, 2, -2};
int result = s.maximumSubarraySum(nums);
System.out.println(result);
}
}
``````

# Objective

Given the heads of two linked lists, find the node where they converge; if no such node is found, return `null` instead.

# Observations

1. To determine whether or not the two lists converge, we need to compare the nodes in the two lists.
2. The first node in either list that also appears on the other list is the node where the lists converge.
3. The two lists do not converge if they both contain distinct nodes.
Code
``````import java.util.*;

/**
*	Find the intersection point of two converging linked lists.
**/
class Solution {

/**
*
*	@return The number of nodes in the list
**/
public static int getLength(ListNode head) {
// List length
int length = 0;
// A pointer that walks through the list

// If the current node exists
while (tmp != null) {
// Increment the counter
length++;
// Move forward to next node
tmp = tmp.next;
}

// Return the length of the list
return length;
}

// Get the length of both lists

// Create pointers to reference the heads of both lists

// If list A is shorter, skip over the extra leading nodes in list B
while (lengthA < lengthB) {
lengthB--;
tmpB = tmpB.next;
} // End once the lists at the end of both pointers are the same length

// If list B is shorter, skip over the extra leading nodes in list A
while (lengthA > lengthB) {
lengthA--;
tmpA = tmpA.next;
} // End once the lists at the end of both pointers are the same length

// Now that both list heads are pointing to the same number of nodes,
// walk the pointers forward until they match
// We only need to check one node because the lists have the same length
while (tmpA != null) {
// If the two references point to the same node
if (tmpA == tmpB) {
// Return one of the references
return tmpA;
}

// Walk pointers forward
tmpA = tmpA.next;
tmpB = tmpB.next;
}

// No intersection found
return null;
}

/**
*
*	@return A reference to the node where the two lists converged
*			or null if they don't intersect
**/
// Pointers to the list heads

// A set of all the nodes in one of the lists
Set traversedNodes = new HashSet();

// Use one pointer to iterate through the first list
while (tmpA != null) {
// Add each node to the set
// Walk pointer forward
tmpA = tmpA.next;
}

// Use the other pointer to iterate through the second list
// to find the first already seen node
while (tmpB != null) {
// If current node was already seen when traversing listA
if (traversedNodes.contains(tmpB)) {
// The point of convergence was found, return the node
return tmpB;
}

// Walk pointer forward
tmpB = tmpB.next;
}

// No intersection found
return null;
}
}

class ListNode {
/* The data value stored within the node */
E data;
/* A reference to the next element in the list */
ListNode next;

ListNode(E data) {
this.data = data;
this.next = null;
}
}``````

# Objective

Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.

# Observations

1. We want to find two elements satisfying:
`element1 + element2 = value`
2. We need to find `element1` and `element2` within the array that satisfy the equation above (if they even exist), but `value` is known.
3. We can rearrange this equation as:
• `element1 = value - element2`
• `element2 = value - element1`
Code
``````import java.util.*;

class Solution {

/**
*	@param int[] nums An array of non-negative integers
*	@param int sum The value the pair of elements must sum to
*
*	@return The distinct pair of VALUES in the array whose corresponding
*			values sum to the value of 'sum', or [-1, -1] if not found.
**/
public static int[] twoSumValues(int[] nums, int sum) {
// Create a map of num elements to indices
Map numToIndex = new HashMap();

// Fill the map
for (int i = 0; i < nums.length; i++) {
// It doesn't matter if indices are overwritten
// because the final value will map to the largest index
numToIndex.put(nums[i], i);
}

// Iterate through values from smallest index to largest
// This ensures that overwritten values still match to later indices
// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
for (int i = 0; i < nums.length - 1; i++) {

// See if a match exists in map
Integer index = numToIndex.get(sum - nums[i]);

// If match exists and the second element's index is later than the first
if (index != null && index > i) {
// Return the pair of distinct indices
return new int[]{nums[i], nums[index]};
}
}

// No solution found
return new int[]{-1, -1};
}

/**
*	@param int[] nums An array of non-negative integers
*	@param int sum The value
*
*	@return The distinct pair of INDICES in the array whose corresponding
*			values sum to the value of 'sum', or [-1, -1] if not found.
**/
public static int[] twoSumIndices(int[] nums, int sum) {
// Create a map of num elements to indices
Map numToIndex = new HashMap();

// Fill the map
for (int i = 0; i < nums.length; i++) {
// It doesn't matter if indices are overwritten
// because the final value will map to the largest index
numToIndex.put(nums[i], i);
}

// Iterate through values from smallest index to largest
// This ensures that overwritten values still match to later indices
// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
for (int i = 0; i < nums.length - 1; i++) {

// See if a match exists in map
Integer index = numToIndex.get(sum - nums[i]);

// If match exists and the second element's index is later than the first
if (index != null && index > i) {
// Return the pair of distinct indices
return new int[]{i, index};
}
}

// No solution found
return new int[]{-1, -1};
}
}``````

# Objective

Given a string of characters, determine whether or not some permutation of the string creates a palindrome.

# Observations

1. A palindrome is a word that reads the same forward as it does backward.
2. We can use a sequence of characters to build a palindrome if either of the following conditions are satisfied:
• Each character occurs an even number of times.
• Each character occurs an even number of times except for one character.
Code
``````import java.util.*;

class Solution {
/**
*	@param String s The string to check
*	@return true if the string can be permuted into a palindrome
**/
public static boolean hasPalindromicPermutation(String s) {
// Create a set to hold unmatched characters
Set unmatched = new HashSet();

for (int i = 0; i < s.length(); i++) {
// The current character
char c = s.charAt(i);

// If the character exists in the set, remove it
if (unmatched.contains(c)) {
unmatched.remove(c);
}
// Character is unmatched, add it to the set
else {