Coding Practice with Kick Start 2022 – Session #1 problem walkthroughs

Join Google engineers for a walk through of each problem from the first session of Coding Practice with Kick Start. They provide new approaches and tips to solve algorithmic and mathematical problems.

Chapters
0:00 - Introduction with Lizzie Sapiro Santor, Kick Start Program Manager
0:55 - Problem 1: Centauri Prime with Chidera Olibie, Software Engineer
4:21 - Problem 2: H-Index with Karnika Agarwal, Software Engineer
12:06 - Problem 3: Hex with Brendan Wood, Software Engineer
22:34 - Problem 4: Milk Tea with Hyuni Kim, Software Engineer
35:06 - Wrap up

#KickStart

[itsme]

My first kickstarter, It was a pain to even use the online editor, but I managed to pass till centauri prime but then spent hours trying to figure how to solve the h_index one and ran out of time. I am glad that I started this jam, and will definetely stick with it.

[prayaschaudhary]

I think time complexity of brute force for H-index problem will be O(N^3).

[AYUSHKUMAR-dcmx]

**Python Code**
*Centauri Prime*

# TODO: Complete the get_ruler function
def get_ruler(kingdom):
# TODO: Add logic to determine the ruler of the kingdom
# It should be either 'Alice', 'Bob' or 'nobody'.

s = kingdom[-1]
if s in "Yy":
ruler = "nobody"
elif s in "AEIOUaeiou":
ruler = 'Alice'
elif s not in "AEIOUaeiou":
ruler = "Bob"

return ruler

def main():
# Get the number of test cases
T = int(input())
for t in range(T):
# Get the kingdom
kingdom = input()
print('Case #%d: %s is ruled by %s.' % (t + 1, kingdom, get_ruler(kingdom)))

if __name__ == '__main__':
main()

[whymhere]

H-index question can be solved with Fenwick Tree (or Binary Indexed Tree) and Binary Search too

[sushilchettri]

This was my first time trying, could do just centauri prime both one was funny, made an algorithm for hrs and after it was working perfectly for the sample code, came to know that the players can win through diagonally too 😂 ....well i should have checked that it was a rhombus, and that milk tea one, made an algorithm to produce the desired output but couldn't handle how to modify the output according to the forbiddens
It was a great experience, thanks ...honestly it was a little bit frustrating but I ll do my best next time, i hate h-index one, it hurts my brain

[ilyapavlenko]

Everything is 'solvable' imho, except the HEX problem which was tricky 4 me

[wekness_spotter]

These events do are really good but I would highly suggest that the explanations of these videos should also be good because people like me have a lot problem understanding especially with unclear messages and understanding in language like java (which is not what everyone know properly).

[farkon]

Actually I think I inplomented right solution for H-index. But while competition it gave Time Limit Expaction. Propably it`s just slow python ):

[kartikgoswami]

This was my first time trying, i easily solved sample and centauri prime without any serious help.... I was not even able to understand the other questions : }, I was doing this question late night with my friend we both enjoyed laughed, cried but this all was fun. I am still trying to solve "milk tea" without any help
this was really a great experience (my eyes are still hurting) I will do my best next time and solve all problems on my own

[kadgx]

Something about walking the boundary between red and blue in the hex seems a bit off... if the last piece placed wasn't on the far edge, for example... it might be possible that removing a piece from the far edge doesn't remove the "win", when removing a middle piece would.

[quanglongbui]

In the solution, instead of comparison to 'y' or 'Y'. I convert it to lowerCase at the line to easier and after that I just compare to 'y' instead above. In addtion, we can only check the character that include or not in set, no matter the order of each elements of set. So, I have implemented the TreeSet for that.

[akasegaonkar]

My code for Hex is an O(n^2) solution (that ACed), and I'm pretty sure is wrong

For red, I traversed from bottom left to bottom right and called dfs from each node coloured red to check if it reached the top row. I assigned priorities for the dfs traversal (i.e. for each hexagon, first visit the top left if red, then left if red, etc. in an anticlockwise manner).

While writing the code, I thought that since we would be choosing the "leftmost" path every single time, we could find out if that there were atleast two paths from bottom to top to prove that a case is impossible. Similar approach for blue hexagons as well (but mirrored).

My code passed both test cases, and after giving some thought I realised that my code was incorrect (figured out some counter examples, where you would prefer to got bottom left over top left).

So is this a case of me being lucky (weak test cases) or is my solution correct?

[chits]

In Centaury prime source code @ time 4:03, test case should start with t=1 t <=T .

[anubhabsahu]

Happy to see Indian names getting featured #KARNIKAAGARWAL

[pampanasubrahmanyam]

In H-Index problem for the test case N=3; 5 1 2 ; at line A[N if Citations[i]>N else citation[i]] we will get index out of range error right as A is [0, 0, 0] but we are trying to set A[5]+=1 at i=0?

[bhavin]

Thanks for that, for problem 4 Milk tea, at each step we are getting rid of prefix that has score more than M+1 element in that step. What if that prefix at the time was having higher score but at the end of P bits the score actually is lower. We were asked to get the smallest complanins, doesn't have mean we might have prefix removed in a step but actually it was with the smallest complaints ?
I don't have specific example at the moment but please let me what am i missing in this thinking ?

[JisKriker]

Thanks for the walk through. Next to the technical content, it is encouraging to see, that one doesn't need to have English as a mother tongue to be a Google SE.

[Mandeepsingh-jocf]

I tried TEA (last) problem and don't know where this code gets wrong can anyone please help:
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<algorithm>
#include<math.h>

using namespace std;

bool maxer(pair<string, int>& a, pair<string, int>& b) {
return a.second < b.second;
}

bool checkit(vector<string> a, string b) {
for (auto j : a) {
if (j == b)
return true;
}
return false;
}

int main() {

int t, caser = 1;
cin >> t;

while (t--) {

int n, m, p;
cin >> n >> m >> p;
vector<string> a(n), checku(m);
vector<int> scores(p);
for (int i = 0; i < n; i++)
cin >> a[i];

for (int i = 0; i < m; i++)
cin >> checku[i];

for (int i = 0; i < p; i++) {
int ones = 0;
for (int j = 0; j < n; j++) {
if (a[j][i] == '1') {
ones++;
}
}
scores[i] = ones;
}

map<string, int> maper;
vector<pair<string, int>> dum;
string stringer;

int comb = (pow(2, p) - 1), ans = 10000;
m = 100 < comb ? 100 : comb;

for (int i = 0; i < p; i++) {

if (dum.size()) {
int si = dum.size();

for (int j = 0; j < si; j++) {
stringer = dum[0].first;
string h = stringer;
stringer += "0";
dum.push_back({ stringer, maper[h] + scores[i] });
maper[stringer] = maper[h] + scores[i];
stringer.pop_back();

stringer += "1";
dum.push_back({ stringer, maper[h] + (n - scores[i]) });
maper[stringer] = maper[h] + (n - scores[i]);
stringer.pop_back();

dum.erase(dum.begin() + 0);
}

sort(dum.begin(), dum.end(), maxer);
int q = dum.size() - m;
while (q > 0) {
dum.pop_back();
q--;
}

}
else {
stringer = "";
stringer += "0";
int z = scores[0];
dum.push_back({ stringer, z });
maper[stringer] = scores[0];
stringer.pop_back();

stringer += "1";
int o = n - scores[0];
dum.push_back({ stringer, o });
maper[stringer] = o;
stringer.pop_back();

}

}

for (auto r : dum) {
if (!checkit(checku, r.first))
ans = ans < r.second ? ans : r.second;

}

cout << "Case #" << caser << ": " << ans << "\n";
caser++;

}

return 0;
}

[TesterAnimal]

What if it the country ends with À or Å or Ö or Ø etc etc? Lots of codepoints correspond to vowels in various languages.

[brentmcd]

is this read write data ? the blue /red game ?