EMC Interview Question
Software Engineer in TestsTeam: RSA
Country: India
Interview Type: Written Test
public static void test() {
char[] a = new char[] { 'a', 'a', 'b', 'q', 'b' };
LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<Character, Integer>();
for (int i = 0; i < a.length; i++) {
Character c = a[i];
int n = 0;
if (lhm.containsKey(c)) {
n = lhm.get(a[i]);
}
lhm.put(a[i], n + 1);
}
for (Entry<Character, Integer> e : lhm.entrySet()) {
if ((Integer) e.getValue() == 1) {
System.out.println(e.getKey());
break;
}
}
}
Considering the solution for small case characters only:
Another solution to this would be:
1) create an array A of dimension 2*26.
2) create another array B of dimension 26 and initialize by -1;
traverse through the given array of characters and for each encounter of a character x check in B's index x - 'a' if the value v is not -1. Check A[v] and increase it by 1.
Traverse through A and the first 1 in the value will be the first unique character.
public static void findUnique(char[] a) {
int[] A = new int[26];
int[] B = new int[26];
int elementsInA = 0;
int index = 0;
for (int i = 0; i < 26; i++)
B[i] = -1;
for (int i = 0; i < a.length; i++) {
index = B[a[i] - 'a'];
if (index != -1) {
A[index] += 1;
} else {
B[a[i] - 'a'] = elementsInA++;
A[B[a[i] - 'a']] = 1;
}
}
int foundAt = -1;
for(int i = 0 ; i < A.length ; i++){
if(A[i] == 1){
foundAt = i;
break;
}
}
if(foundAt == -1)
System.out.println("No unique");
else{
for(int i = 0 ; i < B.length ; i++){
if(B[i] == foundAt){
System.out.println((char)(i+'a'));
break;
}
}
}
}
int a[26],min,elt;
for(i=0;i<26;i++)
a[i]=-1;
for(i=0;i<n;i++){
if(a[InputArray[i]]==-1)
a[InputArray[i]]=i;
else
a[InputArray[i]]=-2;
}
for(i=0;i<26;i++)
if(a[i]<min && i!=-1 && i!=-2){
min=a[i];
elt=i;
}
print the elt th letter
This is great. But I notice that in this solution, we assume there should be only lower case char in the list and make it possible to solve this problem in O(n). If we don't know the char set of the list, can we solve it still in O(n)?
How about sorting the given array using radix sort (length of each input element is just 1, so it just takes O(n) time). And then walk through the array and return the first unique element?
a) the worst case scenario for any sorting technique is atleast nlogn
b) why would u sort messing up the initial configuration?the result may not be correct
The worst case scenario for any sorting algo is not nlogn. See this page wikipedia/Radix_sort about Radix sort and you will know what my suggested solution
givn progrm will run in o(n) time
#include<stdio.h>
main()
{
int i,p=0,k;
char s[50];
printf("enter the string");
gets(s);
k=strlen(s);
for(i=0;i<k;i++)
{
if(s[p]==s[i])
{
if(p!=i)
{i=-1;p++;}
}
else
{
if(i==(k-1))
{
printf("first unique element is %c at index %d",s[p],p);
break;
}
}
}
}
import java.util.*;
public class Unique {
static public void main(String[] args){
char[] A ={'a','a', 'u', 'b'};
System.out.println("First unique element is "+findUniqueFirstCharFromArray(A));
}
public static char findUniqueFirstCharFromArray(char[] a){
char uniqueChar=0;
HashMap<Character,Boolean> intMap = new HashMap<Character, Boolean>();
for(int i=0;i<a.length;i++){
if(intMap.containsKey(a[i]) ){
intMap.put(a[i], true);
}
else {
intMap.put(a[i], false);
}
}
for(int i=0;i<intMap.size();i++)
if(intMap.get(a[i])==false){
uniqueChar=a[i];
break;
}
return uniqueChar;
}
}
import java.util.*;
public class Unique {
static public void main(String[] args){
char[] A ={'a','a', 'u', 'b'};
System.out.println("First unique element is "+findUniqueFirstCharFromArray(A));
}
public static char findUniqueFirstCharFromArray(char[] a){
char uniqueChar=0;
HashMap<Character,Boolean> intMap = new HashMap<Character, Boolean>();
for(int i=0;i<a.length;i++){
if(intMap.containsKey(a[i]) ){
intMap.put(a[i], true);
}
else {
intMap.put(a[i], false);
}
}
for(int i = 0; i < a.length; i++) {
if(intMap.get(a[i]) == false) {
uniqueChar = a[i];
break;
}
return uniqueChar;
}
}
Here is bit wise solution : O(1) space complexity
private static char firstUnique(char[] a) {
int result = 0;
int location = a[0] - 'a' + 1;
int j = 1 << location;
result = result | j;
for (int i = 1; i < a.length ; i++) {
location = a[i] - 'a' + 1;
j = 1 << location;
if((result & j) == 0)
return a[i];
result = result | j;
}
return '\0';
}
Parse the array in forward order and maintain an ArrayList that contains the characters that you have already parsed.
for each character in the array that is not present in the already parsed arrayList, traverse the complete array and stop traversing as soon as you get a duplicate.
When for a character you traverse the complete list but dont get a duplicate - is the first unique character in the array
public static void getUniqueElement(){
LinkedHashMap<Character, Integer> uniqueFinder = new LinkedHashMap<Character, Integer>();
char[] input = {'a','a','u','b','u', 'b', 'd'};
boolean flag = true;
for (Character entry : input){
if(uniqueFinder.containsKey(entry))
uniqueFinder.put(entry , uniqueFinder.get(entry)+1);
else
uniqueFinder.put(entry , 1);
}
for(Character entry : uniqueFinder.keySet()){
if( uniqueFinder.get(entry) == 1 ){
System.out.println("First unique element is " + entry);
flag = false;
break;
}
}
if(flag)
System.out.println("There are no unique elements ");
}
private static char firstUnique(char[] elements)
{
for (int i = 0; i < elements.Length; i++)
{
bool isUnique = true;//assume this char is unique before compare
for (int j = 0; j < elements.Length; j++)
{
if (i == j)
continue;//continue when compare with itself
else if (elements[i].Equals(elements[j]))
{
//this one is not unique,compare next one
isUnique = false;
break;
}
}
if (isUnique == true)
{
return elements[i];
}
else
{
continue;
}
}
return char.MinValue;//not found
}
public static char findU(char[] a)
{
char u = ' ';
for (int i = 0; i < a.Length;i++ )
{
for(int j=i;j<a.Length-i;j++)
{
if(a[i]!=a[j])
{
u = a[j];
return u;
}
}
}
if (u == ' ')
{
Console.WriteLine("No unique element");
return ' ';
}
else
return u;
}
static void Main(string[] args)
{
char[] arr = { 'a', 'a', 'a', 'a' };
Console.WriteLine(findU(arr));
Console.ReadLine();
}
public static char findU(char[] a)
{
char u = ' ';
for (int i = 0; i < a.Length;i++ )
{
for(int j=i;j<a.Length-i;j++)
{
if(a[i]!=a[j])
{
u = a[j];
return u;
}
}
}
if (u == ' ')
{
Console.WriteLine("No unique element");
return ' ';
}
else
return u;
}
static void Main(string[] args)
{
char[] arr = { 'a', 'a', 'a', 'a' };
Console.WriteLine(findU(arr));
Console.ReadLine();
}
public class UniqueArray {
public static void main(String[] args) {
char[] c = { 'a', 'a', 'x', 'a', 'e', 'f', 'g' };
for (int i = 0; i < c.length; i++) {
int count = 0;
for (int j = 0; j < c.length; j++) {
if (i != j) {
if ((c[i] == c[j]))
count++;
}
}
if (count == 0) {
System.out.println("The first unique char is :" + c[i]);
System.exit(0);
}
else
{
System.out.println(c[i]+" is a duplicate.");
}
}
}
}
List<String> listUnique = new LinkedList<String>();
for (String s : args)
{
if (listUnique.contains(s)) {
listUnique.remove(s);
continue;
}
listUnique.add(s);
}
String firstUnique = (listUnique.size() > 0) ? listUnique.get(0) : null;
System.out.println("First unique element is " + firstUnique);
If the given input string contains only lower case and alpha symbols, then below is the straightforward implementation:
- ashot madatyan June 03, 2012