## Amazon Interview Question for SDE-2s

• 0
of 0 votes

Country: United States
Interview Type: In-Person

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

I think that if the maximum frequency is at most the total number of other characters + 1, then the arrangement exists. We can construct the solution by starting with the character with the maximum frequency and decrementing its counter, then adding the next different character with the maximum frequency and decrementing and so on. If many chars have the same frequency any one of them can be chosen. Keeping track only if that arrangement exists would be O(1) time and space for each character from the infinite sequence, while constructing the solution with the algorithm above would be O(n) time (the max-heap's size does not depend on the input size) and O(1) space.

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

@koustav, would you mind explaining your algo at a high level? I think your algo is creating max heap and simulating the arrangement?

The idea I had was to use min-heap. Basic idea is to count the frequencies of chars, then create create min heap based on those frequency. With the min heap, we would then check if the difference of the children with current is <= 1, else its not possible for such arrangement.

For example:

``````- input: "AAABBCCDEF"
- calculate frequency of each character:  [3,2,2,1,1,1]
- create min heap: [1,2,1,3,2,1]
1
2 1
3 2 1
- now for each node calculate Math.abs( (leftChild+rightChild) - current ) and return that value.
- At root node, the tree is arrangable only if the Math.abs( (leftChild+rightChild) - current )  <= 1``````

That seems like it would work, any thoughts? I'll test it out the idea in bit, but wondering if anyone had thoughts?

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

1. Keep count of each character.
2. Sort them in decreasing order based on there number of count.
3. Pick first two and start decrementing from both of them till one of them reaches to Zero.
4. Item which count is zero remove that and move to step 2 again.
If only one char left with any count then it's not possible.

Another Note:

``````In question input is:        "AAABBCCDEF"
Output is:                  "ABABCDCEF"
where output should be:     "ABABCACDEF"``````

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

``````static class HeapNode {
char c;
int count;

public HeapNode(char c, int count) {
this.c = c;
this.count = count;
}

public char getC() {
return c;
}

public void setC(char c) {
this.c = c;
}

public int getCount() {
return count;
}

public void setCount(int count) {
this.count = count;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + c;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
HeapNode other = (HeapNode) obj;
if (c != other.c)
return false;
return true;
}

@Override
public String toString() {
return "HeapNode [c=" + c + ", count=" + count + "]";
}

}

public static String arrange(String str) {
int count[] = new int[26];
int max = Integer.MIN_VALUE;
for (char c : str.toCharArray()) {
count[c - 'a'] = count[c - 'a'] + 1;
if (max < count[c - 'a']) {
max = count[c - 'a'];
}
}
if (max > ((str.length() / 2) + 1)) {
System.out.println("Can't be done");
return "";
}
char c = 'a';
PriorityQueue<HeapNode> maxHeap = new PriorityQueue<HeapNode>(new Comparator<HeapNode>() {
@Override
public int compare(HeapNode o1, HeapNode o2) {
return o2.count - o1.count;
}
});
for (int i = 0; i < count.length; i++) {
if (count[i] != 0) {
HeapNode node = new HeapNode(c++, count[i]);
maxHeap.add(node);
}
}
StringBuffer sbf = new StringBuffer();
HeapNode temp = null;
while (!maxHeap.isEmpty()) {
HeapNode node = maxHeap.poll();
sbf.append(node.c);
node.count--;
if (temp != null && temp.count > 0) {
maxHeap.add(temp);
}
temp = node;
}
return sbf.toString();
}

public static void main(String args[]) throws Exception {
System.out.println(arrange("abcaabddddd"));
}``````

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