Smart Cities Initiative for Youth: Solving Urban Challenges Workshop on 5/19 and 5/20

My friend Cindy and some of her LinkedIn coworkers are starting a nonprofit named Sci-Fy (Smart Cities Initiative for Youth) to educate high-school students about the importance of living in places that encourage economic prosperity, health, and a sense of community. They’re hosting a Solving Urban Challenges workshop at LinkedIn headquarters in San Francisco on May 19th and 20th from 9am to 5pm for teens in 9th to 12th grade. At this workshop, students will:

• Learn about the pillars of a sustainable city
• Conduct case studies on smart and sustainable cities around the world
• Interact with city and industry professionals that are working on solving urban challenges
• Form their own solution to an urban challenge facing their community!

To participate, teens in 9th to 12th grade must apply before 11:59pm on April 21st at www.sci-fy.org.

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;
// Maximum sum of current subarray
int currentMax = nums;

// 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
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 {
}
}

// For the string to be a palindrome, only 0 or 1 character can be unmatched
return (unmatched.size() < 2);
}
}``````

How can I run my code?

One of the difficult things about learning to code is figuring out how to run your code; when you’re able to connect what you’re writing to what it produces (or doesn’t produce), it can go a long way toward making many programming concepts click a lot sooner. This page lists tools that I find super helpful.

CodeRunner

This programming editor makes it quick and easy to write and run code in a lot of different languages (which is especially helpful when you’re learning something new, or when you need to demo some small piece of code). It’s very customizable, and it’s a single button click to add arguments, compile flags, and program input. CodeRunner is only about \$15, and I’ve more than gotten my money’s worth over the years I’ve been using it. Try it or buy it at coderunnerapp.com.

I was watching the Flutter presentation video from I/O 17 and thought it was pretty awesome, so I resolved to learn Dart (a very Java-like language used to make apps in Flutter). Google has a really great From Java to Dart tutorial, and they also have a web-based editor named DartPad for you to experiment with as you learn the language. For larger projects, the recommended editor is IntelliJ, which has a Dart plugin (note: you must install the plugin to create Dart projects).

Javadoc: Setting the @author Name in Eclipse

If Eclipse isn’t generating Javadocs that have the `@author` name you want displayed, this should help.

Mac OS

1. Navigate to the Applications > eclipse folder.
2. Right click on the eclipse application launcher and choose the `Show Package Contents` option. 3. Navigate to the Contents > Eclipse folder and open the `eclipse.ini` file in the editor of your choice. 4. In the `eclipse.ini` file, find `-vmargs` and add the line `-Duser.name=atebitbyte` underneath it, where atebitbyte is the name you want displayed (e.g., `@author atebitbyte`) when you generate Javadoc comments.
5. Save the file, reopen Eclipse, and any future comments should have the new author name.

Modifying Comment Templates

Another way to modify the comment templates is to open the Eclipse > Preferences… menu and go to Java > Code Style > Code Templates. You can write and export your own custom templates, or import a template you made previously. Installing Eclipse Luna on Ubuntu

I wrote this a few years ago and am mainly posting it for testing and my own reference. I’ll probably update it eventually.

Download and extract eclipse. It should be in your downloads folder with the name `eclipse-cpp-luna-SR1a-linux-gtk-x86_64.tar.gz`

Steps and Notes: Terminal Commands:
Update Repositories `sudo apt-get update`
Install Java `sudo apt-get install openjdk-7-jdk`
Change to user directory `cd ~`
Move eclipse package to /opt directory `sudo mv Downloads/eclipse-cpp-luna-SR1a-linux-gtk-x86_64.tar.gz /opt/`
Change to /opt directory `cd /opt`
Unzip the eclipse package `sudo tar -xvf eclipse-cpp-luna-SR1a-linux-gtk-x86_64.tar.gz`
Create a desktop entry: `cd ~/../../usr/share/applications`
Create a file called eclipse.desktop in the applications directory. `sudo touch eclipse.desktop`

Edit the file; if vim is not already installed, you may need to type:
sudo apt-get-install vim to install it.

`sudo vim eclipse.desktop`
Type i, which is the insert key and will allow you to begin typing into your file. `i`
File Contents:

`[Desktop Entry]`

`Name=Eclipse`
`Type=Application`
`Exec=/opt/eclipse/eclipse`
`Terminal=false`
`Icon=/opt/eclipse/icon.xpm`
`Comment=Integrated Development Environment`
`NoDisplay=false`
`Categories=Development;IDE;`
`Name[en]=eclipse`

Hit the escape key, then w (write), then (quit), and hit enter/return.

`esc+wq+enter`

Install the desktop file.

Failure to include the [Desktop Entry] group header at the top of the eclipse.desktop file will cause this command to give the error message: Error on file “eclipse.desktop”: Key file does not start with a group

`sudo desktop-file-install eclipse.desktop`

Eclipse is now installed.

More on desktop entries.

More on desktop-file-install.