Issue # 38: IT training - current issues and challenges from leading companies

Hello! New week – new release of brandisers. This time, with interviews at IT company Accolite.

By the way, the answers to the problems from the previous issue have already been published, check yourself and your wit.

Well, let’s go!

Questions

1. Rich or poor

A place has two kinds of residents, Poor, who always tell the truth, and their opposites, Rich, who always lie. You encounter two people A and B. What are A and B if A says “B is a Poor” and B says “The two of us are opposite types”?

Transfer

In one place there are two kinds of inhabitants: the poor, who always tell the truth, and the rich, who always lie. Do you encounter two people A and B. Which class does each of the people A and B belong to if A says “B is poor” and B says “We are both opposite types”?

2. Boy with marbles

A boy goes to 20 of his friend’s houses with ‘n’ number of newly purchased marbles in his hands. At every house he visits, he gives away half of marbles he have and take one of his friend’s marble’s and adds it with the one’s he is left with, he never had a problem of dividing an odd number of marbles left and finally after leaving the his 20th friends house, he is left with 2 marbles, can you guess the ‘n’ value?

Transfer

The boy goes to the 20 houses of his friends with the “n” number of recently bought balls in his hands. In each house that he visits, he gives half the balls that he has, and takes one of his friend’s balls and adds it to those that he has left. He never had a problem with sharing the odd number of remaining balls, and finally, after he left the last house of his 20 friends, he had 2 balls left. Can you guess the value of “n”?

Tasks

1. Swap two nibbles in a byte

Given a byte, swap the two nibbles in it. For example 100 is be represented as 01100100 in a byte (or 8 bits). The two nibbles are (0110) and (0100). If we swap the two nibbles, we get 01000110 which is 70 in decimal.

Input:

The first line contains ‘T’ denoting the number of testcases. Each testcase contains a single positive integer X.

Output:

In each separate line print the result after swapping the nibbles.

Constraints:
1 ≤ T ≤ 70 1 ≤ X ≤ 255

Example:
Input:
2 100 129

Output:
70 24

Transfer

Dan byte, swap the two parts in it. For example, 100 can be represented as 01100100 in bytes (or 8 bits). The two parts are (0110) and (0100). If we swap the two parts, we get 01000110, which is 70 in the decimal system.

Input:

The first line contains the letter “T”, indicating the number of tests. Each test contains one positive integer X.

Conclusion:

On each separate line print the Result after replacing the parts.

Limitations:
1 ≤ T ≤ 70 1 ≤ X ≤ 255

Example:
Input:
2 100 129

Conclusion:
70 24

2. Count pairs with given sum

Given an array of integers, and an integer ‘K’, find the count of pairs of elements in the array whose sum is equal to ‘K’.

Input:

First line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains 2 space separated integers N and K denoting the size of array and the sum respectively. Second line of each test case contains N space separated integers denoting the elements of the array.

Output:

Print the count of pairs of elements in the array whose sum is equal to the K.

Constraints:
1<=T<=50 1<=N<=50 1<=K<=50 1<=A[i]<=100

Example:
Input
2 4 6 1 5 7 1 4 2 1 1 1 1
Output
2 6

Transfer

Given an array of integers and an integer “K”, find the number of pairs of elements in the array whose sum is “K”.

Input:

The first line of input contains an integer T, indicating the number of tests. Then T tests follow. Each test consists of two lines. The first line of each test contains 2 integers N and K, separated by spaces, indicating the size of the array and the sum, respectively. The second line of each test contains N integers, separated by a space, indicating the elements of the array.

Conclusion:

Print the number of pairs of elements in the array whose sum is K.

Limitations:
1< = T< = 50 1< = N< = 50 1< = K< = 50 1<=A[i]< = 100

Example:
Enter
2 4 6 1 5 7 1 4 2 1 1 1 1
Conclusion
2 6

3. Trie | (Insert and Search)

Trie is an efficient information retrieval data structure. Use this data structure to store Strings and search strings. Your task is to use TRIE data structure and search the given string A. If found print 1 else 0.

Input:

The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines.
First line of each test case consisting of a integer N, denoting the number of element in a Trie to be stored.
Second line of each test case consists of N space separated strings denoting the elements to be stored in the trie.
Third line of each test case consists of a String A to be searched in the stored elements.

Output:

Print the respective output in the respective line.

Constraints:
1<=T<=20 1<=N<=20

Example:
Input:
1 8 the a there answer any by bye their the
Output:
1

Transfer

Trie is an efficient data structure for finding information. Use this data structure to store strings and search for strings. Your task is to use the TRIE data structure and look for the given string A. If it is found, print 1, if not, print 0.

Input:

The first line of input contains a single integer T, indicating the number of tests. Then T tests follow. Each test consists of three lines.
The first line of each test consists of an integer N, indicating the number of elements in TRIE that must be stored.
The second line of each test consists of N lines, separated by spaces, indicating the elements that will be stored in TRIE.
The third line of each test consists of line A, which must be searched for in stored items.

Conclusion:

Print 1 or 0 in the corresponding line.

Limitations:
1< = T< = 20 1< = N< = 20

Example:
Input:
1 8 the a there answer any by bye their the
Conclusion:
1

Answers to the tasks will be given during the next week - have time to solve it. Good luck