Entretiens de codage: 5 choses à savoir pour gagner – The Startup

fun bigOne(nums: IntArray): Int {
if (nums.isNotEmpty())
return nums[0]
else
return 0
}

fun bigN(nums: Array): Int {
var sum = 0
nums.indices.forEach {
sum += nums[it]
}
return sum
}

fun bigNN(nums: Array): Int {
var value = 0
nums.indices.forEach {a ->
nums.indices.forEach {b ->
value += nums[a] * nums[b]
}
}
return value
}

fun binarySearch(nums: Array, target: Int): Int {
var start = 0
var end = nums.size - 1
while (start < end) {
val median = (start + end) /2
if (nums[median] == target) {
return median
}
if (nums[median] > target) {
end = median - 1
} else {
start = median + 1
}
}
return -1
}

Problème de fenêtre coulissante

String s consists of only alphabet letters on which you can perform at most k operations. In one operation, you can choose a character of the string and change it to any other alphabet letter. Find the maximum length of the substring containing all the same letters you can get.

fun findLongestRepeatingPattern(string: String, k: Int): Int {
val charToNum: MutableMap = mutableMapOf()
var maxLen = 0
var start = 0
var samePatternLength = 0
string.indices.forEach { end ->val endChar = string[end]
val endCharNum = charToNum.getOrDefault(endChar, 0) + 1
charToNum[endChar] = endCharNum

samePatternLength =
Math.max(samePatternLength, endCharNum)
val numOfDifferentChars =
end - start + 1 - samePatternLength
if (numOfDifferentChars > k) {
val startChar = string[start]
val endCharNum = charToNum.getOrDefault(endChar, 0)
if (endCharNum > 0) {
charToNum[startChar] = endCharNum - 1
}
start++
}
maxLen = Math.max(maxLen, end - start + 1)
}
return maxLen
}

Lowest Common Root of deepest Leaves from the binary tree

class TreeNode(var value: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
data class DepthAndNode (
var depth: Int = 0,
var treeNode: TreeNode? = null
)
fun commonRootDeepestLeaves(node: TreeNode?): DepthAndNode {
if (node == null) {
return DepthAndNode(0, null)
}
val treeNode: TreeNode?
val left = commonRootDeepestLeaves(node.left)
val right = commonRootDeepestLeaves(node.right)
if (left.depth == right.depth) {
treeNode = node
} else if (left.depth < right.depth) {
treeNode = right.treeNode
} else {
treeNode = left.treeNode
}

return DepthAndNode(
1 + left.depth.coerceAtLeast(right.depth), 
treeNode
)
}

There are items with the difference price. There are also coupon that gives the discount if you buy it bundle the items together. You have a target number of each item to buy. What's the minimum money you have to spend get those require items. Example, itemA : $2, itemB: $5 itemC: $6
You have to buy two itemA, one itemB and two itemC.
There is a coupon with which you buy two itemA and two item B, you only ned to pay $10. There is another coupon that allows you to buy one itemB and one item C with $8. What's the minimum cost to get two itemA, one itemB and two itemC? 

data class Coupon(
val price: Int,
val items: List
)
/*
* prices is the list of the price of each item. 
* prices[0]: item0 price, prices[1]: item1 price, etc
* coupons is the list of coupon
* need is the list of the number 
that you would need to buy per each item in index
*/
fun findMinCost(
prices: List,
coupons: List,
need: List
): Int {
var cost = calculatePlainCost(prices, need)
for (coupon in coupons) {
if (canCouponHandle(coupon, need)) {
cost = Math.min(
cost,
coupon.price +
findMinCost(
prices,
coupons,
extractCoupon(coupon, need))
)
}
}
return cost
}

Given the 2 by 2 matrix, starting from upper right corner, check if you can make a given letter by moving right, left, down and up. A diagram below shows the example of finding a given word apple.

fun isTargetThereByBFS(target: CharSequence, cellNode: CellNode) 
: Boolean {
val queue = LinkedList()
var currIndex = 0
queue.add(TreeNode(cellNode, currIndex))
while(queue.size > 0) {
if (queue.peek().level > currIndex) {
currIndex++
if (currIndex == target.length) {
return true
}
}
val node = queue.poll()
if (target[currIndex] == node.cellNode.value) {
node.cellNode.children?.forEach {
queue.add(TreeNode(it, currIndex + 1))
}
}
}
return false
}

There are items with the difference price. There are also coupon that gives the discount if you buy it bundle the items together. You have a target number of each item to buy. What's the minimum money you have to spend get those require items.Example, itemA : $2, itemB: $5 itemC: $6
You have to buy two itemA, one itemB and two itemC.
Needed: (2, 1, 2)There is a coupon with which you buy two itemA and two item B, you only ned to pay $10. There is another coupon that allows you to buy one itemB and one item C with $8. What's the minimum cost to get two itemA, one itemB and two itemC?
Coupon1: (2, 2, 0) : $10
Coupon2: (0, 1, 1) : $8

F(2,1,2) = F(0, 0, 2) + Coupon1

F(2, 1, 2) = F(2, 0, 1) + Coupon2

F(2, 1, 2) = $2*2 + $5 + %6*2 = $21

fun calculateMinimumCost(): Int {
val dp = Array(itemA + 1) {
Array(itemB + 1) {
IntArray(itemC + 1)
}
}
dp[0][0][0] = 0
for (a in 1..itemANum) {
for (b in 1..itemBNum) {
for (c in 1..itemCNum) {
dp[a][b][c] = calculatePlainCost(a, b, c)
coupons.forEach { coupon ->
dp[a][b][c]
= Math.min(
dp[a][b][c],
dp[a-coupon.a < 0 ? 0 : a-coupon.a]
[b-coupon.b < 0 ? 0 : b-coupon.b]
[c-coupon.c < 0 ? 0 : c-coupon.c] 
+ coupon.price
)
}
}
}
}
}