## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

Construct a directed graph with nodes A, B, C, ... and edges (A,B), (C,D) etc. Then do a topological sort and you're done.

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

``````#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
int number;
cout<<"\n Enter the number of inputs:";
cin>>number;

char inputChar1,inputChar2;
pairedVector dataVector;

for(int i=0;i<number; i++)
{
cout<<"\n Enter the paired chars:";
cin>>inputChar1;
cin>>inputChar2;

/* pair the char for insetion*/
charPair p = std::make_pair(inputChar1, inputChar2);

/* Inserting the data into Vector for string pair*/
dataVector.push_back(p);
}

charPair min;
for(int i=0; i< dataVector.size()-1; i++)
{
min=dataVector[i];
int swapIndex=i;
for(int j=i; j<dataVector.size(); j++)
{
if(min>dataVector[j])
{
min=dataVector[j];
swapIndex=j;
}
}
/* Swap the values */
charPair tmp=dataVector[swapIndex];
dataVector[swapIndex]=dataVector[i];
dataVector[i]=tmp;

}
/* Define an iterator to get the values from the vector*/
pairedVector::iterator it;
int i=0;
for( it=dataVector.begin(); it!=dataVector.end(); ++it)
{
cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
++i;
}

return 0;
}``````

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

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
int number;
cout<<"\n Enter the number of inputs:";
cin>>number;

char inputChar1,inputChar2;
pairedVector dataVector;

for(int i=0;i<number; i++)
{
cout<<"\n Enter the paired chars:";
cin>>inputChar1;
cin>>inputChar2;

/* pair the char for insetion*/
charPair p = std::make_pair(inputChar1, inputChar2);

/* Inserting the data into Vector for string pair*/
dataVector.push_back(p);
}

charPair min;
for(int i=0; i< dataVector.size()-1; i++)
{
min=dataVector[i];
int swapIndex=i;
for(int j=i; j<dataVector.size(); j++)
{
if(min>dataVector[j])
{
min=dataVector[j];
swapIndex=j;
}
}
/* Swap the values */
charPair tmp=dataVector[swapIndex];
dataVector[swapIndex]=dataVector[i];
dataVector[i]=tmp;

}
/* Define an iterator to get the values from the vector*/
pairedVector::iterator it;
int i=0;
for( it=dataVector.begin(); it!=dataVector.end(); ++it)
{
cout<<"\n Pair < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
++i;
}

return 0;
}

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

Java Version using Topological Sort:

``````public class AlphabeticalOrdering {
static Map<Character, List<Character>> tuples = new HashMap<Character, List<Character>>();
static int alphabetCount = 0;
static Map<Character, Boolean> vertex = new HashMap<Character, Boolean>();

public static List<Character> ordering(Tuple tuple[]){

for(Tuple t : tuple){
if(tuples.containsKey(t.x)){
}else{
tuples.put(t.x, list);
}

vertex.put(t.x, false);
vertex.put(t.y, false);
}

alphabetCount = vertex.size();

}

public static List<Character> topologicalSort(){
Stack<Character> s = new Stack<Character>();

for(Map.Entry<Character, Boolean> entry : vertex.entrySet()){
if(!entry.getValue())
topologicalSortUtil(entry.getKey(), s);
}

while(!s.isEmpty())

return result;
}

public static void topologicalSortUtil(char v, Stack<Character> s){
vertex.put(v, true);

if(tuples.containsKey(v)){
Iterator<Character> it = tuples.get(v).listIterator();
while(it.hasNext()){
char n = it.next();
if(!vertex.get(n))
topologicalSortUtil(n, s);
}
}

s.push(v);
}
public static void main(String[] args) {
Tuple tuple[] = {
new Tuple('A', 'B'),
new Tuple('C', 'D'),
new Tuple('C', 'E'),
new Tuple('D', 'E'),
new Tuple('A', 'C'),
new Tuple('B', 'C')
};

System.out.println(ordering(tuple));
}

}

class Tuple{
char x;
char y;

public Tuple(char a, char b){
x = a;
y = b;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

List<String> newList = Arrays.asList("AB", "BC", "CD", "DE", "MZ", "NM");
char[] chrs;
Set<Character> charSet = new TreeSet<>();
for (Iterator<String> iterator = newList.iterator(); iterator.hasNext();) {
String string = (String) iterator.next();
chrs = string.toCharArray();
for (int i = 0; i < chrs.length; i++) {
char c = chrs[i];

}

}

System.out.println(charSet);

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
int number;
cout<<"\n Enter the number of inputs:";
cin>>number;

char inputChar1,inputChar2;
pairedVector dataVector;

for(int i=0;i<number; i++)
{
cout<<"\n Enter the paired chars:";
cin>>inputChar1;
cin>>inputChar2;

/* pair the char for insetion*/
charPair p = std::make_pair(inputChar1, inputChar2);

/* Inserting the data into Vector for string pair*/
dataVector.push_back(p);
}

charPair min;
for(int i=0; i< dataVector.size()-1; i++)
{
min=dataVector[i];
int swapIndex=i;
for(int j=i; j<dataVector.size(); j++)
{
if(min>dataVector[j])
{
min=dataVector[j];
swapIndex=j;
}
}
/* Swap the values */
charPair tmp=dataVector[swapIndex];
dataVector[swapIndex]=dataVector[i];
dataVector[i]=tmp;

}
/* Define an iterator to get the values from the vector*/
pairedVector::iterator it;
int i=0;
for( it=dataVector.begin(); it!=dataVector.end(); ++it)
{
cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
++i;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

// Function for paired char to store
typedef std::pair<char,char> charPair;

//Vector to hold the paired data
typedef std::vector<charPair> pairedVector;

int main()
{
int number;
cout<<"\n Enter the number of inputs:";
cin>>number;

char inputChar1,inputChar2;
pairedVector dataVector;

for(int i=0;i<number; i++)
{
cout<<"\n Enter the paired chars:";
cin>>inputChar1;
cin>>inputChar2;

/* pair the char for insetion*/
charPair p = std::make_pair(inputChar1, inputChar2);

/* Inserting the data into Vector for string pair*/
dataVector.push_back(p);
}

charPair min;
for(int i=0; i< dataVector.size()-1; i++)
{
min=dataVector[i];
int swapIndex=i;
for(int j=i; j<dataVector.size(); j++)
{
if(min>dataVector[j])
{
min=dataVector[j];
swapIndex=j;
}
}
/* Swap the values */
charPair tmp=dataVector[swapIndex];
dataVector[swapIndex]=dataVector[i];
dataVector[i]=tmp;

}
/* Define an iterator to get the values from the vector*/
pairedVector::iterator it;
int i=0;
for( it=dataVector.begin(); it!=dataVector.end(); ++it)
{
cout<<"\n Pair  < "<<dataVector[i].first<<","<<dataVector[i].second<<">"<<endl;
++i;
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````case class LetterOrder(lesser: String, greater: String)

object Prob {
def main(args: Array[String]): Unit = {
val orderings = Seq(
LetterOrder("A", "B"),
LetterOrder("C", "D"),
LetterOrder("C", "E"),
LetterOrder("D", "E"),
LetterOrder("A", "C"),
LetterOrder("B", "C")
)

val alphabet = orderings
.flatMap(lo => Seq(lo.lesser, lo.greater))
.toSet
.toList

def sortByOrdering(x: String, y: String): Boolean =
if (orderings.contains(LetterOrder(x, y))) {
true
} else {
orderings.find(_.lesser == x) match {
case Some(LetterOrder(_, otherGreater)) =>
sortByOrdering(otherGreater, y)

case None =>
false
}
}

println(alphabet.sortWith(sortByOrdering))
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Recursive:

``````def topoSort(ts):
r,g,v = ([[]],{},set())
for [a,b] in ts:
g.update({a: g.get(a, []) + [b]})
def go(k):
if k not in v:
for m in g.get(k, []):
go(m)
r[0] += [k]
for k in g.keys():
go(k)
return r[0][::-1]

print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])``````

Iterative:

``````def topoSort(ts):
r,g,v = ([],{},set())
for [a,b] in ts:
g.update({a: g.get(a, []) + [b]})
for k in g.keys():
st = [(k, g.get(k, []))]
while st:
(k,ms) = st.pop()
if k not in v:
if ms:
st += [(k, ms[1:])]
st += [(ms[0], g.get(k, []))]
else:
r += [k]
return r[::-1]

print topoSort(["AB", "CE", "CD", "DE", "AC", "BC"])``````

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.

### 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.