Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
Can be implemented with DS - combination of hash map & stack.
1. put data in above DS
2. While putting data in step-1, assign head with new node in HashMap which was inserted in step-1
3. after completing the iteration on the input string & putting all data in above DS using step-1& step-2, start reading data from above DS with stack.pop() operation
Run-time complexity - O(N)
Memory complexity - O(N)
public class StringReverse {
public static void main(String[] args) {
String input = "aabdceaaabbbcd";
reverseWithOneCharacterOnce(input);
}
private static void reverseWithOneCharacterOnce(String input) {
Set<Character> alreadyPrintedCharacter = new HashSet<Character>();
String reversed = "";
for (int index = input.length() - 1; index >= 0; index--) {
Character ch = input.charAt(index);
if (!alreadyPrintedCharacter.contains(ch)) {
alreadyPrintedCharacter.add(ch);
reversed = reversed + ch;
}
}
System.out.println(reversed);
}
}
1. Create data-structure - hybrid of HashMap & Stack. Head = pointing to the top of the stack. Put() - put value in hash map & changes head to point to new value inserted.
2. Start iterating over the input of string
3. After completing the iteration in step-2, start stack.pop(head) & print till stack is empty.
#include <bits/stdc++.h>
#include<queue>
#include<vector>
#define ll long long int
using namespace std;
class Word
{
public:
int index;
char w;
};
bool comp(Word a,Word b)
{
return (a.index > b.index);
}
int main()
{
vector<Word> v1;
unordered_map<char,int> u1;
string str="aabdceaaabbbcd";
for(int i= str.length() - 1;i>=0;i--)
{
Word obj;
obj.index=i;
obj.w=str[i];
if(u1.count(str[i])==0)
{
u1[str[i]]=1;
v1.push_back(obj);
}
}
sort(v1.begin(),v1.end(),comp);
for (int i=0;i<v1.size();i++)
{
cout<<v1[i].w;
}
return 0;
};
#include <bits/stdc++.h>
#include<queue>
#include<vector>
#define ll long long int
using namespace std;
class Word
{
public:
int index;
char w;
};
bool comp(Word a,Word b)
{
return (a.index > b.index);
}
int main()
{
vector<Word> v1;
unordered_map<char,int> u1;
string str="aabdceaaabbbcd";
for(int i= str.length() - 1;i>=0;i--)
{
Word obj;
obj.index=i;
obj.w=str[i];
if(u1.count(str[i])==0)
{
u1[str[i]]=1;
v1.push_back(obj);
}
}
sort(v1.begin(),v1.end(),comp);
for (int i=0;i<v1.size();i++)
{
cout<<v1[i].w;
}
return 0;
};
#include <bits/stdc++.h>
#include<queue>
#include<vector>
#define ll long long int
using namespace std;
class Word
{
public:
int index;
char w;
};
bool comp(Word a,Word b)
{
return (a.index > b.index);
}
int main()
{
vector<Word> v1;
unordered_map<char,int> u1;
string str="aabdceaaabbbcd";
for(int i= str.length() - 1;i>=0;i--)
{
Word obj;
obj.index=i;
obj.w=str[i];
if(u1.count(str[i])==0)
{
u1[str[i]]=1;
v1.push_back(obj);
}
}
sort(v1.begin(),v1.end(),comp);
for (int i=0;i<v1.size();i++)
{
cout<<v1[i].w;
}
return 0;
};
public static String printReversedOnlyOnce(String s) {
if (s == null || s.equals("")) {
return null;
}
StringBuilder sb = new StringBuilder();
char[] c = s.toCharArray();
Map<Character, Boolean> mapChars = new HashMap<>();
for (int i = c.length - 1; i >= 0; i--) {
if (!mapChars.containsKey(c[i])) {
sb.append(c[i]);
mapChars.put(c[i], Boolean.TRUE);
}
}
return sb.toString();
}
/* print all characters present in the given string only once in a revers order*/
import java.io.*;
import java.util.*;
public class SringReverseOnce {
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.print("Enter String input: ");
String in = sc.next();
int n = in.length();
char buf[] = in.toCharArray();
for(int i=n-1;i>=0;i--)
{ int flag;
flag =0;
for(int j=n-1;j>=i;j--)
{
if(buf[i]==buf[j] && j!=i)
{ flag =1;
break;
}
}
if(flag==0)
{System.out.print(buf[i]);}
}
}
}
define boolean array of character set with false value.
if characters ascii value location of character set is false, set it true and print character,
otherwise ignore the character.
/**
* Print String in reverse order but without any duplicate characters
* Assume character set is asci characters 0 - 255
*/
private static boolean printStringRevNoDuplicate(String str){
int setSize = 255;
boolean[] charSet = new boolean[setSize];
for(int index = str.length() - 1; index >= 0; --index){
if(!charSet[str.charAt(index)]){
charSet[str.charAt(index)] = true;
System.out.print(str.charAt(index));
}
}
System.out.println();
return true;
}
def solution(s):
result = []
table = [0] * 256
for x in reversed(s):
if not table[ord(x)]:
result.append(x)
table[ord(x)] += 1
print(result)
# Extra feature: Print the char appears only once in reversed order
print('Print the char shows only once')
reduced = [x for x in result if table[ord(x)] == 1]
print(reduced)
Time complexity: O(n)
private static String reverse(String string) {
StringBuffer s1 = new StringBuffer(string);
s1.reverse();
System.out.println(s1);
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j)) {
s1.deleteCharAt(j);
} else {
continue;
}
}
}
return s1.toString();
}
private static String reverse(String string) {
StringBuffer s1 = new StringBuffer(string);
s1.reverse();
System.out.println(s1);
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j)) {
s1.deleteCharAt(j);
} else {
continue;
}
}
}
return s1.toString();
}
private static String reverse(String string) {
StringBuffer s1 = new StringBuffer(string);
s1.reverse();
System.out.println(s1);
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j)) {
s1.deleteCharAt(j);
} else {
continue;
}
}
}
return s1.toString();
}
private static String reverse(String string) {
StringBuffer s1 = new StringBuffer(string);
s1.reverse();
System.out.println(s1);
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j)) {
s1.deleteCharAt(j);
} else {
continue;
}
}
}
return s1.toString();
}
Here is a C++ implementation
#include <iostream>
#include <unordered_set>
#include <string>
void printReverseUniqueString(std::string inputStr)
{
std::unordered_set<char> uniqueChars;
std::string uniqueString;
for(std::string::iterator i = inputStr.end(); i!= inputStr.begin(); i--)
{
if(uniqueChars.count(*i) == 0)
{
uniqueString.push_back(*i);
uniqueChars.insert(*i);
}
}
std::cout << uniqueString << std::endl;
}
Here is a C++ implementation
#include <iostream>
#include <unordered_set>
#include <string>
void printReverseUniqueString(std::string inputStr)
{
std::unordered_set<char> uniqueChars;
std::string uniqueString;
for(std::string::iterator i = inputStr.end(); i!= inputStr.begin(); i--)
{
if(uniqueChars.count(*i) == 0)
{
uniqueString.push_back(*i);
uniqueChars.insert(*i);
}
}
std::cout << uniqueString << std::endl;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int main(int argc, char **argv)
{
if(argc != 2)
{
printf("usage: %s [test_chars]\n", argv[0]);
return 0;
}
char *test_chars = argv[1];
char temp[256];
memset(temp, 0, sizeof(temp));
for(int i = strlen(test_chars); i >= 0; i--)
{
if(temp[test_chars[i]] == 0)
{
printf("%c", test_chars[i]);
temp[test_chars[i]]++;
}
}
printf("\n");
return 0;
}
public class Solution {
public String removeDuplicateLetters(String s) {
boolean[] validate=new boolean[300];
StringBuilder sb = new StringBuilder();
for(char c:s.toCharArray()){
if(validate[c]){
continue;
}
validate[c]=true;
}
for(int i=299;i>=0;i++){
if(validate[i]){
sb.append((char)i);
}
}
return sb.toString();
}
}
/* We can solve this by using HashMap or HashSet. Hope this is also one of the effective solution */
public class ReverseArrayOnlyOneCharacter {
public static void main(String[] args) {
String str = "aabdceaaabbbcd";
int[] tmparr = new int[str.length()];
for (int i = str.length() - 1; i >= 0; i--) {
int ch = (int) str.charAt(i);
int mod = (((ch - 97) % 26) % (str.length() - 1));
if (tmparr[mod] == ch) {
continue;
} else {
System.out.println((char)ch);
tmparr[mod] = ch;
}
}
}
}
int visited[255];
void print_rev(char *str, int index, int len)
{
if(index < 0)
return;
visited[(str[index])%len] = 1;
printf("%c", str[index]);
index--;
while(visited[(str[index])%len])
{
index = index-1;
}
print_rev(str, index, len);
}
int main()
{
char *str1 = "aabdceaaabbbcd";
int len = strlen(str1);
int i = 0;
for(i = 0; i<len; i++)
visited[i] = 0;
print_rev(str1, len-1, len);
return 0;
}
import java.util.*;
import java.lang.*;
/* Print all the characters present in the given string only once in a reverse order.
* Time and space complexity should not be more than o(N)
*/
/* Test : aabdceaaabbbcd => dcbae */
public class ReverseUniqueString {
public String printReverse(String input) throws Exception {
String msg = null;
List<Character> charPresent = new ArrayList<Character>();
String output = "";
try {
if(null != input) {
for(int i = input.length()-1; i > 0; i--) {
Character c = input.charAt(i);
if(!charPresent.contains(c)) {
charPresent.add(c);
}
}
}
for(Character c : charPresent) {
output = output + c.toString();
}
} catch (Exception e) {
msg = "Error while determining and printing reverse order of character found.";
System.err.println(msg);
throw new Exception(msg,e);
}
return output;
}
}
/*----------------------Tests------------------------------*/
import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
public class ReverseUniqueStringTest {
@Before
public void setUp() throws Exception {
}
@After
public void tearDown() throws Exception {
}
@Test
public void testGeneralScenario() throws Exception {
ReverseUniqueString r = new ReverseUniqueString();
String output = r.printReverse("aabdceaaabbbcd");
Assert.assertEquals(output,"dcbae");
}
@Test
public void testNullString() throws Exception {
ReverseUniqueString r = new ReverseUniqueString();
String output = r.printReverse(null);
Assert.assertEquals(output,"");
}
@Test
public void testAllSame() throws Exception {
ReverseUniqueString r = new ReverseUniqueString();
String output = r.printReverse("aaaaaa");
Assert.assertEquals(output,"a");
}
}
public class Reverse {
public static void main(String[] args) {
String s = "aabdceaaabbbcd";
char[] c = s.toCharArray();
Set<String> mySet = new LinkedHashSet<String>();
for(char c1 : c){
mySet.add(String.valueOf(c1));
}
System.out.println(mySet);
Comparator<String> reverse = Comparator.reverseOrder();
List<String> myList = new ArrayList<String>(mySet);
Collections.sort(myList, reverse);
System.out.println(myList);
}
}
public class Reverse {
public static void main(String[] args) {
String s = "aabdceaaabbbcd";
char[] c = s.toCharArray();
Set<String> mySet = new LinkedHashSet<String>();
for(char c1 : c){
mySet.add(String.valueOf(c1));
}
System.out.println(mySet);
Comparator<String> reverse = Comparator.reverseOrder();
List<String> myList = new ArrayList<String>(mySet);
Collections.sort(myList, reverse);
System.out.println(myList);
}
}
public void reversePrint(String value)
{
value = value.toUpperCase();
int MAX_CHAR_SET=26;
int[] charIndexer = new int[MAX_CHAR_SET];
if(value == null || value.equals("") | value.length()==0)
return;
int charIdx = 0;
for(int idx = value.length() -1 ; idx >= 0; --idx)
{
charIdx = getCharIdx(value.charAt(idx));
if(charIndexer[charIdx] ==0)
{
System.out.print(value.charAt(idx));
++ charIndexer[charIdx];
}
}
}
private int getCharIdx(char c)
{
return ((int)c)-65;
}
#include <stdio.h>
#include <iostream>
#include<string.h>
using namespace std;
int main()
{
char s[10001];
int arr[27];
int t,i,j,k,n;
cin>>t;
while(t--)
{
cin>>s;
n = strlen(s);
for(i = 0;i<27;i++) arr[i] = 0;
for(j=n-1;j>=0;j--)
{
if(!arr[s[j] - 'a'])
{
cout<<s[j];
arr[s[j]-'a'] = 1;
}
}
}
return 0;
}
#include <stdio.h>
#include <iostream>
#include<string.h>
using namespace std;
int main()
{
char s[10001];
int arr[27];
int t,i,j,k,n;
cin>>t;
while(t--)
{
cin>>s;
n = strlen(s);
for(i = 0;i<27;i++) arr[i] = 0;
for(j=n-1;j>=0;j--)
{
if(!arr[s[j] - 'a'])
{
cout<<s[j];
arr[s[j]-'a'] = 1;
}
}
}
return 0;
}
private static void printCharactersInReverseOrder(String iInputString) {
char[] charArray = iInputString.toCharArray();
String alreadyEvaluatedCharacters = "";
for (int i = charArray.length - 1; i >= 0; i--) {
if (!alreadyEvaluatedCharacters.contains(String.valueOf(charArray[i]))) {
alreadyEvaluatedCharacters = alreadyEvaluatedCharacters + charArray[i];
}
}
System.out.println("String in Reverse Order with characters printed only once => " + alreadyEvaluatedCharacters);
}
private static void printCharactersInReverseOrder(String iInputString) {
char[] charArray = iInputString.toCharArray();
String alreadyEvaluatedCharacters = "";
for (int i = charArray.length - 1; i >= 0; i--) {
if (!alreadyEvaluatedCharacters.contains(String.valueOf(charArray[i]))) {
alreadyEvaluatedCharacters = alreadyEvaluatedCharacters + charArray[i];
}
}
System.out.println("String in Reverse Order with characters printed only once => " + alreadyEvaluatedCharacters);
}
private static void printCharactersInReverseOrder(String iInputString) {
char[] charArray = iInputString.toCharArray();
String alreadyEvaluatedCharacters = "";
for (int i = charArray.length - 1; i >= 0; i--) {
if (!alreadyEvaluatedCharacters.contains(String.valueOf(charArray[i]))) {
alreadyEvaluatedCharacters = alreadyEvaluatedCharacters + charArray[i];
}
}
System.out.println("String in Reverse Order with characters printed only once => " + alreadyEvaluatedCharacters);
}
public class StringReversePrint {
public static void main(String[] args){
printUniqueReverse("aaaabbfbccaaeeaaaff"); //faecb
}
public static void printUniqueReverse(String word){
char[] cword = word.toCharArray();
int[] tab = new int[256];
StringBuilder sb = new StringBuilder();
for(int i=(cword.length -1); i>=0;i--){
char c = cword[i];
if(tab[c] == 0){
sb.append(c);
tab[c] = 1;
}
}
System.out.println(sb.toString());
}
}
{{
bool set[128] = { false };
string str = { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbcccaabbcc" };
int length = str.length();
int endIndex = length - 1;
while (endIndex >= 0)
{
if (!(set[str.at(endIndex) - 'a']))
{
cout << str.at(endIndex);
set[str.at(endIndex) - 'a'] = true;
}
endIndex--;
}
}}
bool set[128] = { false };
string str = { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbcccaabbcc" };
int length = str.length();
int endIndex = length - 1;
while (endIndex >= 0)
{
if (!(set[str.at(endIndex) - 'a']))
{
cout << str.at(endIndex);
set[str.at(endIndex) - 'a'] = true;
}
endIndex--;
}
public class ReverseString {
public static void main(String[] args) {
String input = "aabdceaaabbbcd";
reverseWithUniqueCharacterSet(input);
}
public static void reverseWithUniqueCharacterSet(String input) {
LinkedHashSet<Character> output = new LinkedHashSet<Character>();
char[] inputCharArray=input.toCharArray();
for(int i=inputCharArray.length-1; i>=0;i--){
if(output.add(inputCharArray[i])){
System.out.print(inputCharArray[i]);
}
}
}
}
Assuming we only have lowercase a-z (We can extend this for all ASCII easily)
Following code has O(n) time and constant space. Space is Actually O(26) which is constant.
public class Test {
public static void printOnceReverse(char[] s) {
if(s.length == 0) return;
boolean[] flag = new boolean[26];
int i;
for(i=0; i<s.length; i++) {
int index = s[i] - 'a';
flag[index] = true;
}
for(i=s.length-1; i>=0; i--) {
int index = s[i] - 'a';
if(flag[index] == true) {
System.out.print(s[i]);
flag[index] = false;
}
}
System.out.println();
}
public static void main(String[] args) {
printOnceReverse("aabdceaaabbbcd".toCharArray());
printOnceReverse("aaaabbcddddccbbdaaeee".toCharArray());
printOnceReverse("aaafffcccddaabbeeddhhhaaabbccddaaaa".toCharArray());
}
}
private static String reverse(String param) {
StringBuilder buf = new StringBuilder();
for(int i = param.length(); i > 0; i--) {
char ch = param.charAt(i-1);
if (buf.indexOf(ch + "") == -1)
buf.append(ch);
}
return buf.toString();
}
public static void main(String[] args) {
System.out.println(reverse("aaaabbbbddddeeeewwww"));
}
package amazon;
public class PrintAllStringInReverseWhichOccursOnlyOnce {
public static void main(String[] args) {
char[]c = "aabdceaaabbbcd".toCharArray();
int[] temp = new int[128];
for(char x :c){
temp[x]++;
}
for(int i=c.length-1;i>=0;i--){
if(temp[c[i]]>0){
System.out.print(c[i]);
temp[c[i]]=0;
}
}
}
}
import java.util.*;
public class StringAmazon {
public static void main(String args[]){
String inputStr;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the String");
inputStr=sc.nextLine();
StringAmazon sa =new StringAmazon();
System.out.println(sa.reverseString(inputStr));
}
private String reverseString(String str){
//String output = null;
StringBuilder sbr = new StringBuilder();
if(str.length()==0)
return null;
if(str.length()==1)
return str;
for(int i=str.length()-1; i>0; i--){
if(str.charAt(i)!=str.charAt(i-1)){
sbr=sbr.append(str.charAt(i));
}
}
sbr.append(str.charAt(0));
return sbr.toString();
}
}
//============================================================================
// Name : StringPrintReverseOnlyOnce.cpp
// Author : Nitish Raj, Scientist, DRDO, raj.nitp@gmail.com
// Version :
// Copyright : Your copyright notice
// Description : StringPrintInReverseMannerWithNoDuplicate, Ansi-style
//============================================================================
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
int main()
{
typedef tr1::unordered_map<char,int> charmap;
charmap _map;
string _str="aaaabbbbgggggffffafffbuuaaiiiiaaa";
int str_size = _str.length();
while(str_size>0){
if(!_map.count(_str[str_size-1])){
_map.insert(pair<char,int>(_str[str_size-1],1));
cout<<_str[str_size-1];
}
str_size--;
}
/*cout<<endl;
charmap::hasher fn = _map.hash_function();
std::cout << "a: " << fn ('a') << std::endl;
std::cout << "i: " << fn ('i') << std::endl;
std::cout << "u: " << fn ('u') << std::endl;
std::cout << "b: " << fn ('b') << std::endl;
std::cout << "f: " << fn ('f') << std::endl;
std::cout << "g: " << fn ('g') << std::endl;
charmap ::iterator itr = _map.begin();
while(itr != _map.end())
{
cout<<itr->first;
itr++;
}
*/
return 0;
}
private static void reverseString() {
String input = "aabdceaaabbbcd";
Set<Character> print = new LinkedHashSet<Character>();
for (int i = input.length() - 1; i >= 0; i--) {
print.add(input.charAt(i));
}
for (Iterator iterator = print.iterator(); iterator.hasNext();) {
System.out.println((Character) iterator.next());
}
}
Python : Used Stack and Dictionary. Complexity O(N)
s1 = 'aabdceaaabbbcd'
#output = dcbae
s2 = 'aaaabbcddddccbbdaaeee'
#output = eadbc
s3 ='aaafffcccddaabbeeddhhhaaabbccddaaaa'
#output = adcbhef
def check(s1):
len1 = len(s1)
if len1 <= 1:
return s1
dict1 = {}
count = 0
list1 = []
for i in range(len1-1,0,-1):
if s1[i] in dict1:
dict1[s1[i]] = count
count += 1
else:
dict1[s1[i]] = count
count += 1
if s1[i] not in list1:
list1.append(s1[i])
print dict1
print list1
s2 = ''
for items in list1:
s2 = s2 + items
print s2
check(s3)
- A May 31, 2016public class StringReverse { public static void main(String[] args) { String input = "aabdceaaabbbcd"; reverseWithOneCharacterOnce(input); } private static void reverseWithOneCharacterOnce(String input) { Set<Character> alreadyPrintedCharacter = new HashSet<Character>(); String reversed = ""; for (int index = input.length() - 1; index >= 0; index--) { Character ch = input.charAt(index); if (!alreadyPrintedCharacter.contains(ch)) { alreadyPrintedCharacter.add(ch); reversed = reversed + ch; } } System.out.println(reversed); } }