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
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s