Morgan Stanley Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
#define ALPH_SIZE 26 //or use a real hash for other encodings
bool hash[ALPH_SIZE] = {0};
char min='z', char max='a', c;
if(s.length == 0) return; //or whatever
for(int i=0; i < s.length ; i++)
{
c=tolower(s[i]);
if(c < min) min=c;
if(c > max) max = c;
hash[c]=true;
}
for(c=min; c<=max; c++)
if(!hash[c]) println( ... yada yada .... ), break;
I like the idea, but if you index into an array of bools using a char, it's going to convert the char to an integer to get the index, isn't it? And that's an array bounds write if the array only has 26 elements, because 'a' != 0.
You could make ALPH_SIZE = 128 and I think it would work, with some unused array space, although the container used is so lightweight I can't imagine it matters. The best solution though presumably would be to subtract 'a' from the character c to get an integer to use as the correct array index.
You can also return early if s.length == 1, as there cannot be a missing character (there's no range).
public static void main(String[] aStrings){
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the String");
String input = scanner.next();
input = input.substring(0).toLowerCase();
char[] s = input.toCharArray();
Arrays.sort(s);
String sortedInputString = new String(s);
int len = sortedInputString.length()-1;
char fAlpha = sortedInputString.charAt(0);
int f = (int)fAlpha;
int found = 0,hcount = 1;
for (int lcount=0 ; lcount < len && found == 0 ; lcount++,hcount++) {
if(((int)sortedInputString.charAt(hcount) - (int)sortedInputString.charAt(lcount)) > 1)
found = 1;
if(((int)sortedInputString.charAt(hcount) - (int)sortedInputString.charAt(lcount) != 0))
f++;
}
if(found == 0)
System.out.println("NONE");
else{
char missingAlpha = (char)f;
String missing = ""+ missingAlpha;
System.out.println(missing + " is the missing character .");
}
}
Very rough outline with very rough pseudo-pseudo-code.
Capital letters A~Z have int values of 65 to 90.
Small letters a~z have int values of 97 to 122.
We can go through the string, convert cap to small as needed, and also update the max/min seen in the string at each character. Once we have gone through the string, scan from min/max for the missing value.
for each character c in the string
{
if the int value of c is less than 91
{
push c+32 to vector;
}
else
{
push c to vector
}
update min/max as needed
}
scan through the vector from min to max, the numbers should be consecutive except for the missing number
public static void main(String args[]) {
String inputString = "AbdefghijkmnopqrstuvwxlZ";
char[] newArray = inputString.toUpperCase().toCharArray();
int prevChar = 0, currentChar = 0, nextChar = 0, k = 0;
Arrays.sort(newArray);
for (int i = 0; i < newArray.length; i++) {
prevChar = (i != 0) ? newArray[i - 1] : 0;
currentChar = newArray[i];
nextChar = (i != newArray.length) ? newArray[i + 1] : 0;
char missingCharLower = ((prevChar != 0) && ((prevChar - currentChar) == -2)) ? (char) (currentChar - 1) :
'!';
char missingCharUpper = ((nextChar != 0) && ((nextChar - currentChar) == 2)) ? (char) (currentChar + 1) :
'!';
char finalMissing = (missingCharLower != '!') ? missingCharLower : (missingCharUpper != '!') ?
missingCharUpper : '#';
if (finalMissing != '#') {
System.out.println("Missing Character is:" + finalMissing);
break;
}
}
String s1 = "baADfc";
String s2 = s1.toUpperCase();
Set<Character> charList = new TreeSet<Character>();
for (int i = 0; i < s2.length(); i++) {
charList.add(s2.charAt(i));
}
String sortedString =charList.toString();
for(int i=0;i<sortedString.length()-1 ;i++)
{
if((int)sortedString.charAt(i+1)-(int)sortedString.charAt(i)>1)
{
System.out.println("missing character:::::::"+(char)((int)sortedString.charAt(i)+1));
break;
}
}
}
String s1 = "baADfc";
String s2 = s1.toUpperCase();
Set<Character> charList = new TreeSet<Character>();
for (int i = 0; i < s2.length(); i++) {
charList.add(s2.charAt(i));
}
String sortedString =charList.toString();
for(int i=0;i<sortedString.length()-1 ;i++)
{
if((int)sortedString.charAt(i+1)-(int)sortedString.charAt(i)>1)
{
System.out.println("missing character:::::::"+(char)((int)sortedString.charAt(i)+1));
break;
}
}
}
import java.util.Scanner;
import java.util.Arrays;
class MissingString
{
public static void main(String[] args)
{
String s;
Scanner x=new Scanner(System.in);
System.out.println("enter the string");
s=x.nextLine();
char c[]=s.toLowerCase().toCharArray();
Arrays.sort(c);
int t=0;
for(int i=1;i<=c.length-1;i++)
{
t=(int)c[i]-(int)c[i-1];
int l=(int)c[i]-1;
while(t>1)
{
System.out.println((char)l--);
t--;
}
}
}
}
package com.javafries.string;
import java.util.Arrays;
/**
* @author vishal
*
*/
public class MissingCharFinder {
/**
* @param args
*/
public static void main(String[] args) {
String str = "AHfB";
System.out.println("String : " + str);
findMissingChar(str);
}
/**
* Finds the missing characters.
*
* @param str , not null
*/
private static void findMissingChar(String str) {
// Convert to upper case
str = str.toUpperCase();
// Get character array of string.
char[] charArray = str.toCharArray();
//Sort the character array.
Arrays.sort(charArray);
printRange(charArray);
System.out.println("Missing characters");
// Iterate over character array.
for (int i = 0; i < charArray.length -1; i++) {
// Find the difference between current char and next char.
int charDiff = charArray[i+1] - charArray[i];
if (charDiff > 1) {
for(int j=1 ; j < charDiff; j++) {
char c = (char) (charArray[i] + j);
System.out.print(c + " ");
}
}
}
}
/**
* Prints range of sorted character array.
*
* @param charArray , not null
*/
private static void printRange(final char[] charArray) {
StringBuilder builder = new StringBuilder(30);
builder.append("Range is from '").append(charArray[0]).append("' to '").append(charArray[charArray.length -1]).append("'");
System.out.println(builder.toString());
}
}
package com.javafries.string;
import java.util.Arrays;
/**
* @author vishal
* Visit java-fries.com
*/
public class MissingCharFinder {
/**
* @param args
*/
public static void main(String[] args) {
String str = "AHfB";
System.out.println("String : " + str);
findMissingChar(str);
}
/**
* Finds the missing characters.
*
* @param str , not null
*/
private static void findMissingChar(String str) {
// Convert to upper case
str = str.toUpperCase();
// Get character array of string.
char[] charArray = str.toCharArray();
//Sort the character array.
Arrays.sort(charArray);
printRange(charArray);
System.out.println("Missing characters");
// Iterate over character array.
for (int i = 0; i < charArray.length -1; i++) {
// Find the difference between current char and next char.
int charDiff = charArray[i+1] - charArray[i];
if (charDiff > 1) {
for(int j=1 ; j < charDiff; j++) {
char c = (char) (charArray[i] + j);
System.out.print(c + " ");
}
}
}
}
/**
* Prints range of sorted character array.
*
* @param charArray , not null
*/
private static void printRange(final char[] charArray) {
StringBuilder builder = new StringBuilder(30);
builder.append("Range is from '").append(charArray[0]).append("' to '").append(charArray[charArray.length -1]).append("'");
System.out.println(builder.toString());
}
}
public static void solution_2(String one){
char[] arr = one.toLowerCase().toCharArray();
Arrays.sort(arr);
System.out.println(arr);
for (int i = 0; i < arr.length; i++) {
if(i+1<arr.length && Math.abs(arr[i]-arr[i+1])>1){
System.out.println("Missing:"+new Character(++arr[i]));
}
}
}//EOM solution_2
public static void solution_2(String one){
char[] arr = one.toLowerCase().toCharArray();
Arrays.sort(arr);
System.out.println(arr);
for (int i = 0; i < arr.length; i++) {
if(i+1<arr.length && Math.abs(arr[i]-arr[i+1])>1){
System.out.println("Missing:"+new Character(++arr[i]));
}
}
}//EOM solution_2
public class FindMissingCharactersFromaRangeOfString {
static void findMissing(String str) {
char ch[] = str.toCharArray();
Set<Character> ch1 = new TreeSet<Character>();
for (Character a : ch)
ch1.add(Character.toLowerCase(a));
ArrayList<Character> a1 = new ArrayList<Character>(ch1);
//System.out.println(a1);
int p = a1.get(0);
int m = 0;
for (int a : a1) {
if ((p + m) == a) {
// System.out.println((char)a);
}
else
System.out.println("Missed="+(char) (p + m));
m++;
}
// a1.add(a);
// System.out.println(a1);
}
public static void main(String[] args) {
String str = "baADfc";
findMissing(str);
}
}
import java.util.Arrays;
class MissingChar{
public static void main(String[] args)
{
String s="zadbfc";
char[] ch=s.toCharArray();
Arrays.sort(ch);
int len=ch.length;
for(int i=0;i<len;i++)
{
System.out.println(ch[i]);
}
byte b1=(byte)ch[len-1];
byte b2=(byte)ch[0];
System.out.println(b1);
System.out.println(b2);
String s1="";
for(byte i=b2;i<=b1;i++)
{
String a=(char)i+"";
if(s.contains(a))
{}
else
{
s1=s1+a;
}
}
System.out.println("Missing Char "+s1);
}
}
public class FindMissingChar {
public static void main(String[] args) {
// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);
String input = "abdcf";
input = input.substring(0).toLowerCase();
char[] s = input.toCharArray();
Arrays.sort(s);
System.out.println(s);
for(int i=1;i<input.length();i++)
{
if (s[0]!=s[i]-i*1)
{
System.out.println((char)(s[i]-1));
break;
}
}
}
}
public class FindMissingChar {
public static void main(String[] args) {
// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);
String input = "abdcf";
input = input.substring(0).toLowerCase();
char[] s = input.toCharArray();
Arrays.sort(s);
System.out.println(s);
for(int i=1;i<input.length();i++)
{
if (s[0]!=s[i]-i*1)
{
System.out.println((char)(s[i]-1));
break;
}
}
}
}
public class FindMissingChar {
public static void main(String[] args) {
// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);
String input = "abdcf";
input = input.substring(0).toLowerCase();
char[] s = input.toCharArray();
Arrays.sort(s);
System.out.println(s);
for(int i=1;i<input.length();i++)
{
if (s[0]!=s[i]-i*1)
{
System.out.println((char)(s[i]-1));
break;
}
}
}
}
package arrays;
public class OnlyAOnlyBArrayElements {
public static void main(String[] args) {
int[]a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
int[]b={1,3,5,7,9,11,13,15};
int[]temp = new int[128];
for(int i=0;i<a.length;i++){
temp[a[i]]++;
}
for(int i=0;i<b.length;i++){
if(temp[b[i]]==0){
System.out.print(b[i]);
}
}
System.out.println();
temp = new int[128];
for(int i=0;i<b.length;i++){
temp[b[i]]++;
}
for(int i=0;i<a.length;i++){
if(temp[a[i]]==0){
System.out.print(a[i]);
}
}
}
}
import java.util.Arrays;
class MissingCharInString {
public static void main(String[] args) {
String s;
s = "acbfd";
char c[] = s.toLowerCase().toCharArray();
Arrays.sort(c);
int t = 0;
int a = (int) c[0];
for (int i = 0; i <= c.length - 1; i++) {
while ((int) c[i] != a++) {
System.out.println((char) (a - 1));
}
}
}
}
import java.util.Arrays;
class MissingCharInString {
public static void main(String[] args) {
String s;
s = "acbfd";
char c[] = s.toLowerCase().toCharArray();
Arrays.sort(c);
int t = 0;
int a = (int) c[0];
for (int i = 0; i <= c.length - 1; i++) {
while ((int) c[i] != a++) {
System.out.println((char) (a - 1));
}
}
import java.util.Arrays;
class MissingCharInString {
public static void main(String[] args) {
String s;
s = "acbfd";
char c[] = s.toLowerCase().toCharArray();
Arrays.sort(c);
int a = (int) c[0];
for (int i = 0; i <= c.length - 1; i++) {
while ((int) c[i] != a++) {
System.out.println((char) (a - 1));
}
}
}
}
import java.util.Arrays;
class MissingCharInString {
public static void main(String[] args) {
String s;
s = "acbfd";
char c[] = s.toLowerCase().toCharArray();
Arrays.sort(c);
int a = (int) c[0];
for (int i = 0; i <= c.length - 1; i++) {
while ((int) c[i] != a++) {
System.out.println((char) (a - 1));
}
}
}
}
and
import java.util.Arrays;
class MissingCharInString {
public static void main(String[] args) {
String s;
s = "acbfdh";
char c[] = s.toLowerCase().toCharArray();
Arrays.sort(c);
int a = (int) c[0];
for (int i = 0; i <= c.length - 1; i++) {
while ((int) c[i] != a++) {
System.out.println((char) (a - 1));
}
}
}
}
public static void main(String[] args) {
String str= "baADfc".toLowerCase();
int rangeEnd = ((int)'f'%97)+1;
int[] array = new int[rangeEnd];
char[] charArray = str.toCharArray();
for(char c : charArray) {
array[(int)c%97] = 1;
}
for(int i=0; i< array.length; i++) {
if(array[i] == 0)
System.out.println("missing :"+ (char)(i+97));
}
}
public class Main {
public static void main(String[] args) {
String str = "baADfc".toLowerCase();
str.toLowerCase();
int range = 0;
for (char c : str.toCharArray()) {
if ((int) c > range) {
range = (int) c;
}
}
System.out.println((char) range);
String alphabet = "abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i <= range; i++) {
if (alphabet.contains("" + (char) i)) {
if (!str.contains("" + (char) i)) {
System.out.println("Missing Character "+(char) i);
}
}
}
}
}
public class MissingCharInStringRange {
public void missingChar(String str) {
int min = 122, max=97;
str = str.toLowerCase();
int len = str.length();
Map<Integer, Integer> intMap = new HashMap<>();
for (int i = 0; i <len ; i++) {
intMap.put((int)str.charAt(i), 0);
System.out.println(intMap.keySet());
if ((int)str.charAt(i) < min) {
min = (int)str.charAt(i);
}
if ((int)str.charAt(i) > max) {
max = (int)str.charAt(i);
}
}
System.out.println("Max is " + max);
System.out.println("Min is " + min);
System.out.println("Missing characters are");
for (int i = min; i <=max ; i++) {
if (!intMap.containsKey(i)) {
System.out.println((char)i);
}
}
}
public static void main(String []args) {
MissingCharInStringRange m1 = new MissingCharInStringRange();
m1.missingChar("ghfab");
}
}
public class MissingCharInStringRange {
public void missingChar(String str) {
int min = 122, max=97;
str = str.toLowerCase();
int len = str.length();
Map<Integer, Integer> intMap = new HashMap<>();
for (int i = 0; i <len ; i++) {
intMap.put((int)str.charAt(i), 0);
System.out.println(intMap.keySet());
if ((int)str.charAt(i) < min) {
min = (int)str.charAt(i);
}
if ((int)str.charAt(i) > max) {
max = (int)str.charAt(i);
}
}
System.out.println("Max is " + max);
System.out.println("Min is " + min);
System.out.println("Missing characters are");
for (int i = min; i <=max ; i++) {
if (!intMap.containsKey(i)) {
System.out.println((char)i);
}
}
}
public static void main(String []args) {
MissingCharInStringRange m1 = new MissingCharInStringRange();
m1.missingChar("ghfab");
}
}
lets say an array
mark elements like a=1,b=2c=3 etc..
1. Sort the array using any sorting algorithm, lets say insertion sort.
2. subtract consecutive pair of arrays it should not be greater than one
lest say a-b >1 false, b-c >1 false, c-d > 1 false, d-f>1 true!!!.
3. d+1th element is your answer.
- Deepali October 01, 2014