Category: Lintcode

Leetcode 69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis:

To get the sqrt of x, we can use binary search to have a mid value. Then check the value of mid * mid. If it equals to x, then that’s the sqrt. Otherwise, keep going and make the mid larger to less.

Note in the code, we should make the start, mid and end to be long to avoid the precision losing.

Time complexity: O(logn)

Space complexity: O(1)

Below is the code:

public class Solution {
    public int mySqrt(int x) {
        // O(logn) binary search
        
        // Corner case
        if (x == 0 || x == 1) {
            return x;
        }
        
        // Make them to be long 
        long start = 1;
        long end = x;
        
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            
            if (mid * mid <= x) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (start * start <= x) {
            return (int) start;
        } else if (end * end <= x) {
            return (int) end;
        }
        
        return 0;
    }
}

Lintcode String Compression

Lintcode String compression

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3.

If the “compressed” string would not become smaller than the original string, your method should return the original string.

You can assume the string has only upper and lower case letters (a-z).

str=aabcccccaaa return a2b1c5a3
str=aabbcc return aabbcc
str=aaaa return a4

Analysis:

Here we use StringBuilder to create a new String, instead of String concatenation. That’s because for String concatenation operation, it’ll build a new string for every operation.

The basic algorithm is:

  • Create stringbuilder and initialize the first temp char, with count = 1
  • Go through the string char by char
  • If char(i) equals to temp, continue and add count
  • If not, add the temp and count to stringbuilder, reset the temp to be char(i) and count to be 1
  • Go out of the loop and add the last char and count for it
  • Compare the stringbuilder with initial str

Time complexity: O(n) 

Space complexity: O(n)

The following is the code for the algorithm:

public class Solution {
    /**
     * @param str a string
     * @return a compressed string
     */
    public String compress(String str) {
        // Corner case
        if (str == null) {
            return null;
        } else if (str.length() <= 2) {
            return str;
        }
        
        StringBuilder sb = new StringBuilder();
        char temp = str.charAt(0);
        int count = 1;
        
        for (int i = 1; i < str.length(); i++) {             
           // If same char continues, then add the count             
           if (str.charAt(i) == temp) {                 
               count++;             
           } else {                   
           // Encounter different char, set temp to the char and count to 1       
              sb.append(temp);                 
              sb.append(count);                 
              temp = str.charAt(i);                 
              count = 1;             
           }         
       }                  

      // Do not forget the last char and the count!!!           
      sb.append(temp).append(count);                  

      // Compare the result of original str with the new stringbuilder            
      if (sb.length() >= str.length()) {
            return str;
      } else {
            return sb.toString();
      }
   }
}

Note: After go through the for loop, the temp is equals the last – 1 char, so we need to add the last char with its count.

Lintcode 366 Fibonacci

Lintcode 366 Fibonacci

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

  • The first two numbers are 0 and 1.
  • The i th number is the sum of i-1 th number and i-2 th number.

The first ten numbers in Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

Analysis:

This question is a mathematic formula, which defines the Fibonacci series. We can formalize is as:

  • f(0) = 0
  • f(1) = 1
  • f(n) = f(n-1) + f(n-2)

This comes out the the first method.

Recursive method:

public static int fib(int n) {
	// Base case
	if (n == 0) {
		return 0;
	}

	if (n == 1) {
		return 1;
	}
	
	return fib(n - 1) + fib(n - 2);
}

Another method is the non-recursive method:

Non-recursive method:

// Non-recursive method
public static int fib1(int n) {
	// Base case
	if (n <= 1) {
		return n;
	}

	int n1 = 0;
	int n2 = 1;
	int n3 = 0;

	for (int i = 2; i <= n; i++) {
		n3 = n1 + n2;
		n1 = n2;
		n2 = n3;
	}

	return n2;
}

Note:

  • we start from i = 2 
  • Here do not return n3, and return n2, which has been assigned by the value we want, with n2 = n3.

Lintcode 9 Fizz Buzz

Lintcode 9 Fizz Buzz

Given number n. Print number from 1 to n. But:

when number is divided by 3, print “fizz”.
when number is divided by 5, print “buzz”.
when number is divided by both 3 and 5, print “fizz buzz”.

Analysis:

This is a very basic interview question for software engineer job. Basically, we can start by the most intuitive solutions:

  • Check i is divided by 3, not divided by 5, print “fizz”
  • Check i is divided by 5, not divided by 3, print “fuzz”
  • Check i is both divided by 3 and 5, print “fizz buzz”
  • Other numbers, print out the number

Disadvantages: too much % checking. We can improve this by starting from checking 3 and 5, then 5, then 3, then other numbers. The process is like:

  • Check i is both divided by 3 and 5, print “fizz buzz”
  • Check i is divided by 3, not divided by 5, print “fizz”
  • Check i is divided by 5, not divided by 3, print “fuzz”
  • Other numbers, print out the number

This Code is written in below:

for (int i = 1; i <= n; i++) {
	// Start from 15
	if (i % 15 == 0) {
		System.out.println("fizz buzz");
	} else if (i % 5 == 0) { // check with 5
		System.out.println("buzz");
	} else if (i % 3 == 0) { // check with 3
		System.out.println("fizz");
	} else { // print out other nums
		System.out.println(i);
	}
}

Alternative method:
In some interviews, the interviewer requires to use only two module and get the same result. To make this work, we can have a number k to indicate different situations. With different case of k, then print out different result.

for (int i = 1; i <= n; i++) {
	int k = 1;
	if (i % 3 == 0) k++;
	if (i % 5 == 0) k += 2;

	switch(k) {
		case 1:
			System.out.println(i);
			break;

		case 2:
			System.out.println("fizz");
			break;

		case 3:
			System.out.println("buzz");
			break;

		case 4:
			System.out.println("fizzbuzz");
			break;
	}
}

If we take the n to be 20, then the result is:

1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz