Sab labs programming question
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
Explanation:
An efficient solution would be to devise a custom hashing scheme, which has count of even and odd position occurrence of each alphabet character
All input string is hashed using the custom hash function.
Two Strings will be considered equal if their hash is same, otherwise they would be different
Maintain a hash set
Now the problem can be solved by
1. Hashing all input string
2. Check if hash set contains the hash generated for string
2.1 if no, increment count of distinct and add the custom hash string to hash set
2.2 if yes, ignore the string
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
/*
! Asked in SAP Labs, Priceline, Booking.com
You have developed an e-commerce website,SHOPPY.Many people have created accounts at your website.you have the passwords of all the users.you want to know how many distinct password =s are there in total.Details of the passwords are as described:
Each password is a string of characters from a to z
Two passwords, say pass1 and pass2 are said to be same if pass2 can be obtained by swapping the ith character in pass1 where (i+j)%2=0
Input:
input1:N,number of users registered input2[]:Array of strings containing all passwords of the N users.
Output: return T total number of distinct password present
Example: input:2,{abcd,cdab}
output: 1
input:2,{abcd,bcad}
output: 2
*/
public class DistinctPasswd
{
private static final int LOWER_ALPHABET_COUNT = 26;
private static String customHash(String str) {
int[] hashEven = new int[LOWER_ALPHABET_COUNT];
int[] hashOdd = new int[LOWER_ALPHABET_COUNT];
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if((i+1)%2 != 0) {
hashOdd[c-'a']++;
}
else {
hashEven[c-'a']++;
}
}
StringBuilder hashOfInput = new StringBuilder();
for(int i = 0; i < LOWER_ALPHABET_COUNT; i++) {
hashOfInput.append(hashEven[i]).append("#").append(hashOdd[i]).append("|");
}
return hashOfInput.toString();
}
static int countDistinct(String[] input, int n) {
int countOfDistinct = 0;
Set<String> uniqueHashes = new HashSet<>();
for(int i = 0; i < n; i++) {
String hash = customHash(input[i]);
System.out.println("String: " +input[i] + " hash: " +hash) ;
if(!uniqueHashes.contains(hash)) {
uniqueHashes.add(hash);
countOfDistinct++;
}
}
return countOfDistinct;
}
public static void main( String[] args ) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
input[i] = br.readLine();
}
System.out.println(countDistinct(input, input.length));
}
}
I'm not understanding the solution can someone pls explain
- ABhi June 06, 2022