Level Up

Read these:

http://courses.csail.mit.edu/iap/interview/materials.php

Scala By Example Chapter 11 Solutions - Exercise 11.3.2

Exercise 11.3.2 Another way is to define an or-gate by a combination of inverters and and gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?

The delay parameter has also been left unused in this case. However it would not be difficult to conclude that the delay time for this function would be = inverter delay time + AND delay time + inverter delay time = 2 (inverter delay) + AND delay.

Scala By Example Chapter 11 Solutions - Exercise 11.3.1

Exercise 11.3.1 Write the implementation of orGate.

Note that the delay parameter in the function afterDelay has not been used since it removes complexity when testing this case.

Scala By Example Chapter 11 Solutions - Exercise 11.2.1

Exercise 11.2.1 Write a function repeatLoop with also additional syntax for an until clause.

The repeat { command } until (condition) was tricky. The trick is to realize that "until" would be a method call, and for it to be a method call, "repeat {command}" would have to be an object. Since objects are created using new, we could wrap this object creation with a method. The result is below. Note that the second method has been changed to repeatUntilLoop since it would conflict with the previous method repeatUntil.

Scala By Example Chapter 10 Solutions - Exercise 10.3.2

Exercise 10.3.2 Translate the following for comprehensions to higher-order functions.

Scala By Example Chapter 10 Solutions - Exercise 10.3.1

Exercise 10.3.1 Define the following function in terms of for.

This will be revisited later.

Scala By Example Chapter 10 Solutions - Exercise 10.1.1

Exercise10.1.1 Write the function isSafe.

Scala By Example Chapter 9 Solutions - Exercise 9.4.3

Exercise 9.4.3 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations.

This will be revisited later.

Scala By Example Chapter 9 Solutions - Exercise 9.4.2

Exercise 9.4.2 What would be the difference in asymptotic complexity between the two versions of flatten?

This will be revisited later.

Scala By Example Chapter 9 Solutions - Unnamed Exercise after 9.4.1

Exercise: Define forall and exists in terms of filter.

As before, since class List cannot be extended in scala, the methods are implemented as pure functions taking a list parameter.

Scala By Example Chapter 9 Solutions - Exercise 9.4.1

Exercise 9.4.1 Consider a function which squares all elements of a list and re- turns a list with the results. Complete the following two equivalent definitions of squareList.

Scala By Example Chapter 9 Solutions - Exercise 9.2.1

Exercise 9.2.1 Design a tail-recursive version of length.

Ah, tail recursion again. Re-iterating that in a tail recursion, the last line of the function has to be a pure call to itself. To achieve this, an extra parameter needs to be passed to the function that keeps track of some relevant state.
We are getting good at this now, arent we?

Scala By Example Chapter 9 Solutions - Exercise 9.1.1

Exercise 9.1.1 Provide an implementation of the missing function insert.

Insert will also be recursive, and its pretty easy to lay down the flow. Do not forget to concatenate the head after insert is applied on reduced versions of the list since we will need to return the whole inserted list and not a subset.

Scala By Example Chapter 7 Solutions - Exercise 7.2.2

Exercise 7.2.2 Complete the following implementations of function contains and insert for IntTree’s.

This is similar to the IntSet implementations in Chapter 6.

Scala By Example Chapter 6 Solutions - Exercise 6.0.3

Exercise 6.0.3 Write an implementation Integer of integer numbers The implementation should support all operations of class Nat while adding two methods def isPositive: Boolean def negate: Integer

This will be revisited later.

Scala By Example Chapter 6 Solutions - Exercise 6.0.2

Exercise 6.0.2 Add a method def excl(x: Int) to return the given set without the element x. To accomplish this, it is useful to also implement a test method def isEmpty: Boolean for sets.

This will be revisited later.

Scala By Example Chapter 6 Solutions - Exercise 6.0.1

Exercise 6.0.1 Write methods union and intersection to form the union and intersection between two sets.

This will be revisited later.

Scala By Example Chapter 5 Solutions - Exercise 5.3.1

Exercise 5.3.1 Write a function for cube roots using fixedPoint and averageDamp.

Both fixedPoint and averageDamp functions remain the same. Instead of sqrt, now theres a cbrt function which calculates the cube root. The math library is used to avail of the exponential function.

Scala By Example Chapter 5 Solutions - Exercise 5.2.4

Exercise 5.2.4 Can you write an even more general function which generalizes both sum and product?

This function abstracts out the operation which can be passed in as a sum or product function. One thing to be noted here is that an extra argument needs to be passed as the base case which would be 0 for a sum and 1 for a product.

Scala By Example Chapter 5 Solutions - Exercise 5.2.3

Exercise 5.2.3 Write factorial in terms of product.

Scala By Example Chapter 5 Solutions - Exercise 5.2.2

Exercise5.2.2 Write a function product that computes the product of the values of functions at points over a given range.

This is very similar to the sum function that is already worked out in the chapter.

Scala By Example Chapter 5 Solutions - Exercise 5.2.1

Exercise 5.2.1 1. The sum function uses a linear recursion. Can you write a tail- recursive one by filling in the ??’s?

The key is to understand that converting linear recursion to a tail-recursive version involves carrying over a computed value over to the next iteration. Also, note that the call to the iter function at the end need not take in a and b as parameters directly but can be computed values. Thats what facilitates the tail-recursive version. Here's my solution to the exercise.