Category Archives: Algorithm

Algorithms Tips (4) – Basic Data Structure

Here we record some basic data structures which are easily involved in coding.

  • PriorityQueue
    Sometimes, we want to sort hashmap by its value, we can introduce PriorityQueue to override its compare function to reach the goal. (Laster, I will add more compare function to popular PriorityQueue’s field.)

     Map<Integer, Integer> tweets = new HashMap();
     PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
       @Override
       public int compare(Integer a, Integer b) {
         return tweets.get(b) - tweets.get(a);
         // tweets.get(a)-tweets.get(b) is increasing/ascending
         // tweets.get(b)-tweets.get(a) is downing trend
       }
     });
     pq.add(key);
     pq.poll(); //return head and delete head 
     pq.peek(); // return head
  • Set
    If we want to add unique value to the output, we can use set as an intermedium variable to help to check during adding process.

    Set set = new HashSet();
    set.add("a");
    set.remove("a");
    Iterator iterator = set.iterator();
    while(iterator.hasNext()) {
      String elem = iterator.next();
    }
  • TreeMap
    A TreeMap provides an efficient means of sorting key/value pairs in sorted order and allows rapid retrieval. Its elements will be sorted in an ascending key order.

    TreeMap tm = new TreeMap();
    tm.put("a", 2);
    tm.put("b", 1);
    tm.get("a"); // return 2
    tm.lastKey(); // return "b"
    tm.firstKey(); // return "a"
    tm.remove("a"); 
    TreeMap<Integer, HashSet> t = new TreeMap();
    // if HashSet's size is zero, we need to use t.remove(key) to 
    remove this element in TreeMap. Because its null value will 
    influence TreeMap's firstKey and lastKey result.
  • List
    Arrays.asList("a", "b");// initialize List with values
    // List to Array
    lists.toArray(new String[lists.size()]);

    For recursion method, we might need to copy the last result to current result. For example, for f(i-1), its result is left (List<Integer>) and for f(i), its result is to merge left with current value.
    Wrong version:

     List<List<Integer>> rec = new ArrayList<List<Integer>>():
     rec.addAll(left);
     for(List<Integer> left: lefts) {
       left.add(nums[index]);
       rec.add(elem);
     }

    Right version:

     List<List<Integer>> rec = new ArrayList<List<Integer>>():
     rec.addAll(left);
     for(List<Integer> left: lefts) {
       ArrayList<Integer> elem = new ArrayList<Integer>(left);
       elem.add(nums[index]);
       rec.add(elem);
     }

    The problem of the wrong version is that it will change left’s content. For example, if left=[[], [1]] and nums[1]=2, the wrong version’s output is [[2],[1,2],[2],[1,2]]. For the right version, it creates a new ArrayList to physically build a new list, so later add method won’t change original content. So the right output is [[], [1], [2], [1,2]].

  • Stack
    Stack<String> s = new Stack();
    s.push("zara");
    s.peek();
    s.pop();
  • String
    int integer = 1;
    String t = String.valueOf(integer);

The string is very common, so the only special point is to convert to char[] when needed.

  •  char[] arr = str.toCharArray();
     Arrays.sort(arr);
     String t = String.valueOf(arr);
     String t1 = new String(arr);

 

Algorithm Tips (3) – Building Suitable Data Structure

The more LeetCode questions we practice, the more rules we find. We can split all questions to serval categories, such as Stack, Map/HashMap, Dynamic Programming, etc. It looks good to use these existing data structure to improve the solution, but sometimes, we still need to build our own suitable data structure to fit some questions’ special scenario.

Today I take “Binary Tree Maximum Path Sum” as an example. (Later, I will enhance this post by adding more examples.)

Question:

Given a binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Analysis:

For any node, it has two cases, one is single side(not circle), the other is go-through-circle. We need to record the two cases for each node and then to be provided to parent’s node to evaluate. So it is quite clear to solve the problem. Now you can use int[] which contains 2 elements to code it, but we all know it is not the good one and hard to read. The better solution is to build our own data structure to describe the two cases clearly.

private class ResultType {
  int singlePath, maxPath;
  ResultType(int singlePath, int maxPath) {
    this.singlePath = singlePath;
    this.maxPath = maxPath;
  }
}

Here we conclude above two cases to two parameters: singlePath is to record the maximum path for single side(not circle) and maxPath to record the maximum value for the current node, including circle case and non-circle case. So the whole codes are here:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   private class ResultType {
     int singlePath, maxPath;
     ResultType(int singlePath, int maxPath) {
       this.singlePath = singlePath;
       this.maxPath = maxPath;
     }
   }
   public int maxPathSum(TreeNode root) {
     ResultType res = helper(root);
     return res.maxPath;
   }
 
   public ResultType helper(TreeNode root) {
     if (root == null) 
       return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
     ResultType left = helper(root.left);
     ResultType right = helper(root.right);
 
     int singlePath = Math.max(0, 
             Math.max(left.singlePath, right.singlePath)) + root.val;
     int maxPath = Math.max(left.maxPath, right.maxPath);
     maxPath = Math.max(maxPath, 
             Math.max(left.singlePath, 0)+
                      Math.max(right.singlePath, 0)+root.val);
     return new ResultType(singlePath, maxPath);
   }
}

We see parent’s singlePath = Max(their children’s singlePath + root value) and parent’s maxPath = Max( children’s maxPath,  children’s singlePath + root value).

Meanwhile, we comparing singlePath with zero, to determine whether to involve it or not.

Another clever point is to return Integer.MIN_VALUE, not zero for the empty node. This is very clever to solve the case, like only one node with a negative value. Because in this case, this negative value is still the maximum value for this node.

Algorithm Tips (2) – Avoiding Data Overflow

Today we talk about overflow. This is a very shy problem when interviewing. And it is also a very good way to distinguish whether you are a good programmer or just so-so programmer.

When I interviewed in a big company (I forgot its name, maybe eBay), the interviewer asked me to write a sum function. So easy?! In fact, No. You have to consider overflow for your solution.

Concept of Overflow and Underflow

First, let’s understand what’s overflow and what’s underflow. Overflow and underflow are related to a data type. Every data type has its own range. For example, int, in Java, you can use Integer.MIN_VALUE and Integer.MAX_VALUE to know its range. In Java arithmetic operators, it doesn’t report overflow and underflow problem and never throws an error exception. It just simply swallows it.

  • int operators:
    When the value of an operation is larger than 32 bits, then the low 32 bits only taken into consideration and the high order bits are discarded. And when its most significant bit(MSB) is 1 then the value is treated as negative.
  • floating point operators:
    Overflow will result in Infinity and underflow will result as 0.0.

Solutions to avoid overflow or underflow

Second, there are several ways to avoid it.

  • using long to replace int
  • using uint to replace int
  • using double to apply intermediate variable
  • use the mod method to avoid it, This is a very common solution in LeetCode, within the question, it already obviously reminds you to use mod 100000007 if the answer is very large.

Examples

Finally, I list my solution for LeetCode-576 (Out of Boundary Paths) (Here I don’t list the content of the question, you can read it from LeetCode’s website. ) to help you understand how to avoid overflow issue. Meanwhile, it is a good way to see how to use three dimensions array to fix the problem with dynamic programming method.

public class Solution {
  public int findPaths(int m, int n, int N, int i, int j) {
    final int MOD = 1000000007;
    if (N == 0) return 0;
    long[][][] dp = new long[m][n][N+1]; //k:1-N
    for(int ii=0; ii<m;ii++) {
      for(int jj=0; jj<n;jj++) {
        int count = 0;
        if (ii-1<0) count++;         if (ii+1>=m) count++;
        if (jj-1<0) count++;         if (jj+1>=n) count++;
        dp[ii][jj][1] = count;
      }
    }
    for(int k=2; k<=N;k++) {
      for(int ii=0; ii<m; ii++) {
        for(int jj=0; jj<n; jj++) {
          long count = 0;
          if (ii-1>=0) count += dp[ii-1][jj][k-1];
          if (jj-1>=0) count += dp[ii][jj-1][k-1];
          if (ii+1<m) count += dp[ii+1][jj][k-1];
          if (jj+1<n) count += dp[ii][jj+1][k-1];
          dp[ii][jj][k] = count%MOD;
        }
      }
    }
    long rec = 0;
    for(int k=1; k<=N; k++) {
      rec += dp[i][j][k];
    }
    return (int)(rec%MOD);
    }
}

Another simple LeetCode question also requires us to consider overflow issue: Valid Binary Search Tree. Here is the solution which considers using Long to replace Integer to avoid overflow.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 public boolean isValidBST(TreeNode root) {
   return isValidBSTCheck(root, Long.MIN_VALUE, Long.MAX_VALUE);
 }
 public boolean isValidBSTCheck(TreeNode root, long min, long max) {
   if (root == null) return true;
   if (root.val > min && root.val < max) {
     return isValidBSTCheck(root.left, min, root.val) && isValidBSTCheck(root.right, root.val, max);
   } else return false;
 }
}

Algorithm Tips (1) – Avoiding Data Allocation

For next following posts, I will write down some tips when coding. These are all summaries while I practice on LeetCode. I know there are so many LeetCode answers of questions online, but that is a just question-to-answer model. If we just read the question and then answer it, we never grow up fast. We need to know why others’ algorithm is faster than mine and what’s the differences between them; in future, how can we apply others’ good places into our own. So, let’s start!

Example-1:

We all know Map (key-value pair) is a good data structure to optimize algorithm speed sometimes. Because Map’s get speed is O(1) with well-designed hash function. But if we don’t write it well, it still might lose its advantage.

Worse Case:

Map<Integer, List<Integer>> map = new HashMap();
// nums is a int[] array. 
for(int i=0; i< nums.length; i++) {
    List<Integer> value = new ArrayList();
    value.add(nums[i]);
    if (map.containsKey(i)) {       
        value.addAll(map.get(i));
    } 
    map.put(i, value);
}

Better Version:

Map<Integer, List<Integer>> map = new HashMap();
for(int i=0; i<nums.length; i++) {
    if (!map.containsKey(i)) {
        map.put(i, new ArrayList<>());
    }
    map.get(i).add(nums[i]);
}

For small volume of data, this kind of advantage might be not too obvious, but for big data, the second version is much better than the first one.

It is quite easy to understand its improvement. For the first version, it has “addAll” to insert the whole list to another one. From physical side, we know it needs to handle a lot of things, such as allocating space. In fact, ArrayList.addAll already did some optimization, like allocating enough space to add every single element in one step, rather than having to reallocate multiple times if adding large numbers of elements. To avoid these things, the second version uses an empty data (” new ArrayList<>()” ) to well get rid of space allocation issue.

Example-2:

The Question requests to design a set data structure that supports all operations in average O(1) time.

Worse Version:

List<Integer> data;
public boolean insert(int val) {
  if (data.contains(val)) return false;
  else {
    data.add(val);
    return true;
  }
}
public boolean remove(int val) {
  if (data.contains(val)) {
    int index = data.indexOf(val);
    data.remove(index);
    return true;
  } else return false;
}

Better Version:

List<Integer> data;
Map<Integer, Integer> map; // to store val->index
public boolean insert(int val) {
  if (map.containsKey(val)) return false;
  else {
    data.add(val);
    map.put(val, data.size()-1);
    return true;
  }
}
public boolean remove(int val) {
  if (!map.containsKey(val)) return false;
  else {
    int index = map.get(val);
    if (index != data.size()-1) {
      int lastValue = data.get(data.size()-1);
      data.set(index, lastValue);
      map.put(lastValue, index);
    }
    data.remove(data.size()-1);
    map.remove(val);
    return true;
  }
}

We see the great difference between the two version is that we introduce a Map to store each value’s index; for remove function, we swap the target with the last element of the list and then finally delete the last one.

The reason we improve like this is to reach O(1) purpose. ArrayList’s indexOf and remove method are opposite with this target.

  • remove(int)
    This method removes a single element at given position. After that all elements from the right are shifted to the left via System.arraycopy.all, so this method has O(n) complexity. Each call to remove the last element would not invoke System.arraycopy all, so such method call complexity would be O(1).
  • remove(Object)
    This method removes the first occurrence of a given element from the list. It iterates all list elements, so it has O(n) complexity. This method would access all array elements in any case – either read them while looking for requested element or move them from one position to the left by System.arraycopy call after requested element was found.
    Never call remove(Object) when you know at which position you can find your element.
  • contains(Object), indexOf(Object)
    The first method checks a given object whether it’s present in the list (and defined as indexOf(elem)>=0). The second method tries to find the position of given element in the list. Both methods have O(n) complexity because they are scanning an internal array from the beginning in order to find given element. 

Summary of List:

  • add elements to the end of the list
  • remove elements from the end
  • avoid contains, indexOf and remove(Object) methods
  • even more avoid removeAll and retainAll methods
  • use subList(int, int).clear() idiom to quickly clean a part of the list

Additional Read:

  1. java.util.ArrayList performance guide

 

Functional Programming Principles in Scala (1)

This is online course, named functional programming principles in Scala. I use this course to practice my Scala programming. So here I do summary of my solutions according to its assignments online. Please I don’t follow its restriction, I only want to implement my solution by Scala. Don’t compare my idea with their online course exactly. Follow your heart. 🙂

Exercise 1: Pascal’s Triangle.

Do this exercise by implementing the pascal function, which takes a column c and a row r, counting from 0 and returns the number at that spot in the triangle. For example,pascal(0,2)=1, pascal(1,2)=2 and pascal(1,3)=3

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}
pascal(0, 2) // output: 1
pascal(1, 2) // output: 2
pascal(1, 3) // output: 3

Exercise 2: Parentheses Balancing

Write a function which verifies the balancing of parentheses in a string, which we represent as a List[Char] not a String. For example, the function should return true for the following strings:

  • (if (zero? x) max (/ 1 x))
  • I told him (that it’s not (yet) done). (But he wasn’t listening)

The function should return false for the following strings:

  • 🙂
  • ())(

The last example shows that it’s not enough to verify that a string contains the same number of opening and closing parentheses.

import scala.collection.mutable.Stack
def balance(chars: List[Char]): Boolean = {
  val stack = new Stack[Char]()
  var flag = true
  for (c <- chars if flag == true) {
    if (c == '(') stack.push(c)
    else if (c == ')') {
      if (stack.size == 0) flag = false
      else stack.pop
    }
  }
  if (stack.size == 0 && flag == true) flag = true
  else flag = false
  flag
}
balance("(if (zero? x) max (/ 1 x))".toList) // output: true
balance("I told him (that it’s not (yet) done). (But he wasn’t listening)".toList) // output: true
balance(":-)".toList) // output: false
balance("())(".toList) // output: false

Exercise 3: Counting Change

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2: 1+1+1+1, 1+1+2, 2+2.

def countChange(money: Int, coins: List[Int]): Int = {
  if (money <= 0) 0
  else if (money == 1) 1
  else {
    var sum: Int = 0
    for (coin <- coins) {
      sum += countChange(money - coin, coins)
    }
    sum
  }
}

countChange(4, List(1,2)) // output: 3

Algorithm (2): Linked Lists

Before we enter into “Question and Answer” model, we need to know how to use LinkedList in Scala. In Scala, it already provides LinkedList collection directly. by “import scala.collection.mutable.LinkedList”.

import scala.collection.mutable.LinkedList
val temp = new LinkedList[String]
val temp1 = temp append LinkedList("abc", "efg")
println(temp1)
// output: LinkedList("abc", "efg")
// Note: now temp is still LinkedList()

2.1 Write code to remove duplicates from an unsorted linked list. Follow up: how would you solve this problem if a temporary buffer is not allowed?

import scala.collection.mutable.LinkedList
import scala.collection.mutable.HashMap
def removeDuplicate(data: LinkedList[String]): LinkedList[String] = {
  val record = new HashMap[String, Int]
  var dataTemp = data
  var previous: LinkedList[String] = LinkedList()
  while (dataTemp != LinkedList()) {
    if (record.isDefinedAt(dataTemp.elem)) {
      previous.next = dataTemp.next
    } else {
      record.put(dataTemp.elem, 1)
      previous = dataTemp
    }
    dataTemp = dataTemp.next
  }
  data
}

Here we use hashmap to store each element and its appearance time. We use record.isDefinedAt to check whether this key exists or not and use record.put to add new pair to map.

For linkedlist, we use dataTemp.elem to get current data and dataTemp.next to its tail: linkedlist. Also in Scala, you can directly use “dataTemp.distinct” to remove duplicates.

2.2 Implement an algorithm to find last n elements of a singly linked list

def getNth(data: LinkedList[String], n: Int): LinkedList[String] = {
  var length = 0
  var dataTemp = data
  while (dataTemp != LinkedList()) {
    length += 1
    dataTemp = dataTemp.next
  }
  if (n == length) {
    data
  } else if (n > length) {
    LinkedList()
  } else {
    dataTemp = data 
    var count = 1
    while (dataTemp != LinkedList() && count + n != length) {
      count += 1
      dataTemp = dataTemp.next
    }
    dataTemp.next
  }
}

Note: I change the question content which is different with the book.

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

Example:

Input: the node ‘c’ from the linked list a->b->c->d->e

Result: nothing is returned, but the new linked list looks like a->b->d->e

def removeMiddle(data: LinkedList[String], middle: String) = {
  var dataTemp = data
  var returnData = data
  var previous = data
  while(dataTemp.next.elem != middle) {
    previous = dataTemp.next
    dataTemp = dataTemp.next
  }
  previous.next = dataTemp.next.next
  println(returnData)
}

2.4 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example:

Input: (3->1->5), (5->9->2)

Output: 8->0->8

This question looks like to implement an add function for linked list.

def addLinkedList(first: LinkedList[Int], second: LinkedList[Int]): LinkedList[Int] = {
  var sum = LinkedList[Int]()
  var firstTemp = first
  var secondTemp = second
  var flag = 0
  while (firstTemp != LinkedList() && secondTemp != LinkedList()) {
    val temp = firstTemp.elem + secondTemp.elem + flag
    sum = sum append LinkedList(temp % 10)
    flag = if (temp <= 9) 0 else 1
    firstTemp = firstTemp.next
    secondTemp = secondTemp.next
  }
  if (firstTemp == LinkedList()) {
    while (secondTemp != LinkedList()) {
      val temp = secondTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      secondTemp = secondTemp.next
    }
  } 
  if (secondTemp == LinkedList()){
    while (firstTemp != LinkedList()) {
      val temp = firstTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      firstTemp = firstTemp.next
    }
  }
  if (flag != 0) {
    sum = sum append LinkedList(flag)
  }
  sum
}

2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.

Definition:

Circular linked list: A(corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

example:

Input: A->B->C->D->E->C [the same C as earlier]

Output: C

Algorithm (1): Arrays and Strings

When I preparing interview, I use “Cracking the Coding Interview” this book. I write my solutions by Scala.

1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

def uniqueCharacter(data: String): Boolean = {
  var flag = true
  val dataSorted = data.sorted
  for (i <- 0 until dataSorted.length - 1 if flag == true) {
    if (dataSorted(i) == dataSorted(i + 1)) {
      flag = false
    }
  }
  flag
}

But sorting is not the best idea. When we use sorting, the time complexity is O(nlogn). For this problem we don’t care about sort result; we care the duplicate characters. In this case, we can use array to store the appearance times for each character. Here we assume the string only contains ASCII. The max number of characters is 256.

def uniqueCharacter(data: String): Boolean = {
  if (data.length > 256) {
    false
  } else {
    val recordData = new Array[Boolean](256)
    var flag = true
    for (each <- data if flag == true) {
      val index: Int = each.toInt
      if (recordData(index)) {
        flag = false
      } 
      recordData(index) = true
    }
    flag
  }
}

1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. Note: one or two additional variables are fine. An extra copy of the array is not.

At first, I use String as input, but I find I can’t assign a value to a char in a string. So i transfer the input to Array[Char].

def removeDuplicate(data: Array[Char]): String = {
  val recordData = new Array[Boolean](256)
  var length = 0
  for (i <- 0 until data.length) {
    if (!recordData(data(i).toInt)) {
      recordData(data(i).toInt) = true
      data(length) = data(i)
      length += 1
    }
  }
  data.mkString("").substring(0, length)
}

Test Cases for this solution are following:

  • string doesn’t contain any duplicates
  • string contains all duplicates:”aaaaaa”
  • null string
  • empty string
  • string with all continuous duplicates:”aaaabbbbb”
  • string with non-continuous duplicate:”ababababa”

1.4 write a method to decide if two strings are anagrams or not

Simply method which I can think out quickly after I see the question is to use sort.

def checkAnagrams(first: String, second: String): Boolean = {
  if (first.length != second.length) {
    false
  } else {
    if (first.sorted == second.sorted) {
      true
    } else {
      false
    }
  }
}

But sorting cost time, the better solution is O(n).

def checkAnagrams(first: String, second: String): Boolean = {
  if (first.length != second.length) {
    false
  } else {
    val record = new Array[Int](256)
    for (eachfirst <- first) {
      record(eachfirst.toInt) += 1
    }

    var flag = true
    for (eachsecond <- second if flag == true) {
      record(eachsecond.toInt) -= 1
      if (record(eachsecond.toInt) < 0) {
        flag = false
      }
    }
    flag
  }
}

1.5 write a method to replace all spaces in a string with ‘%20’

In Scala, there is a method, name replace can do this thing exactly. Here is the first simply solution:

def replaceSpace(data: String): String = {
  var returnString = ""
  for (each <- data) {
    if (each == ' ') {
      returnString += "%20"
    } else {
      returnString += each.toString
    }
  }
  returnString
}

But this method creates a new return string, which wastes memory space. We can make use of local space and create additional space for space and loop from back to front. In Scala, the length of Array is not changeable, but ArrayBuffer can.

1.6 Given an image represented by an N*N matrix, where each pixel in the image is bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

def rotate(data: Array[Array[Int]], row: Int): Array[Array[Int]] = {
  val center: Int = row / 2
  for (i <- 0 until center) {
    for (j <- 0 until center) {
      val temp = data(i)(j)
      data(i)(j) = data(row-1-j)(i)
      data(row-1-j)(i) = data(row-1-i)(row-1-j)
      data(row-1-i)(row-1-j) = data(j)(row-1-i)
      data(j)(row-1-i) = temp
    }
  }
  data
}

1.7 Write an algorithm such that is an element in an M*N matrix is 0, its entire row and column is set to 0.

Here we create two arrays to record zero status for the whole matrix.

def setZero(data: Array[Array[Int]], row: Int, col: Int): Array[Array[Int]] = {
  val rowArray = new Array[Boolean](row)
  val colArray = new Array[Boolean](col)
  for (i <- 0 until row if rowArray(i) == false) {
    for (j <- 0 until col if colArray(j) == false) {
      if (data(i)(j) == 0) {
        rowArray(i) = true
        colArray(j) = true
      }
    }
  }
  for (i <- 0 until row) {
    for (j <- 0 until col) {
      if (rowArray(i) == true || colArray(j) == true)
        data(i)(j) = 0
    }
  }
  data
}

1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring(i.e., “waterbottle’ is a rotation of erbottlewat”).

def checkRotation(first: String, second: String): Boolean = {
  var flag = false
  for (i <- 0 until first.length if flag == false) {
    if (isSubstring(first.substring(i, first.length), second) &&
      isSubstring(first.substring(0, i), second)) {
      flag = true
    }
  }
  flag
}