EMC Interview Question for Software Engineer in Tests


Team: RSA
Country: India
Interview Type: Written Test




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

If the given input string contains only lower case and alpha symbols, then below is the straightforward implementation:

#include <stdio.h>
void first_unique(char buf[], int cnt)
{
    char syms[26] = {0,};
    int i;
    for (i = 0; i < cnt; ++i){
        syms[buf[i] - 'a']++;
    }
    for (i = 0; i < cnt; ++i){
        if (syms[buf[i] - 'a'] == 1){
            printf("%c at %d\n", buf[i], i);
            return;
        }
    }
}
int main()
{
    int cnt;
    char buf[] = {'a', 'a', 'u', 'b'};
    cnt = sizeof(buf)/sizeof(buf[0]);
    first_unique(buf, cnt);
    return 0;
}

- ashot madatyan June 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

how can you find the 'first' unique one?

- aaronss April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
			}
		}
	}

- dharmendra June 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
				}
			}
		}
	}

- dharmendra June 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Sathya June 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)?

- njuprincerain June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes. make an array of size 128 to cover all charecters

- Anonymous June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- dreamCoder June 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dreamCoder June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bhattpranoti@yahoo.co.in

- Anonymous June 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@dreamcoder
ok even then i dont understand why u wanna sort. by ur method the ans will be 'b'. But the actual ans is 'u'.

- Anonymous June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is hashing : Create array of 26, use ascii value to index the array element, increment the array value once a letter is found. then read the Input array for 2nd time and check if its corresponding value is 1 if yes then thats the first unique element.

- Rishi June 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}

- mohit June 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Evan June 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}
}

- pgmr - correction in the above code June 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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';
	}

- Siva Naresh June 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is not working for a,b,a,u,c,b

- dharmendra June 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int find(char [] ch){
boolean [] flag=new boolean[256];
for (int i=0;i<ch.length;++i){
if (flag[ch[i]]){
return i;
}else{
flag[ch[i]]=true;
}
}

return -1;
}

- Anonymous June 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String ar[]){
String [] arr1 = {"a","a","u","b"};
HashSet<String> hs1 = new HashSet<String>();
for (String y : arr1)
//hs1.add(y);
if(!hs1.add(y))
System.out.println("Found Duplicate " + y);
}
}

- nataraj.mpatil July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Shruti May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think I have used similar solution, however I have used HashMaps with character -key and Integer -Value, the values represent the frequency of each character. Searching and inserting in hash is much faster. Please check the code below.

- Sriram May 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ");
		
	}

- Sriram May 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Build a binary search tree and each node will have a counter which will be incremented if node is already present.
2) after building the binary tree
3) find the nodes which are visited once
4) from those elements we can find the which element is unique

- samana srikanth August 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
        }

- bz0915 August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are we not trying too hard ? What about --
1) Counting sort (since it's been mentioned that the type id char) -O(n)
2) from 1 to n-2 for every element check the prev and the next -- O(n)
3) First element that is neither equal to prev not equal to next is the first unique

- Aditya July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Ruby

# O(n)
def first_unique_element arr
	1.upto(arr.size-1) {|i| return arr[i] if arr[i] != arr[i-1]}
end

- VinceBarresi September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}

- Kumar84 September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

- Kumar84 September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.");
}
}

}

}

- viveksuriyancs93 November 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a = ['a', 'a', 'b', 'q', 'b']

count = {}

for i in a:
if i in count:
count[i] += 1
else:
count[i] = 1

print [k for k, v in count.iteritems() if v == 1]

- Anonymous June 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{a = ['a', 'a', 'b', 'q', 'b']

count = {}

for i in a:
if i in count:
count[i] += 1
else:
count[i] = 1

print [k for k, v in count.iteritems() if v == 1] }}

- Tejas June 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a = ['a', 'a', 'b', 'q', 'b']

count = {}

for i in a:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1

print [k for k, v in count.iteritems() if v == 1]

- Tejas June 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);

- Ashok June 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, this solution prints First unique element is null. I believe it will not work in situations if there are three occurrences of a character.

- dharmendra June 02, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More