Microsoft Interview Question
Software Engineer / Developersimport java.io.*;
public class uniqueChar
{
boolean checkUniqueChar(String strin)
{
int m;
char []str=strin.toCharArray();
java.util.Arrays.sort(str);
for(int i=0;i<str.length-1;i++)
{
if(str[i]==str[i+1])
return false;
}
return true;
}
public static void main(String argv[]) throws IOException
{
String str;
System.out.println("enter the string\n");
InputStreamReader in=new InputStreamReader(System.in);
BufferedReader bin=new BufferedReader(in);
str=bin.readLine();
System.out.println(new uniqueChar().checkUniqueChar(str));
//return 0;
}
}
Assuming you don't know the character-set beforehand...
There's a trade-off between using a HashSet and a HashTable.
HashTable:
Need to check if integer is already 1.
HashSet:
Need to check if node already exists by letting the data structure traverse, typically, a BST. Seems cleaner than using a hashtable but slower lookup. Seems more OO.
A simple solutions using strchr and memset-
#include<stdio.h>
int main()
{
char str[' '], *ptr, ch;
int i=0, j;
printf("\nEnter a string: ");
scanf("%s",str);
while(str[i] != '\0')
{
ch = str[i];
ptr = strchr(str, ch);
memset(ptr, '0', sizeof(char));
// Look again if another instance of the char exists
ptr = strchr(str, ch);
if(ptr == NULL)
{
i++;
continue;
}
else
{
printf("\nString contains duplicate character (%c)!\n",c
h);
return;
}
}
printf("\nString contains unique elements\n\n");
}
A simple solutions using strchr and memset-
#include<stdio.h>
int main()
{
char str[' '], *ptr, ch;
int i=0, j;
printf("\nEnter a string: ");
scanf("%s",str);
while(str[i] != '\0')
{
ch = str[i];
ptr = strchr(str, ch);
memset(ptr, '0', sizeof(char));
// Look again if another instance of the char exists
ptr = strchr(str, ch);
if(ptr == NULL)
{
i++;
continue;
}
else
{
printf("\nString contains duplicate character (%c)!\n",c
h);
return;
}
}
printf("\nString contains unique elements\n\n");
}
Actually, quicksort is nlogn on avg, so it could be O(n^2)...
If storage isn't a concern, use dynamic programming to get a 0.5*c*n running time. Associate array or hashset will do. Search the string from the front and back using one iterator. Store each unique character. During search, do a lookup. Hence, the running time is O(n).
to make this in o(n) times you can use extra memory space.
Use the following approach:
take an extra array of 26 chars.
parse the string from left to right.
if it encounters
[a]; increment a[1]+1;
[b]; do a[2]+1;
.
.
..
.
.
[z]; do a[z]+1
if this new array contains 2 in any field. there is duplication.
Associate a prime number with each unique character
Find the product of all the prime numbers associated with the string.
Then for uniqueness divide the product by square of each of the prime numbers .
If it leads to zero remainder then there is repeatition of the character
Very cool answer. It's much more creative than those hash table or hash set. it's easier and cool. But the problem is, if the universe is really big. can you generate enough prime numbers?
No the Solution is fine as there are just 26 alphabets and you can have associated 26 prime numbers(which is not big). so its fine..
We can use STL bitset<N> for this purpose. where N is equal to 255 (if we have ascii) & 52 (if we have only alphabets. <br>
Here every bit will act like a boolean (true/false) for single character. Initially we will reset all bits. If we found 'a' in the string, we will set the bit equivalent its ascii value. If this char repeats again, we can identify it just be checking the corresponding bit in bitset.
Regards
Few comments on the disscusions so far:
1>Associating prime numbers is not a good idea 'coz finding huge set of prime numbers itself is a big task in term of runtime and memory offcourse.
2> If we dont have any extra memory then quick sort or any good in house sort will be a good idea with run time - bestcase(nLogn) and worstcase (n*n)
3>If extra memory if available, then using hashtable (or hashset based on language specific implementation) will be better choice than array of size 2^16. 'Coz array needs 2^16 memory anyway where as Hashtable-memory will grow as we process the string. If 2nd and 3rd characters are duplicate , hashtable uses only 2 memory spaces to discover it compared to array's huge fixed size of 2^16. Runtime of both is O(n)
4> Finally "hitesh1407"'s solution of using bits to indicate if a char is present in the string is a very good idea given the chances of the input string having duplicate is very less.
So if we know the input string is very prone to have duplicates - hashtable is a better choice, otherwise option <4> may turn out a good choice.
I feel that a bit vector representation would be the most efficient in terms of memory. Depending on the character set, use appropriate number of bits and as you read char by char, set the bits accordingly if it is not already set, in which case, the string doesn't contain unique characters.
void uniChar(char *uni){
char temp[256] /// 2^16 if you want even for uni-code characters else 2^8 is enough
for(int i=0;i<256;i++)
temp[i]=0;
i=0;
while(uni[i]){
if(temp[uni[1])==1)
return false;
else
temp[uni[i]]=temp[uni[i]]+1;
i++;
}
return true;
}
void uniChar(char *uni){
Hashtable h=new Hastable();
char c;
int i=0;
while(uni[i]){
int temp=h.get(uni[i]);
if(!temp)
h.put(uni[i],1);
else if(temp ==1)
return false;
}
return true;
}
I'm assuming only one thing: The string is only with ASCII or UNICODE. No mixing.
This is not the most efficient algorithm, but:
Start building BST using the integer representation of the characters. In the process of building if you find a node with the same value this is duplication. This way I don't need to separate stack memory for all possible characters from any table. I can finish in the 5th iteration. In the worst case scenario I will have a tree that will contain all the allowed characters.
Thanks
Here is a solution using bitvector (borrowed from k2code.blogspot.in/2014/03/determine-if-string-has-all-unique.html) :
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
import java.util.*;
public class HashTables {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner n =new Scanner(System.in);
String s = n.nextLine();
Hashtable<Character,Integer> hs=new Hashtable<Character,Integer>();
Enumeration repeat;
int flag=0;
int p=0;
for(int i=0;i<s.length();i++)
{
for(int j=i+1;j<s.length();j++)
{
if(s.charAt(i) == s.charAt(j))
{
if(hs.isEmpty())
{
hs.put(s.charAt(i),p);
p++;
}
else
{
repeat = hs.keys();
while(repeat.hasMoreElements())
{
if(s.charAt(i) != (char)repeat.nextElement())
{
flag = 1;
}
else
{
flag = 0;
}
}
if(flag == 1)
{
hs.put(s.charAt(i), p);
p++;
}
}
}
}
}
System.out.println(hs);
n.close();
}
}
use hashing. if a character is already present in the hash table, return false.
- lancer February 16, 2006