> For the complete documentation index, see [llms.txt](https://wenbo-notes.gitbook.io/cs1010-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wenbo-notes.gitbook.io/cs1010-notes/past-year-exam/pe2-review/pe2-ay21-22.md).

# PE2 (AY21/22)

## Problems

Questions:

{% file src="/files/pVPjetXlXQm0VW5iUiVH" %}
Questions
{% endfile %}

Official Answers:

{% file src="/files/E2t54kNdgUcP2ujMbBsw" %}
Official Answers
{% endfile %}

### 1. Ease

This is a give-away question.

### 2. Max

This is also a give away question, the main part is to think about the logic of `is_larger()` clearly. My solution is below:

{% code lineNumbers="true" %}

```c
bool is_larger(char *s1, char *s2) {
  if (s1[0] == '-' && s2[0] != '-')
  {
    return false;
  }
  if (s1[0] != '-' && s2[0] == '-')
  {
    return true;
  }
  long len_s1 = (long)strlen(s1);
  long len_s2 = (long)strlen(s2);
  if (s1[0] == '-' && s2[0] == '-')
  {
    if (len_s1 > len_s2)
    {
      return false;
    }
    if (len_s1 < len_s2)
    {
      return true;
    }
    for (long i = 1; i < len_s1; i += 1)
    {
      if (s1[i] < s2[i])
      {
        return true;
      }
      if (s1[i] > s2[i])
      {
        return false;
      }
    }
    return false;
  }
  if (len_s1 > len_s2)
  {
    return true;
  }
  if (len_s1 < len_s2)
  {
    return false;
  }
  for (long i = 0; i < len_s1; i += 1)
  { 
    if (s1[i] > s2[i])
    {
      return true;
    }
    if (s1[i] < s2[i])
    {
      return false;
    }
  }
  return false;
}
```

{% endcode %}

### 3. Cycle

> This question utilises the idea of building a frequency table/counting sort

Okay, I think this question is not that interesting, that's because the most important information in this question is not given clearly. That is 148 is **the largest number** that is a "cycle", so this means our largest cycle number is 148, which should be the largest index of our frequency table.

### 4. Box\*

> This problem is a variation of binary search.

The tricky point is to deal with the edge/boundary cases. The change point is that:

1. If mid is '#', we change our search range to (mid+1, end)
2. If mid is '.' we change our search range to (start, mid)

And our base case is when our search range is 1 (`start==end`), we return `start`, which is either the first position of `.` or the position of the edge.

{% hint style="info" %}
In this problem, the `end` is not inclusive!
{% endhint %}

### 5. Path\*

This question is very likely to [PE1 Review](/cs1010-notes/past-year-exam/pe1-review.md#ex5-q6-social). The idea are very similar, the only thing that serves as a game changer is that you need an array `visited` to mark whether a person has appeared in your path or not.

## Tips

1. The `strlen()` from C standard lib `<string.h>` will return **the number of characters in a string** (excluding the terminating `'\0'`).
2. Whenever you see the Time complexity is $$O(logN)$$, try to think of **binary search**.