9 weeks ago

John 910

Hyderabad

Question 1

Birthday Treat

It is Rob's birthday and he is very excited about the night's birthday party. The city in which Rob lives has N blocks. The roads of this city are made in such a way that there is only one route from 1 city to another. Rob only has friends from all the dead ends of the city.

It is evening and Rob only wants to call the friends who live nearest to his house. Nearest houses are those which are at the same distance from Rob's house as the nearest dead end.

Rob lives in block 0. Help him find out the number of friends he can call for the birthday party.

Input Specification:

input1: N, the number of blocks in the city. 
input2: A 2D array of 2 elements (a, b), which signifies that there is a way between block a and b. Size of input2 is input1  -1.

Output:

Your function should return the sum of all the block of the friends who will be called for the birthday party.

Question 2

Nick has been given a list of random numbers by his teacher. These numbers are marks of several students of his class. He is required to arrange the marks in increasing order and hence check whether the new arrangement of marks are successive in nature or not. You need to write a function such that it returns 1 if the complete arrangement consists of consecutive marks, otherwise return 0.

Note: If two students have the same marks, then after arranging them in increasing order, they will not be considered as consecutive.

Input Specification:

input1: Integer N, ie, size of the array input2: Integer array for elements of the array

Output Specification:

Return 1 if all the numbers are consecutive after arrangement, otherwise return 0.

Example 1:

input1: 6 
input2: {3, 7, 2, 5, 4, 6}

Output:

1

Question 3

Anagrams

An anagram is a word, phrase, or name formed by rearranging the letters of another word phrase, or name.

Write a function to check if two given strings are anagrams or not. Return "yes" if they are anagrams, otherwise return "no".

Input Specification:

input1: the first string 
input2: the second string

Output Specification:

Return "yes" if they are anagrams, otherwise return "no".

Example 1:

input1: build 
input2: dubli

Output: yes

21 months ago

Yash Sahijwani 940

Solution for Birthday Treat Problem

Analysis

The city can be viewed as a graph, where each block is a node, and a road connecting 2 blocks is an edge between them. In the question it is mentioned that there is only one route from one city to another. This means that the graph is actually a tree, because if the graph is not a tree then there would be a cycle in the graph leading to multiple routes.

So there are N nodes, and since it is a tree, N-1 edges. It is also mentioned that only dead ends have friends. By dead end, it is meant that a block which you can only reach by one road, and exit by that road only. Such nodes in a tree, which have degree (number of edges connected to) equal to 1, are leafs of the tree.

Hence, the main idea for finding all the dead-ends/leaves which can be called, we first find the distance of all leaves from the root node 0, then select the leaf with the minimum distance among all leaves, and then count the number of leaves which have distance equal to this minimum distance.

Implementation

• Make a graph in the adjacency list format from the given edges. Run BFS (Breadth First Search) / DFS (Depth First Search), taking the root node as 0, to find the distance of all nodes from node 0.
• Loop over all nodes of the tree, check which nodes have size of adjacency list equal to 1 (these are the leaves of the tree since they have only 1 edge), and then take minimum of their distances.
• Loop over all the leaves you found in step 2, and count the number of leaves which have distance equal to the minimum distance found in step 2. This will be the final answer.

Pseudo Code

Make tree from edges.
Initialize distance array with all distances set to INT_MAX
Set distance[0] = 0
Run BFS(Tree, Starting Node = 0)
Initialize nearest_distance = INT_MAX
FOR (i = 1 -> N-1)
   IF (adj_list[i].size() == 1)
       nearest_distance = min(nearest_distance, distance[i])
Initialize answer = 0
FOR (i = 1 -> N-1)
   IF (adj_list[i].size() == 1 && distance[i]==nearest_distance)
       answer++

21 months ago

Yash Sahijwani 940

Solution for Problem 2 Nick's Check

Analysis

The marks need to be sorted in increasing order first so we can sort the array in O(NlogN). Then for each element in the array, starting from the second element, we check if the previous element is 1 smaller than the current element. If not, the condition is not satisfied, else if it is satisfied for all elements, the condition is satisfied.

Pseudo Code

Sort Array
Initialize boolean possible = True
FOR (i = 1 -> N-1)
   IF (arr[i]!=arr[i-1]+1)
       possible = false
return possible

21 months ago

Yash Sahijwani 940

Solution for Anagrams

Analysis

Two strings are anagrams, if one string can be formed from the other just by rearranging the letters. This means that the frequency of each character should be the same in both the strings. So the idea behind the solution would be to count the frequency of each character in both strings, and see if they are equal for all characters or not.

Implementation

• Make two arrays of length 26, one for storing frequency of characters of string 1, and the other for string 2.
• For both the strings, iterate over each character, find its position in the alphabet, relative to 'a', e.g. 'c' has position 2, 'a' has position 0, 'f' has position 5. Then increment the frequency counter for the position for that string in the corresponding array.
• Loop over all the 26 characters, and see if the frequencies are same or not.

Better Implementation

Instead of using 2 arrays, you can simply use a single array, and increment the frequency counter for every character of string 1, and decrement the counter for every character of string 2. So for each position in the frequency array, the frequency should be 0, for both of them to be anagrams.