# Software Engineer
# Problems
# Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
```
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
```
```
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
```
{% tabs %}
{% tab title="Scala" %}
```scala
trait TreeNode {
def value: Int
def left: TreeNode
def right: TreeNode
}
object EmptyNode extends TreeNode {
def value = throw new Error("accessing empty node")
def left = throw new Error("accessing empty node")
def right = throw new Error("accessing empty node")
}
class NoneEmptyNode(var value: Int, var left: TreeNode = EmptyNode, var right: TreeNode = EmptyNode) extends TreeNode
def lowestCommonAncestor(root:TreeNode, p:TreeNode, q:TreeNode):TreeNode = {
if (root == EmptyNode || root == p || root == q) return root
val left:TreeNode = lowestCommonAncestor(root.left, p, q)
val right:TreeNode = lowestCommonAncestor(root.right, p, q)
if (left != EmptyNode && right != EmptyNode) root
else if (left != EmptyNode) right
else left
}
```
{% endtab %}
{% tab title="Python" %}
```python
def lowestCommonAncestor(root, p, q):
if p is root or q is root or not root:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
```
{% endtab %}
{% endtabs %}
# Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable.HashMap
def lengthOfLongestSubstring(s: String): Int = {
var map = new HashMap[Char, Int]
var j, k, length = 0
for ((c, i) <- s.zipWithIndex) {
k = map.get(c).getOrElse(j)
j = j max k
length = length max i - j
map += (c -> i)
}
length
}
lengthOfLongestSubstring("")
lengthOfLongestSubstring("pwwkew")
lengthOfLongestSubstring("bbbbb")
lengthOfLongestSubstring("abcabcbb")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.annotation.tailrec
/**
* find longest palindrome (length only)
*
* @param s
* @return
*/
def longestPalindromeLength(s: String): Int = {
@tailrec def check(prev: Int, next: Int, acc: Int): Int = {
if (prev < 0 || next >= s.length || s(prev) != s(next)) acc
else check(prev - 1, next + 1, acc + 2)
}
var maxLength = 0
for (i <- 0 until s.length) {
// check odd length and even length
maxLength = maxLength max check(i, i, -1) max check(i, i + 1, 0)
}
maxLength
}
longestPalindromeLength("")
longestPalindromeLength("a")
longestPalindromeLength("bab")
longestPalindromeLength("baab")
/**
* find longest palindrome (substring)
*
* @param s
* @return
*/
def longestPalindrome(s: String): String = {
@tailrec def check(prev: Int, next: Int, acc: Int): Int = {
if (prev < 0 || next >= s.length || s(prev) != s(next)) acc
else check(prev - 1, next + 1, acc + 2)
}
var maxLength, length, index = 0
for (i <- 0 until s.length) {
length = check(i, i, -1) max check(i, i + 1, 0)
maxLength = maxLength max length
if (length == maxLength) index = i
}
// recover string from index and length
val diff = maxLength / 2
maxLength match {
case l if l % 2 == 0 => s.subSequence(index - diff + 1, index + diff + 1).toString
case _ => s.subSequence(index - diff, index + diff + 1).toString
}
}
longestPalindrome("bananas")
longestPalindrome("abracadabra")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
{% tabs %}
{% tab title="First Tab" %}
```scala
def longestCommonPrefix(strs: Array[String]):String = {
if (strs.length == 0) ""
else {
strs.reduceRight((s1,s2) => {
val l = s1.length min s2.length
var i = 0
while (i < l && s1(i) == s2(i)) {
i += 1
}
s1.take(i)
})
}
}
longestCommonPrefix(Array())
longestCommonPrefix(Array("a"))
longestCommonPrefix(Array("abc","abcdef","abpoiuyt"))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
```
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
```
Note: You may assume both s and t have the same length.
{% tabs %}
{% tab title="Scala" %}
```scala
def isIsomorphic(s: String, t: String): Boolean = {
if (s.length != t.length) false
else if (s.length == 0) true
else {
var mapping = Map[Char, Char]()
for (i <- 0 until s.length) {
mapping.get(s(i)) match {
case Some(j) => {
if (j != t(i)) return false
}
case None =>
mapping += (s(i) -> t(i))
}
}
true
}
}
isIsomorphic("egg", "add")
isIsomorphic("foo", "bar")
isIsomorphic("paper", "title")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
{% tabs %}
{% tab title="Scala" %}
```scala
val M = Array("", "M", "MM", "MMM")
val C = Array("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
val X = Array("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
val I = Array("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")
/**
*
* @param num
* @return
*/
def intToRoman(num: Int):String = {
if (num < 0 || num > 3999) throw new Error("out of range")
else {
M(num/1000) + C((num%1000)/100) + X((num%100)/10) + I(num%10)
}
}
intToRoman(3745)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Frog Jump
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog has just jumped k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
Note:
The number of stones is ≥ 2 and is < 1,100. Each stone's position will be a non-negative integer < 231. The first stone's position is always 0.
**Example 1:**
> \[0,1,3,5,6,8,12,17]
```
There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.
Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
```
**Example 2:**
> \[0,1,2,3,4,8,9,11]
```
Return false. There is no way to jump to the last stone as
the gap between the 5th and 6th stone is too large.
```
{% tabs %}
{% tab title="Scala" %}
```scala
def canCross(stones: Array[Int]): Boolean = {
def steps(pos: Int = 0, step: Int = 1): Boolean = {
if (pos == stones.length - 1) true
else {
val pivot = stones(pos) + step
for (i <- pos + 1 until stones.length if stones(i) <= pivot + 1 && stones(i) >= pivot - 1) {
if (steps(i, stones(i) - stones(pos))) return true
}
false
}
}
steps()
}
canCross(Array(0,1,3,5,6,8,12,17))
canCross(Array(0,1,2,3,4,8,9,11))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Find the Difference
Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s and then add one more letter at a random position.
Find the letter that was added in t.
Example:
Input:
> s = "abcd" t = "abcde"
Output:
> e
Explanation:
> 'e' is the letter that was added.
{% tabs %}
{% tab title="Scala" %}
```scala
def findTheDifference(s: String, t: String):Char = {
var acc = t(t.length-1)
for (i <- 0 until s.length) {
acc ^= s(i) ^ t(i)
}
acc
}
findTheDifference("abcd", "abcde")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Find k closest elements to a given value
Given a sorted array arr\[] and a value X, find the k closest elements to X in arr\[].
Examples:
Input:
> K = 4
> X = 35
> arr\[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}
Output:
> 30 39 42 45
Note that if the element is present in array, then it should not be in output, only the other closest elements are required.
{% tabs %}
{% tab title="Scala" %}
```scala
def findKClosest(arr: Array[Int], target: Int, k: Int): List[Int] = {
def findClosest(start: Int, end: Int): Int = {
val mid = (start + end) / 2
arr(mid) match {
case m if m == target || (m < target && arr(mid + 1) > target) => mid
case m if m > target => findClosest(start, mid - 1)
case m if m < target => findClosest(mid + 1, start)
}
}
if (k <= 0) Nil
else {
var lst: List[Int] = Nil
val m = findClosest(0, arr.length - 1)
var (l, r) = (m, m + 1)
// excludes numbers equal to target
while (l >= 0 && arr(l) == target) l -= 1
while (r < arr.length && arr(r) == target) r += 1
// select left/right closest
while (lst.length < k && l >= 0 && r < arr.length) {
if (target - arr(l) < arr(r) - target) {
lst = arr(l) :: lst
l -= 1
} else {
lst = arr(r) :: lst
r += 1
}
}
// select left/right closest if l < 0/r >= arr.length
while (lst.length < k && r < arr.length) {
lst = arr(r) :: lst
r += 1
}
while (lst.length < k && l >= 0) {
lst = arr(l) :: lst
l -= 1
}
lst
}
}
val arr = Array(12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56)
findKClosest(arr, 35, 4)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Longest Common Subsequence
Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
{% tabs %}
{% tab title="Scala" %}
```scala
def lcs(s: String, t: String): Int = {
val (m, n) = (s.length, t.length)
val table = Array.ofDim[Int](s.length + 1, t.length + 1)
for (i <- 0 to m) {
for (j <- 0 to n) {
if (i == 0 || j == 0) 0
else if (s(i - 1) == t(j - 1)) table(i)(j) = table(i - 1)(j - 1) + 1
else table(i)(j) = table(i - 1)(j) max table(i)(j - 1)
}
}
table(m)(n)
}
lcs("AGGTAB", "GXTXAYB")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Binary Search Tree from Sorted Array
Given a sorted array, write an algorithm to create a binary search tree with minimal height
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable
trait BTree
object Empty extends BTree
case class Node(var value: Int, var left: BTree = Empty, var right: BTree = Empty) extends BTree
def printBTree(root: BTree): Unit = {
val queue = mutable.Queue[(BTree, Int)]((root, 0))
var prev = -1
while (!queue.isEmpty) {
val (node, level) = queue.dequeue()
node match {
case n: Node => {
if (level != prev) {
print("\n#")
prev = level
}
print(n.value)
queue.enqueue((n.left, level + 1))
queue.enqueue((n.right, level + 1))
}
case _ =>
}
}
}
/**
* 4.3
*
* @param arr
* @return
*/
def buildTree(arr: Array[Int]): BTree = {
buildTreeRange(arr, 0, arr.length - 1)
}
def buildTreeRange(arr: Array[Int], start: Int, end: Int): BTree = {
if (arr.length == 0 || end < start) Empty
else {
val mid: Int = (end + start) / 2
val node: Node = Node(arr(mid))
node.left = buildTreeRange(arr, start, mid - 1)
node.right = buildTreeRange(arr, mid + 1, end)
node
}
}
val root = buildTree(Array(1, 2, 3, 4))
printBTree(root)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Balanced Binary Tree
Implement a function to check if a binary tree i balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable
trait BTree
object Empty extends BTree
case class Node(var value: Int, var left: BTree = Empty, var right: BTree = Empty) extends BTree
def printBTree(root: BTree): Unit = {
val queue = mutable.Queue[(BTree, Int)]((root, 0))
var prev = -1
while (!queue.isEmpty) {
val (node, level) = queue.dequeue()
node match {
case n: Node => {
if (level != prev) {
print("\n#")
prev = level
}
print(n.value)
queue.enqueue((n.left, level + 1))
queue.enqueue((n.right, level + 1))
}
case _ =>
}
}
}
/**
* 4.1
*
* @param root
* @return
*/
def isBalanced(root: BTree): Boolean = {
def depth(node: BTree): Int = {
node match {
case Empty => 0
case n: Node => {
val (left, right) = (depth(n.left), depth(n.right))
if (left == -1 || right == -1 || math.abs(left - right) > 1) -1
else (left max right) + 1
}
}
}
depth(root) != -1
}
val a = Node(1, Empty, Empty)
val b = Node(2, Empty, Empty)
val c = Node(3, a, b)
isBalanced(Empty)
isBalanced(c)
val e = Node(4, Empty, a)
val d = Node(5, Empty, e)
val f = Node(5, Empty, d)
isBalanced(f)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Sort Using Two Stacks
Write a program to sort a stack using additional stacks but no other data structures
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable.Stack
/**
* 3.6
* @param s1
* @return
*/
def sort(s1:Stack[Int]): Stack[Int] = {
val s2 = Stack[Int]()
while (!s1.isEmpty) {
val tmp = s1.pop()
while (!s2.isEmpty && s2.head < tmp) {
s1.push(s2.pop())
}
s2.push(tmp)
}
s2
}
val s = Stack[Int]()
s.push(3)
s.push(9)
s.push(5)
val s3 = sort(s)
while (!s3.isEmpty) {
println(s3.pop())
}
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# O(1) Stack
How would you design a stack which, in addition, to push and pop, also has a function min which returns the minimum element?
Push, pop and min should all operate in O(1) time.
{% tabs %}
{% tab title="Scala" %}
```scala
/**
* 3.2
* @param value
* @param min
*/
case class Frame(value: Int, min: Int)
class Stack {
var elems:List[Frame] = Nil
def push(elem: Int): Unit = this.elems = this.elems match {
case Nil => Frame(elem, elem) :: this.elems
case _ => Frame(elem, elems.head.min min elem) :: this.elems
}
def pop: Int = this.elems match {
case Nil => -1
case x :: xs => {
this.elems = xs
x.value
}
}
def min: Int = this.elems match {
case Nil => -1
case x :: xs => x.min
}
}
val s = new Stack
s.push(5)
s.push(3)
s.push(99)
s.min
s.pop
s.pop
s.min
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# k-th element to last of a LinkedList
Implement an algorithm to find the kth to last element of a singly linked list
{% tabs %}
{% tab title="Scala" %}
```scala
trait Node {
def value: Int
def next: Node
}
object Empty extends Node {
def value: Int = throw new Error("access empty variable")
def next: Node = throw new Error("access empty variable")
}
case class NonEmpty(val value: Int, val next: Node = Empty) extends Node
def toLinkedList(lst: List[Int]): Node = {
if (lst.isEmpty) Empty
else new NonEmpty(lst.head, toLinkedList(lst.tail))
}
def printLinkedList(head: Node): Unit = head match {
case Empty =>
case node: NonEmpty => {
println(node.value)
printLinkedList(node.next)
}
}
/**
* 2.2
*
* @param head
* @param k
* @return
*/
def kthElement(head: Node, k: Int): Node = head match {
case Empty => head
case node: NonEmpty =>
if (node.next == Empty) Empty
else {
var slow = head
var fast = head.next
for (i <- 0 until k - 1 if fast != Empty) {
fast = fast.next
}
while (fast != Empty) {
slow = slow.next
fast = fast.next
}
slow
}
}
var node = kthElement(toLinkedList(List(1, 2, 3)), 3)
node.value
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Dedup LinkedList
Write code to remove duplicates from an unsorted linked list
FOLLOW UPHow would you solve this problem if a temporary buffer is not allowed
{% tabs %}
{% tab title="Scala" %}
```scala
trait Node {
def value: Int
def next: Node
}
object Empty extends Node {
def value: Int = throw new Error("access empty variable")
def next: Node = throw new Error("access empty variable")
}
case class NonEmpty(value: Int, next: Node = null) extends Node
def toLinkedList(lst: List[Int]): Node = {
if (lst.isEmpty) Empty
else new NonEmpty(lst.head, toLinkedList(lst.tail))
}
def printLinkedList(head: Node): Unit = head match {
case Empty =>
case node: NonEmpty => {
println(node.value)
printLinkedList(node.next)
}
}
/**
* 2.1
*
* @param head
* @return
*/
def deduplicate(head: Node): Node = {
val dict = scala.collection.mutable.Map[Int, Boolean]()
def dedup(node: Node): Node = {
node match {
case Empty => Empty
case current: NonEmpty => {
dict.get(current.value) match {
case Some(value) => dedup(current.next)
case None => {
dict += (current.value -> true)
new NonEmpty(current.value, dedup(current.next))
}
}
}
}
}
dedup(head)
}
var node = toLinkedList(List(1, 2, 3, 4, 4, 5, 6, 6))
printLinkedList(deduplicate(node))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Check Rotated String
Find if a string is a rotation of another by using only one substring call
{% tabs %}
{% tab title="Scala" %}
```scala
def isRotation(s1: String, s2: String):Boolean = {
if (s1.length != s2.length) false
else s1.concat(s1) contains s2
}
isRotation("waterbottle", "erbottlewat")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Compress String by Character Count
Compress string by character count
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.annotation.tailrec
// compress to list of tuples
def compress(str: String):List[(Char, Int)] = str match {
case "" => Nil
case _ => {
val (x,xs) = str span (c => c == str.head)
(str.head, x.length) :: compress(xs)
}
}
// compress to string
def compressString(str: String):String = {
val sb = new StringBuilder
@tailrec def compress(s: String):Unit = {
if (!s.isEmpty) {
val (x,xs) = s span (c => c == s.head)
sb.append(s.head)
sb.append(x.length.toString)
compress(xs)
}
}
compress(str)
sb.toString
}
// compress in-place using char array
def compressInPlace(ch: Array[Char]):Unit = {
var prev = ch.head
var count = 1
var write = 0
for (c <- ch.tail) {
c match {
case c if c == prev => count += 1
case _ => {
ch(write) = prev
if (count > 1) {
for (j <- count.toString) {
ch(write+1) = j
write += 1
}
}
write += 1
count = 1
prev = c
}
}
}
ch(write) = prev
if (count > 1) ch(write+1) = count.toChar
ch(write+1) = '\0'
}
// initialize string
val s = "aabccccccccccccccccccccccccccccccccccccccccccaaad"
compress(s)
compressString(s)
val ch = Array.fill(50){' '}
for (i <- 0 until s.length) {
ch(i) = s(i)
}
compressInPlace(ch)
ch.mkString("").substring(0,ch.indexOf('\0'))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Escape HTML whitespace
Escape white space with %20 in place
{% tabs %}
{% tab title="Scala" %}
```scala
def htmlEncode(ch: Array[Char]) = {
var spaces = 0
for (c <- ch) {
if (c == ' ')
spaces += 1
}
val newLength = ch.length + 2 * spaces
ch(newLength) = '\0'
for (i <- ch.length - 1 to 0 by -1) {
if (ch(i) == ' ') {
ch(newLength - 1) = ch(i)
ch(newLength - 2) = ch(i - 1)
ch(newLength - 3) = ch(i - 2)
newLength - 3
} else {
ch(newLength - 1) = ch(i)
newLength - 1
}
}
}
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Check String Permutation
Given two strings, write a method to decide if ones is a permutation of the other
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable.Map
def isPermutation(s1: String, s2: String): Boolean = {
if (s1.length != s2.length) false
else if (s1.isEmpty) true
else {
val charMap = Map[Char, Int]() withDefaultValue 0
for (i <- 0 until s1.length; j <- 0 until s2.length) {
charMap(s1(i)) += 1
charMap(s2(j)) -= 1
}
charMap.values.forall(_ == 0)
}
}
isPermutation("", "")
isPermutation("abcd", "dcba")
isPermutation("abcd", "ecba")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Unique String
Implement an algorithm to determine if a string has all unique characters,What if you cannot use additional data structures?
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable.Map
def uniqueWithMap(s:String): Boolean = {
val charMap = Map[Char, Int]()
for (i <- 0 until s.length) {
charMap.get(s(i)) match {
case Some(j) => return false
case None => charMap += (s(i) -> i)
}
}
true
}
def uniqueWithBitMask(s:String): Boolean = {
var code_pt,checker = 0
for (i <- 0 until s.length) {
code_pt = 1 << (s(i).toInt - 'a'.toInt)
if ((checker & code_pt) > 0) return false
checker |= code_pt
}
true
}
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Container With Most Water
Given an array S of n integers, are there elements a, b, c in S \
such that a + b + c = 0? \
\
Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array
> S = \[-1, 0, 1, 2, -1, -4]
A solution set is:
> ```
> [ [-1, 0, 1], [-1, -1, 2] ]
> ```
{% tabs %}
{% tab title="Scala" %}
```scala
/**
*
* @param height
* @return
*/
def maxArea(height: Array[Int]):Int = {
var i,j,lvl,vol: Int = 0
j = height.length - 1
while (i < j) {
lvl = height(i) min height(j)
vol = vol max lvl * (j-i)
while (i <= j && height(i) <= lvl) i += 1
while (j >= 0 && height(j) <= lvl) j -= 1
}
vol
}
maxArea(Array())
maxArea(Array(1,1))
maxArea(Array(1,1,5,2,3))
maxArea(Array(1,1,3,2,5))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# 4 Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
> Note: The solution set must not contain duplicate quadruplets.
For example, given array
> S = \[1, 0, -1, 0, -2, 2]
and
> target = 0
A solution set is:
> ```
> [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
> ```
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.util.Sorting.quickSort
def fourSum(nums: Array[Int], target: Int):List[(Int,Int,Int,Int)] = {
quickSort(nums)
var ret:List[(Int,Int,Int,Int)] = Nil
for (i <- 0 until nums.length) {
for (j <- i + 1 until nums.length) {
// fixed first two indexes
var (k,l) = (j + 1, nums.length - 1)
while (k < l) {
nums(i)+nums(j)+nums(k)+nums(l) match {
case sum if sum == target => {
val tup = (nums(i),nums(j),nums(k),nums(l))
// check duplicate
if (ret.isEmpty || tup != ret.head) {
ret = tup :: ret
}
l -= 1
k += 1
}
case sum if sum > target => l -= 1
case sum if sum < target => k += 1
}
}
}
}
ret
}
fourSum(Array(1, 0, -1, -1, 0, -2, 2), 0)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# 3 Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array
> S = {-1 2 1 -4}, and target = 1
The sum that is closest to the target is 2.
> (-1 + 2 + 1 = 2)
{% tabs %}
{% tab title="Scala" %}
```scala
def threeSumClosest(nums: Array[Int], target: Int): Int = {
nums.length match {
case l if l < 3 => throw new Error("not enough numbers")
case l if l == 3 => nums.sum
case _ => {
scala.util.Sorting.quickSort(nums)
var ret = Int.MaxValue
for (i <- 0 until nums.length) {
var j = i + 1
var k = nums.length - 1
while (j < k) {
val current = nums(j) + nums(k) + nums(i)
if (current == target) return target
else if (math.abs(current - target) < math.abs(ret - target)) {
ret = current
}
if (current > target) k -= 1
if (current < target) j += 1
}
}
ret
}
}
}
threeSumClosest(Array(1, 2, 3), 9)
threeSumClosest(Array(23, 3, 5, 1, 2), 9)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# 3 Sum
Given an array S of n integers, are there elements a, b, c in S such that \
a + b + c = 0? \
\
Find all unique triplets in the array which gives the sum of zero.
> Note: The solution set must not contain duplicate triplets.
For example, given array
> S = \[-1, 0, 1, 2, -1, -4]
A solution set is:
> ```
> [ [-1, 0, 1], [-1, -1, 2] ]
> ```
{% tabs %}
{% tab title="Scala" %}
```scala
def threeSum(nums: Array[Int]):List[(Int,Int,Int)] = {
scala.util.Sorting.quickSort(nums)
var i,j,k,target: Int = 0
j = nums.length - 1
var ret = List[(Int,Int,Int)]()
for (i <- 0 until nums.length) {
k = i + 1
j = nums.length - 1
target = 0 - nums(i)
while (k < j) {
nums(j) + nums(k) match {
case n if n == target => {
ret = Tuple3(nums(i),nums(k),nums(j)) :: ret
while (k < j && nums(k) == nums(k+1)) k += 1
while (k < j && nums(j) == nums(j-1)) j -= 1
j -= 1
k += 1
}
case n if n > target => j -= 1
case n if n < target => k += 1
}
}
}
ret
}
threeSum(Array(0,-1,2,3,4,5,6,1))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# 2 Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
> nums = \[2, 7, 11, 15]\
> target = 9
returns
> \[0, 1]
because nums\[0] + nums\[1] = 2 + 7 = 9.
UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
{% tabs %}
{% tab title="Python" %}
```python
def twoSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
memo = {}
for i in range(len(nums)):
compliment = memo.get(nums[i])
if compliment != None:
return [compliment, i]
memo[target-nums[i]] = i
```
{% endtab %}
{% tab title="Javascript" %}
```javascript
// @flow
const twoSum = (nums: ?number[], target: number) => {
var memo: {
[compliment: number]: number
} = {}
if (nums == null) return null;
for (var i = 0; i < nums.length; i++) {
if (memo[nums[i]] != null) {
return [memo[nums[i]], i]
}
memo[target - nums[i]] = i
}
}
```
{% endtab %}
{% endtabs %}
# Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
> \[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray
> \[4,-1,2,1]
has the largest sum = 6.
{% tabs %}
{% tab title="Scala" %}
```scala
def maxSubArray(nums: Array[Int]): Int = {
var sum = nums.head
var maxSum = nums.head
for (i <- nums) {
sum = i max sum + i
maxSum = sum max maxSum
}
maxSum
}
val nums = Array(-2, 1, -3, 4, -1, 2, 1, -5, 4)
maxSubArray(nums)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Nested List Weight Sum
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1: Given the list
> \[\[1,1],2,\[1,1]]
return
> 10 (four 1's at depth 2, one 2 at depth 1)
Example 2: Given the list
> \[1,\[4,\[6]]]
return
> 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)
{% tabs %}
{% tab title="Scala" %}
```scala
trait NestedItem {
def getInt: Int
def getList: List[NestedItem]
}
class NestedInt(value: Int) extends NestedItem {
def getInt: Int = value
def getList: List[NestedItem] = throw new Error("get list from int")
}
class NestedList(value: List[NestedItem]) extends NestedItem {
def getInt: Int = throw new Error("get int from list")
def getList = value
}
def depthSum(nestedList: List[NestedItem], depth: Int = 1): Int = {
var sum = 0
for (item <- nestedList) {
item match {
case i: NestedInt => sum += i.getInt * depth
case lst: NestedList => sum += depthSum(lst.getList, depth + 1)
}
}
sum
}
def wrap(lst: List[Any]): NestedList = {
new NestedList(lst.map((item) => item match {
case i: Int => new NestedInt(i)
case l: List[Any] => wrap(l)
}))
}
val test1 = wrap(List(List(1, 1), 2, List(1, 1)))
depthSum(test1.getList)
val test2 = wrap(List(1, List(4, List(6))))
depthSum(test2.getList)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
{% tabs %}
{% tab title="Scala" %}
```scala
def isPalindrome(x: Int): Boolean = {
if (x < 0 || (x != 0 && x % 10 == 0)) false
else {
var _x = x
var res = 0
while (x > res) {
res = res * 10 + _x % 10
_x /= 10
}
x == res || x == res / 10
}
}
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Pow(x, n)
Implement pow(x, n).
{% tabs %}
{% tab title="Scala" %}
```scala
def myPow(_x: Double, _n: Int): Double = {
var (x, n) = (_x, _n)
if (x == 0) 0
if (n == 0) 1
else {
if (n < 0) {
x = 1 / x
n = -n
}
var pow = 1
while (n > 0) {
if ((n & 1) == 1) {
pow *= x
}
x *= x
n <<= 1
}
pow
}
}
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Regular Expression Matching
Implement regular expression matching with support for '.' and '\*'.
'.' Matches any single character. '\*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be: bool isMatch(const char \*s, const char \*p)
Some examples:
```
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
```
{% tabs %}
{% tab title="Scala" %}
```scala
def isMatch(s: String, p: String): Boolean = {
if (s.isEmpty) true
else if (p.isEmpty) false
else if (p.length >= 2 && p(1) == '*') {
if (p.head == '.' || s.head == p.head) {
isMatch(s.tail, p.substring(2)) || isMatch(s.tail, p)
}
else isMatch(s, p.substring(2))
}
else {
if (p.head == '.' || s.head == p.head) {
isMatch(s.tail, p.tail)
}
else false
}
}
isMatch("aa", "a")
isMatch("aa", "aa")
isMatch("aaa", "aa")
isMatch("aa", "a*")
isMatch("aa", ".*")
isMatch("ab", ".*")
isMatch("aab", "c*a*b")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Remove Nth Node From End of List
Similar to \[k-th element to last of a LinkedList]\({% post\_url 2016-09-07-cci-2-2 %})
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list:
> 1->2->3->4->5
and
> n = 2
After removing the second node from the end, the linked list becomes
> 1->2->3->5
Note: Given n will always be valid. Try to do this in one pass.
{% tabs %}
{% tab title="Scala" %}
```scala
trait Node {
def value: Int
def next: Node
}
object Empty extends Node {
def value: Int = throw new Error("access empty variable")
def next: Node = throw new Error("access empty variable")
}
class NonEmpty(var value: Int, var next: Node = Empty) extends Node
def toLinkedList(lst: List[Int]): Node = {
if (lst.isEmpty) Empty
else new NonEmpty(lst.head, toLinkedList(lst.tail))
}
def printLinkedList(head: Node): Unit = head match {
case Empty =>
case node: NonEmpty => {
println(node.value)
printLinkedList(node.next)
}
}
/**
* @param head
* @param k
* @return
*/
def removeNthElement(head: Node, k: Int):Node = head match {
case Empty => head
case node: NonEmpty =>
if (node.next == Empty) Empty
else {
var prev: Node = Empty
var slow: Node = head
var fast: Node = head.next
for (i <- 0 until k - 1 if fast != Empty) {
fast = fast.next
}
while (fast != Empty) {
prev = slow
slow = slow.next
fast = fast.next
}
prev match {
case Empty => slow.next
case p:NonEmpty => {
if (p.next != Empty)
p.next = p.next.next
head
}
}
}
}
val node = removeNthElement(toLinkedList(List(1,2,3)), 2)
printLinkedList(node)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Reverse Integer
Reverse digits of an integer.
Example1:
> x = 123, return 321
Example2:
> x = -123, return -321
{% tabs %}
{% tab title="Scala" %}
```scala
def reverse(x: Int): Int = {
var _x = x
var result = 0
while (_x != 0) {
result = result * 10 + _x % 10
_x /= 10
}
if (result <= Int.MaxValue && result >= Int.MinValue) result else 0
}
reverse(123)
reverse(-123)
reverse(Int.MinValue)
reverse(Int.MaxValue)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Roman to Integer
Given a roman numeral, convert it to an integer. \
\
Input is guaranteed to be within the range from 1 to 3999.
> Please read the above updated description carefully.
{% tabs %}
{% tab title="Scala" %}
```scala
val map: Map[Char, Int] = Map[Char, Int](
'M' -> 1000,
'D' -> 500,
'C' -> 100,
'L' -> 50,
'X' -> 10,
'V' -> 5,
'I' -> 1
)
/**
*
* @param s
* @return
*/
def romanToInt(s: String): Int = {
var ret, prev, current = 0
for (c <- s.reverse) {
current = map(c)
if (prev > current) ret -= current
else {
ret += current
prev = current
}
}
ret
}
romanToInt("MMMDCCXLV")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Rotate Array
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, \
the array
> \[1,2,3,4,5,6,7]
\
is rotated to
> \[5,6,7,1,2,3,4]
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
{% tabs %}
{% tab title="Scala" %}
```scala
def rotate(nums: Array[Int], k: Int) = {
val r = k % nums.length
reverse(nums, 0, nums.length - 1)
reverse(nums, 0, r - 1)
reverse(nums, r, nums.length - 1)
nums
}
def reverse(nums: Array[Int], start: Int, end: Int): Array[Int] = {
val diff = (end - start) / 2
var tmp = 0
for (i <- 0 until diff) {
tmp = nums(start + i)
nums(start + i) = nums(end - i)
nums(end - i) = tmp
}
nums
}
/**
* http://blog.thedigitalcatonline.com/blog/2015/05/13/99-scala-problems-16-20/#.V84U_ZMrJE5
*/
def rotate[A](n: Int, l: List[A]): List[A] = {
val wrapn = if (l.isEmpty) 0 else n % l.length
if (wrapn < 0) rotate(l.length + n, l)
else l.drop(wrapn) ::: l.take(wrapn)
}
rotate(Array(1, 2, 3, 4, 5, 6, 7, 8, 9), 2)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.
For example, Consider the following matrix:
> ```
> [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
> ```
```
Given
> target = 3
return
> true
```
{% tabs %}
{% tab title="Scala" %}
```scala
def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
if (matrix.isEmpty) false
else {
val (m, n) = (matrix.length, matrix(0).length)
val length = m * n
def find(start: Int, end: Int): Boolean = {
if (end < start) false
else {
val mid = (start + end) / 2
matrix(mid / n)(mid % n) match {
case num if num == target => true
case num if num < target => find(mid + 1, end)
case num if num > target => find(start, mid - 1)
}
}
}
find(0, length - 1)
}
}
val mat = Array(
Array(1, 3, 5, 7),
Array(10, 11, 16, 20),
Array(23, 30, 34, 50)
)
searchMatrix(mat, 11)
searchMatrix(mat, 99)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Shortest Word Distance
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example, Assume that
> words = \["practice", "makes", "perfect", "coding", "makes"].
Given
> word1 = “coding”, \
> word2 = “practice”, \
> return 3.
Given
> word1 = "makes", \
> word2 = "coding", \
> return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
#### [Shortest Word Distance II](https://leetcode.com/problems/shortest-word-distance-ii/)
The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
#### [Shortest Word Distance III](https://leetcode.com/problems/shortest-word-distance-iii/)
The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example, Assume that
> words = \["practice", "makes", "perfect", "coding", "makes"].
Given
> word1 = “makes”, word2 = “coding”, return 1.
Given
> word1 = "makes", word2 = "makes", return 3.
{% tabs %}
{% tab title="Scala" %}
```scala
def shortestDistance(words: Array[String], word1: String, word2: String) = {
var minDist = Int.MaxValue
var (word1Index, word2Index) = (-1, -1)
for ((word, i) <- words.zipWithIndex) {
if (word == word1) word1Index = i
else if (word == word2) word2Index = i
if (word1Index != -1 && word2Index != -1) minDist = minDist min math.abs(word1Index - word2Index)
}
minDist
}
val words = Array("practice", "makes", "perfect", "coding", "makes")
shortestDistance(words, "coding", "practice")
shortestDistance(words, "makes", "coding")
/**
* Follow up
* https://leetcode.com/problems/shortest-word-distance-ii/
*
* @param words
*/
class WordDistance(words: Array[String]) {
val indexes: Map[String, Array[Int]] = (for {
(word, i) <- words zipWithIndex
} yield (word, i)).groupBy(_._1).mapValues(_.map(_._2))
def shortest(word1: String, word2: String): Int = {
var minDist = Int.MaxValue
for (x <- indexes(word1); y <- indexes(word2)) {
minDist = minDist min math.abs(x - y)
}
minDist
}
}
val wd = new WordDistance(words)
wd.shortest("coding", "practice")
wd.shortest("makes", "coding")
/**
* Follow up
*
* @param words
* @param word1
* @param word2
* @return
*/
def shortestDistanceIII(words: Array[String], word1: String, word2: String) = {
var minDist = Int.MaxValue
var (word1Index, word2Index) = (-1, -1)
val sameWord: Boolean = word1 == word2
for ((word, i) <- words.zipWithIndex) {
if (sameWord && word == word1) {
word1Index = word2Index
word2Index = i
} else {
if (word == word1) word1Index = i
else if (word == word2) word2Index = i
}
if (word1Index != -1 && word2Index != -1) minDist = minDist min math.abs(word1Index - word2Index)
}
minDist
}
shortestDistanceIII(words, "makes", "coding")
shortestDistanceIII(words, "makes", "makes")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Two Sum III - Data structure design
Design and implement a TwoSum class. It should support the following operations: add and find.
> add - Add the number to an internal data structure.
> find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
```
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
```
{% tabs %}
{% tab title="Scala" %}
```scala
import scala.collection.mutable.Map
class TwoSum {
var counter = Map[Int, Int]() withDefaultValue 0
def add(num: Int): Unit = {
counter += (num -> (counter(num) + 1))
}
def find(target: Int): Boolean = {
for ((num, count) <- counter) {
val diff = target - num
val found = {
if (diff == num) counter(num) > 1
else counter(diff) > 0
}
if (found) return true
}
false
}
}
val twoSum = new TwoSum
for (i <- Array(1, 3, 5))
twoSum.add(i)
twoSum.find(4)
twoSum.find(7)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Valid Parentheses
Given a string containing just the characters
> '(', ')', '{', '}', '\[' and ']'
determine if the input string is valid.
The brackets must close in the correct order,
> "()" and "()\[]{}"
are all valid but
> "(]" and "(\[)]"
are not.
{% tabs %}
{% tab title="Scala" %}
```scala
val brackets:Map[Char, Char] = Map[Char, Char] (
')' -> '(',
'}' -> '{',
']' -> '['
)
def isValid(s: String): Boolean = {
var lst: List[Char] = Nil
for (c <- s) {
if (brackets contains c) {
for (open <- brackets.get(c)) {
if (lst.head == open) lst = lst.tail
else return false
}
} else {
lst = c :: lst
}
}
lst.isEmpty
}
isValid("()")
isValid("()[]{}")
isValid("(]")
isValid("([)]")
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
> ```
> P A H N A P L S I I G Y I R
> ```
```
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
> convert("PAYPALISHIRING", 3)
should return
> "PAHNAPLSIIGYIR"
```
{% tabs %}
{% tab title="Scala" %}
```scala
def convert(s: String, numRows: Int): String = {
numRows match {
case 1 => s
case n if n > 1 => {
val lengthPerCycle = 2 * numRows - 2
val cycles = (s.length / lengthPerCycle) + 1
val sb = new StringBuilder
for (i <- 0 until numRows) {
for (cycle <- 0 until cycles) {
// print full vertical
val col = (cycle * lengthPerCycle) + i
if (col < s.length)
sb.append(s(col))
// print diagonal
val dia = ((cycle + 1) * lengthPerCycle) - i
if (i != 0 && i < numRows - 1 && dia < s.length)
sb.append(s(dia))
}
}
sb.toString()
}
case _ => throw new Error("negative number")
}
}
convert("PAYPALISHIRING", 3)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Quicksort
Extract from [Scala by Example](http://www.scala-lang.org/docu/files/ScalaByExample.pdf)
{% tabs %}
{% tab title="Scala" %}
```scala
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length - 1)
}
val arr = Array(3,5,7,3,2,6,8,3,5,1,5,2)
sort(arr)
arr mkString ","
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
```
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
```
{% tabs %}
{% tab title="Scala" %}
```scala
class ListNode(var value: Int, var next: ListNode = null) {
def +(that: ListNode): ListNode = {
if (that == null) this
else {
val sum = this.value + that.value
var next = new ListNode(sum / 10) + this.next + that.next
if (next.value == 0 && next.next == null) next = null
new ListNode(sum % 10, next)
}
}
}
/**
* wrapper function
* @param l1
* @param l2
* @return
*/
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
if (l1 != null && l2 != null) l1 + l2
else if (l1 == null) l2
else l1
}
/**
* utility function
* @param nums
* @return
*/
def createLinkedList(nums: Array[Int]): ListNode = {
nums
.map(num => new ListNode(num))
.foldRight[ListNode](null)((l: ListNode, r: ListNode) => {
l.next = r; l
})
}
/**
* utility function
* @param n
*/
def printLinkedList(n: ListNode): Unit = {
var head = n
while (head != null) {
println(head.value)
head = head.next
}
}
var n1 = createLinkedList(Array(0))
var n2 = createLinkedList(Array(1))
printLinkedList(addTwoNumbers(n1, n2))
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Best Time to Buy and Sell Stock
Say you have an array for which the *i*th element is the price of a given stock on day *i*.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
**Example 1:**
```
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
```
**Example 2:**
```
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
```
{% tabs %}
{% tab title="Python" %}
```python
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_profit = 0
min_price = float('inf')
for i in range(len(prices)):
min_price = min(min_price, prices[i])
max_profit = max(max_profit, prices[i] - min_price)
return max_profit
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:
> Digit string "23"
Output:
> \["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
> Although the above answer is in lexicographical order, your answer could be in any order you want.
{% tabs %}
{% tab title="Scala" %}
```scala
val counts = Vector(3, 3, 3, 3, 3, 4, 3, 4)
// generate char mapping for given int char
def decode(c: Char): Seq[Char] = {
val index = c.toInt - '2'.toInt
for (i <- 0 until counts(index)) yield (counts.take(index).sum + 'a'.toInt + i).toChar
}
// complete keypad mappings
val mappings: Map[Char, Seq[Char]] = {
(for (i <- '2' to '9') yield (i -> decode(i))).toMap
} withDefaultValue Seq(' ')
/**
* generate each combination starting from last index.
*
* @param digits
* @return
*/
def letterCombinations(digits: String): List[String] = {
var ret: List[String] = Nil
if (digits.isEmpty) ret
else {
val letters: Array[Char] = Array.fill(digits.length) {
' '
}
def generate(index: Int): Unit = {
for (c <- mappings(digits(index))) {
letters(index) = c
if (index == 0) {
ret = letters.mkString("") :: ret
} else {
generate(index - 1)
}
}
}
generate(digits.length - 1)
ret
}
}
/**
* generate each combination but fixed length
*
* @param digits
* @return
*/
def letterCombinations(digits: Array[Char]): Seq[String] = {
if (digits.length != 7) throw new Error("must be 7 digits")
else {
for {
a <- mappings(digits(0))
b <- mappings(digits(1))
c <- mappings(digits(2))
d <- mappings(digits(3))
e <- mappings(digits(4))
f <- mappings(digits(5))
g <- mappings(digits(6))
} yield (s"$a$b$c$d$e$f$g")
}
}
letterCombinations("2463832")
letterCombinations("2463832".toCharArray)
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}
# Data Structures
# Heap
{% tabs %}
{% tab title="Python" %}
```python
class Heap:
def __init__(self):
self.lst = []
def get_left_child_index(self, index):
return (2 * index) + 1
def get_right_child_index(self, index):
return (2 * index) + 2
def get_parent_index(self, index):
return (index - 1) // 2
def has_left_child(self, index):
return self.get_left_child_index(index) < len(self.lst)
def has_right_child(self, index):
return self.get_right_child_index(index) < len(self.lst)
def has_parent(self, index):
return self.get_parent_index(index) >= 0
def swap(self, first, second):
self.lst[first], self.lst[second] = self.lst[second], self.lst[first]
def peek(self):
if not self.lst:
return None
return self.lst[0]
def poll(self):
if not self.lst:
return None
item = self.lst[0]
self.swap(0, -1)
self.lst.pop()
self.heapify_down()
return item
def add(self, data):
self.lst.append(data)
self.heapify_up()
def heapify_up(self):
index = len(self.lst) - 1
while self.has_parent(index):
parent_index = self.get_parent_index(index)
if self.lst[parent_index] > self.lst[index]:
self.swap(parent_index, index)
index = parent_index
def heapify_down(self):
index = 0
while self.has_left_child(index):
smaller_index = self.get_left_child_index(index)
if self.has_right_child(index) and self.lst[self.get_right_child_index(index)] < self.lst[smaller_index]:
smaller_index = self.get_right_child_index(index)
if self.lst[index] < self.lst[smaller_index]:
break
self.swap(index, smaller_index)
index = smaller_index
h = Heap()
h.add(20)
h.add(17)
h.add(15)
h.add(10)
print(h.poll())
print(h.poll())
print(h.poll())
print(h.poll())
```
{% endtab %}
{% tab title="Second Tab" %}
{% endtab %}
{% endtabs %}