Look and Say sequence problem [reviewed]

Problem

Implement the pattern function producing the following pattern:

  0: 1
  1: 11
  2: 21
  3: 1211
  4: 111221
  5: 312211

 Your function should generate the string sequences shown above, given the input as a integer.

  For example, input = 4, output should be 111221

We first need to understand what "Look and Say sequence" to solve this problem.

Starting with 1, your algorithm "11", which is read "one one".
The first "1" is the number of "1" shown.
"11" produce "21", equivalent to "two one".

Now, you need to write the algorithm counting the occurrence of the same number while traversing from the left to right and store the result as "count integer" in a separate string.

We just need to perform the step above as many as the given input until returning the result.

Here is the algorithm running in O(NM), where N is the given input, M is the longest look-and-say string processed.



Practice statistics

14:12 min to write up the code with logical flaw
2:18 min to fix up the typo
9:53: to debug the logical flaws through compilation.


UPDATE(2019-07-26): Solve the problem again in python.
Was able to finish the code in 17 mins. No typos this time !!

Here is a solution in python.



Practice statistics
10:00: to come up with algorithm for look and say and write the code half way

7:00: to write the code. (No bug !! Good job !!)


Comments

Post a Comment

Popular posts from this blog

Planting flowers with no adjacent flower plots

Image
Problem Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die. Given a flowerbed (represented as an array containing booleans), return if a given number of new flowers can be planted in it without violating the no-adjacent-flowers rule  Sample inputs  Input: 1,0,0,0,0,0,1,0,0  3 => true  4 => false  Input: 1,0,0,1,0,0,1,0,0  1 => true  2 => false  input: 0  1 => true  2 => false  public boolean canPlaceFlowers(List flowerbed, int numberToPlace) {  // Implementation here  }
Read more
  Given an array of  intervals  where  intervals[i] = [start i , end i ] , merge all overlapping intervals, and return  an array of the non-overlapping intervals that cover all the intervals in the input . Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: 1 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i <= end i <= 10 4
Read more

Find the maximum number of bomb that can be detonated

  Problem You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb. The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range. You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range.  These bombs will further detonate the bombs that lie in their ranges. Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb. Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So...
Read more