# Barikote Ramen, Cerveja de Wasabi, Meu Nome é Chihiro e Primeiro Kimchi

2023-04-01 tag_movies tag_beer tag_food ^ ctrl_c

Mais um lámen experimentado hoje. Dessa vez foi o próximo da Brigadeiro. Minúsculo. Você pede antes de entrar, em um painel. Estilo bem japonês, mas toca música de anime lá dentro. Pedi o Tantan Men da casa e ele é melhor que Tantan do Momo. A base do caldo de todos os lámens da casa é tonkotsu, mas não achei tão intenso quanto o do Ikousha. O forte desse lámen é seu equilíbrio entre picância, carne, umami e o uso de amêndoas.

Tinha umas cervejas diferentonas e caras. Pedi uma Pale Ale com Wasabi, a Wasabiru. O sabor não lembra nada a pimenta japonesa. No máximo o amargor? Mas Pale Ale também é amargo. Podem ser amargores diferentes... não, é só truque psicológico. Se não me dissessem que tem Wasabi eu nem iria perceber.

A Mitiko pediu um doce que é uma espécie de bolinho frito com um creme de melão dentro. O creme tem o cheiro e o gosto exatos daquele sorvete, o Melona.

Assistimos um filme japonês em casa, desses subversivos japoneses da Netflix. Chama Meu Nome é Chihiro e é sobre uma ex- acompanhante que está trabalhando em uma casa de obentô. Ela já pensou em se matar e faz sexo quando tem vontade. Ela é um ser solitário orbitando sua quase vida sem buscar nada em especial, mas acaba encontrando amizades pelo caminho, de crianças e velhos. Há uma relação paternal com seu ex chefe do bordel que se revela como aqueles estudos de constelação familiar. O filme é bem lento, não chega a lugar nenhum e para se movimentar você precisa de diálogos expositivos. Tudo que é importante é falado e o que é visto é apenas sugerido e não possui potência na mensagem. O filme se apaixona por paisagens de beira mar, por do sol, e se esquece do espectador. O filme não está interessado em interagir com o espectador. Assim como Chihiro. É introspectivo, filme de elevador.

Mas, mudando de pato pra ganso, meu Kimchi ficou bom. 48 horas fermentando em um calor de 30 graus e ele começa a ficar mais azedo e menos intenso na pimenta vermelha coreana. Degustei ele e um que compro no mercado do Rudge Ramos, em São Bernardo do Campo, e ele pareceu mais intenso. Pode ser pelo frescor. A receita que usei, de uma senhora coreana explicada mal e porcamente pela sua filha, parece uma boa base para experimentação. É necessário alguns itens exóticos como nabo e maçã, mas o resultado ficou bacana. Vamos ver sua evolução.

# Instalei um contador de visitas

2023-04-04 ^ ctrl_c

Estou revisando como fazer para estar no Flow durante leisure time e uma das poucas regras necessárias é que você precisa coletar feedback sobre como está indo na atividade. No caso da escrita achei difícil eu mesmo ser o responsável por esse feedback, principalmente por não estar sendo no momento um leitor assíduo. Então minha primeira ideia foi saber se pessoas estão lendo meus posts, aproveitando o fato deles serem públicos.

Para minha surpresa hoje me deparo, além das minhas próprias visitas, alguém lendo sobre a sorveteria Banana da Terra em Morretes. Com certeza não sou eu, já que o dispositivo é um MacOS e dos EUA. Outro acesso tinha relação com o vcpkg.

Não sei bem se esse é um analytics com histórico ou são os acessos de tempo real. De qualquer forma agora já sei de pelo menos alguém que está acessando o blogue. Isso é um feedback válido? Deixe o que acha nos comentários.

Ops, não há comentários no blogue. Não dá para aguentar tanto feedback da humanidade.

# Flow pragmático

2023-04-05 tag_essays ^ ctrl_c

Seja durante o trabalho ou no lazer, quando não está claro qual o objetivo final não é fácil focar.

Por isso reli minhas anotações sobre o livro de Mihaly Csikszentmihalyi sobre como estruturar nossa consciência de forma a conseguir aos poucos alinhar a energia psíquica a maior parte do tempo possível. E deve ser aos poucos, já que o "eu" não pode se sentir impelido a fazer algo; ele precisa entender dentro de si o que ele quer fazer mais que tudo na vida.

> Uma artista original começa um novo trabalho com uma forte intuição e objetivos indefinidos, se mantém modificando o trabalho em resposta a resultados inesperados que surgiram, e termina com um trabalho concluído que não lembra em nada o que havia imaginado no começo. Se a artista é responsável pelos seus sentimentos internos, sabe o que ela gosta e o que ela não gosta, e presta atenção ao que está acontecendo, um bom trabalho está prestes a emergir.

Dentro dos meus recortes compilei e agrupei esta lista de ações em dicas mais compactadas e temáticas dos ensinamentos do livro para induzir um call to action mais pragmático:

Seja estoico

• Ignore obrigações externas desde o começo.
• Se livre das recompensas sociais e fisiológicas.
• Aprenda a controlar o corpo e seus sentidos.
• Seja você o desejo de aprender.

Seja humilde

• Defina o objetivo geral e secundários.
• Vá definindo minidesafios envolvidos na atividade.
• Se concentre no que você está fazendo.
• Se a atividade se tornar chata continue aumentando as apostas.

Seja prático

• Encontre qual o feedback para medir seu progresso.
• Centralize sua atenção em objetos externos.
• Sem input externo falta a atenção e começam os devaneios.
• Desenvolva habilidades para oportunidades disponíveis.

Recortes

> The solution is to gradually BECOME FREE OF SOCIETAL REWARDS and learn how to substitute for them rewards that are under one's own powers. This is not to say that we should abandon every goal endorsed by society; rather, it means that, in addition to or instead of the goals others use to bribe us with, we develop a set of our own.

> (...) unless a person LEARNS TO SET GOALS AND TO RECOGNIZE AND GAUGE FEEDBACK (...) she will not enjoy them (activities).

> Because most jobs, and home life in general, lack the pressing demands of flow experiences, concentration is rarely so intense that preoccupations and anxieties can be automatically ruled out. Consequently the ordinary state of mind involves unexpected and frequent episodes of entropy interfering with the smooth run of psychic energy.

> Some things we are initially forced to do against our will turn out in the course of time to be intrinsically rewarding.

> When a society suffers from anomie, flow is made difficult because it is not clear what is worth investing psychic energy in; when it suffers from alienation the problem is that one cannot invest psychic energy in what is clearly desirable.

> Gradually I learned to be indifferent to myself and my deficiencies; I came to CENTER MY ATTENTION INCREASINGLY UPON EXTERNAL OBJECTS: the state of the world, various branches of knowledge, individuals for whom I felt affection.

> (...) the easiest step toward improving the quality of life consists in simply LEARNING TO CONTROL THE BODY AND ITS SENSES.

> (a) to SET AN OVERALL GOAL, AND AS MANY SUBGOALS as are realistically feasible; (b) to FIND WAYS OF MEASURING PROGRESS in terms of the goals chosen; (c) to KEEP CONCENTRATING ON WHAT ONE IS DOING, and to KEEP MAKING FINER AND FINER DISTINCTIONS IN THE CHALLENGES INVOLVED IN THE ACTIVITY; (d) to DEVELOP THE SKILLS NECESSARY TO INTERACT WITH THE OPPORTUNITIES AVAILABLE; and (e) to KEEP RAISING THE STAKES if the activity becomes boring.

> Leisure that uses up external resources, however, often requires less attention, and as a consequence it generally provides less memorable rewards.

> (...) the importance of personally TAKING CONTROL OF THE DIRECTION OF LEARNING FROM THE VERY FIRST STEPS cannot be stressed enough. If a person feels coerced to read a certain book, to follow a given course because that is supposed to be the way to do it, learning will go against the grain. But if the decision is to take that same route because of an inner feeling of rightness, the learning will be relatively effortless and enjoyable.

> Giving up the self with its instincts, habits, and desires is so unnatural an act that only someone supremely in control can accomplish it.

> (...) keeping order in the mind from within is very difficult. We need external goals, external stimulation, external feedback to keep attention directed. And WHEN EXTERNAL INPUT IS LACKING, ATTENTION BEGINS TO WANDER, AND THOUGHTS BECOME CHAOTIC -- resulting in the state we have called "psychic entropy" (...)

> Even pain is better than the chaos that seeps into an unfocused mind. Hurting oneself, whether physically or emotionally, ensures that attention can be focused on something that, although painful, is at least controllable -- since we are the ones causing it.

> The ultimate test for the ability to control the quality of experience is what a person does in solitude, with no external demands to give structure to attention. It is relatively easy to become involved with a job, to enjoy the company of friends, to be entertained in a theater or at a concert. But what happens when we are left to our own devices? Alone, when the dark night of the soul descends, are we forced into frantic attempts to distract the mind from its coming? Or are we able to take on activities that are not only enjoyable, but make the self grow?

> A person who rarely gets bored, who does not constantly need a favorable external environment to enjoy the moment, has passed the test for having achieved a creative life.

> If a person is unwilling to ADJUST PERSONAL GOALS WHEN STARTING A RELATIONSHIP, then a lot of what subsequently happens in that relationship will produce disorder in the person's consciousness, because novel patterns of interaction will conflict with old patterns of expectation.

> The process of discovering new goals in life is in many respects similar to that by which an artist goes about creating an original work of art. Whereas a conventional artist starts painting a canvas knowing what she wants to paint, and holds to her original intention until the work is finished, an original artist with equal technical training commences with a deeply felt but undefined goal in mind, keeps modifying the picture in response to the unexpected colors and shapes emerging on the canvas, and ends up with a finished work that probably will not resemble anything she started out with. If the artist is responsive to her inner feelings, knows what she likes and does not like, and pays attention to what is happening on the canvas, a good painting is bound to emerge. On the other hand, if she holds on to a preconceived notion of what the painting should look like, without responding to the possibilities suggested by the forms developing before her, the painting is likely to be trite.

> For an autotelic person, the primary goals emerge from experience evaluated in consciousness, and therefore from the self proper.

# Não capture este cachorro [link]

2023-04-05 tag_chess ^ ctrl_c

Um jogo onde me esforcei em dar o mate, mesmo sem saber muito se iria dar certo. Acabou que existiu oportunidade para ambos os lados, equilíbrio e muitos erros, claro.

Capture este cachorro e dou mate em 1.

1. Nf3 d5 2. g3 Nc6 3. Bg2 Nf6 4. d4 e6 5. b3 Bd6 6. Bb2 O-O 7. Nbd2 b5 8. O-O
a6 9. Re1 Bb7 10. Rc1 Nb4 11. a3 Nc6 12. Ba1 Bxa3 13. Rb1 Re8 14. c3 Bd6 15. b4
Ne7 16. Qb3 Nf5 17. e3 Nh6 18. Qc2 Nhg4 19. Ng5 g6 20. Ndf3 h6 21. Nh3 Ne4 22.
Nd2 Nxd2 23. Qxd2 e5 24. e4 exd4 25. f3 Ne3 26. cxd4 Nxg2 27. Kxg2 dxe4 28. d5
exf3+ 29. Kxf3 Rxe1 30. Rxe1 a5 (30... Bxb4  $146ão parece uma variante tão boa,
mas aos poucos as negras vão expondo o rei.} 31. Qxb4 Qxd5+ 32. Re4 c5 33. Qb1
Qd2) 31. Qxh6 {Já é M11 (12+ se sacrificar mais peças).} 31... Bxd5+ 32. Kf2 f6
33. Ng5  $146ão capture este cachorro.} (33. Qxg6+ {Este era o lance.}) 33... fxg5
(33... Qd7  $146ão parece que segura, mas tem um duplo que captura o bispo.} 34.
Bxf6 Qf5+ 35. Kg1 Qxf6 36. Qh7+ Kf8 {E só fica equilibrado porque no lance
seguinte as negras perdem a dama.} 37. Rf1 Qxf1+ 38. Kxf1) 34. Qh8+ Kf7 35. Qg7#
1-0

# Timemore C2 [link]

2023-04-05 tag_coffee ^ ctrl_c

Chegou meu segundo moedor manual depois do quebra-galho que foi o Hario Slim por mais de dois anos. Depois de muito pesquisar fiquei muito satisfeito em comprar este modelo da Timemore, por três motivos.

Para começar o custo/benefício é imbatível. Há muitos moedores manuais hoje em dia, mas nenhum entrega tanta qualidade com tão poucos moluscos. No caso da Timemore a construção de seu moedor de entrada é barateado por conta de algumas partes feitas em plástico reforçado, mas ainda assim a engenharia por trás do mecanismo criado por eles impressiona por não ser um top de linha. A sensação ao segurar um moedor desse é que ele parece mais caro.

Depois do custo o que mais me conquistou com certeza foi sua velocidade e comodidade. Estou acostumado a gastar cerca de três minutos todos os dias para moer meu café no Hario Slim, e isso sabendo que havia várias opções mais rápidas no mercado. Agora eu me sinto mais zen e privilegiado em conseguir colocar minha água para esquentar e apenas depois começar a pesar os grãos e moê-los, pois eu sei que o máximo de tempo que irei gastar são 40 segundos (isso moendo para Aeropress). Eu gostaria de dizer que não tem preço para isso, mas na verdade tem. Olhe o item anterior =)

Por fim, e apesar de já ter tocado no assunto de qualidade, acredito que o conjunto deste motivo final poderia ser chamado de versatilidade. Isso porque a fabricação do moedor permite futuros upgrades das mós, além de sua suposta longevidade (e rapidez, claro) me permitir relaxar por mais que dois anos dessa vez. Enquanto não me aventuro no espresso, o único ponto fraco deste moedor de acordo com os reviews, posso com alegria explorar muitas opções de moagem e de extração dessa bebida gloriosa de todas as manhãs.

Cliques sugeridos

• Espresso: 7-10 clicks
• Moka Pot: 9-11 clicks
• **Aeropress**: 13-14 clicks (testando com sucesso 11)
• Siphon (cloth): 13-15 clicks
• **Pour Over (cloth)**: 13-15 clicks
• Siphon (metal, glass filter): 15-16 clicks
• **Pour Over (paper)**: 15-17 clicks
• Chemex: 17-19 clicks
• Pour Over (metal filter): 18-20 clicks
• **Press Pot**: 25-29 clicks

# Como analisar assembly x64 [link]

2023-04-05 tag_debugging tag_videos ^ ctrl_c

Recomendo a leitura do artigo "X64 Deep Dive" para se habituar às idiossincrasias sobre o formato assembly do x64, especialmente se você costuma depurar assembly para Windows. O artigo descreve as novas funcionalidades que suportam os 64 bits do formato do executável Windows, o Portable Executable, além de explicar em detalhes o funcionamento de mecanismos que mudaram, como o tratamento de exceção (e o unwinding no código).

Criei um repositório para praticar alguns desses assuntos e recriar algum código-fonte para mostrar como o Visual Studio gera código em x64 e como depurar este código. Através deste repo e do vídeo que pretendo gravar a respeito caminharemos pelas mudanças desde o x86 para aumentarmos nossas habilidades em debugging de código x64. Entre algumas mudanças segue uma lista do que considerei mais importante:

• Fastcall é a convenção de chamada default para x64.
• RBP não é mais usado como frame pointer.
• A última chamada da função pode ser otimizada com tail elimination.
• Com isso o FPO (Frame Pointer Omission) pode comer solto.
• RSP se mantém inalterado no corpo da função, entre o prólogo e o epílogo (gostei disso).
• A técnica de homing space (opcional na compilação) salva os 4 primeiros parâmetros passados na pilha para a memória.
• O Child-SP (RSP) é usado para caminhar tanto pelos parâmetros quanto pelas variáveis locais.

Testes

FastCall

/*
"Fastcall registers are used to pass parameters to functions. Fastcall is the
default calling convention on X64 where in the first 4 parameters are passed via
the registers RCX, RDX, R8, R9." - X64 Deep Dive
int TestFastCall() {
push        rdi
sub         rsp,30h # RBP is no longer used as frame pointer.
	int res = FastCallTest(1, 2, 3, 4);
mov         r9d,4
mov         r8d,3
mov         edx,2
mov         ecx,1
call        FastCall
mov         dword ptr res,eax
	return res;
mov         eax,dword ptr res
}
add         rsp,30h # RBP is no longer used as frame pointer.
pop         rdi
ret
*/

Tail Call Elimination

/*
"X64 compiler can optimize the last call made from a function by replacing it
with a jump to the callee. This avoids the overhead of setting up the stack
frame for the callee." - x64 Deep Dive
# TailCall3
	return a + b;
lea         eax,rcx+rdx
}
ret
# TestTailCallElimination
	TailCall1(1);
	TailCall2(2);
	return TailCall3(1, 2);
mov         edx,2
lea         ecx,rdx-1
jmp         TailCall3
*/

Frame Pointer Omission

/*
"Unlike the X86 CPU where the EBP register is used to access parameters and
local variables on the stack, X64 functions do not make use of the RBP register
for this purpose i.e. do not use the EBP register as a
frame pointer." - x64 Deep Dive
# Win32 (x86)
int TestFramePointerOmission() {
	return 1;
00601593  mov         eax,1
}
00601599  ret
# Win62 (x64)
int TestFramePointerOmission() {
	return 1;
00007FF7D6E215E2  mov         eax,1
}
00007FF7D6E215E8  ret
*/

RSP Is The Same

/*
Since RSP is used to reference both parameters and local variables in x64,
the side effect and feature of x64 function is that RSP does not change
thru all its body, changing only in prolog (begin) and epilog (end) parts
of the function.
# Win32
int RSPIsTheSame(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8) {
# prolog-begin
push        ebp
mov         ebp,esp
# prolog-end
	RSPIsTheSameCall1(p1);
mov         eax,dword ptr p1
push        eax # RSP--
call        RSPIsTheSameCall1
add         esp,4 # RSP++
	RSPIsTheSameCall4(p1, p2, p3, p4);
mov         ecx,dword ptr p4
push        ecx # RSP--
mov         edx,dword ptr p3
push        edx # RSP--
mov         eax,dword ptr p2
...
call        RSPIsTheSameCall4
add         esp,10h # RSP++
	RSPIsTheSameCall8(p1, p2, p3, p4, p5, p6, p7, p8);
mov         edx,dword ptr p8
push        edx # RSP--
...
call        RSPIsTheSameCall8
add         esp,20h # RSP++
	return 1;
mov         eax,1
}
# epilog-begin
pop         ebp
# epilog-end
ret
# Win64
int RSPIsTheSame(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8) {
# prolog-begin
mov         dword ptr rsp+20h,r9d
mov         dword ptr rsp+18h,r8d
mov         dword ptr rsp+10h,edx
mov         dword ptr rsp+8,ecx
push        rdi
sub         rsp,40h # RSP last change
# prolog-end
	RSPIsTheSameCall1(p1);
mov         ecx,dword ptr p1
call        RSPIsTheSameCall1
	RSPIsTheSameCall4(p1, p2, p3, p4);
mov         r9d,dword ptr p4
...
call        RSPIsTheSameCall4
	RSPIsTheSameCall8(p1, p2, p3, p4, p5, p6, p7, p8);
mov         eax,dword ptr p8
mov         dword ptr rsp+38h,eax
...
call        RSPIsTheSameCall8
	return 1;
mov         eax,1
}
# epilog-begin
add         rsp,40h # RSP restore
pop         rdi
# epilog-end
ret
*/

Homing Space

/*
"(...) homing space and is used to store parameter values if either the function
accesses the parameters by address instead of by value or if the function is
compiled with the /homeparams flag. The minimum size of this homing space is
0x20 bytes or four 64-bit slots, even if the function takes less than 4
parameters. When the homing space is not used to store parameter values, the
compiler uses it to save non-volatile registers." - x64 Deep Dive
"The register based parameter homing space exists only for non-leaf 
functions." - x64 Deep Dive
# Win64 Debug
int HomingSpaceNonLeaf(int p1, int p2, int p3, int p4) {
mov         dword ptr rsp+20h,r9d # homing space saving params
mov         dword ptr rsp+18h,r8d
mov         dword ptr rsp+10h,edx
mov         dword ptr rsp+8,ecx
push        rdi
sub         rsp,20h
# Win64 Release
int TestHomingSpaceNonLeaf() {
sub         rsp,28h
	int ret = HomingSpaceNonLeaf(1, 2, 3, 4);
mov         edx,2 # even begin non-leaf function, params are not saved in release
lea         r9d,rdx+2
lea         r8d,rdx+1
lea         ecx,rdx-1
call        HomingSpaceNonLeaf
*/

Child-SP

/*
"The value of the Child-SP register displayed by the debugger's "k" command
represents the address at which the stack pointer (RSP) points to, as the point
where the function displayed in that frame, has finished executing its prolog.
The next item that would be pushed on the stack would be the return address of
the function as it invokes its callees. Since X64 functions do not modify the
value of RSP after the function prolog, any stack accesses performed by the rest
of the function are done relative to this position of the stack pointer. This
includes access to stack based parameters and local variables." - x64 Deep Dive
*/
# Win64 Debug
			p5 = i + j + (i % 2 ? p1 : p2) + (j % 2 ? p3 : p4);
mov         eax,dword ptr rsp+0Ch
cdq
and         eax,1
xor         eax,edx
sub         eax,edx
test        eax,eax
je          ChildSPF3+0BBh
mov         rax,qword ptr p1
mov         eax,dword ptr rax
mov         dword ptr rsp+14h,eax # reference child-sp
jmp         ChildSPF3+0C6h
mov         rax,qword ptr p2
mov         eax,dword ptr rax
mov         dword ptr rsp+14h,eax # reference child-sp
mov         eax,dword ptr rsp+10h # reference child-sp
cdq
and         eax,1
xor         eax,edx
sub         eax,edx
test        eax,eax
je          ChildSPF3+0E3h
mov         rax,qword ptr p3
mov         eax,dword ptr rax
mov         dword ptr rsp+18h,eax # reference child-sp
jmp         ChildSPF3+0EEh
mov         rax,qword ptr p4
mov         eax,dword ptr rax
mov         dword ptr rsp+18h,eax # reference child-sp
mov         eax,dword ptr rsp+10h # reference child-sp
mov         ecx,dword ptr rsp+0Ch # reference child-sp
add         ecx,eax
mov         eax,ecx
add         eax,dword ptr rsp+14h # reference child-sp
add         eax,dword ptr rsp+18h # reference child-sp
mov         rcx,qword ptr p5
mov         dword ptr rcx,eax

Parameter Retrieval

/*
"(...) as execution progresses within the function body, the contents of the
parameter registers change and the initial parameter value gets overwritten. So,
to determine the value of these register based parameters at any point during
function execution, one needs to find out - where is the value of the parameter
being read from and where is the value of the parameter being written to?
Answers to these questions can be found by performing a sequence of steps in the
debugger which can be grouped as follows: Determine if the parameters are loaded
into the registers from memory. If so, the memory location can be examined to
determine the parameter values. Determine if the parameters are loaded from
non-volatile registers and if those registers are saved by the callee. If so,
the saved non-volatile register values can be examined to determine the
parameter values. Determine if the parameters are saved from the registers into
memory. If so, the memory location can be examined to determine the parameter
values. Determine if the parameters are saved into non-volatile registers and if
those registers are saved by the callee. If so, the saved non-volatile register
values can be examined to determine the parameter values." - x64 Deep Dive
# Win64 Release
1. Parameters are loaded into the registers from memory.
mov         dword ptr rbp+30h,5 # p5 = 5
mov         dword ptr rbp+28h,6 # p6 = 6
mov         dword ptr rbp+20h,7 # p7 = 7
mov         dword ptr rbp+18h,8 # p8 = 8
call        ChildSPF1
2. Parameters are loaded from non-volatile registers and those registers
are saved by the callee.
	int oldP7 = *g_ParameterRetrieval_p7_retrieval;
	return p1 + p2 + p3 + p4 + p5 + p6 + oldP7 + p8;
mov         eax,dword ptr rdx
mov         r10,rcx
add         eax,dword ptr r8
add         eax,dword ptr r9
mov         rdx,qword ptr p5
mov         rcx,qword ptr g_ParameterRetrieval_p7_retrieval
3. Parameters are saved from the registers into memory.
# Win64 Release
	g_ParameterRetrieval_p7_retrieval = &p7;
mov         r10,qword ptr p7
mov         r11,rcx
	return p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
mov         rcx,qword ptr p8
mov         qword ptr g_ParameterRetrieval_p7_retrieval,r10 # save nonvolatile register
4. Parameters are saved into non-volatile registers and those registers
are saved by the callee.
# Win64 Release
int ParameterRetrieval3(int& p1, int& p2, int& p3, int& p4, int& p5, int& p6, int& p7, int& p8) {
mov         qword ptr rsp+8,rbx
mov         qword ptr rsp+10h,rsi
mov         qword ptr rsp+18h,rdi
mov         qword ptr rsp+20h,r14
push        r15 # saves what will be p7
	int oldP7 = p7;
	for (int i = 0; i < 7; ++i) {
		p7 += p1;
mov         r10d,dword ptr rcx
mov         r14,rcx
mov         r15,qword ptr p7 # going to use p7
mov         rbx,rdx
mov         rdi,r9
mov         esi,dword ptr r15 # Parameters are saved into non-volatile registers...
add         r10d,esi
...
	}
	int ret = p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
...
	p7 = oldP7;
	return ret;
}
...
mov         dword ptr r15,esi # ... and those registers are saved by the callee.
mov         rsi,qword ptr rsp+18h
pop         r15
ret
*/

Recortes do artigo original

> On X64, the first 4 parameters are always passed in registers and the rest of the parameters are passed via the stack. This is one of main causes of grief during debugging since register values tend to change as functions execute and it becomes difficult to determine the original parameter values that were passed to a function, half-way into its execution. Other than this one issue with retrieving parameters, x64 debugging is not that different from x86 debugging.

> Unfortunately, there is no silver bullet to finding parameters. All the techniques here depend heavily on the X64 assembler instructions generated by the compiler. If the parameters are not in "reachable memory", there is simply no way to get them. Having private symbols for modules and functions that appear in the call stack doesn't help too much either. Private symbols do tell the number and types of parameters a function takes, but that's about it. It does not tell what those parameter values are.

>

> Determine if the parameters are loaded from non-volatile registers and if those registers are saved by the callee.

>

> Determine if the parameters are saved from the registers into memory.

>

> Determine if the parameters are saved into non-volatile registers and if those registers are saved by the callee.

>

> Each one of the techniques requires disassembling the caller and the callee functions involved in the parameter passing.

>

> The debugger's ".frame /r" command displays the values of non-volatile registers when a particular function was executing.

> it is important to always verify parameter register overwrites

> It is important to examine the instructions up to the call to the next function (...) to ascertain that these non-volatile registers are not being overwritten.

# Cracking the code interview

2023-04-07 tag_books ^ ctrl_c

Este livro foi recomendado pela minha amiga para treinar para as entrevistas técnicas que ando fazendo. Escolhi ler este em seguida após terminar o Algorithm For Dummies. As primeiras anotações são como compor o CV e qual a estratégia de cada big tech nos seus processos. Escapei esta parte, não estou interessado em trabalhar em um Google da vida. Porém, há alguns detalhes que achei relevante recortar.

Estava em cerca de 8% do livro e desisti. Suas dicas são deveras avançadas para quem está apenas querendo tirar a ferrugem de algoritmos. Iniciei um outro chamado A Common-Sense Guide to Data Structures que parece mais a minha cara.

Recortes

>

> False negatives are acceptable. This is sad (and frustrating for candidates), but true. From the company's perspective, it's actually acceptable that some good candidates are rejected. The company is out to build a great set of employees. They can accept that they miss out on some good people.

> (...)

> They're far more concerned with false positives: people who do well in an interview but are not in fact very good.

>

> Could you learn it as needed? Sure. But it's very difficult to know that you should use a binary search tree if you don't know of its existence. And if you do know of its existence, then you pretty much know the basics.

> Whiteboards also tend to encourage candidates to speak more and explain their thought process. When a candidate is given a computer, their communication drops substantially.

>

> If you are thinking right now that you have too much experience and can't fit it all on one or two pages, trust me, you can. Long resumes are not a reflection of having tons of experience; they're a reflection of not understanding how to prioritize content.

> (...)

> For each role, try to discuss your accomplishments with the following approach: "Accomplished X by implementing Y which led to z". Here's an example:

> - Reduced object rendering time by 75% by implementing distributed caching, leading to a 10% reduction in log-in time.

> Here's another example with an alternate wording:

> - Increased average match accuracy from 1.2 to 1.5 by implementing a new comparison algorithm based on windiff.

>

> Which one is faster? The first one does one for loop and the other one does two for loops. But then, the first solution has two lines of code per for loop rather than one. If you're going to count the number of instructions, then you'd have to go to the assembly level and take into account that multiplication requires more instructions than addition, how the compiler would optimize something, and all sorts of other details. This would be horrendously complicated, so don't even start going down this road. Big O allows us to express how the runtime scales. We just need to accept that it doesn't mean that O(N) is always better than O(N2).

> We already said that we drop constants. Therefore, 0( N2 + N2) would be O ( N2 ). If we don't care about that latter N2 term, why would we care about N? We don't. You should drop the non-dominant terms.

> If your algorithm is in the form "do this, then, when you're all done, do that" then you add the runtimes. If your algorithm is in the form "do this for each time you do that" then you multiply the runtimes.

> This is a good takeaway for you to have. When you see a problem where the number of elements in the problem space gets halved each time, that will likely be a 0( log N) runtime.

> Rather than making assumptions, let's derive the runtime by walking through the code.

# Duas séries pretas e um filme preto... e branco

2023-04-09 tag_movies tag_series ^ ctrl_c

Coisa neste poste: Alfaville (Alphaville), Swarm (Enxame), Todo Mundo Odeia o Chris.

Estou revendo esta série que estreou nos anos 2000, quando minha família adorava assistir na TV aberta pela nostalgia de épocas menos abastadas. A série se chama Todo Mundo Odeia o Chris, é baseada vagamente na infância do comediante Chris Rock vivendo no Brooklin dos anos 80. Muito é inventado e adaptado, mas a essência do que era viver nos subúrbios de Nova York em uma família proletariada negra se mantém.

Minha família se identificava e muito, mas não pela cor da pele, e sim por ser a história de uma família pobre, que tem que vender o almoço pra comprar a janta e se desdobrar para criar três filhos. É sobre pobreza. A pobreza nos une em torno das desgraças, que são o tempero da vida. Usamos das desgraças para dar risada uns dos outros e tornar a vida mais leve, exatamente o oposto de porta-bandeiras de movimentos sociais. Desgraça é o que os pobres têm de sobra. É a moeda social de troca de facto, e no Brasil é a maneira como as pessoas se promovem, através da exploração da compaixão alheia.

Esta é uma série lúdica para todos, inclusive crianças, que não apanham tanto quanto poderiam. Apesar de Chris receber várias ameaças nervosas de sua mãe, nós sabemos como isso funciona na cabeça de uma criança. É um sitcom charmoso, com algumas fachadas externas e cenários internos que nos remetem a uma época mais inocente da TV e da vida real. Sem celulares a TV das crianças era a atração principal, uma caixa de 19 polegadas com uma imagem sofrível em que se exercitava a imaginação. Ou seja, o paraíso. Uma das últimas décadas antes de tudo mudar.

Ainda sobre séries negras saiu no Prime uma produção de Donald Glover, o rapaz de Community. Ele dirige alguns episódios e escreve todos. É sobre assassinatos que aconteceram nos últimos anos que devem estar relacionados com uma garota que tem sérios problemas psicológicos. Ela faz parte de um culto online chamado Enxame, de fãs da Beyoncé, chamada na ficção de Ny'Ja e censurado seu nome no documentário sobre o caso real. Este grupo faz de tudo ao seu alcance para destruir na rede pessoas que criticam sua deusa. Essa garota faz o que sabe fazer de melhor: matar golpeando suas vítimas com toda a força. Ela usa objetos pesados como martelo e frigideira e não para enquanto não vê o sangue escorrendo pelo chão. O motivo: pessoas que falaram mal nas redes sociais sobre a cantora. Existe uma relação com uma irmã que acaba se matando, o que desencadeia toda a ação. Vários dos detalhes dos casos são reais e ao final temos um episódio documental sobre a investigação deste caso ainda em andamento que me faz pensar que a investigadora do caso seria uma ótima adição ao elenco e à história.

A série estabelece um clima tenso e reflexivo. Temas do momento como o feminismo são trazidos à tona mais como alvo do que como bandeira. Até o racismo nota-se um tom de revisionismo da última década. Por exemplo, apesar de matar geral e ser altamente suspeita, a garota passa despercebida principalmente porque não se pode mexer com os negros pós-BLM. Abre-se a questão de quais as armadilhas que a sociedade passará quando alguns privilegiados podem cometer crimes, por serem considerados desprivilegiados, e sequer serem investigados.

Para finalizar este post eis um filme em preto... e branco. Fui assistir ao filme do Godard. Está rolando algumas exibições na Cinemateca, gratuitas, porque o diretor se matou ano passado e com isso encerrou forçosamente sua cinematografia (graças a Deus). Alguns trabalhos "icônicos" estão em exibição e aproveitei para ver no cinema algumas obras que estão ou deveriam estar (deveriam?) no checklist de um crítico de cinema.

Um desses filmes é Alfaville, uma distopia futurista que possui detalhes orwelianos misturados com um ar de filme noir de investigação. Um agente visita a icônica cidade onde os humanos estão vivendo o paraíso coletivista, como formigas obedientes, e seguem uma voz desagradável do chefão, que dá comandos e analisa situações. É como uma inteligência artificial, um ChatGPT futurista, que apenas informa a conclusão sem pensar nos fatos. O governo autoritário, surpresa, é fascista, e eles matam quem chora e se apaixona, além de outras formas de evitar o uso da lógica. Palavras que constituem risco à estabilidade dessa sociedade aos poucos são eliminadas. Mulheres são catalogadas por nível de sedução, e é essa uma de suas principais funções. O cara se apega pela filha de um amigo que se perdeu nesse mundo. Ninguém pode culpá-lo, ela é uma belezinha. Mas para olhar para as pernas dela precisamos ficar ouvindo aquele blá blá blá filosófico de filme francês.

Alfaville possui três ou quatro falas e cenas poderosas espalhadas em um filme do Godard, onde tiroteios e perseguições parecem arquitetadas por uma criança de 10 anos. Tudo é proposital, claro. O diretor domina a linguagem cinematográfica e a subverte pelo bem de atacar a lógica burguesa, seja lá o que isso quer dizer. Não façamos perguntas demais.

Este não é um dos piores filmes do diretor. Também não é dos melhores. Até porque eles não existem, começo a desconfiar. De qualquer forma, é altamente assistível, como a maioria de seus "trabalhos". Mas esse tem um algo a mais. O filme imprime um universo tão coeso e intenso em seu discurso que acaba se tornando uma entidade à parte. Assim como Metrópolis, Alfaville vira um lugar palpável em nossa imaginação coletiva sobre os lugares visitáveis do cinema. Todos nos lembraremos da voz desagradável avisando quando uma sala está ocupada ou livre conforme andamos pelo corredor. Todos lembraremos (ou não) daqueles condenados na piscina, declamando poesia e sendo esfaqueados por garotas de biquíni.

Valeu a pena ter ido no cinema junto dos jovens tirando fotos da tela para sair bem nas redes sociais? Filmes do Godard são sempre uma experiência. Se são boas ou más experiências é irrelevante. Cinema de arte não deve ser julgado. Especialmente quando se está dormindo na sala.

# Como descobrir se uma string é mutuamente rotativa

2023-04-09 tag_coding tag_interview ^ ctrl_c

Uma string mutuamente rotativa é uma string que se rotacionarmos para a direita ou para a esquerda, com os caracteres "indo parar" do outro lado, é comparável com a string original. Exemplos:

• "abacate" é mutuamente rotativa com "cateaba";
• "roma" é mutuamente rotativa com "maro";
• "ab" é mutuamente rotativa com "ba";
• "123456" é mutuamente rotativa com "456123".

Há alguns passos simples e um código esperto que consegue verificar isso. Os passos são os seguinte:

• Inicialize as duas strings em duas variáveis;
• Veja se o tamanho das duas é similar (se não retorne false);
• Junte a primeira string com ela mesma (s = s + s);
• Verifica se a segunda string existe na string duplicada;
• Se existir quer dizer que uma é rotação da outra.

Ficou confuso? Vai ficar mais simples ao ver a implementação em C++:

bool RotationMutually(string s1, string s2)
{
    if (s1.size() != s2.size()) return false;
    s1 += s1;
    return s1.find(s2) != s1.npos;
}

# Como funciona o bubble sort

2023-04-09 tag_coding tag_interview ^ ctrl_c

Uma das piores ordenações possíveis, mas uma das mais simples de entender, é a bubble sort. Ela é passada para estudantes de computação porque é um algoritmo possível de explicar sem entrar em muitos detalhes do seu funcionamento, e também porque seu funcionamento é intuitivo.

O objetivo do algoritmo é ordenar uma lista.

Para conseguir ordenar o algoritmo precisa comparar todos os elementos e trocar as posições dos elementos desordenados, um a um.

Como a lista é varrida de cabo a rabo os elementos na posição mais errada possível vão caminhando em direção à sua posição correta.

Ou seja, se o primeiro elemento estiver na última posição são feitas N-1 trocas, do último para o penúltimo, do penúltimo para o antepenúltimo e assim por diante, até que o loop que varre todos os elementos faça a última comparação, entre o primeiro e o segundo elemento.

Note que é necessário fazer o caminho reverso para mover um elemento que está em primeiro, mas que deveria estar em último.

Para isso o loop que percorre a lista inteira precisa primeiro garantir que todo o resto da lista está ordenado.

Para conseguir isso a cada passada do primeiro loop é feito outro loop com o resto da lista.

Isso é feito da seguinte forma em C++:

vector BubbleSort(vector array)
{
    for (size_t i = 0; i < array.size(); ++i)
    {
        for (size_t j = 0; j < array.size() - 1 - i; ++j)
        {
            if (arrayj > arrayj + 1)
            {
                swap(arrayj, arrayj + 1);
            }
        }
    }
    return array;
}

Se você leu o código deve ter percebido que existe um pequeno truque na hora de estipular o final do loop mais interno: ele diminui do tamanho do array menos o que já foi percorrido do elemento do loop externo. Em outras palavras, quanto mais avançarmos para a frente com o índice do loop externo menos avançamos para o final do array.

Isso é feito porque sabemos que já foram feitas i comparações antes, o que quer dizer que os elementos na posição size-i já foram devidamente movidos para dentro do intervalo que será comparado na passada deste próximo loop interno.

Para sentir o passo a passo dessas iterações, observe como os elementos de uma lista completamente desordenada se comporta e até onde vão as comparações do loop interno e, o mais importante, por que ele não precisa ir mais além.

i = 0
6 5 4 3 2 1
j - - - - j
5 4 3 2 1 6
i = 1
5 4 3 2 1 6
j - - - j
4 3 2 1 5 6
i = 2
4 3 2 1 5 6
j - - j
3 2 1 4 5 6
i = 3
3 2 1 4 5 6
j - j
2 1 3 4 5 6
i = 4
2 1 3 4 5 6
j j
1 2 3 4 5 6

Parece um algoritmo rápido, mas isso acontece porque está escondido cada uma das comparações e trocas do loop interno. Por exemplo, no primeiro bloco acima foram feitas cinco comparações e cinco trocas (N-1).

A complexidade deste algoritmo é de O(n^2) comparações e O(n^2) trocas.

Ou seja, nada bom. Mas fácil de entender =)

# Como funciona o insertion sort

2023-04-09 tag_coding tag_interview ^ ctrl_c

Entre os algoritmos de ordenação mais simples de se entender o insertion sort está na lista. E isso acontece porque ele é intuitivo. É mais ou menos como podemos fazer para ordenar um deck de cartas: pegamos item a item e vamos inserindo em um segundo deck, mas dessa vez observando onde cada carta deve ser inserida para que o deck final esteja ordenado.

Implementar isso em código segue o mesmo princípio, mas em vez de ter um segundo deck podemos dividir o deck, ou array, em dois: ordenado e não ordenado. Varremos o array desordenado e movemos cada elemento para a posição em que ele deve ficar no array ordenado.

Para dividir o array usamos um índice. Peguemos o segundo elemento, por exemplo. O primeiro elemento já está ordenado, pois está sozinho. A partir daí verificamos onde o segundo elemento será colocado: onde está ou antes do primeiro elemento. Decidido isso partimos para o terceiro elemento, onde fazemos a mesma comparação, primeiro com o primeiro ou segundo elemento, depois com o outro. Então fazemos a troca (ou não). E assim por diante. No final, quando estivermos comparando o último elemento, todo o deck ordenado estará completo.

Essa lógica computacional é boa de entender porque realiza uma mímica com a lógica humana, passo a passo. Imagine um ser humano pegando a terceira carta, comparando com a segunda, comparando com a primeira, dessa forma realizando a troca entre a primeira e a terceira, por exemplo.

A parte não intuitiva ou mais complexa é que para inserir um elemento que deveria estar na segunda posição, mas está na quinta, é necessário ir realizando a troca entre o quinto e quarto elementos, depois entre o terceiro e o quarto, até chegar na segunda posição. Isso se tratando de um array. Esse algoritmo pode funcionar mais rápido se utilizada uma lista ligada (menos trocas).

Em código C++ ficaria assim:

vector InsertionSort(vector array)
{
    for (size_t i = 1; i < array.size(); ++i)
    {
        size_t j = i;
        while ( j > 0 )
        {
            if (arrayj-1 > arrayj)
            {
                swap(arrayj-1, arrayj);
            }
            --j;
        }
    }
    return array;
}

# Como inverter uma lista ligada

2023-04-09 tag_coding tag_interview ^ ctrl_c

Inverter uma string ou qualquer array em geral é muito simples se for pensar: itere do começo ao fim e do fim ao começo trocando as posições dos primeiros elementos com os últimos. Caminhe até a metade. Fim.

No entanto, para uma lista ligada a coisa não é tão intuitiva assim. É necessário um certo manejo e um certo entendimento de como uma lista é estruturada durante a troca de ponteiros.

O passo a passo parece simples:

• Declare três nodes: anterior, atual e seguinte;
• Enquanto no node atual o node anterior será nulo;
• Deixe o próximo do atual ser o anterior para inverter a lista;
• Em cada iteração do loop os nodes atual e anterior são incrementados por 1.

Esse desafio tem seus truques. O importante na lógica abaixo é atravessar a lista mantendo o tracking dos elementos seguinte e anterior. Tendo o elemento atual, anterior e próximo a troca de posições se torna simples, mas não tão simples quanto você deve estar imaginando porque:

• o node seguinte se torna o próximo do atual;
• o próximo do atual se torna o anterior (aqui é a invertida);
• o anterior se torna o atual (aqui é o passado);
• o atual se torna o próximo;
• continue até que o antigo final da lista se torne o novo head, apontando para o último anterior.

H -> 1 -> 2 -> 3 -> 4 -> 5 -> 0
1 -> 0
2 -> 1 -> 0
3 -> 2 -> 1 -> 0
4 -> 3 -> 2 -> 1 -> 0
5 -> 4 -> 3 -> 2 -> 1 -> 0
H -> 5 -> 4 -> 3 -> 2 -> 1 -> 0

Os passos numerados estão de acordo com o código C++ abaixo:

shared_ptr LinkedListReverse(shared_ptr head)
{
    shared_ptr present = head->next; // begin
    shared_ptr preceding = nullptr;
    shared_ptr following;
    while (present != nullptr)
    {
        following = present->next; // 1
        present->next = preceding; // 2
        preceding = present;       // 3
        present = following;       // 4
    }
    shared_ptr rhead = make_shared();
    rhead->value = 0;
    rhead->next = preceding;
    return rhead;
}

# Como inverter uma string

2023-04-09 tag_coding tag_interview ^ ctrl_c

O bom de estar praticando para fazer entrevistas técnicas é ter material para novos postes. E este poste é sobre um assunto bem simples para quem já sabe como funcionam strings, mas complexo o suficiente para quem nunca ouviu falar de memória no computador.

Vamos começar pela resposta. O algoritmo que deve ser seguido é:

• Declare a string que você quer inverter;
• Obtenha o tamanho dessa string;
• Faça um loop do começo ao fim ou do fim ao começo;
• No loop atualize a posição inicial e final da string;
• Troque de posição os elementos final e inicial;
• Pronto.

Simples, não? Em C++:

string ReverseString(string s)
// string passada por parâmetro
{
    size_t begin = 0; // posição inicial
    size_t end = s.size() - 1; // posição final
    while (begin < end) // enquanto não invertemos as posições
    {
        char buf = sbegin; // troca elementos de posição
        sbegin = send;
        send = buf;
        ++begin; // atualize a posição inicial e final da string
        --end;
    }
    return s; // string invertida
}

# Como pegar caracteres repetidos em uma string

2023-04-09 tag_coding tag_interview ^ ctrl_c

A resposta rápida para esta questão é: hash tables.

Com hash tables você consegue através de uma chave agrupar qualquer tipo de informação. No caso de caracteres repetidos em uma string a chave é o próprio caractere. Os passos para conseguir isso são os seguintes:

• Declare um map entre char e int (como contador);
• Faça um loop caractere por caractere da string;
• Incremente o contador para cada caractere que passar;
• O contador está pronto, imprima o map.

Em C++ um código que faz isso seria como o abaixo:

void MatchingCharacters(string s)
{
    map m; // declarar um map entre char e int
    for_each(s.begin(), s.end(), &mm { mc += 1; }); // loop caractere a caractere incrementando contador para cada um
    for( auto c: m ) {
      cout << c.first << ": " << c.second << "\n";
    }
}

# Onde fica o meio de uma lista ligada?

2023-04-09 tag_coding tag_interview ^ ctrl_c

É simples descobrir o meio de um array: pegue seu tamanho e divida por dois. Agora, para uma lista ligada, mesmo que você saiba qual o índice do meio, não é por meio de índices que acessamos seus elementos, mas por ponteiros.

Nesse caso é necessário dar uma de esperto:

• Declare dois ponteiros: primeiro e segundo;
• Ambos são inicializados para o início da lista;
• Faça um loop que percorra a lista até o final;
• A cada iteração incremente o primeiro ponteiro em dois nodes;
• A cada iteração incremente o segundo ponteiro em um node;
• Quando o primeiro ponteiro atingir o final o segundo estará no meio.

O princípio de contador de lista ligada é a contagem de iterações do começo até o final da lista, mas para manter o tracking de uma posição relativa como o meio dessa lista é necessário manter um segundo contador.

Através dessa mesma lógica você poderia encontrar posições arbitrárias no meio da lista, como o terceiro elemento onde seu valor começa com a letra 'p', etc.

Abaixo um código em C++ para não ficar tão abstrato:

shared_ptr LinkedListTraverseToTheMiddle(shared_ptr& head)
{
    shared_ptr next = head;
    shared_ptr nextDouble = head;
    bool secondNext = true;
    while (nextDouble->next)
    {
        if (secondNext)
        {
            next = next->next;
        }
        nextDouble = nextDouble->next;
        secondNext = !secondNext;
    }
    return next;
}

# Métodos de extração de café e suas sutilezas

2023-04-09 ^ ctrl_c

Comprei um Melitta e filtros de papel. O objetivo é usar como suporte para meu filtro de pano, mas aproveitei para voltar a praticar passar café como todas as pessoas fazem, mas também para degustar o resultado e entender se há alguma diferença com outros métodos que utilizo diariamente.

Posso estar enganado, mas a sensação geral para mim é que o resultado é cheio de sutilezas, mas nenhuma delas determinante. O mesmo café passado na prensa francesa possui corpo, textura e acidez bem presente. Feito na Aeropress no filtro de papel carece de acidez, mas apresenta um equilíbrio maior junto de uma certa doçura no final. Passado no pano revela notas mais ácidas junto de uma textura próxima da prensa, mas sem amargor.

Já o Melitta foi o primeiro método que trouxe um certo amargor para este café, além de um corpo que eu não sabia que poderia encontrar em filtros de papel. Interessante. Já valeu a pena gastar 10 reais neste conjuntinho. O filtro de papel é cerca do dobro do preço dos da Aeropress, o que faz sentido, pois a quantidade de papel é muito maior. O curioso nessa comparação de preços é que Melitta é um método usado pelas massas com um preço por filtro bem maior que Aeropress, um método mais elitizado e hipster, mas que acaba oferecendo um custo/benefício melhor em seus insumos. E isso porque nem falamos no filtro de metal.

Porém, o bom do mundo do café é que você sempre pode gastar mais. Mesmo em filtros de papel do tipo Melitta. Já ouviu falar na iniciativa Hario V60?

# Segundo maior número

2023-04-09 tag_coding tag_interview ^ ctrl_c

Esta é uma das primeiras questões que peguei para praticar para entrevistas que é ligeiramente mais complicada do que parece, apesar de simples o suficiente para matar em alguns segundos. A questão: como determinar qual o segundo maior número de um array?

Note que não é o maior número, mas o segundo maior. O que parece fácil. O que está implícito e o candidato deve descobrir é que para saber o segundo maior é necessário manter o tracking do primeiro todo o tempo.

Sempre que precisar resolver problemas com segundos ou terceiros elementos você deve manter uma segunda ou terceira variável. A primeira variável mantém o maior elemento e a segunda variável o segundo maior elemento. Sempre que você encontrar algum elemento maior que esses dois você deve atualizá-los de acordo. Depois de varrer toda a lista a segunda variável irá conter o segundo maior número.

Em C++:

int SecondLargest(vector array)
{
    int first = max(array0, array1);
    int second = min(array0, array1);
    for (size_t i = 2; i < array.size(); ++i)
    {
        if (arrayi >= first)
        {
            second = first;
            first = arrayi;
        }
        else if( arrayi > second )
        {
            second = arrayi;
        }
    }
    return second;
}

# Calisthenics for Beginners by Matt Schifferle

2023-04-10 tag_body tag_books tag_self ^ ctrl_c

Esta minha leitura do livro de Matt Schifferle foca em exercícios que utilizam o próprio peso do corpo e uma abordagem avessa às complicações dos treinos de academia.

Schifferle à primeira vista lembra Mistery, o guru das conquistas de The Pick Up Artist. Ambos acreditam em suas filosofias para transformar a vida de seus seguidores. Será que ambos utilizam alquimia dentro dos conceitos que meu amigo me ensinou quando conversávamos sobre as definições instigantes de Timothy Leary (não me lembro se isso está em Prometheus Rising)? Não. Schifferle é um vendedor de mais uma forma de fazer exercício como qualquer outro treinador.

No entanto, suas críticas sobre exercícios serem mais difíceis do que precisam é pertinente. O miolo de seu livro é um conjunto de exercícios simples de seguir. No entanto, não há uma estrutura para que leigos consigam criar seus próprios treinos como prometido pela capa. É um bom início ao treinamento da calestenia, mas para por aí. Sua filosofia é muito senso comum sem nenhum insight poderoso. Seu jeito de falar me desanima por ser simplista demais. Não há um gancho que seja forte para capturar nossa atenção.

Admiro sua intenção, contudo. Se você souber ler nas entrelinhas vai descobrir que pode voar com suas próprias asas, graças à internet e seus infinitos vídeos de exercícios.

>

> Liquid sources. The first tip is to cut back;

>

> Whole foods. The second tip is to focus on whole foods;

>

> Portion control. A lot of weight control also boils down to portion control.

>

Exercícios

Nível 1: comece forte

• Hollow Body Hold
• Box Squat
• Hip Bridge
• Incline Push-Up
• Incline Row
• Incline Handstand
• Tight Hang
• Mountain Climbers
• Marching
• Cross-Punches

Nível 2: vá mais fundo

• Lying Leg Raise
• Split Squat
• Table Bridge
• Floor Push-Up
• Australian Pull-Up
• Hanging Tuck
• Wall-Walking Handstand
• Standing Calf Raises
• Side Plank
• Isometric Squat
• Squat Thrusts
• Step-Ups
• Side Skip Shuffle

Nível 3: power up

• Hanging Leg Raise
• Bulgarian Split Squat
• Reverse Plank
• Archer Push-Up
• Pull-Up
• Front Lever
• Handstand Push-Up
• Starfish Planks
• Towel Hangs
• Burpee
• Ski Hops
• Cross-Punch With Front Kicks

Flexibilidade e Restauração

• Cool Down Stretches
• Standing Quad Stretch
• Hands Clasp Behind Stretch
• Seated Toe Pulls
• Seated Twist
• Sit-Backs
• Standing Arm Pull
• Standing Overhead Side Reach
• Lying Front Stretch

Poses para Restaurar

• Child's Pose
• Lying Front Pose With Full Belly Breathing
• Lying Chair Pose

Recortes

> Calisthenics has a transformative power that many athletes fail to recognize: the power to harness the very laws of nature to substantially improve your health.

> I’m truly excited to present you with not only a body-changing but also a potentially life-changing training regimen.

> (...) calisthenics went from being too easy to far too difficult. Neither perception will help you accomplish your goals. That’s why it’s essential to wipe the slate clean. You can define what calisthenics is for you and your life.

> The highly adaptable nature of calisthenics is due to the fact that your own body is your gym. You no longer have to conform your body to an artificial piece of equipment. Instead, you use your body—and its current abilities—to stimulate your improvement.

> Mother Nature is the ultimate nutritionist.

> Granted, it takes practice to accurately read your body’s natural signals. For example, it’s easy to believe you’re hungry when, in fact, you’re bored or stressed. It’s also easy to ignore your satiety cues if you’re eating while distracted like while watching a movie. Nevertheless, you have plenty of opportunities to practice every day, and, over a short period of time, you can develop a keen sense of what your body really needs.

> Customize the stoplight strategy to your needs and preferences. Keep in mind that one person’s red light food may be another’s yellow or even green light food.

> Liquid sources. The first tip is to cut back on or, if possible, eliminate calories from liquid sources. It’s exceptionally easy to add extra calories, especially in the form of refined sugar, with beverages. Some beverages contain more sugar than multiple candy bars! Thankfully, as liquid calories make it easy to bloat your diet, they also make it easy to slim your diet by cutting them back as much as possible. Whole foods. The second tip is to focus on whole foods, including plant and protein sources. Whole foods are the opposite of refined foods; they fill you up, give you energy, and make it much harder to consume more calories than your body can handle. That’s a heck of a 1-2-3 punch for helping you shed fat fast. Portion control. A lot of weight control also boils down to portion control. On a fundamental level, your body uses your fat when you don’t consume enough to support your current bodyweight. This is why you want to make sure you’re not eating too much, even if your diet is squeaky clean.

> It’s important that you eat even when trying to lose weight. Eating too little for days on end can make you feel tired and sluggish, not to mention leave you open to hunger cravings. Such conditions not only reduce your ability to burn calories through activity but also make you vulnerable to periods of overeating.

> Our busy lives make it all too tempting to finish a workout, and then rush to complete the next item on our to-do list. I don’t recommend ending your workout in such a sudden manner. When you finish your workout without winding down, your nervous system remains in sympathetic dominance, which promotes your body’s fight-or-flight instincts—a stressful state in which to spend the rest of your day.

> Sleep is the biggest component of rest. It’s so important that I often tell people that improving their sleep habits can be more beneficial to their fitness goals than improving their diet and exercise program combined. Getting proper sleep should always be as high a priority as sticking to your diet and exercise habits. If you’re struggling to make progress and running on little rest, I promise getting enough sleep will help.

> As you continue your training, please keep a few things in mind. First, exercise and physical training are meant to make you feel good and improve your quality of life. If you ever find that your quality of health and life are eroding, please stop and reconsider your approach. Fitness habits that compromise your well-being are neither healthy nor productive. Second, listen to your body and trust your instincts. Diet and exercise are far from an exact science; even the leading experts don’t have all of the answers. If you feel that making a change in your approach may be a good idea, then it is worth acting on that instinct. Lastly, know that you’ll learn far more from personal experience than from any book. Resources like this and the others listed in the back of the book (see here ), are great places to get ideas, but the real source of knowledge and understanding is to take massive action. Make your plan and take your first step. Where you go from there is up to you, and I’m sure it’s going to be a fun and rewarding lifelong journey.

> Internal pain is a much more serious issue, often showing up in the joints, ligaments, and tendons. You can usually identify tendon pain in the form of a sharp and burning sensation around a joint, especially when the joint is under a load. Tendon pain often occurs in joints that have little muscular support like the knees, elbows, and wrists. Pain in these areas should always be addressed and never “worked through” or ignored. Doing so only leads to a greater degree of internal damage, often requiring more serious measures to address it in the future.

> The most important thing to remember is that your healthy habits should improve how you feel. They should make you feel happier, more motivated, more energized, and should reduce pain. If you start to experience chronic fatigue, pain, or a general loss of motivation, there’s a good chance something is having a detrimental influence on your mind and body and should be addressed as soon as possible.

> Recovery also includes mental and emotional rest. Meditation, relaxing, and just plain having fun are not luxuries. They are essential elements in your health and should be pursued on a daily basis. Make time to blow off steam and do something that feels good. Sing and dance to your favorite song as you drive home from work. Take a walk along the local nature trail or in the park during your lunch break. Talk to a friend about something other than work.

> In fitness, stress is like medicine. In the right doses, stress stimulates health and progress. However, if you get the dose wrong, stress can poison both body and mind and break your results rather than make them.

> The first important aspect of health and recovery is rest. Your body doesn’t change during your workouts; it changes—grows stronger, more flexible, and more fit—in recovery. Therefore, if you hardly rest, you’ll severely compromise your results.

> Taking time to cool down is like landing an airplane after a long flight. Failing to practice recovery methods is akin to taking your plane up in the sky, and then just letting it drop whenever it runs out of gas. While it is possible to skip your cool down exercises, practicing them ensures that you remain in control, so you’re less likely to crash later on.

Referências

• www.reddeltaproject.com is my personal website, where you’ll also find my podcast and YouTube videos on calisthenics training and practical fitness solutions.
• www.schoolofcalisthenics.com is an expansive Internet resource for learning both basic and advanced calisthenics skills to take your training to the next level.
• www.dragondoor.com is the home of the kettlebell and progressive calisthenics revolution; you’ll find loads of books, articles, and other resources to make your training fun and supremely effective.
• www.monkii.co makes some of the highest quality portable calisthenics training equipment in the world. It’s innovative, versatile, and built to last a lifetime.
• www.calimove.com hosts some of the most practical calisthenics training programs and videos on the internet.
• www.jgcalisthenics.co.uk/home is the online resource of Jake Gay, who’s been documenting the beginning of his calisthenics career and his impressive results.
• www.spri.com is one of the most popular sources for training equipment for both home and commercial gym use.
• www.ringtraining.com is the ultimate resource for innovative gymnastics ring equipment that will add challenge and variety to your calisthenics training.
• www.precisionnutrition.com/blog is one of the leading sources for effective, down-to-earth information on nutrition without the dogmatic hype and fads.
• www.strongerbyscience.com is a great resource if you want to dive deeper into the latest research on strength training and nutrition.

# Como inverter um número

2023-04-11 tag_coding tag_interview ^ ctrl_c

Existe uma solução para a inversão de um número que não é bonita, mas prática: transforme em string e inverta essa string.

int ReverseNumberStringVersion(int number)
{
    string s = to_string(number);
    size_t beg = 0, end = s.size() - 1;
    while (beg < end)
    {
        char buf = sbeg;
        sbeg = send;
        send = buf;
        ++beg;
        --end;
    }
    return stoi(s);
}

Contudo, a maneira bonita de se fazer isso é mantendo o domínio do problema na matemática. E dessa forma:

• Pegue o dígito mais à direita do número;
• Some o dígito com o novo número invertido;
• Multiplique o resultado por 10;
• Divida o número por 10.

int ReverseNumberNumberVersion(int number)
{
    int reversedNumber = 0;
    while (number) {
        reversedNumber *= 10;
        int next = number % 10;
        reversedNumber += next;
        number /= 10;
    }
    return reversedNumber;
}

# Como verificar se um número é primo

2023-04-11 tag_coding tag_interview ^ ctrl_c

Apesar de existir matemáticos ao redor do mundo tentando responder esta pergunta da maneira computacionalmente mais rápida possível, existe uma forma ingênua e eficiente para números baixos:

• Faça um loop entre 2 e a metade do número;
• Se algum desses números dividir sem resto retorne false;
• Se acabar o loop retorne true: o número é primo.

Note que a mesma lógica pode ser aplicada para obter os fatores de um número, seus divisores, etc.

O código em C++:

bool PrimeNumber(int number)
{
    if (number == 2) return true;
    for (int i = 2; i <= (number / 2); ++i)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

# Código para Fibonacci

2023-04-11 tag_coding tag_interview ^ ctrl_c

Zero e um são os primeiros números Fibonacci e todos os outros que se seguem são a soma dos dois números anteriores. Ou seja, para implementar isto em código basta:

• Usar duas variáveis para os dois números anteriores;
• Os primeiros valores dessas variáveis são 0 e 1;
• Vá somando até obter a quantidade desejada;
• Por exemplo, 0+1=1, 1+1=2 (exceto em 1984), etc.

Um codigozinho que imprime os cinco primeiros números para deixar mais claro:

void Fibonacci()
{
    int num1 = 0, num2 = 1;
    int total = 5;
    cout << "fibonacci of first " << total << " elements\n";
    for (int i = 0; i < total; ++i)
    {
        int result = num1 + num2;
        cout << result << ' ';
        num1 = num2, num2 = result;
    }
    cout << endl;
}

# Misoya Ramen

2023-04-11 tag_food ^ ctrl_c

Fomos neste Ramen da Paulista. É um lugar tranquilo na Antônio Carlos, a apenas duas quadras da Paulista. É bom ter uma opção de lámen em outro bairro que não seja a Liberdade ou a Saúde.

Pedimos a versão mais forte do caldo nas versões simples e com três pedaços de carne de porco, que foram o ponto alto do meu prato. Entre os acompanhamentos junto ao caldo vem uma batata frita grossa sem necessidade e sem nenhum sabor a mais, além de carne moída e uma massa própria para missô, mas que não parecia fresca, o que surpreendeu por estarmos em uma casa de lámen.

O sabor é mais intenso que outros caldos missô da cidade. Talvez o gergelim tostado boiando no caldo pode ter dado um quê a mais no sabor além da fermentação.

A quantidade dos pratos é média, o que é bastante para quem come pouco como eu, na medida para quem come um pouco mais e pouco para quem come muito, que terá a sorte de pedir algum complemento como guioza ou frango Karaage.

Este é um bom lámen, mas infelizmente o preço não me apetece. Eu não sairia de casa para jantar em um lugar desses, pois há casas de lámen mais em conta e com um sabor mais interessante. Mas valeu a pena conhecer. Talvez um dia quando estiver na região de bobeira explore uma versão picante ou os complementos.

# Café com Canela

2023-04-12 tag_movies ^ ctrl_c

Essa moça tem uma raba interessante e passa um café gostosinho. Eu sei que os idealizadores deste filme não esperam um comentário como esse de um projeto mergulhado em representatividade e diálogos fracos. Se você compartilha da visão da equipe por trás, então não leia este texto. Obrigado.

Este filme foi apresentado pela Petrobrás e ganhou o prêmio Petrobrás, o que já diz quase tudo sobre ele. Mas dê uma olhada nos títulos dos textos acadêmicos sobre o filme:

• A (auto) representação da mulher negra no cinema brasileiro contemporâneo;
• O corpo múltiplo negro feminino à luz de um cinema da negrura em Café com Canela;
• Café, canela e transgressão: descolonizando narrativas feministas;
• Políticas Públicas e a Inclusão da Mulher Negra no Cinema;
• Feminilidades e Negritudes nas Telas: Diálogos entre a Psicologia e o Cinema;
• O que o cinema quer da gente é coragem: negridade e dissidência sexual & de gênero nas produções da Rosza Filmes;
• Direções do olhar: um estudo sobre as poéticas e técnicas de diretoras negras do cinema brasileiro;
• Por um cinema negro no feminino: dororidade e pretagonismo das mulheres no filme Café com Canela;
• Café com canela e a edificação do afeto no Cinema Negro Feminino;
• "Café com Canela" contribui para maior representatividade no cinema.

Os textos acima poderão lhe proporcionar diversas formas de xerocar a opinião diversa que existe na imprensa; tão diversa que um é a cópia de outro que é a cópia de outro que é a cópia...

Porém, se você está curioso para entender como perdeu duas horas de sua vida, talvez este texto esclareça um pouco. Compartilho do seu tédio, caro leitor.

Era uma vez um diretor que se achava muito criativo. Então ele pegou sua câmera e aproximou ao máximo da cara das pessoas. "Eu amo planos detalhe", ele diria se fosse entrevistado. A tela balança e você já não sabe se está assistindo um filme ou dentro de um bote salva vidas.

O elenco de amadores poderia ser divertido, mas está seguindo um roteiro triste, de quem não tem confiança em seu conteúdo e apela para trucagens no tempo para criar a atmosfera, ou pelo menos tentar, de um drama pela perda de um ente querido.

A mudança de razão de tela e fotografia do começo conta a história sobre a divisão do presente e passado. O passado está nas memórias dessa mulher que perdeu tudo quando perdeu o filho.

Do outro lado da ponte nós temos a rabuda, que é mulher, negra, independente, pobre e tem uma bike e uma receita de coxinha da família. Ela gosta de cuidar. Cuida de sua mãezinha, acamada.

Os pontos que Café com Canela tenta unir estão tão espaçados na narrativa que quando eles se juntam não é natural, mas fabricado. Como os personagens engraçadinhos que compõem a trupe de amigos da rabuda.

Lá pelo final você entende. A velha aprende a andar de bicicleta. E ela agora pode cruzar uma ponte e superar o passado traumático. Às vezes a única coisa que falta é uma canela no café para aquela energia extra.

# Hacker Rank Warm Up [link]

2023-04-16 tag_coding tag_interview ^ ctrl_c

Here I am doing interview exercise tests at Hacker Rank. I am trying to recap what I've been doing the last two months before going on. Let's see what I learned, starting with the Warm Up exercises.

Counting Valleys

To solve the counting valleys problem keep a valley counter that only increments when the hiker is coming up to the sea level. Monitor the altitude and the new altitude and compare. If the altitude was negative (into a valley) and the new altitude is zero (sea level) then that's a new valley to count. This strategy avoid to count valleys inside valleys before the hiker gets up to sea level.

This solution has a complexity of O(n).

int countingValleys(int steps, string path) {
    int valleys = 0;
    int altitude = 0;
    for (int s = 0; s < steps; ++s)
    {
        int step = paths == 'D' ? -1 : 1;
        int newAltitude = altitude + step;
        if (altitude < 0 && newAltitude == 0)
        {
            valleys++;
        }
        altitude = newAltitude;
    }
    return valleys;
}

Cloud Jump

To solve the cloud jump problem create a loop and advance current position until finished. Try the double jump at first and ordinary jump else by incrementing position by 1 or 2 and incrementing jump counter. If in the end position just increment and get out of the loop. Return the jump counter.

This solution has a complexity of O(n).

int jumpingOnClouds(vector c) {
    int jumps = 0;
    size_t i = 0;
    while (i < c.size()) {
        if (i < c.size() - 2 && ci + 2 == 0) {
            i += 2;
            ++jumps;
        }
        else if (i < c.size() - 1) {
            i += 1;
            ++jumps;
        }
        else {
            i += 1;
        }
    }
    return jumps;
}

Repeated Strings

To solve the repeated string problem we count the 'a' occurrences for the full unique string and divide n by the size of the unique string size, getting the number of times we need to multiply the full occurrences.

For the partial string after the number of full unique strings we format this string and count independently this last part.

The total of occurrences is calculated multiplying the times there will be full unique strings and sum up the partial string 'a' occurrences.

This algorithm has a complexity of O(n) because we got to count every char.

long repeatedString(string s, long n) {
    long fullOccur = (long) count(s.begin(), s.end(), 'a');
    long fullMult = n / s.size();
    string partialStr = s.substr(0, n % s.size());
    long partialOccur = (long) count(partialStr.begin(), partialStr.end(), 'a');
    return fullOccur * fullMult + partialOccur;
}

Sales by Match

To solve the sales by match problem we traverse all the array of socks and keep inserting and deleting a set of colors. If the current color is not found in the set we insert it. If the current color is found we increase a pair counter and remove the color from the set. The next time the same color appears it will be inserted again waiting for its pair.

The complexity of this solution is O(N), since we have to traverse all array of socks.

int sockMerchant(int n, vector ar)
{
    int ret = 0;
    set colors;
    for (int color : ar)
    {
        if (colors.find(color) != colors.end())
        {
            ret++;
            colors.erase(color);
        }
        else
        {
            colors.insert(color);
        }
    }
    return ret;
}

# Hunger (Fome de Sucesso)

2023-04-17 tag_movies ^ ctrl_c

Esse filme tem várias boas ideias que quando juntas viram uma mistureba que se torna intragável. Pelo menos filmes, até onde eu sei, não dão indigestão. A história lida com a questão do status dos cozinheiros entre seus clientes ricos e famosos. Em uma época de Master Chef e programas de culinária dominando a timeline é curioso entender esse fascínio, inclusive das massas, por gente que cozinha difícil e dizem por aí que é delicioso.

O filme também aproveita o estereótipo de chefes de cozinha jogarem coisas em sua equipe quando fica nervoso e ser ultra exigente porque teve uma infância difícil e quer se vingar dos 1%.

Do outro lado do ringue temos uma moça que cuida do restaurante da família. Ela sai de fazer frituras para chefe profissional, entre vários outros detalhes que você vai perceber que não faz o menor sentido no mundo da alta gastronomia.

Tudo é um show de luzes que quer iluminar temas sociais referentes a comida, mas sua trama é simplista e episódica a ponto de já sabermos de antemão todo o desenrolar da história. Por exemplo, uma vez que a cozinheira sai das asas do seu tutor fica óbvio demais, além de artificial, que vai surgir um confronto direto entre eles. Há uma tentativa séria de ilustrar o filme com cenas impactantes, mas sem pano de fundo que a sustente elas são formas que o próprio chefe do filme tenta iludir seus clientes: com luzes e fumaça.

# Árvore de segmentos [link]

2023-04-17 tag_coding tag_interview ^ ctrl_c

Não existe sequer uma entrada em português sobre Segment Tree, uma árvore binária específica para guardar intervalos. E este acredito ser um assunto importante para testes de entrevista ou competições de programação porque ele é muito útil para alguns problemas. Vamos dar uma olhada em como ela funciona.

Em primeiro lugar, ela é uma árvore binária. No entanto, seus ramos representam intervalos. A raiz possui o intervalo inteiro (mínimo e máximo) e os ramos vão se dividindo em intervalos menores, até que as folhas indiquem apenas um elemento.

É importante notar que uma árvore de segmento é maior que simplesmente um array, mas diferente de um array, a árvore brilha quando precisamos somar intervalos. Como ela está estruturada de maneira que cada ramo contém a soma de seus galhos, para obter a maioria dos intervalos sua complexidade desce de O(N) para O(log N).

Dessa forma, podemos concluir que o espaço ocupado por uma árvore binária para implementar um segment tree completo deve ocupar por volta de `2*N-1`, o espaço para implementar uma árvore binária completa com N folhas.

No entanto, o tamanho para estocar uma segment tree não é esse, mas tipicamente `4*N`. O motivo disso é que nós precisamos de `2*next_power_of_two(N)-1` para garantir que as divisões da árvore todas vão estar representadas, mas como custa processamento descobrir qual a próxima potência de 2 que é maior que N uma aproximação válida é usar `4*N`.

Vamos observar a implementação de uma árvore de segmentos. A primeira coisa é alocar o espaço necessário em um vetor. Digamos que nossa árvore irá conter os intervalos de 1 a 1000 (inclusive).

vector tree4*1000;

Nossa árvore está pronta. =)

Vamos atualizar algum valor nela. Por exemplo, definir o valor 42 para o node 666:

void update(int node, int left, int right, int pos, int value, vector& tree) {
    if (left == right) {
        treenode = value;
    } else {
        int nodeLeft = 2 * node;
        int nodeRight = 2 * node + 1;
        int middle = (left + right) / 2;
        if (pos <= middle)
            update(nodeLeft, left, middle, pos, value, tree);
        else
            update(nodeRight, middle+1, right, pos, value, tree);
        treenode = treenodeLeft + treenodeRight;
    }
}
int main() {
    vector tree(4 * 1000);
    update(1, 1, 999, 666, 42, tree);
}

Algumas informações relevantes sobre esses parâmetros:

• node é a localização do ramo atual;
• left é o início do intervalo que estamos;
• right é o final do intervalo que estamos;
• pos é o número do ramo que pretendemos trocar;
• value é o valor que pretendemos colocar no ramo;
• tree é a árvore de segmentos.

Todos esses parâmetros existem porque a função update é recursiva e ela precisa passar a localização dentro do array no formato de um mapa para uma árvore binária. A busca também segue o mesmo princípio, de O(log N), ou seja, para encontrar a posição desejada (variável pos) a função irá seguir limitando o intervalo entre left e right até que ambos tenham o mesmo valor, situação em que estaremos em uma folha.

Depois da atualização vem a parte interessante: os ramos acima da folha são atualizados com a soma entre seus ramos esquerdo e direito, recursivamente. Isso quer dizer que o valor 42 irá ecoar por todos os ramos de cima até chegar na raiz, que também irá conter 42, já que este é o primeiro valor diferente de zero de toda a árvore.

Vamos definir mais alguns valores em outras posições para em seguida implementar a soma:

int main() {
    vector tree(4 * 1000);
    update(1, 1, 999, 666, 42, tree);
    update(1, 1, 999, 600, 58, tree);
    update(1, 1, 999, 700, 45, tree);
    update(1, 1, 999, 999, 55, tree);
}

Com isso a soma dos seguintes intervalos deve contar os seguintes totais:

• o intervalo 666,666 deve conter o valor 42, da única folha selecionada;
• o intervalo 600,700 deve conter o valor 145, da soma de 666, 600 e 700;
• o intervalo 600,999 deve conter o valor 200, da soma adiciona de 999;
• a raiz, ou o intervalo 1,999 deve conter o mesmo valor;
• intervalos abaixo de 1,599 devem conter 0.

Vamos implementar a função de soma e descobrir.

int sum(int node, int left, int right, int posLeft, int posRight, const vector& tree) {
    if (posLeft > posRight)
        return 0;
    if (posLeft == left && posRight == right)
        return treenode;
    int nodeLeft = 2 * node;
    int nodeRight = 2 * node + 1;
    int middle = (left + right) / 2;
    return sum(nodeLeft, left, middle, posLeft, min(posRight, middle), tree)
        + sum(nodeRight, middle + 1, right, max(posLeft, middle + 1), posRight, tree);
}
int main() {
    vector tree(4 * 1000);
    update(1, 1, 999, 666, 42, tree);
    update(1, 1, 999, 600, 58, tree);
    update(1, 1, 999, 700, 45, tree);
    update(1, 1, 999, 999, 55, tree);
    vector> intervals = { 
        {666, 666}, {600, 700}, {600, 999}, 
        {1, 999}, {1, 599} };
    for (const vector& i : intervals) {
        int isum = sum(1, 1, 999, i0, i1, tree);
        cout << "the interval " << i[0 << "," << i1 
            << "] has the value " << isum << endl;
    }
}

Mais uma vez, existem muitos parâmetros porque a função é recursiva e precisa se localizar, e o princípio é o mesmo da função update, de usar as variáveis como um mapas para navegar por uma array.

• node é a localização do ramo atual;
• left é o início do intervalo que estamos;
• right é o final do intervalo que estamos;
• posLeft é o início do intervalo que queremos a soma;
• posRight é o final do intervalo que queremos a soma;
• tree é a árvore de segmentos.

Note que a única variável que de fato indexa o array é a variável node. Porém, qual vai ser o índice de node é determinado pelos cálculos que giram em torno de ir para a direita ou para a esquerda pela árvore. Se for pela esquerda o próximo índice é o índice em node vezes 2, pois existem node ramos no nível em que estamos, e se for pela direita o próximo índice é node vezes 2 mais um, que é o próximo após o ramo da esquerda.

Se ficou difícil de entender, lembre-se que a busca em uma árvore binária segue a mesma lógica daquele jogo de adivinhação, em que você chuta um número de X a Y e a pessoa que sabe qual o número irá dizer se o número é maior ou menor do que você chutou. Como você é muito esperto irá sempre dividir a faixa de onde está para acertar o número o mais rápido possível.

Por exemplo, vamos supor que você deve chutar qual número é de 1 a 100. O número é 64.

• seu chute inicial é 50;
• a resposta: mais alto;
• seu próximo chute é 75 (entre 50 e 100);
• a resposta: mais baixo;
• seu próximo chute é 63;
• a resposta: mais alto;
• seu próximo chute é 67;
• mais baixo;
• 65;
• mais baixo;
• 64;
• acertou!

Entre 100 possíveis chutes foram feitos 6, ou cerca de log 100 chutes. Exatamente como é feita a busca na árvore binária, seja de segmentos ou não. Essa é a grande vantagem de usar o mapa para se localizar no array como uma árvore binária, pois a busca não será linear.

O fato da árvore ser de segmentos é apenas um detalhe que incorre em mantermos atualizados os nodes com a soma de todos os ramos abaixo, algo custoso a princípio, mas que na hora de obter a soma de intervalos faz valer a pena.

# Hash Table Giratória

2023-04-19 tag_coding tag_interview ^ ctrl_c

Ainda estudando e praticando testes de entrevista me veio essa em que seja possível realizar somas para todas as chaves de uma hash table. Curioso, nunca tinha pensado nesta feature. Imagine que temos uma tabela de hash entre inteiros em que `{ 1: 8, 2: 9 }`. A chave corresponde ao hash.

| -5: | -4: | -3: | -2: | -1: | 0: | 1:8 | 2:9 | 3: | 4: | 5: |...

Então eu aplico um comando na tabela inteira adicionando o valor 2 às chaves, fazendo seus elementos irem parar duas posições à frente de onde estavam. A posição 1 vira 3 e a posição 2 vira 5, mantendo os mesmos valores.

| -5: | -4: | -3: | -2: | -1: | 0: | 1: | 2: | 3: | 4:8 | 5:9 |...

Em primeiro momento eu pensei em mover posições em um vetor para resolver esta questão, mas em seguida descobri que a mesma lógica pode ser aplicada a números negativos, o que deixou tudo muito confuso na minha cabeça.

Depois de pensar em uma caminhada cheguei à conclusão que não é necessário ficar movendo memória uma vez que as posições relativas se mantém. Com base nisso eu desenvolvi a lógica de apenas manter um referencial do início "real" da tabela, ou seja, qual valor deve ser adicionado para se chegar à posição real após os deslocamentos. Dessa forma a posição na memória dos elementos permanece a mesma, mas do ponto de vista de indexação eles estariam, no exemplo acima, duas posições à frente. Para isso eu colocaria meu indexador duas posições atrás.

| -5: | -4: | -3: | -2: | -1: | 0: | 1:8 | 2:9 | 3: | 4: | 5: |...
                              |
                              beg    1     2     3    4    5   ...
add_to_key 2
| -5: | -4: | -3: | -2: | -1: | 0: | 1:8 | 2:9 | 3: | 4: | 5: |...
                  |
                  beg      1    2    3     4     5   ...

Agora sempre que alguém referenciar a posição 0 ela estará em -2 e assim por diante. Como a posição dentro de um array não precisa ser alterada não me preocupei em atualizar as chaves, apenas os campos internos de uma hash table: sua chave e valor.

A implementação não ficou exatamente assim, pois arrays não possuem índices negativos em C++. Para implementar eu já iniciei meu contador de início na metade do array, permitindo índices positivos e negativos na faixa de 100 elementos para cada lado.

struct HashTable {
    typedef vector> BufferType;
    HashTable(int tableSize) {
        this->tableSize = tableSize;
        bufferRaw = new BufferTypetableSize;
        buffer = shared_ptr(bufferRaw, default_delete());
        currentPosition = tableSize / 2; // for positive and negative room
    }
    BufferType& operator [] (int position) {
        int actualPosition = (currentPosition + position) % tableSize;
        return buffer.get()actualPosition;
    }
    int tableSize;
    shared_ptr buffer;
    vector>* bufferRaw;
    int currentPosition;
};
int HashFunction(int key, int tableSize) {
    return key % tableSize;
}
vector* FindItem(HashTable& hashTable, int key) {
    for (vector& items : hashTableHashFunction(key, hashTable.tableSize)) {
        if (items0 == key) {
            return &items;
        }
    }
    return nullptr;
}

Uma parte importante no código acima é entender que a hash function apenas pega o resto da divisão do tamanho da tabela. Porém, o método de subscrito da tabela considera onde ela começa, o `currentPosition`, que pode ser em qualquer lugar, dependendo das movimentações do usuário.

int actualPosition = (currentPosition + position) % tableSize;

O código que realiza as operações de fato apenas busca ou modifica valores:

vector TestCase(vector operations, vector> operands) {
    HashTable hashTable(DEFAULT_HASH_TABLE_SIZE);
    vector results;
    for( int i = 0; i < operations.size(); ++i ) {
        if (operationsi == "get") {
            if (auto* item = FindItem(hashTable, operandsi0))
                results.push_back((*item)1);
        }
        else if (operationsi == "insert") {
            if (auto* item = FindItem(hashTable, operandsi0))
                (*item)1 = operandsi1;
            else
                hashTableHashFunction(operands[i0, hashTable.tableSize)].push_back(operandsi);
        }
        else if (operationsi == "add_to_values") {
            for (int j = 0; j < hashTable.tableSize; ++j)
                for (auto& item : hashTablej)
                    item1 += operandsi0;
        }
        else if (operationsi == "add_to_keys") {
            for (int j = 0; j < hashTable.tableSize; ++j)
                for (auto& item : hashTablej)
                    item0 += operandsi0;
            hashTable.currentPosition -= operandsi0;
        }
    }
    return results;
}

Um teste simples de rotacionamento de índices na hash table:

void TestCase005() {
    vector operations;
    vector> operands;
    operations.push_back("insert");
    operands.push_back({ 1, 2 });
    operations.push_back("insert");
    operands.push_back({ 2, 3 });
    operations.push_back("add_to_values");
    operands.push_back({ 2 });
    operations.push_back("add_to_keys");
    operands.push_back({ -150 });
    operations.push_back("get");
    operands.push_back({ -148 });
    vector results = TestCase(operations, operands);
    assert(results.size() == 1);
    assert(results0 == 5);
}

E dessa forma é possível gastar apenas O(N) para atualizar chaves ou valores dentro de uma hash table, sem movimentação de memória alguma.

# Sexo, Mentiras e Videotape

2023-04-19 tag_movies ^ ctrl_c

Já assisti esse filme três vezes, mas em décadas diferentes. É curioso como ele se revela um filme novo em cada época da vida.

Na primeira vez, pós adolescente, a impressão geral era a de choque, a do escândalo. Já acostumado a novelas globais, este filme me pareceu uma continuação dos dramas envolvendo traição com a dose extra de estar acontecendo em família. Bom, talvez este seja um tema popular em novelas também. E eu já estava na vibe de filmes como Segredos e Mentiras, que também é muito bom. Havia uma época no cinema em que esses filmes bombavam.

Na segunda vez, semi-adulto, naquela faixa dos 30 quando você acha que sabe das coisas do mundo e ainda faz questão de levantar bandeira, o filme foi uma frustração pela falta de sexo. Ele estava implícito e portanto inexistente. Qualquer um que já tenha visto Juliete Binoche transando com seu sogro em Perdas e Danos deve entender que existem diversos níveis de exposição ao sexo nos filmes, e no caso deste que tem sexo no nome, ficamos apenas com as mentiras e os videotapes, um nome estranho hoje, e talvez até ontem, quando as distribuidoras brasileiras eram muito ruins em dar nome aos filmes. Bom, elas continuam sendo.

Talvez o fato das palavras sexo e videotape estarem no mesmo título seja natural aguardar por algumas filmagens picantes. A pornografia audiovisual, arte cinematográfica deixada de lado pelo público por diversos motivos, mantém em nossas memórias a prioridade de detectar se existe no recinto esses dois elementos que juntos são poderosíssimos. Agora entendo minha frustração.

No entanto, o filme de Steven Soderbergh (Traffic, Erin Brockovich) não brilha nem pelo choque nem pelo sexo, mas pela nossa fascinação em descobrir como as relações de flerte, aquelas que estão abaixo de mera conversação, funcionam no filme. Diferentes níveis de atração erótica entre esses quatro personagens bastam para nos entreter por um bom tempo.

A descrição pequeno burguesa de Ann quando questionada o que há de bom no casamento é o começo de uma aventura dentro da psique dessas pessoas. Ela conclui que o que ela gosta no casamento é sua bela casa e seu marido ser sócio da firma de advocacia em que trabalha. Você quase se enxerga em um filme francês da década de 60.

Depois a história se transforma em um estudo de interações que envolvem Cynthia, a irmã de Ann, e Graham, um antigo amigo da época do colégio do marido de Ann. O mais impressionante é o equilíbrio químico dessas interações. Nada está faltando no filme para que a história se mova de forma natural, trágica e hipnotizante.

Quando menos esperamos o filme encontra seu ápice em justamente um videotape. E ele não é sobre sexo como já havia falado. Ele é sobre como nossa relação com o sexo pode se tornar um problema patológico. E tudo que fica na esfera do não-dito no filme pode ser explicado por quem os personagens são e como eles deveriam ser. Por exemplo, antes Graham e John eram grandes amigos no colégio e John nunca mudou. Hoje ele trai sua esposa com sua própria irmã. É de se esperar que Graham fosse esse tipo de pessoa no passado, o que esconde mágoas com uma minazinha que Graham luta para não repetir.

Não, Sexo, Mentiras e Videotape não é sobre apenas sexo e não contém cenas explícitas. Não é apenas sobre mentiras, apesar de haver muitas, mas elas não definem quem aquelas pessoas são. É apenas ao assistir um videotape no terceiro ato, no ápice do filme, quando a verdade fala mais alto, que a áurea por trás dessa história toda pode respirar em paz.

O filme acaba super rápido comparado com os draminhas de hoje. E que filme, senhores. Essa terceira vez com certeza foi a melhor de todas.

# Clos de los siete, by Michel Rolland

2023-04-24 tag_wine ^ ctrl_c

Quem é Michel Rolland, você talvez se pergunte. Eu faço a mesma pergunta, já que essa história de marketing pessoal pode ser tão enganoso quanto marketing de vinho. Bom, eu pesquisei e vi que ele é apreciado no mundo inteiro e é denominado um dos flying winemakers, que são enólogos que não estão presos em uma vinícola ou, melhor ainda, na colheita de apenas uma região no mundo. Eles vão além da própria bodega e região e criam diferentes obras espalhadas pelas oportunidades que o mundo inteiro do vinho oferece.

No caso dos "de los siete" é um blend de sete terrenos distintos da região de Mendoza, na Argentina. Pelo menos foi o que eu ouvi falar.

Disponível no menu de vinhos do restaurante Outback, descobri esses dias. Altamente elogiado nas rodinhas da internet. E eu só queria abrir um vinho baratinho de minha adega, mas descobri que o potencial de guarda passa dos dez anos. Fica como dica para a próxima viagem a Mendoza.

# Edsger Dijkstra

2023-04-24 tag_quotes tag_coding ^ ctrl_c

"One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in '59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame."

Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001

> "... one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities." - Edsger Dijkstra

# Kazu Lámen

2023-04-24 tag_food ^ ctrl_c

Este foi o melhor miojo que já comi. Porém, é uma casa de lámen, o que complica um pouco minha avaliação. Eu conseguiria fazer um miojo muito semelhante a este shio se praticasse algumas vezes. O dono desta casa de lámen conseguiu e cobra 50 reais por um miojo. Mas é um muito bom.

# Suzume no Tojimari: A Porta Fechada de Suzume

2023-04-24 tag_movies ^ ctrl_c

Mitiko me convidou para ver este filme que pela capa tinha cara daqueles filmes adolescentes de Makoto Shinkai. Quando estávamos entrando na sala vi seu nome no pôster. O visual que o cara usa para seus filmes é tão batido que não foi conquista nenhuma adivinhar o diretor.

Isso não é aleatório. Shinkai é idolatrado ou acredita ser no mundo inteiro. Isso faz com que o indivíduo alimente este vínculo com os fãs e consigo mesmo. Diretores autorais como Tarantino, Almodóvar, Allen fazem isso o tempo todo. Se trata de dedicar seu tempo e habilidade para manter um universo que foi criado através do hype das massas.

No caso de Shinkai este hype sobrevive em um universo com um estilo muito peculiar. Há um exagero nas formas, cores e efeitos que trabalham juntos para reforçar sua própria estética e nada mais. Quando você olha para dentro desse universo o que você vê 100% do tempo é o quão belo é o resultado.

Para a maioria das pessoas isso basta. Como toda pessoa saudável ainda não infectada pelo vírus do relativismo estético, apreciar uma obra de arte que é bela pela sua própria beleza é praticamente tudo o que podemos esperar de um filme. Algumas pessoas sequer se perguntam se poderia haver algo a mais.

É natural hoje percebemos virtudes através da superfície das coisas, não apenas de um filme, mas de tudo. Porém, no caso do audiovisual a relação não poderia ser mais direta. Se a imagem é belíssima e a trilha sonora empolgante é óbvio que estamos presenciando uma obra belíssima e empolgante.

Isso me faz lembrar a evolução das telas e seus pixels. Hoje os DVDs e sua resolução standard são coisa do passado longínquo (quem dirá o VHS). Até pouco tempo atrás o Blu-ray era o máximo de qualidade, e portanto virtude, que um filme poderia chegar. Hoje com a independência da mídia física podemos ir além, com transmissões de 4k, que possuem 4 vezes mais resolução, e portanto é quatro vezes melhor que um filme em Blu-ray. Acho que você já percebeu onde quero chegar, apesar de não ter pensado em ir tão longe.

Shinkai está reproduzindo o óbvio de sua adorada obra que ele percebe pelo feedback de sua legião de fãs, mas também de seu próprio senso estético. Ele é um cineasta jovem que representa a próxima geração após os filmes dos Estúdios Ghibli, de Hayao Miyazaki. Essa turma viveu uma evolução cada vez mais rápida da forma, em um descompasso cada vez mais distante do conteúdo. É natural que obras como Viagem para Agartha entre outras sejam confundidas com A Viagem de Chihiro ou Meu Amigo Totoro como produtos de mesma qualidade. Na verdade, se formos pensar em termos de resolução de tela e efeitos visuais há ainda mais qualidade nas obras recentes de Shinkai.

Desenhado à mão, Chihiro e Totoro não possuem a tecnologia disponível hoje de mesclar cenários e personagens 3D em cima da textura de um anime japonês, que é o que se observa nos filmes de Chinkai. Por causa disso, seguindo a lógica dos DVDs e do 4k, animes mais recentes são ainda melhores que os antigos e ultrapassados desenhos artesanais de uma época mais analógica.

Eu acredito que você já consiga caminhar com seus próprios pés a partir dessa argumentação, caro leitor.

# Vinho do Outback

2023-04-24 tag_wine ^ ctrl_c

O mundo do vinho é impressionante, mesmo. O Outback consegui arrumar um rótulo da Austrália que harmoniza com suas comidas picantes. É um Cabernet Sauvignon leve, porém com várias características de especiarias e seu final adstringente some junto com o alimento. O final chega a ser levemente doce. Não consegui descobrir o produtor.

# A Common-Sense Guide to Data Structures and Algorithms

2023-04-28 tag_interview tag_books ^ ctrl_c

Meu próximo livro para praticar entrevistas técnicas é este de Jay Wengrow. Jay queria explicar de maneira menos matemática e alienígena para programadores como algoritmos e estruturas de dados funcionam e como conceber bons algoritmos e medir a eficiência de algoritmos já prontos. Tudo isso serve também para você que deseja passar nas entrevistas técnicas e suas pegadinhas.

Ainda não terminei o livro, mas achei a didática de Jay Wengrow fabulosa, visto que os dois livros anteriores que li do assunto, Algorithm for Dummies e Cracking the code interview eram muito chatos e burocráticos. Aqui Jay está conversando de programador para programador. Mesmo que você nunca tenha ouvido falar em complexidade de algoritmo e nem seja um programador tão experiente assim vai conseguir entender os fundamentos de estruturas de dados e como manipulá-los na memória de diversas maneiras.

> A subproblem is a version of the very same problem applied to a smaller input.

Jay vai passando seu conhecimento aos poucos. Primeiro ele simplifica demais e usa analogias que nos deixam em uma zona de conforto. Depois ele vai complicando aos poucos. Quando menos esperamos já estamos sabendo o porquê de detalhes da computação que antigamente apenas aceitávamos como verdade. Ele me faz lembrar muito a didática do Tanenbaum, que constrói um argumento usando bom senso.

Bom, o título de seu livro já denuncia: este é um guia livre de bullshitagem escrito por quem coloca a mão na massa. Parei de lê-lo na parte de recursão porque comecei a parar de fazer entrevistas técnicas e projetos começaram a vir. O meu próximo exercício seria o seguinte:

"Use recursion to write a function that accepts an array of strings and returns the total number of characters across all the strings. For example, if the input array is "ab", "c", "def", "ghij", the output should be 10 since there are 10 characters in total. Use recursion to write a function that accepts an array of numbers and returns a new array containing just the even numbers. There is a numerical sequence known as “Triangular Numbers.” The pattern begins as 1, 3, 6, 10, 15, 21, and continues onward with the Nth number in the pattern, which is N plus the previous number. For example, the 7th number in the sequence is 28, since it’s 7 (which is N) plus 21 (the previous number in the sequence). Write a function that accepts a number for N and returns the correct number from the series. That is, if the function was passed the number 7, the function would return 28. Use recursion to write a function that accepts a string and returns the first index that contains the character “x.” For example, the string, "abcdefghijklmnopqrstuvwxyz" has an “x” at index 23. To keep things simple, assume the string definitely has at least one “x.” This problem is known as the “Unique Paths” problem: Let’s say you have a grid of rows and columns. Write a function that accepts a number of rows and a number of columns, and calculates the number of possible “shortest” paths from the upper-leftmost square to the lower-rightmost square. For example, here’s what the grid looks like with three rows and seven columns. You want to get from the “S” (Start) to the “F” (Finish). By “shortest” path, I mean that at every step, you’re moving either one step to the right: or one step downward: Again, your function should calculate the number of shortest paths."

Recortes

> Here’s what the notation means. It expresses the answer to what we’ll call the “key question.” The key question is: if there are N data elements, how many steps will the algorithm take? Go ahead and read that sentence again. Then, emblazon it on your forehead, as this is the definition of Big O Notation that we’ll be using throughout the rest of this book.

> Big O is originally a concept from mathematics, and therefore, it’s often described in mathematical terms. For example, one way of describing Big O is that it describes the upper bound of the growth rate of a function, or that if a function g(x) grows no faster than a function f(x), then g is said to be a member of O(f).

> If you want to dig further into the math behind Big O, check out Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press, 2009) for a full mathematical explanation. Justin Abrahms also provides a pretty good definition in his article: https://justin.abrah.ms/computer-science/understanding-big-o-formal-definition.html.

> The soul of Big O is what Big O is truly concerned about: how will an algorithm’s performance change as the data increases? This is the soul of Big O. Big O doesn’t want to simply tell you how many steps an algorithm takes. It wants to tell you the story of how the number of steps increase as the data changes.

> Because there will always be some amount of data at which the tides turn, and O(N) takes more steps from that point until infinity, O(N) is considered to be, on the whole, less efficient than O(1) no matter how many steps the O(1) algorithm actually takes.

> The same is true even for an O(1) algorithm that always takes one million steps. As the data increases, there will inevitably reach a point at which O(N) becomes less efficient than the O(1) algorithm, and will remain so up toward an infinite amount of data.

> This is actually the reason why this algorithm is called Bubble Sort: in each pass-through, the highest unsorted value “bubbles” up to its correct position.

> In reality, however, Selection Sort is described in Big O as O(N2), just like Bubble Sort. This is because of a major rule of Big O that I’m now introducing for the first time: Big O Notation ignores constants.

> This is simply a mathematical way of saying that Big O Notation never includes regular numbers that aren’t an exponent. We simply drop these regular numbers from the expression.

> However, when two algorithms fall under the same classification of Big O, it doesn’t necessarily mean that both algorithms have the same speed. After all, Bubble Sort is twice as slow as Selection Sort even though both are O(N2). So, while Big O is perfect for contrasting algorithms that fall under different classifications of Big O, when two algorithms fall under the same classification, further analysis is required to determine which algorithm is faster.

> Big O Notation only takes into account the highest order of N when we have multiple orders added together.

> That is, if we have an algorithm that takes N4 + N3 + N2 + N steps, we only consider N4 to be significant—and just call it O(N4). Why is this?

> One type of problem in which recursion is a natural fit is when we need to delve into multiple layers of a problem without knowing how many layers there are.

> one area in which recursion shines is where we need to act on a problem that has an arbitrary number of levels of depth. A second area in which recursion shines is where it is able to make a calculation based on a subproblem of the problem at hand.

> When going bottom up, we’re employing the same strategy for making the calculation whether we’re using a loop or recursion. The computational approach is the same. But to go top down, we need recursion. And because recursion is the only way to achieve a top-down strategy, it’s one of the key factors that makes recursion a powerful tool.

> (...) recursion shines when implementing a top-down approach because going top down offers a new mental strategy for tackling a problem.

> when tackling a top-down problem, it helps to think the following three thoughts: Imagine the function you’re writing has already been implemented by someone else. Identify the subproblem of the problem. See what happens when you call the function on the subproblem and go from there.

Próximas leituras

• Stein Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Clifford)
• Data Structures and Algorithms in C++ (Lee Wittenberg)
• How to Think About Algorithms (Jeff Edmonds)
• Course in Algorithms Through Puzzles (Ryuhei Uehara First )
• Guide to Competitive Programming Learning and Improving Algorithms Through Contests (Antti Laaksonen)

# Easter Egg

2023-04-28 tag_coding ^ ctrl_c

Mexendo em um projeto legado encontro encontro esta pérola. Será que ainda fazem essas coisas hoje em dia?

Eu sabia que existia um neste programa porque o código deste aplicativo foi 100% feito por mim, desde o começo até passar das dez mil linhas de código. No entanto, eu me lembro que a primeira versão deste cheat era no formato de créditos de filme, com os nomes da equipe descendo. Isso estamos falando de 20 anos atrás. Não me lembrava que ele foi readaptado para nossa minúscula equipe nessa fase do projeto, o que me gerou um saudosismo gostoso ao ver esta imagem.

Lá estava Taz, o nosso membro mais antigo, que começou como beta tester e continua sendo por todos esses anos a única pessoa com quem já trabalhei que consegue testar um software de verdade, de cabo a rabo. E se ele mesmo estivesse desenvolvendo a primeira versão esta já teria qualidade suficiente para entregar ao cliente. Claro que isso envolveria muitas e muitas horas além do orçamento para discutir e testar a solução. Mas, dane-se, quando você gosta do que faz todo o tempo gasto se torna prazeroso. As noites no escritório que passamos polindo uma última vez uma ferramenta que encapsulava uma chave criptográfica no resource do arquivo são memórias impagáveis da época.

Também na "foto" estava Rosamaria, a membro mais recente e que aprendeu sobre C++ e baixarias no Windows de sopetão. Para quem nem desconfiava que estaria entrando na área eu me lembro que ela se saiu super bem. O ponto alto para mim sempre será quando ela fez a engenharia reversa de um thin client descobrindo como fazer o inventário da solução e adaptando o código e suas sei lá quantas linhas e módulos distintos, para funcionar com a versão mais enxuta e cheia de idiossincrasias do Windows CE. Desnecessário dizer, Rosamaria é uma programadora de verdade.

E no meio, estava eu, no papel do que hoje seria tipo um tech lead, mas sem a menor vocação ou maturidade para tal. Não me lembro de mim mesmo nessa época como um bom profissional. Mas também não sei se faria diferente. Eu nem sei bem como faria. As memórias de experiências recentes com SCRUM e reflexões em retrospecto estão me levando a crer que nessa área ou você quer muito fazer as coisas funcionar e irá desenvolver as habilidades para tal com muito suor e lágrimas, ou você será um estorvo, ou em outras palavras: o motivo pelo qual essas metodologias são criadas em primeiro lugar. É a analogia do Joel e a maravilhosa história do chefe de cozinha que virou administrador de fast food ou algo assim. Pesquise para você ler no Joel on Software, caro leitor.

Pois é, esse Easter Egg é muito mais que um desenho simpático e as memórias que chegam. É um convite de reflexão sobre a vida de computeiro e como ela passa por seus ciclos. Será que ainda fazem Easter Eggs nos escritórios ou nos home-offices, ou as pessoas simplesmente trabalham?

# Hacker Rank Array - Part 1 [link]

2023-04-28 tag_coding tag_interview tag_english ^ ctrl_c

The next step after the Warm Up challenges are the array challenges. And so I did it. Now I am going to recap what I did and how I did. And what complexity the algorithms have.

Array Manipulation

To solve the array manipulation problem ChatGPT helped me with the code. Now in the review I realized how segment trees work and how binary trees can be implemented using arrays.

The issue about this problem is that summing up intervals costs too much processing to large intervals. In order to do that, segment trees help, since its nodes contain the sum of all its nodes bellow. This way, to get the sum of determined intervals all we need to do is to get the bigger intervals and sum it up.

// Segment tree to array manipulation implementation
long query(int node, int left, int right, int pos, const vector& tree) {
    if (left == right) {
        return treenode;
    }
    else {
        int nodeLeft = 2 * node;
        int nodeRight = 2 * node + 1;
        int middle = (left + right) / 2;
        if (pos <= middle)
            return treenode + query(nodeLeft, left, middle, pos, tree);
        else
            return treenode + query(nodeRight, middle + 1, right, pos, tree);
    }
}
void update(int node, int left, int right, int posLeft, int posRight, int value, vector& tree) {
    if (posLeft > posRight) return;
    if (posLeft == left && posRight == right) {
        treenode += value;
    }
    else {
        int nodeLeft = 2 * node;
        int nodeRight = 2 * node + 1;
        int middle = (left + right) / 2;
        update(nodeLeft, left, middle, posLeft, min(posRight, middle), value, tree);
        update(nodeRight, middle + 1, right, max(posLeft, middle + 1), posRight, value, tree);
    }
}
// Solution
long arrayManipulation(int n, vector> queries) {
    int m = queries.size();
    vector t(4 * n); // room for binary tree
    for (int i = 0; i < m; i++) {
        int l, r, x;
        l = queriesi0;
        r = queriesi1;
        x = queriesi2;
        update(1, 1, n, l, r, x, t);
    }
    long max_val = 0;
    for (int i = 1; i <= n; i++) {
        max_val = max(max_val, query(1, 1, n, i, t));
    }
    return max_val;
}

Left Rotation

To solve the left rotation problem in C++ is somewhat easy, since there is already an algorithm in STL to do that: `std::rotate`. Anyway, I didn't know that before my first implementation, that was to create a new vector and copy the old vector to the new one obeying the new positions.

However, the last version of the solution of this issue was using the `std::rotate` function, that is a simple, elegant algorithm:

template 
  void rotate (ForwardIterator first, ForwardIterator middle,
               ForwardIterator last)
{
  ForwardIterator next = middle;
  while (first!=next)
  {
    swap (*first++,*next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

The logic is to swap from left to right, leveraging the end part of the vector to making the swaps. The rightmost point is called next and begins in the middle point. The leftmost point is the first point. When the next point reaches the end it go back to the middle point again, because the last element was moved already and the middle now contains the original first elements that was swaped. If, however, the leftmost point reaches the middle point before the next point reaches the end, the middle point changes to the next point, what means the point where first and middle meet is changing to the next point, making the first to chase the middle point until all rightmost elements be exchanged with it, using the next as a moving buffer. The same logic is repeated until first and next point meet.

So the solution changed from this:

// Solution
vector rotLeft(vector a, int d) {
  vector ra(a.size());
  auto it = a.begin();
  advance(it, d);
  copy(it, a.end(), ra.begin());
  auto it2 = ra.begin();
  advance(it2, a.size() - d);
  copy(a.begin(), it, it2);
  return ra;
}

To this:

// Solution
vector rotLeft(vector a, int d) {
  rotate(a.begin(), a.begin() + d, a.end());
  return a;
}