CS-OA cs-vo Faang

Welcome to Summer 2024-Core/DatabaseEngineering Intern Test

Q1. Sequential String

A special string s of length n consists of characters 0-9 only. Its characters can only be accessed sequentially i.e. the first '1' chosen is the leftmost '1' in s. There is an array arr of m strings, also consisting of characters 0-9. Calculate the minimum number of characters needed from s to construct a permutation of each of the strings in arr.

Return an array of integers where the ℎith element denotes the minimum length of a substring that contains a permutation of the ℎith string in arr. If a string cannot be constructed, return -1 at that index.

Example

Consider n=12,n="064819483898",3,=["088","364","07"]n=12,s="064819483898",m=3,arr=["088","364","07"]

  • To construct "088", Alice needs to access the first 7 characters ("0648194") of the special string and use only '0', '8', and '8'. Since the characters can be rearranged, the results for '088', '808', and '880' are all 7.
  • To construct "364", access the first 10 characters ("0648194838") of the special string and use only '6', '4', and '3'. Rearrange to match "364".
  • String "07" cannot be constructed from the special string. No '7' is available.

The return array is [7, 10, -1]. Note that only bolded characters are used to construct the strings.

Function Description

Complete the function countMinimumCharacters in the editor below.

countMinimumCharacters(string s, vector<string> arr) -> vector<int>


The image also shows a code editor with the implementation of the countMinimumCharacters function and a note that all available test cases passed.

Q2 Coloring Houses

The city of Hackerland can be represented with an even number n houses arranged in a row. A painter must paint the houses using at most three colors. The following conditions must hold true:

  1. No two adjacent houses are the same color.
  2. The houses which are at the same distance from both ends must not be colored with the same color. For example, 6n=6 then houses will be [1,2,3,4,5,6][1,2,3,4,5,6], so the houses at the same distance from both the ends will be [1,6],[2,5],[3,4][1,6],[2,5],[3,4].

The task is to find the number of ways to paint the houses using at most three colors such that both the above conditions hold true. Since the answer can be large, report it modulo 109+7109+7. Two ways are considered different if at least one house is colored differently.

Example

For 4n=4, some of the possible valid arrangements are:

  • (color1,color2,color3,color2)(color1,color2,color3,color2)
  • (color1,color3,color1,color3)(color1,color3,color1,color3)

The number of ways to paint 4 houses using three colors is 18. Return 18 modulo (109+7)(109+7) which is 18.

Function Description

Complete the countWaysToColorHouses function in the editor below.

我们还提供VO辅助,面试代面,如果有需要请联系我

If you need a complete question bank or assistance, please contact us.

有任何OA均可以联系我,100%AC,错一个不收钱。如果害怕自己解决不了OA,请扫码联系我 or telegram

If you're afraid that you can't solve the OA on your own, please scan the code to contact me or telegram