isMAC48Address [CodeSignal]

URL: CodeSignal

A media access control address (MAC address) is a unique identifier assigned to network interfaces for communications on the physical network segment.

The standard (IEEE 802) format for printing MAC-48 addresses in human-friendly form is six groups of two hexadecimal digits (0 to 9or A to F), separated by hyphens (e.g. 01-23-45-67-89-AB).

Your task is to check by given string inputString whether it corresponds to MAC-48 address or not.

Example

• For inputString = "00-1B-63-84-45-E6", the output should be
  isMAC48Address(inputString) = true;
• For inputString = "Z1-1B-63-84-45-E6", the output should be
  isMAC48Address(inputString) = false;
• For inputString = "not a MAC-48 address", the output should be
  isMAC48Address(inputString) = false.

Input/Output

• [execution time limit] 3 seconds (java)
• [input] string inputString

  Guaranteed constraints:
  15 ≤ inputString.length ≤ 20.

• [output] boolean
  • true if inputString corresponds to MAC-48 address naming rules, falseotherwise.

boolean isMAC48Address(String inputString) {
String[] str = inputString.split("-");
if(str.length != 6 || inputString.length()!=17 ) return false;

for(int i = 0; i<str.length; i++){
if(str[i].length() >2) return false;
if(!Character.isDigit(str[i].charAt(0))&&(str[i].charAt(0) < 'A' || str[i].charAt(0) >'F'))
return false;
if(!Character.isDigit(str[i].charAt(1))&&(str[i].charAt(1) < 'A' || str[i].charAt(1) >'F'))
return false;
}
return true;
}

Election Winners[CodeSignal]

URL: CodeSignal

Elections are in progress!

Given an array of the numbers of votes given to each of the candidates so far, and an integer k equal to the number of voters who haven’t cast their vote yet, find the number of candidates who still have a chance to win the election.

The winner of the election must secure strictly more votes than any other candidate. If two or more candidates receive the same (maximum) number of votes, assume there is no winner at all.

Example

For votes = [2, 3, 5, 2] and k = 3, the output should be
electionsWinners(votes, k) = 2.

• The first candidate got 2 votes. Even if all of the remaining 3 candidates vote for him, he will still have only 5 votes, i.e. the same number as the third candidate, so there will be no winner.
• The second candidate can win if all the remaining candidates vote for him (3 + 3 = 6 > 5).
• The third candidate can win even if none of the remaining candidates vote for him. For example, if each of the remaining voters cast their votes for each of his opponents, he will still be the winner (the votes array will thus be [3, 4, 5, 3]).
• The last candidate can’t win no matter what (for the same reason as the first candidate).

Thus, only 2 candidates can win (the second and the third), which is the answer.

Input/Output

• [execution time limit] 3 seconds (java)
• [input] array.integer votesA non-empty array of non-negative integers. Its ith element denotes the number of votes cast for the ith candidate.

  Guaranteed constraints:
  4 ≤ votes.length ≤ 105,
  0 ≤ votes[i] ≤ 104.

• [input] integer kThe number of voters who haven’t cast their vote yet.

  Guaranteed constraints:
  0 ≤ k ≤ 105.

• [output] integer

 

int electionsWinners(int[] votes, int k) {
int[] max = votes.clone();
Arrays.sort(max);
int sol = 0;
if(k ==0){
for(int i = 0; i<votes.length; i++){
if((votes[i]) == max[max.length-1]){
sol++;
}
}
if(sol >=2) return 0;
}
else{
for(int i = 0; i<votes.length; i++){
if((k+votes[i]) > max[max.length-1]){
sol++;
}
}
}
return sol;
}

buildPalindrome [CodeSignal]

URL: buildPalindrome

Given a string, find the shortest possible string which can be achieved by adding characters to the end of initial string to make it a palindrome.

Example

For st = "abcdc", the output should be
buildPalindrome(st) = "abcdcba".

Input/Output

• [execution time limit] 3 seconds (java)
• [input] string stA string consisting of lowercase English letters.

  Guaranteed constraints:
  3 ≤ st.length ≤ 10.

• [output] string

 

String buildPalindrome(String st) {
if(st.equals(new StringBuilder(st).reverse().toString())) return st;
for(int i = 0; i<st.length(); i++){
String str = st;
str += new StringBuilder(st.substring(0,i)).reverse().toString();
if(str.equals(new StringBuilder(str).reverse().toString())){
st = str;
break;
}
}
return st;
}

avoidObstacles [CodeSignals]

You are given an array of integers representing coordinates of obstacles situated on a straight line.

Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.

Find the minimal length of the jump enough to avoid all the obstacles.

Example

For inputArray = [5, 3, 6, 7, 9], the output should be
avoidObstacles(inputArray) = 4.

Check out the image below for better understanding:

Input/Output

• [execution time limit] 3 seconds (java)
• [input] array.integer inputArray

  Non-empty array of positive integers.

  Guaranteed constraints:
  2 ≤ inputArray.length ≤ 1000,
  1 ≤ inputArray[i] ≤ 1000.

• [output] integer
  • The desired length.

 

int avoidObstacles(int[] inputArray) {

Arrays.sort(inputArray);

int sol,i;

for(i = 1; ; i++){
sol = 0;
for(int n:inputArray){
if(n%i==0){
break;
}
else
sol++;
}
if(sol == inputArray.length)
return i;
}

}

New Numeral System[CodeSignal]

Your Informatics teacher at school likes coming up with new ways to help you understand the material. When you started studying numeral systems, he introduced his own numeral system, which he’s convinced will help clarify things. His numeral system has base 26, and its digits are represented by English capital letters – A for 0, B for 1, and so on.

The teacher assigned you the following numeral system exercise: given a one-digit number, you should find all unordered pairs of one-digit numbers whose values add up to the number.

Example

For number = 'G', the output should be
newNumeralSystem(number) = ["A + G", "B + F", "C + E", "D + D"].

Translating this into the decimal numeral system we get: number = 6, so it is ["0 + 6", "1 + 5", "2 + 4", "3 + 3"].

Input/Output

• [execution time limit] 3 seconds (java)
• [input] char number

  A character representing a correct one-digit number in the new numeral system.

  Guaranteed constraints:
  'A' ≤ number ≤ 'Z'.

• [output] array.string
  • An array of strings in the format "letter1 + letter2", where "letter1" and "letter2" are correct one-digit numbers in the new numeral system. The strings should be sorted by "letter1".

  Note that "letter1 + letter2" and "letter2 + letter1" are equal pairs and we don’t consider them to be different.

 

String[] newNumeralSystem(char number) {
char[] alpha = {'A','B','C','D','E','F','G','H','I','J','K','L',
'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};


int start = 0, end = 0;
for(int i = 0; i<26; i++){
if(number == alpha[i]){
end = i;
break;
}
}

ArrayList<String> list = new ArrayList<String>();

while(start <= end){
String str = String.valueOf(alpha[start]) + " + "+ String.valueOf(alpha[end]);
list.add(str);
start++;
end--;
}

return list.toArray(new String[list.size()]);
}

firstDuplicate [CodeSignal]

Given an array that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

For a = [2, 1, 3, 5, 3, 2], the output should be
firstDuplicate(a) = 3.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For a = [2, 4, 3, 5, 1], the output should be
firstDuplicate(a) = -1.

Input/Output

[execution time limit] 3 seconds (java)

[input] array.integer a

Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.

[output] integer

The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

 

1 2 3 4 5 6 7 8 9 10 11 12

int firstDuplicate(int[] a) { HashSet hs = new HashSet(); for(int n:a){ if(hs.contains(n)) return n; else hs.add(n); } return -1; }

 

Sort by Height [CodeFights]

Some people are standing in a row in a park. There are trees between them which cannot be moved. Your task is to rearrange the people by their heights in a non-descending order without moving the trees. People can be very tall!

Example

For a = [-1, 150, 190, 170, -1, -1, 160, 180], the output should be
sortByHeight(a) = [-1, 150, 160, 170, -1, -1, 180, 190].

Input/Output

• [execution time limit] 3 seconds (java)
• [input] array.integer a

  If a[i] = -1, then the ith position is occupied by a tree. Otherwise a[i] is the height of a person standing in the ithposition.

  Guaranteed constraints:
  1 ≤ a.length ≤ 1000,
  -1 ≤ a[i] ≤ 1000.

• [output] array.integer
  • Sorted array a with all the trees untouched.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int[] sortByHeight(int[] a) { int[] temp = a.clone(); Arrays.sort(a); List<Integer> list = new ArrayList<Integer>(); for(int n: a){ if(n != -1) list.add(n); } for(int i = 0, j=0; i<temp.length; i++){ if(temp[i] != -1){ temp[i] = list.get(j); j++; } } return temp; }

isLucky [Codefights]

Ticket numbers usually consist of an even number of digits. A ticket number is considered lucky if the sum of the first half of the digits is equal to the sum of the second half.

Given a ticket number n, determine if it’s lucky or not.

Example

• For n = 1230, the output should be
  isLucky(n) = true;
• For n = 239017, the output should be
  isLucky(n) = false.

Input/Output

• [execution time limit] 3 seconds (java)
• [input] integer nA ticket number represented as a positive integer with an even number of digits.

  Guaranteed constraints:
  10 ≤ n < 106.

• [output] boolean
  • true if n is a lucky ticket number, false otherwise.

 

1 2 3 4 5 6 7 8 9 10 11

boolean isLucky(int n) { String tempStr = Integer.toString(n); char[] charArray = tempStr.toCharArray(); int len = charArray.length; int firstHalf = 0, secondHalf = 0; for(int i = 0, j=len-1; i<j; i++,j-- ){ firstHalf += Character.getNumericValue(charArray[i]); secondHalf +=Character.getNumericValue(charArray[j]); } return firstHalf == secondHalf; }

commonCharacterCount [Codefights]

Given two strings, find the number of common characters between them.

Example

For s1 = "aabcc" and s2 = "adcaa", the output should be
commonCharacterCount(s1, s2) = 3.

Strings have 3 common characters – 2 “a”s and 1 “c”.

Input/Output

• [execution time limit] 3 seconds (java)
• [input] string s1A string consisting of lowercase English letters.

  Guaranteed constraints:
  1 ≤ s1.length ≤ 15.

• [input] string s2A string consisting of lowercase English letters.

  Guaranteed constraints:
  1 ≤ s2.length ≤ 15.

• [output] integer

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int commonCharacterCount(String s1, String s2) { int len = s1.length(), sol = 0; char[] arr = s1.toCharArray(); for(int i = 0; i<len; i++){ int pos = s2.indexOf(arr[i]); if(pos != -1){ s2 = s2.substring(0,pos) + s2.substring(pos+1); sol++; } } return sol; }

All Longest String [Codefights]

Given an array of strings, return another array containing all of its longest strings.

Example

For inputArray = ["aba", "aa", "ad", "vcd", "aba"], the output should be
allLongestStrings(inputArray) = ["aba", "vcd", "aba"].

Input/Output

• [execution time limit] 3 seconds (java)
• [input] array.string inputArray

  A non-empty array.

  Guaranteed constraints:
  1 ≤ inputArray.length ≤ 10,
  1 ≤ inputArray[i].length ≤ 10.

• [output] array.string
  • Array of the longest strings, stored in the same order as in the inputArray.

 

String[] allLongestStrings(String[] inputArray) {
List<String> list = new ArrayList<String>();
int max = 0;
for(String s: inputArray){
int temp = s.length();
if(max<temp)
max = temp;
}
for(String s: inputArray){
if(s.length() == max)
list.add(s);
}
return list.toArray(new String[list.size()]);

}