This year I’ve participated in Atlassian Girlscript off-campus. As you would have guessed, its first-round was online coding on HackerRank. There was a total of 3 questions and 90 minutes to submit the test.
Online Coding Round:
- Array Reduction
There is an array of n integers called nums. The array can be reduced by one element by performing a move operation.
Each move has:
- Pick two different elements nums[i] and nums[j] (i and j are not equal)
- Remove both elements
- Add the sum of two selected elements to the end of the array
Each move has a cost associated with it – the sum of 2 elements removed from the array during the move. Hence, calculate the minimum total cost of reducing the array to one element.
Input: nums array containing n elements
Output: Integer value displaying the minimum cost
Input: [4, 6, 8]
Output: 18
There are two possibilities;
1. Pick the first two elements i.e. 4, 6
Remove them from the list. The new list will be [8]
Add the sum 4+6=10 to the end of the list [8, 10]
Again, pick two elements. Now only remaining elements are 8, 10
Remove them from the list. []
Add the sum 8+10=18 to the end of the list [18].
18 is the output since one element is the terminating condition.
2. One can also pick 4, 8
Remove them from the list. [6]
Add the sum to last [6, 12]
Again, pick two elements. 6, 12
Remove them from the list []
Add the sum 6+12=18 to the end of the list [18].
Input: [4, 4, 4, 4, 6]
Output: 52
Input: [1, 2, 3, 4]
Output: 19
- Valid BST Permutations
Given an integer, determine the number of valid Binary Search Trees that can be created by nodes numbered from 1 to that integer.
Input: Integer denoting the nodes
Output: Number of total BST
Input: 2
Output: 2
There will be two possible BST with 2 nodes.
2 (root) 1(root)
1 (right child of the root) 2(left child of the root)
Input: 1
Output: 1
Input: 3
Output: 5
- Strongly Connected Groups
A group of software engineers wants to make a strongly connected group such that, each person knows every other person within the group.
If the network has n people and there are m pairs of relationships connecting them, then find the minimum size of the largest strongly connected group. Think of people as graph nodes and their relations as edges.
Input: Integer NumNodes (number of people in the group), integer NumEdges (relations between the nodes)
Output: Integer denoting the minimum number of people who must form a strongly connected group
Input: 5, 4
Outpu: 3
Input: 7, 6
Output: 4
Happy coding!