Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
But I am just curious to know how do you track the first unique character? My solution would be:
Take an integer array with size of character set 256. Set of the values to zero.
Scan the string and set the count values of each character.
Scan the string again, and first character with count 1 would be first unique character. This would be a O(n) approach.
But I am just curious to know how do you track the first unique character? My solution would be:
Take an integer array with size of character set 256. Set of the values to zero.
Scan the string and set the count values of each character.
Scan the string again, and first character with count 1 would be first unique character. This would be a O(n) approach.
@KSS Oh sorry! I took the question as "find the first duplicated char".....
@Saam is right!
public static void main(String[] args) {
int[] a = new int[] { 1, 11, 9, 2, 2, 5, 5, 6, 6, 1 };
HashMap<Integer, ArrayList<Integer>> hMap = new HashMap<Integer, ArrayList<Integer>>();
ArrayList<Integer> count = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
if (hMap.containsKey(a[i])) {
hMap.get(a[i]).add(i);
} else {
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(i);
hMap.put(a[i], arr);
}
}
for (int ele : a) {
int v = hMap.get(ele).size();
if (v == 1) {
count.add(ele);
}
}
System.out.println(count.get(0));
}
#include<stdio.h>
#include<string.h>
int num[26]={0};
int index[26]={0};
int main()
{
char *s="abbbccdefafgg ";
int i;
for(i=0;i<strlen(s);i++)
{
num[s[i]-'a']++;
index[s[i]-'a']=i;
}
int min=strlen(s),p=0;
for(i=0;i<26;i++)
if(num[i]==1 && index[i]<min)
{
min=index[i];
p=i;
}
printf("%c/n",p+'a');
return 0;
}
It would be good if tell what's your logic before giving the code. One minor mistake, you have to include "\0" in the string. Otherwise strlen will not work
A hastable linked to min heap.
Build a hashtable with count of each character in the array.
Build a min heap starting with the 1st character as root, whenever the root character's hastable entry count is greater than one remove the root and adjust the min heap.
At the end of string iteration the root has the 1st unique character in the array.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
public class FirstUniqueArrayCharacter {
public static void main(String[] args) {
// Test some strings
test("aa");
test("ab");
test("aab");
test("ababcbad");
}
private static void test(String text) {
char[] array = text.toCharArray();
Character c = findFirstUniqueCharacter(array);
System.out.println("First unique character in '" + text + "' is: '" + c + "'");
}
// Time complexity is O(n), space complexity is O(n)
private static Character findFirstUniqueCharacter(char[] array) {
// Linked hash map stores entries in insertion-order by default
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
for (char c : array) {
Integer count = map.get(c);
if (count == null) {
count = 0;
}
count++;
map.put(c, count);
}
for (Entry<Character, Integer> entry : map.entrySet()) {
boolean unique = entry.getValue() == 1;
if (unique) {
return entry.getKey();
}
}
return null;
}
}
Assume we are only considering lower-case letters.
Complexity: O(n) time; O(1) space
public static char findUniqueChar(String s) {
int tl = 26;
int[] occurrence = new int[tl];
int[] firstIdx = new int[tl];
for (int i = 0; i < tl; i++) {
occurrence[i] = 0;
firstIdx[i] = -1;
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int idx = c - 'a';
occurrence[idx]++;
if (firstIdx[idx] == -1) {
firstIdx[idx] = i;
}
}
int smallestIdx = Integer.MAX_VALUE;
char uniqueChar = 0;
for (int i = 0; i < tl; i++) {
if (occurrence[i] == 1) {
if (firstIdx[i] < smallestIdx) {
smallestIdx = firstIdx[i];
uniqueChar = (char)(i + 'a');
}
}
}
return uniqueChar;
}
using a hash table
- Ragnarok March 08, 2012scan from left to right, if the table doesn't contain current element, put it in; if it does, just return
-----------------------------------------
Sorry I took the question as "find the first duplicated char".....
as what @Saam had said, using a linkedhashMap will reduce the search time of second round
In fact, I think @Saam 's answer is good enough, but if we want to scan once, we can do this. The solution below is really trivial, while we cost much more space.
while we still have the table[256](or hashMap) to count each char's occurrence frequency, We create a linked list T, each node contains the char that is unique, while use a hashtable<char,Node> to translate the value to the node in T instantly.
Then we need only one round, check if the current char never appeared( table[current] == 0 ), add a node to T, and put it into the hashtable, then table[current]++;
if tab[current] > 0, find if the node contains the element exists using the hashtable, remove the node from T.
Then the first element of T would be the answer when first round ends.