funktional
BAN USER
I'm what they consider an "old school" mobile developer, versed in both iOS and Android. I started iOS back in 2009 when it was still iPhone OS 3. And then we did our first Android project at the start of 2011 for Android 2.3 Gingerbread (API 10).
- -1of 1 vote
AnswersYou are given the arrival and departure times of airplanes at an airport for a single day. Schedules for the airplanes remain the same across all days. You are to determine the number of gates the airport should have so that no plane spends time waiting for a gate.
- funktional in United States for AWS
arr = [9:30, 11:15, 16:30]
dep = [11:45, 11:30, 16:45]
Arr array is sorted by time. And departure array is sorted by corresponding arrival times. Plane 'i' arrives at time arr[i] and departs at time dep[i]
Notes:
After some questions, it was decided that minute was the smallest unit of time we cared about. Gate was considered occupied on the arriving minute, but empty on the departing minute. And that the arrival and departure times could be represented as such as integers. e.g. Day runs from minute 0 to minute 1339 (since using a zero-based index). So our example times represented as:
arr = [570, 675, 990]
dept = [705, 690, 1005]| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Coding
Can you explain your comment as to why the above are not O(n) and why the optimal runtime is O(n log n)?
- funktional September 21, 2016Here was my solution from the interview:
// Day runs from minute 0 to minute 1440 (exclusive)
// Input: example 9:30 => 570
// arr [570, 675, 990]
// dept [705, 690, 1005]
// Assume data is valid - i.e. length, no neg, etc.
int[] arr = { 570, 675, 990 };
int[] dept = { 705, 690, 1005 };
// Create a frequency map for the day
Map<Integer, Integer> freqMap = new HashMap<>();
for (int n = 0; n < arr.length; n++) {
int a = arr[n];
int d = dept[n];
for (int i = a; i < d; i++) {
int count = freqMap.containsKey(i) ? freqMap.get(i) : 0;
freqMap.put(i, count + 1);
}
}
// Calculate the max value
int maxVal = 0;
for (Integer n : freqMap.values()) {
if (n > maxVal) {
maxVal = n;
}
}
System.out.println("Gates needed: " +maxVal);
Time complexity O(n) since the map is bounded by constant 1440 min per day
assuming HashMap has time O(1) with a decent hash algorithm.
The problem sounds like a variation of the subset sum problem. (See Wikipedia.) If you sum the entire list, then the sum is equivalent to the sum of the subset that remains after you remove all of the subsets that sum up to zero.
I did a breadth first search variation, because we want the shortest subset that sums to our target, so it doesn't contain additional subsets that sum to zero. I was a little lazy and just printed out the subset, but code could easily be modified to return the list.
class Solution {
public static class Potential {
int sum;
List<Integer> partial;
List<Integer> remaining;
public Potential(int s, List<Integer> p, List<Integer> r) {
sum = s;
partial = p;
remaining = r;
}
public String toString()
{
return "(" + sum + ", " + Arrays.toString(partial.toArray())
+ ", " + Arrays.toString(remaining.toArray()) + ")";
}
}
static void subsetSum_BFS(List<Integer> numbers, int target) {
Queue<Potential> queue = new LinkedList<>();
Potential start = new Potential(0, new ArrayList<Integer>(), numbers);
queue.add(start);
while (!queue.isEmpty()) {
Potential current = queue.remove();
int sum = current.sum;
for (int i = 0; i < current.remaining.size(); i++) {
List<Integer> remaining = new ArrayList<Integer>();
int n = current.remaining.get(i);
sum += n;
List<Integer> partial = new ArrayList<>(current.partial);
partial.add(n);
if (sum == target) {
System.out.println("sum="+target);
System.out.println(Arrays.toString(partial.toArray()));
return;
}
for (int j= i + 1; j < current.remaining.size(); j++) {
remaining.add(current.remaining.get(j));
}
Potential next = new Potential(sum, partial, remaining);
queue.add(next);
sum -= n;
}
}
System.out.println("Matching subset not found.");
}
static void removeZeroSum(List<Integer> numbers) {
int sum = 0;
for (Integer n : numbers) {
sum += n;
}
System.out.println("target="+sum);
if (sum == 0) {
System.out.println("[]");
System.out.println("Subset empty, bypassing search.");
return;
}
subsetSum_BFS(numbers, sum);
}
public static void main(String[] args) {
// case 1: 6 -6 8 4 -12 9 -8 8
// O/P : 9
Integer[] case1 = {6, -6, 8, 4, -12, 9, -8, 8};
List<Integer> case1List = new LinkedList<>(Arrays.asList(case1));
removeZeroSum(case1List);
// case 2: 20, 5, 6, 10, -11, 10, 2, 2
// O/P : 20 2 2
Integer[] case2 = {20, 5, 6, 10, -11, -10, 2, 2};
List<Integer> case2List = new LinkedList<>(Arrays.asList(case2));
removeZeroSum(case2List);
// case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
// O/P : 20 25
Integer[] case3 = {4, 6, -10, 8, 9, 10, -19, 10, -18, 20, 25};
List<Integer> case3List = new LinkedList<>(Arrays.asList(case3));
removeZeroSum(case3List);
}
}
Much like the subset sum problem, the worst case time complexity is exponential because we can't assume the values are non-negative and hence can't eliminate combinations. So worst case O(2^N*N) when there are no subsets that sum to zero, since there are 2N subsets and, to check each subset, we need to sum at most N elements. Best case would be O(N), when the list sums to zero, because we don't have to check any and the result is just an empty list.
- funktional September 12, 2016There is a problem with your code and test case #3 above.
case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25
O/P : 20 25
HashMap<Integer,Node> mp=new HashMap<Integer,Node>();
HashMap can't handle multiple values of 10 in the same list, so it overwrites the node value.
- funktional September 11, 2016If I read the problem correctly, if you can shuffle and/or remove characters, then the longest palindrome is the sum of all of the even count chars and the longest odd count char (if there is one).
public static int maxLengthPalindrome(String s) {
String[] sArr = s.split("");
Map<String, Integer> charFreq = new HashMap<String, Integer>();
for (int i = 0; i < s.length(); i++) {
String c = sArr[i];
if (charFreq.containsKey(c)) {
int count = charFreq.get(c);
charFreq.put(c, count + 1);
} else {
charFreq.put(c, 1);
}
}
int maxPal = 0;
int maxOdd = 0;
for (String c : charFreq.keySet()) {
int count = charFreq.get(c);
if (count % 2 == 0) {
maxPal += count;
} else if (count > maxOdd) {
maxOdd = count;
}
}
return maxPal + maxOdd;
}
First pass creates the frequency map and is O(n) where n is length of string. Second pass adds up the frequency map and is O(k) where k is the number of keys. Generally k will be bounded by both n and max of the character set, so in practice O(kn) should reduce to O(n).
- funktional September 11, 2016Modified binary search is definitely the way to go. If numbers are in sequence, then the difference between two array values should equal the difference of their indices. If not, then the missing number is somewhere in that range.
public static int findMissingNumber(int[] a) {
// Validate... Assume -1 is fine to return for not found.
if (a == null || a.length == 0) {
System.out.println("Invalid sequence: length.");
return -1;
}
int low = 0;
int mid;
int high = a.length-1;
while (low < high) {
mid = low + (high - low) / 2;
if (a[mid] - a[low] == mid - low) {
// Missing number is in upper half
if (mid + 1 < a.length && a[mid + 1] != a[mid] + 1) {
return a[mid] + 1;
} else {
low = mid + 1;
}
} else {
// Missing number is in lower half
if (mid - 1 >= 0 && a[mid] - 1 != a[mid - 1]) {
return a[mid] - 1;
} else {
high = mid -1;
}
}
}
System.out.println("Invalid sequence: not found.");
return -1;
}
Best case: O(1) Average case: O(log n) Worst case: O(log n)
- funktional September 11, 2016Close but I believe your while loop needs to be:
while(head != NULL)
{
...
Nice use of the Java LinkedList data type, with convenient access to list size. However you need to be careful how you define your index parameter. The problem definition says Kth position from the start and end of a linked list. Since Java uses a zero-based index, if you passed K=2 into your method, you’d actually be swapping 4 & 5, instead of 2 & 7.
- funktional September 11, 2016
Repfrancesdpayne, AT&T Customer service email at Cavium Networks
I am Frances Payne from Jacksonville, United States. I am working as a Rental manager in Magna Gases company. I ...
RepMarryJohan, Consultant at ASAPInfosystemsPvtLtd
I am successfully manage and coordinate graphic design projects from concept through completion. Create and conduct highly persuasive sales and ...
RepShayneLJohnson, Scientific Officer at Cerberus Capital
I'm Shayne and I have a history of sensitivities that range from dietary issues to skin care and other ...
RepAlmaRJude, Quality Assurance Engineer at Brocade
I am Alma from Livermore USA, I also enjoy reading – my favourite topics being social history, the development and use ...
Repsonjamramos45, Graphics Programmer at CGI-AMS
I am a strong writer with a passion for story-telling who has extensive experience of writing literary compositions, articles, reports ...
Repcarmenrhargis, Associate at Achieve Internet
Hi, I am Gladys, I live in Florida, USA, I am working as a project manager in a Life’s ...
Repshanamkyler38, AT&T Customer service email at ABC TECH SUPPORT
Hi, I am Shana and I live in Chicago USA .I am working as a Tax preparer in an Adaptabiz ...
Repshanitajjana, +27655765355 SSD MONEY CLEANING CHEMICAL +27655765355 BLACK MONEY IN JOHANNESBURG, OMAN, SAUDI ARABIA, SUDAN, Somalia ,Zimbabwe Botswana at 247quickbookshelp
Hi I am Shanita from San Bernardino USA. I am working as a manager in flore company. I am outgoing ...
Repverarfurman, Problem Setter at Cerberus Capital
I am Vera from Bullard USA, I am working as a Violin repairer in a Handyman company. My interest in ...
Reprajanadeep17, Android Engineer at 247quickbookshelp
I am a Special education teacher who adapts general education lessons and teaches various subjects to students with mild to ...
Repjenniferdray9, Accountant at ABC TECH SUPPORT
Hi I am Jennifer D. Ray from san Diego.Currently i am working as a parts salesperson in Rite solution ...
Repharoldjmaloney, Accountant at ASU
Hi, I am a Computer systems administrator from texas. Experienced in running a wide variety of software development Company. Looking ...
Repcherylthurber, Developer Advocate at Absolute Softech Ltd
Hi,I am from Taxes, USA. Passionate multilingual translator with 2.5 years experience in Spanish-English translations.Looking to further ...
Repjimmybdepuy, Front-end Software Engineer at Arista Networks
Hi, I am Jimmy from los Angeles. I am a painter. I have Knowledge of different types and shades of ...
Reppaulaamontalvo, AT&T Customer service email at AMD
I am working as Human Resources Associates, and my duties are for obtaining, recording, and interpreting human resources information within ...
RepPriscillaRYoung, Aghori Mahakal Tantrik at Absolute Softech Ltd
Hi, I am Priscilla from California. I am working as a Business management consultant in Quality Merchant Services company. I ...
Repnyladsomerville, abc
Want to purchase best quality silencer at affordable price manufactured by top most trusted brand Innovative Arms.
Contact Stonefirearms now!
Repelisahbuff, Apple Phone Number available 24/7 for our Customers at Altera
I have previous work experience in a customer focused environment. I like to Enjoy my Free Time Playing football.I ...
Repdorarwoods, Kuwait airways reservations at Aspire Systems
I am an Application engineer in the network chef company. In my free time, I enjoy reading programming and technology ...
Repellahrivas6, Android test engineer at 247quickbookshelp
I am working as an internist and I work in medical offices, clinics, and hospitals. An internist may work independently ...
Repsos337837, Personnel assistant at Bountiful Harvest Health Food Store
I am a Risten Personnel Assistant . I am responsible for maintaining human resource records of Department employees . I have a ...
RepGrimesOtto, Java Developer at Coupondesh
I am Grimes Agriculture inspector. I examine agriculture commodities and related operations . I like listening to music, painting, and reading ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
Repjohnlevans657, Principal Software Engineer at Ask.com
Hi, I am John, from Taxes USA, I am a dedicated, extremely organized, and highly competent Administrative Specialist seeking a ...
RepGet powerful wazifa to know who did black magic. Guru Ji is the master of black magic totke, kala jadu ...
swap constraint: exchange only adjacent element.
- funktional September 26, 2016