## Sab labs programming question

Comment hidden because of low score. Click to expand.
1
of 1 vote

I'm not understanding the solution can someone pls explain

Comment hidden because of low score. Click to expand.
0
of 0 vote

``{``

}}

Comment hidden because of low score. Click to expand.
0

import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.BufferedReader;
import java.io.IOException;
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
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)) {
countOfDistinct++;
}
}
return countOfDistinct;
}

public static void main( String[] args ) throws IOException
{
int n = Integer.parseInt(br.readLine());
String[] input = new String[n];
for(int i = 0; i < n; i++) {
}
System.out.println(countDistinct(input, input.length));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution

Comment hidden because of low score. Click to expand.
0
of 0 vote

Amazing solution

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.