# Amazon onsite interview question

• Question 1: You are working on developing a movie with Amazon Video and want to devise an application to easily break up individual shots in a video into scenes.
There is already an algorithm that breaks the video up into shots (short sequences from a particular camera angle) and labels them.

Write a function which will partition a sequence of labels into minimal subsequences so that no labels appear in more than one subsequence.
The output should be the length of each subsequence.

Input:
The input to the function/method consists of an argument - inputList, a list of characters representing the sequence of shots.

Output:
Return a list of integers representing the length of each scene, in the order in which it appears in the given sequence of shots.

Example:

• Input:
inputList = [a,b,a,b,c,b,a,c,a,d,e,f,e,g,d,e,h,i,j,h,k,l,i,j]
• Output:
[9, 7, 8]

Explanation:
The correct partitioning is:
a,b,a,b,c,b,a,c,a,/d,e,f,e,g,d,e,/h,i,j,h,k,l,i,j
To ensure that no label appears in more than one subsequence, subsequences are as small as possible, and subsequences partition the sequence.
The length of these subsequences are 9, 7 and 8.

Question 2: Michelle has created a word game for her students. The word game begins with Michelle writing a string and a number, K, on the board.
The students must find a substring of size K such that there is exactly one character that is repeated one;
in other words, there should be k - 1 distinct characters in the substring.

Write an algorithm to help the students find the correct answer. If no such substring can be found, return an empty list;
if multiple such substrings exist, return all them, without repetitions. The order in which the substrings are does not matter.

Input:
The input to the function/method consists of two arguments - inputString, representing the string written by the teacher;
num an integer representing the number, K, written by the teacher on the board.

Output:
Return a list of all substrings of inputString with K characters, that have k-1 distinct character i.e.
exactly one character is repeated, or an empty list if no such substring exist in inputString.
The order in which the substrings are returned does not matter.

Constraints:
The input integer can only be greater than or equal to 0 and less than or equal to 26 (0 <= num <= 26)
The input string consists of only lowercase alphabetic characters.

Example
Input:
inputString = awaglk
num = 4

Output:
[awag]

Explanation:
The substrings are {awag, wagl, aglk}
The answer is awag as it has 3 distinct characters in a string of size 4, and only one character is repeated twice.

• First problem, sliding window with a hash map?
Second Problem, same thing...? Much more complicated implementation though

• First problem - Find range of all characters. Then merge overlapping intervals.
Second problem - A simple application of sliding window problem.

• Second problem can be done in O(n) time in one such way given below:
List<String> function(String s,int k){
List<String> result= new ArrayList<String>();
if(s==null||s.length()==0||s.length()<k)
return res;
int charCount[]= new int[26];
int len=s.length();
int count=0;
for(int i=0;i<len;i++){
if(charCount[s.charAt(i)-'a']==0)count++;
charCount[s.charAt(i)-'a']++;
if(i>=k-1){
int startIndex=i-k+1;
if(count==3)
charCount[s.charAt(startIndex)-'a']--;
if(charCount[s.charAt(startIndex)-'a']==0)
count--;
}
}
return result;}

• This post is deleted!

• Second problem:

``````public static List<String> findKMinusOneDistinct(String inputString, int k) {

Map<Character, Integer> occurrenceMap = new HashMap<>();
List<String> resultList = new ArrayList<>();

for (int i = 0; i + k <= inputString.length(); i++) {

String str = inputString.substring(i, i + k);
boolean isRepeat = false;

for (char c : str.toCharArray()) {
if (occurrenceMap.containsKey(c)) {
if (!isRepeat)
occurrenceMap.put(c, occurrenceMap.get(c) + 1);
else
break;

isRepeat = true;
} else
occurrenceMap.put(c, 1);
}
//if it makes it through and has precisely 1 repeat character
if (isRepeat)
//empty the map
occurrenceMap.clear();
}
return resultList;
}``````

• Did they give you a copy of these questions? I'm just surprised at the level of details. Anyway, I got the same questions but in an online test a couple of weeks ago.

Q1: Merge Intervals. For each letter, use an array or hash table to store the first index and last index (this will act as the start and end point for each interval). Then combine overlapping intervals at the end. The length of each interval (end index - start index + 1) will be part of the output.

Q2: sliding window. Use a dequeue as so you can easily add and remove letters from both sides. Keep a small hash table to check for duplicates.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.