Question

Microsoft | Codility | 3rd July 2022 | India | OA Coding Questions and Solutions | Set - 67

Answer 1

Hi Folks,

 

I appeared for Micorsoft OA recently, and I got following question :

 

1. Given four digits, find all the valid times that can be formed on a 24 hr clock. Earliest time 00:00 and latest time is 23:59.
   Example : Input: [2, 3, 3, 2] Output: 3
   Explanation: these valid times will be formed with this input : {22:33, 23:23, 23:32} so answer will be 3.

 

I couldn't think much around it in that tight timeline and gave a naive approach
But it passed all test cases as the question required only correctness and not performance.

 

Please do suggest better approach or solution to the same inorder to improve performance too.

 

My Solution :

 

#include <bits/stdc++.h>
using namespace std;

set<int> st;

void combinationsUtil(string str, int l, int r){
    if(l==r) st.insert(stoi(str));
    else{
        for(int i=l;i<=r;i++){
            swap(str[l],str[i]);
            combinationsUtil(str,l+1,r);
            swap(str[l],str[i]);
        }
    }
}

int solution(int A, int B, int C, int D) {
    unordered_map<int,int> map;
    for(int i=0;i<60;i++) map[i]=1;
    for(int i=0;i<60;i++) map[100 + i]=1;
    for(int i=0;i<60;i++) map[200 + i]=1;
    for(int i=0;i<60;i++) map[300 + i]=1;
    for(int i=0;i<60;i++) map[400 + i]=1;
    for(int i=0;i<60;i++) map[500 + i]=1;
    for(int i=0;i<60;i++) map[600 + i]=1;
    for(int i=0;i<60;i++) map[700 + i]=1;
    for(int i=0;i<60;i++) map[800 + i]=1;
    for(int i=0;i<60;i++) map[900 + i]=1;
    for(int i=0;i<60;i++) map[1000 + i]=1;
    for(int i=0;i<60;i++) map[1100 + i]=1;
    for(int i=0;i<60;i++) map[1200 + i]=1;
    for(int i=0;i<60;i++) map[1300 + i]=1;
    for(int i=0;i<60;i++) map[1400 + i]=1;
    for(int i=0;i<60;i++) map[1500 + i]=1;
    for(int i=0;i<60;i++) map[1600 + i]=1;
    for(int i=0;i<60;i++) map[1700 + i]=1;
    for(int i=0;i<60;i++) map[1800 + i]=1;
    for(int i=0;i<60;i++) map[1900 + i]=1;
    for(int i=0;i<60;i++) map[2000 + i]=1;
    for(int i=0;i<60;i++) map[2100 + i]=1;
    for(int i=0;i<60;i++) map[2200 + i]=1;
    for(int i=0;i<60;i++) map[2300 + i]=1;
    
    string str = to_string(A)+to_string(B)+to_string(C)+to_string(D);
    combinationsUtil(str,0,3);

    int count=0;
    set<int>::iterator itr;
    for(itr=st.begin();itr!=st.end();itr++){
        if(map.find(*itr)!=map.end()) count++;
    }
    return count;
}

 

Thanks in advance!

Answer 2

public class Time {
public int getTimeCounts(int[] a) {
int n = a.length;
if (n>4 || n < 0) return -1;
int count = 0;
for (int i =0 ;i<n;i++) {
for (int j=0;j != i && j<n;j++) {
for (int k=0;k != i && k != j && k<n;k++) {
for (int l=0;l!=i && l!=j && l!=k && l<n;l++) {
if (validHour(a[i], a[j]) && validMin(a[k], a[l])) count++
}
}
}
}

 

	return count;
}

public boolean validMin(int b, int c) {
	Integer min = Integer.parseInt(""+b+c);
	return min >= 0 && min < 60 ? true : false;
}

public boolean validHour(int b, int c) {
	Integer min = Integer.parseInt(""+b+c);
	return min >= 0 && min < 24 ? true : false;
}

 

}

Answer 3

Time Complexity : O(1), since we are sorting fixed size array of 4 elements and there are a fixed 4! = 24 permutations possible for the time array. The checks for valid minute and hour are also constant time.

 

// Given four digits, find all the valid times that can be formed on a 24 hr clock. Earliest time 00:00 and latest time is 23:59.
// Example : Input: [2, 3, 3, 2] Output: 3
// Explanation: these valid times will be formed with this input : {22:33, 23:23, 23:32} so answer will be 3.

#include<bits/stdc++.h>

using namespace std;

bool isvalidminute(int a, int b){
    int x = 10*a+b;
    if(x>=0 and x<60) return 1;
    return 0;
}

bool isvalidhour(int a, int b){
    int x = 10*a+b;
    if(x>=0 and x<24) return 1;
    return 0;
}

int solution(int A, int B, int C, int D){
    vector<int> time;
    int count=0;
    time.push_back(A);
    time.push_back(B);
    time.push_back(C);
    time.push_back(D);
    sort(time.begin(),time.end());
    
    do{
        if(isvalidminute(time[2],time[3]) and isvalidhour(time[0],time[1])){
            count++;
            cout<<time[0]<<" "<<time[1]<<" "<<time[2]<<" "<<time[3]<<endl;
        }
    }
    while(next_permutation(time.begin(),time.end()));
    return count;
}

int main() { 
    cout<<solution(2,3,3,2)<<endl;
    return 0;
}