Solution
/* Solution to HackerRank: Vowels in the Back
* URL: https://www.hackerrank.com/contests/regular-expresso/challenges/vowels-in-the-back
*/
"[aeiouy][a-z]{9}$"
HackerRank Contest - Regular Expresso - Balanced Strings
Solution
/* Solution to HackerRank: Balanced Strings
* URL: https://www.hackerrank.com/contests/regular-expresso/challenges/balanced-strings
*/
"^(ab|ba)+$"
possible strings:
ababab
abba
babaab
but not:
a
bab
abbaaba
HackerRank Contest - Regular Expresso - Winning Tic Tac Toe
Solution
/* Solution to HackerRank: Winning Tic Tac Toe
* URL: https://www.hackerrank.com/contests/regular-expresso/challenges/winning-tic-tac-toe
*/
"(X|O)((...\\1){2}|..\\1..\\1|.\\1.\\1..$|\\1\\1(...)*$)"
Case 1
(...\\1){2}) or (...\\1...\\1)
will take care of
X O -
O X O
- - X
Case 2
(..\\1..\\1)
will take care of
X - O
X O -
X - O
OR
- X O
O X -
- X O
OR
- O X
O - X
- O X
Case 3
(.\\1.\\1..$)
will take care of
O - X
- X O
X O -
false positive if ..$ is not included
O X -
X O X
- O X
Case 4
(\\1\\1(...)*$)
will take care of
X X X
O - O
- - -
OR
O - O
X X X
O - -
OR
O - -
O - X
X X X
false positive if (...)*$ is not included
O - X
X X -
- O O
HackerRank - Goodland Electricity
Solution
- Iterate through each city and check if it is already under range of previous tower.
- If not, find a tower within the range to switch on.
/* Solution to HackerRank: Goodland Electricity
* URL: https://www.hackerrank.com/challenges/pylons
*/
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] cities = new int[N];
for(int i=0; i < N; i++){
cities[i] = in.nextInt();
}
int index = 0;
int range = 0;
int changes = 0;
while(index < N){
if(index < range){
// city is already in range
}
else{
// find a tower to switch on
int towerEnd = index+K;
int towerStart = index-K+1;
if(towerStart < 0){
towerStart = 0;
}
int tower = -1;
for(int j=towerStart; j<towerEnd && j<N; j++){
if(cities[j] == 1){
tower = j;
}
}
// no way to handle current city
if(tower == -1){
System.out.println(-1);
return;
}
else{
changes++;
index = tower;
range = index + K;
}
}
index++;
}
System.out.println(changes);
}
}
HackerRank - Max Min
Solution
- Sort the array of numbers
- Find the minimum difference between ith and (i+K-1)th element in each iteration.
/* Solution to HackerRank: Max Min
* URL: https://www.hackerrank.com/challenges/angry-children
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int K = Integer.parseInt(in.readLine());
int[] list = new int[N];
for(int i = 0; i < N; i ++)
list[i] = Integer.parseInt(in.readLine());
int unfairness = Integer.MAX_VALUE;
Arrays.sort(list);
// find minimum difference between ith and (i+K-1)th element in a sorted array
for(int i = 0; i < N-K+1; i++){
int diff = list[i+K-1] - list[i];
unfairness = Math.min(unfairness, diff);
}
System.out.println(unfairness);
}
}
HackerRank - Maximum Perimeter Triangle
Solution
- Iterate the sides in descending order
- Check if sides make a triangle by checking if sum of two sides is greater than third side .
/* Solution to HackerRank: Maximum Perimeter Triangle
* URL: https://www.hackerrank.com/challenges/maximum-perimeter-triangle
*/
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] l = new int[N];
for(int i=0; i < N; i++){
l[i] = in.nextInt();
}
Arrays.sort(l);
// iterate in descending order
for(int a = l.length-1; a > 1; a--){
for(int b = a-1; b > 0; b--){
for(int c = b-1; c > -1; c--){
// check if sum of two sides is greater than the third side
if(l[a] + l[b] > l[c] && l[a] + l[c] > l[b] && l[b] + l[c] > l[a]){
System.out.println(l[c]+" "+l[b]+" "+l[a]);
return;
}
}
}
}
System.out.println(-1);
}
}
HackerEarth - Mirror Image
Solution
- Parse input and build the tree by maintaining an index
HashMap. - Traverse tree and mirror tree simultaneously to find the mirror node.
/* Solution to HackerEarth: Mirror Image
* URL: https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/practice-problems/algorithm/mirror-image-2/
*/
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
//Scanner
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int Q = in.nextInt();
Map<Integer, Node> index = new HashMap<>();
// initialize root node
Node root = new Node(1);
index.put(1, root);
// build tree
for(int i=0; i < N-1; i++){
int parent = in.nextInt();
int child = in.nextInt();
char side = in.next().charAt(0);
// get parent node from index
Node node = index.get(parent);
// create a new child node and add to index
Node childNode = new Node(child);
index.put(child, childNode);
if(side == 'L'){
node.left = childNode;
}
else if (side == 'R'){
node.right = childNode;
}
}
// process queries
for(int i=0; i < Q; i++){
int target = in.nextInt();
System.out.println(findMirror(root, target));
}
}
public static int findMirror(Node root, int target){
if(root.value == target){
return target;
}
else{
return recurse(target, root.left, root.right);
}
}
public static int recurse(int target, Node left, Node right){
// no need to further traverse because either current node or mirror node is null
if(left == null || right == null){
return -1;
}
// if target found return mirror node
if(left.value == target){
return right.value;
}
if(right.value == target){
return left.value;
}
int mirror = recurse(target, left.left, right.right);
// return mirror if found
if(mirror > 0){
return mirror;
}
return recurse(target, left.right, right.left);
}
}
class Node {
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
Track API usage with Google Analytics
Google analytics is a popular tool to track your website usage. Usage of server APIs can also be tracked with this tool. Measurement Protocol APIs can be used to post the usage data to Google Analytics.
HackerRank - Largest Permutation
Solution #1
- Keep indexes of all numbers in a
HashMap. - Check if current maximum number is already at desired index i.e highest at index 0, second highest at index 1 and so on.
- If not, keep on swapping them till all the swaps are exhausted.
/* Solution to HackerRank: Largest Permutation
* URL: https://www.hackerrank.com/challenges/largest-permutation
*/
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] n = new int[N];
Map<Integer,Integer> index = new HashMap<>();
for(int i = 0; i < N; i++){
n[i] = in.nextInt();
index.put(n[i],i);
}
int max = N;
for(int j = 0; j < N ; j++){
int maxIndex = index.get(max);
if(maxIndex != j){
// make a swap
K--;
int temp = n[j];
n[j] = max;
n[maxIndex] = temp;
// update indexes
index.put(max,j);
index.put(temp,maxIndex);
}
max--;
// break the loop if swaps are exhausted
if(K == 0){
break;
}
}
for(int i = 0; i < N; i++){
System.out.print(n[i] + " ");
}
}
}
Solution #2
- Find the maximum number in each iteration.
- Swap them in order of decreasing value till all the swaps are exhausted.
Test cases 13 to 15 timed out for this solution.
HackerRank - Hackerland Radio Transmitters
Solution
- Iterate through each house in a sorted order.
- Check if current house is in range of last transmitter.
- If not, find a house to put transmitter on so that current house is in range.
/* Solution to HackerRank: Hackerland Radio Transmitters
* URL: https://www.hackerrank.com/challenges/hackerland-radio-transmitters
*/
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
int[] x = new int[n];
for(int x_i=0; x_i < n; x_i++){
x[x_i] = in.nextInt();
}
Arrays.sort(x);
int i = 0;
int range = 0;
int count = 0;
while(i < n){
if(x[i] < range){
// current house is already in range of last transmitter
}
else{
count++;
// check where can the transmitter be placed
int j = x[i] + k;
int l = i;
// transmitter can not be placed farther than j to cover current house,
// check for the last house within j
while(l < n && x[l] <= j){
l++;
}
// transmitter is placed at l-1 house
range = x[--l] + k + 1;
// move counter to l as houses till l are already in range of new transmitter
i = l;
}
i++;
}
System.out.println(count);
}
}