Below is the Python code for traversing trees in various recursive modes like In order, Preorder, Post Order and their reverse orders…

The code is provided in python, but can be easily translated to Java/JS/PHP etc

Skip to content
# Category: Algorithms

## #Tree #Traversals

## #Machine #Learning: The Basics, with Ron Bekkerman

## #HackerRank: Computing the Correlation

**Problem**

**Solution**(Source)

## #HackerEarth: #BattleOfBots 9: Taunt

## Sort a list of tuples by Nth item in Python

## K random combinations of N elements in List in Java

## HackerRank: Repeated String

### Problem

### Input Format

### Constraints

### Output Format

### Sample Input 0

### Sample Output 0

### Explanation 0

### Sample Input 1

### Sample Output 1

### Explanation 1

### Solution

## HackerRank: Circular Array Rotation

### Problem

#### Input Format

#### Constraints

#### Output Format

##### Sample Input

##### Sample Output

#### Explanation

### Soluton

## HackerEarth: Battle Of Bots 6: Draughts

## Problem:

## Solution

## HackerEarth: Battle Of Bots #5: Reversi

## Problem:

## My Solution:

Below is the Python code for traversing trees in various recursive modes like In order, Preorder, Post Order and their reverse orders…

The code is provided in python, but can be easily translated to Java/JS/PHP etc

You are given the scores of **N** students in three different subjects – **Mathematics**, ** Physics** and

**Pearson product-moment correlation coefficient**

This is a measure of linear correlation described well on this Wikipedia page. The formula, in brief, is given by:

where **x** and **y** denote the two vectors between which the correlation is to be measured.

**Input Format**

The first row contains an integer **N**.

This is followed by **N** rows containing three tab-space (*‘\t’*) separated integers, **M P C** corresponding to a candidate’s scores in Mathematics, Physics and Chemistry respectively.

Each row corresponds to the scores attained by a unique candidate in these three subjects.

**Input Constraints**

1 <= N <= 5 x 10^{5}

0 <= **M, P, C** <= 100

**Output Format**

The output should contain three lines, with correlation coefficients computed

and rounded off **correct to exactly 2 decimal places**.

The first line should contain the correlation coefficient between Mathematics and Physics scores.

The second line should contain the correlation coefficient between Physics and Chemistry scores.

The third line should contain the correlation coefficient between Chemistry and Mathematics scores.

So, your output should look like this (these values are only for explanatory purposes):

```
0.12
0.13
0.95
```

**Test Cases**

There is one sample test case with scores obtained in Mathematics, Physics and Chemistry by 20 students. The hidden test case contains the scores obtained by all the candidates who appeared for the examination and took all three tests (Mathematics, Physics and Chemistry).

*Think:** How can you efficiently compute the correlation coefficients within the given time constraints, while handling the scores of nearly 400k students?*

**Sample Input**

```
20
73 72 76
48 67 76
95 92 95
95 95 96
33 59 79
47 58 74
98 95 97
91 94 97
95 84 90
93 83 90
70 70 78
85 79 91
33 67 76
47 73 90
95 87 95
84 86 95
43 63 75
95 92 100
54 80 87
72 76 90
```

**Sample Output**

```
0.89
0.92
0.81
```

There is **no special library support** available for this challenge.

Taunt is a two player board game which is played on a 10X4 grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, Orange ( First Player ) or Green ( Second Player ) being conventional. Each player has nine piece in total. The players move their pieces towards to his / her opponent’s area by moving their pieces strategically. Each piece has a different moving feature and is one of the 3 types of pieces.

**Piece 1:** It can move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.

**Piece 2:** It can move to horizontally adjacent cell or can move two steps forward, if the cell doesn’t contain a piece of same color (except the piece itself).

This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.

**Piece 3:** It can move two step diagonally in the forward direction, if the cell doesn’t contain a piece of same color (except the piece itself).

This type of piece can move to its own position if its in the second last row of the grid and going downward or if its in the second row of the grid and going upward.

Players take turns involving moves of pieces as mentioned above and can captures opponent’s piece by jumping on or over opponent’s pieces.

**Note:** Forward direction for first player is downward and for second player is upward.

If a piece (except piece 1) is moving downward and touches the last row, its direction will change i.e. now it will move upward. Similarly, once if a piece (except piece 1) is moving upward and touches the first row, its direction will change i.e. now it will move downward.

Rules:

- Player can only move according to the moves mentioned above.
- A player may not move an opponent’s piece.
- A player can captures opponent’s piece by jumping on or over opponent pieces.

The game will end after 100 moves ( 50 moves for each player ) or when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an 10X4 grid. The top left of the grid is [0,0] and the bottom right is [9,3].

**Input:**

The input will be a 10X4 matrix consisting only of 0,1or2. Next line will contain an integer denoting the total number of moves till the current state of the board. Next line contains an integer – 1 or 2 which is your player id.

In the given matrix, top-left is [0,0] and bottom-right is [9,3]. The y-coordinate increases from left to right, and x-coordinate increases from top to bottom.

A cell is represented by **3** integers.

First integer denotes the player id (1 or 2).

Second integer denotes the type of piece (1, 2 or 3).

Third integer denotes the direction of the piece (0 (upward) or 1 (downward)). When the piece is of first type, direction doesn’t matter as the piece is free to move to horizontally or vertically adjacent cell, if the cell doesn’t contain a piece of same color.

Empty cell is represented by 000.

**Output:**

In the first line print the coordinates of the cell separated by space, the piece you want to move.

In second line print the coordinates of the cell in which the piece will jump.

You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if the piece is able to jump to [1,1], but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

**Starting state**

The starting state of the game is the state of the board before the game starts.

131 131 131 121 121 121 111 111 111 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 210 210 210 220 220 220 230 230 230

**First Input**

This is the input give to the first player at the start of the game.

131 131 131 121 121 121 111 111 111 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 210 210 210 220 220 220 230 230 230 0 1

SAMPLE INPUT

000 000 000 000 000 000 000 111 000 000 111 130 000 000 000 000 000 000 000 000 000 220 000 000 131 000 000 000 121 000 210 000 000 210 131 000 000 210 000 000 58 1

SAMPLE OUTPUT

8 2 8 0

Explanation

This is player 1’s turn, and the player will move the piece at [8,2] and will take two steps diagonally in downward direction and will be at [8,0]

After his/her move the state of game becomes:

000 000 000 000 000 000 000 111 000 000 111 130 000 000 000 000 000 000 000 000 000 220 000 000 131 000 000 000 121 000 210 000 130 210 000 000 000 000 000 000 59 2

**Note:** Direction of the piece is also changed from 1 to 0 as the piece was moving downward and touches the last row. This state will be fed as input to program of player 2.

Here is the code of the default bot.

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Suppose you have a list of tuples that looks something like this:

`[('abc', 121),('abc', 231),('abc', 148), ('abc',221)]`

And you want to sort this list in ascending order by the integer value inside the tuples.

We can achieve this using the `key`

keyword with `sorted()`

.

`sorted([('abc', 121),('abc', 231),('abc', 148), ('abc',221)], key=lambda x: x[1])`

`key`

should be a function that identifies how to retrieve the comparable element from your data structure. For example, the second element of the tuple, so we access `[1]`

.

Given a List of N Strings, generate and print all possible combinations of R elements in array and return X random combinations from the result. Following is the code for implementing it:

Lilah has a string, ** s**, of lowercase English letters that she repeated infinitely many times.

Given an integer, ** n**, find and print the number of letter

`a`

‘s in the first letters of Lilah’s infinite string.The first line contains a single string, `s`

.

The second line contains an integer, `n`

.

`1<=|s|<=100`

`1<=|n|<=10^12`

- For
`25%`

of the test cases,`n <= 10^6`

Print a single integer denoting the number of letter a’s in the first letters of the infinite string created by repeating infinitely many times.

aba

10

7

The first `n = 10`

letters of the infinite string are `abaabaabaa`

. Because there are *7*`a`

‘s, we print on a new line.

a

1000000000000

1000000000000

Because all of the first `n=1000000000000`

letters of the infinite string are a, we print ** 1000000000000** on a new line.

John Watson performs an operation called a right circular rotation on an array of integers, `[a(0),a(1).a(2)...a(n-2),a(n-1)]`

. After performing one right circular rotation operation, the array is transformed from

`[a(0),a(1).a(2)...a(n-2),a(n-1)]`

to

`[a(n-1),a(0),a(1).a(2)...a(n-2)]`

.

Watson performs this operation `k`

times. To test Sherlock’s ability to identify the current element at a particular position in the rotated array, Watson asks `q`

queries, where each query consists of a single integer, `m`

, for which you must print the element at index in the rotated array (i.e., the value of `a(m)`

).

The first line contains space-separated integers, `n`

, `k`

, and `q`

, respectively.

The second line contains space-separated integers, where each integer `i`

describes array element `a(i)`

(where `0 <= i <= n`

).

Each of the `q`

subsequent lines contains a single integer denoting `m`

.

`0 <= i <= 10^5`

`0 <= a(i) <= 10^5`

`0 <= k <= 10^5`

`0 <= q <= 500`

`0 <= m <= N-1`

For each query, print the value of the element at index `m`

of the rotated array on a new line.

3 2 3 1 2 3 0 1 2

2 3 1

After the first rotation, the array becomes `[3,1,2]`

.

After the second (and final) rotation, the array becomes `[2,3,1]`

.

Let’s refer to the array’s final state as array `b`

. For each query, we just have to print the value of `b(m)`

on a new line:

`m=0`

, so we print`2`

on a new line.`m=1`

, so we print`3`

on a new line.`m=2`

, so we print`1`

on a new line.

**Draughts** is a two player board game which is played on a **8X8** grid of cells and is played on opposite sides of the game-board. Each player has an allocated color, **Red ( First Player )** or **White ( Second Player )** being conventional. Players take turns involving diagonal moves of uniform game pieces in the forward direction only and **mandatory captures by jumping** over opponent pieces.

Rules:

- Player can only move diagonally to the adjacent cell and in forward direction, if the diagonally adjacent cell is vacant.
- A player may not move an opponent’s piece.
- If the diagonally adjacent cell contains an opponent’s piece, and the cell immediately beyond it is vacant, the opponent’s piece may be captured (and removed from the game) by jumping over it in the forward direction only.
- If a player made a jump, then its
**mandatory**to keep on jumping as long as the jump is possible. - Player cannot move to the diagonally adjacent cell once the player made a jump.

The game will end when any of the players don’t have any move left. At the end of the game the player with majority of pieces will win.

We will play it on an **8X8** grid. The top left of the grid is **[0,0]** and the bottom right is **[7,7]**.

**Input:**

The input will be a **8X8** matrix consisting only of **0, 1 or 2**. Then another line will follow which will contain a number – ** 1 or 2** which is your player id. In the given matrix, top-left is** [0,0]** and bottom-right is **[7,7]**. The x-coordinate increases from left to right, and y-coordinate increases from top to bottom.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Red in color. The cell marked 2 means it contains second player’s stone which is white in color.

**Output:**

In the first line print the coordinates of the cell separated by space, the piece he / she wants to move.

In second line print an integer N, number of steps or jumps the piece will make in one move.

In the next N lines print the coordinates of the cells in which the piece will make jump.

You must take care that you don’t print invalid coordinates. For example, [1,1] might be a valid coordinate in the game play if [1,1] in diagonal to the piece in which is going to jump, but [9,10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

**Starting state**

The starting state of the game is the state of the board before the game starts.

0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 2 0 2 2 0 2 0 2 0 2 0

**First Input**

This is the input give to the first player at the start of the game.

0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 0 2 0 2 2 0 2 0 2 0 2 0 1

SAMPLE INPUT

0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 2 2 0 2 0 2 0 2 0 1

SAMPLE OUTPUT

2 5 2 4 3 6 1

Explanation

This is player 1’s turn, and the player will move the piece at [2,5] and will make two jumps. First jump will be at [4,3] and second jump will be at [6,1]

After his/her move the state of game becomes:

0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 2 0 2 2 0 2 0 2 0 2 0

This state will be fed as input to program of player 2.

Other valid move for the first player is

2 5 1 3 6

But the following are invalid moves.

Case 1:

2 5 1 4 3

Because after making a jump its possible to jump again and its **mandatory** to jump as long as its possible to jump.

Case 2:

2 5 2 4 3 5 4

Because after making a jump its invalid to move to diagonally adjacent cell.

Here is the code of the Random Bot.

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

This is the solution submitted by me

Reversi is a two player board game which is played on a 10 x 10 grid of cells. Each player has an allocated color, Black ( First Player ) or White ( Second Player ) being conventional. Players take turns placing a stone of their color on a single cell. A player must place a stone on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) occupied line between the new stone and another stone of same color, with one or more contiguous other color stone between them.

During a game, any stone of the opponent’s color that are in a straight line and bounded by the stone just placed and another stone of the current player’s color are turned over to the current player’s color. The game will end when the board is completely filled or both the players don’t have any move left. At the end of the game the player with majority of stone will win.

We will play it on an **10 x 10** grid. The top left of the grid is **[0,0]** and the bottom right is **[9,9]**. The rule is that a **cell[i,j]** is connected to any of top, left, right, or bottom cell.

**Input:**

The input will be a **10 x ****10** matrix consisting only of **0,1,2 or 3**. Then another line will follow which will contain a number – 1 or 2 which is your player id.

In the given matrix, top-left is [0,0] and bottom-right is [9,9].

In cell[row,column], row increases from top to bottom and column increases from left to right.

The cell marked 0 means it doesn’t contain any stones. The cell marked 1 means it contains first player’s stone which is Black in color. The cell marked 2 means it contains second player’s stone which is white in color. The cell marked 3 means it is a valid place for player whose turn it is.

**Output:**

Print the coordinates of the cell separated by space, where you want to play your move. You must take care that you don’t print invalid coordinates. For example, [1 1] might be a valid coordinate in the game play if cell[i,j]=3, but [9 10] will never be. Also if you play an invalid move or your code exceeds the time/memory limit while determining the move, you lose the game.

**Starting state**

The starting state of the game is the state of the board before the game starts.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

**First Input**

This is the input give to the first player at the start of the game.

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 2 1 0 0 0 0 0 0 0 0 1 2 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

**Scoring**

The scores are calculated by running tournament of all submissions. Your latest submission will be taken into tournament. Scores are assigned according to the Glicko-2 rating system. For more information and questions, see Bot problem judge.

SAMPLE INPUT

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 3 2 1 3 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 3 1 1 2 3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

SAMPLE OUTPUT

4 3

Explanation

This is player 1’s turn, and the player puts his/her stone in cell[4,3].

After his/her move the state of game becomes:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 3 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 3 1 2 0 0 0 0 0 0 0 3 1 1 2 0 0 0 0 0 0 1 0 3 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

This state will be fed as input to program of player 2.

Time Limit:1.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Marking Scheme:Marks are awarded if any testcase passes.

Allowed Languages:C, CPP, CLOJURE, CSHARP, D, ERLANG, FSHARP, GO, GROOVY, HASKELL, JAVA, JAVA8, JAVASCRIPT, JAVASCRIPT_NODE, LISP, LISP_SBCL, LUA, OBJECTIVEC, OCAML, OCTAVE, PASCAL, PERL, PHP, PYTHON, PYTHON3, R, RACKET, RUBY, RUST, SCALA, SWIFT, VB