is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
{{I dont think we need DFS. Below is my solution with nlogn running time because of sorting step.
- ishwar.ikj September 16, 2017Have tried all above examples and they all work correctly.
1. reverse sort the characters and keep in an array, also prepare a positions hashMap against each digit with value as positions of occurrence of that digit (In increasing order).
2. Now create 4 lists. 2 for keeping positions of swapFrom and swapTo, 2 for keeping actual bigger numbers and smaller numbers.
3. run a loop for 0 to number of swaps, do below
I) if swappedIn and swappedOut number are same, dont count it as a swap.
II) insert biggest position of swappedIn number in positionsSwappedFrom so that we can insert smaller numbers at these positions later.
III) positionsSwappedTo, bigger, smaller are simple enough to understand from code.
4. sort the smaller numbers in decreasing orders so that we can insert these in those positions from which bigger numbers came.
5. sort positionsSwappedFrom in increasing order.
6. populate the chars array with help of above 4 lists.
7. create answer string from this chars array.
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(swap(sc.next(), sc.nextInt()));
}
public static String swap(String input, int swaps) {
if (input == null || input.length() < 2 || swaps < 1) return input;
char[] chars = input.toCharArray();
Map<Character, List<Integer>> positions = new HashMap<>();
List<Character> sorted = new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
char ch = chars[i];
sorted.add(ch);
if (!positions.containsKey(ch)) {
positions.put(ch, new ArrayList<>());
}
positions.get(ch).add(i);
}
Collections.sort(sorted, Comparator.reverseOrder());
List<Integer> positionsSwappedFrom = new ArrayList<>();
List<Integer> positionsSwappedTo = new ArrayList<>();
int i = -1;
List<Character> bigger = new ArrayList<>();
List<Character> smaller = new ArrayList<>();
while (swaps > 0) {
i++;
if(chars.length <= i) {
break;
}
if (chars[i] == sorted.get(i)) {
continue;
}
List<Integer> charPositions = positions.get(sorted.get(i));
positionsSwappedFrom.add(charPositions.remove(charPositions.size() - 1));
positionsSwappedTo.add(i);
swaps--;
bigger.add(sorted.get(i));
smaller.add(chars[i]);
}
Collections.sort(smaller, Comparator.reverseOrder());
Collections.sort(positionsSwappedFrom);
for(int swap=0; swap<smaller.size(); swap++) {
chars[positionsSwappedTo.get(swap)] = bigger.get(swap);
chars[positionsSwappedFrom.get(swap)] = smaller.get(swap);
}
return new String(chars);
}
}
}}