arsragavan
BAN USER 1of 1 vote
AnswersYou are given a file which contains 3 values  start time, end time, amount of water flowing between the start time and end time for one day
 arsragavan in United States
The start time and end time may overlap and are inclusive. The times are not in a sorted order
Example:
0,10,100
10,15,300
16,20,400
5,15,200
Find the max flow of water at any instant of time.
In the above example, the answer is 600 ( at instant 10) Report Duplicate  Flag  PURGE
A9 Intern Algorithm
One of the approaches would be to take the first, middle and last element and consider the median of the values as the pivot element
 arsragavan March 16, 2015The problem in your approach is that.if I want to reach cat to dog it's not always a 3 step process.. What if this is the path followed
cat > bat > bot > dot > dog. So, it takes 4 steps but your answer will be 3.
The approach is to build a graph with vertices as words. An edge exists between two vertices if the two words differ by only one character. Once the graph is constructed, you need to a BFS to obtain the path/count the number of nodes between two words.
To construct the graph, we pass the dictionary as a Set<String>
public Map<String, List<String>> constructGraph(Set<String> set) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : set) {
for (String match : set) {
if (oneCharDiff(str, match)) {
List<String> list = map.get(str);
if (list == null) {
list = new LinkedList<String>();
map.put(str, list);
}
list.add(match);
}
}
}
return map;
}
In the above code, the function oneCharDiff returns true if there is exactly one character difference between two words.
The following code navigates to the path using the above function,
public static void path(String input, String output, Set<String> set) {
Map<String, List<String>> map = constructGraph(set);
Map<String, String> path = new HashMap<String, String>();
Queue<Word> queue = new LinkedList<>();
String parent = null;
queue.add(new Word(input, parent));
while (!queue.isEmpty()) {
Word word = queue.remove();
input = word.original;
parent = word.parent;
if (!path.containsKey(input)) {
path.put(input, parent);
if (input.equals(output)) {
System.out.println(output);
while (parent != null) {
System.out.println(parent);
parent = path.get(parent);
}
return;
}
List<String> list = map.get(input);
if (list != null) {
for (String child : list)
queue.add(new Word(child, input));
}
}
}
System.out.println("No such path found");
}
Word is a simple class with 2 members  String original and String parent. This is used to print the order of the path followed.
Time complexity : O(n^2) when constructing the graph. Any suggestions to improve the solution are welcome. There is another way to handle this problem using the backtracking method but i'm sure the complexity would be exponential in that case.
Yes this approach works for sure. The solution provided by @Zortlord will also work. But this is easier to understand.
 arsragavan January 19, 2015I have never mentioned it as instance of hour. I just said it's an instance of time. What if the times are given in seconds ? Will you maintain a array of total no of seconds in a day ? I feel this is not the right approach.
 arsragavan December 31, 2014You have given a brute force approach. The complexity is O(n^2).
There is no use of sorting it based on start time. You can directly compare if the interval is overlapping with other interval and add the values.
I guess the interviewer won't ask for which library function you will use
 arsragavan December 23, 2014Thanks for pointing out. I did not add the code for returning the lowest position of the element. I think the following piece of code will help in fixing it.
if (a[mid] == x) {
while (mid > 0)
if (a[mid  1] == x)
mid;
return mid;
}

arsragavan
September 12, 2014 It's very much similar to Bin search. One point to be noted is to check if the right side of the mid or left side of mid is sorted.
1. If the element is equal to a[mid] then return mid
2. If the right side of mid is sorted (meaning a[mid]<a[high],
a. If x > a[mid] and x< a[high] then x lies between mid and high
b. Else x lies between low and mid1
3. If the left side of mid is sorted (meaning a[low] < a[mid]),
a. If x < a[mid] and x >a[low] then x lies between low and mid
b. Else x lies between mid and high
public int find(int[] a, int x) {
int low = 0;
int high = a.length  1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == x)
return mid;
if (a[mid] <= a[high]) {
if (x > a[mid] && x <= a[high])
low = mid + 1;
else
high = mid  1;
} else {
if (x < a[mid] && x >= a[low])
high = mid  1;
else
low = mid + 1;
}
}
return 1;
}

arsragavan
September 09, 2014 Space:O(n), Time :O(n)
rev = reverse_list(list);
while(true) {
if (list == rev  list.next == rev) {
list.data = list.datarev.data;
break;
}
list.data = list.datarev.data;
list = list.next;
rev = rev.next;
}
One thing to add is while reversing, we shouldn't just swap the values. But must swap the nodes to get the stopping condition right..
 arsragavan May 12, 2014How can we do it in less than O(n). What if all the n charecters are the same charecter (which is to be replaced).
 arsragavan April 23, 2014Giving a complex solution is better than providing a solution from library...
may be you can tell the interviewer abt the lib function and then can give your solution
Everytime you have to do k comparisons with each of k element in your current array. So, it's definitely going to be O(n^2)
 arsragavan April 07, 2014How abt this solution, Since he has not mentioned anything abt how much the memory can hold, we can take the first k elements from each file and put into a file.
Then we can use Quickselect algorithm to find the k smallest elements.
We can argue that this can be achieved in O(n) complexity...
I doubt if the complexity is O(100k)
From the first file, you will create a array of k size.
And, everytime you have to traverse all the elements in your array of k size for comparison with the first k elements of the file..
So, I guess the complexity is O(100*k^2).
Please correct me if I am wrong..
n is all the 100 million numbers = input size
k = heap size
You shouldn't create a minheap. If you construct a minheap, then you have the compare the new element with all the elements in the heap.
You should construct a max heap with first k elements. This will place the max element in the root. For each incoming element.
1) Check whether the element is less than the root.
2) If it's less than the root
3) Replace root with the incoming element
4) Heapify
This will produce a heap of k smallest elements at the end of traversing all the elements.
Complexity:O(nlogk)
public static String altCount(String str) {
String output = "";
str = str.toUpperCase();
for(int i = 0;i<str.length();i++) {
int count = 1;
output += str.charAt(i);
while (i< str.length()1 && str.charAt(i+1) == str.charAt(i)) {
i++;
count++;
}
output +=count;
}
return output;
}

arsragavan
April 01, 2014 public static String count(String str) {
StringBuilder strB = new StringBuilder(str.toUpperCase());
int count = 1;
for(int i = 0;i<strB.length();i++) {
if (i < strB.length()1 && strB.charAt(i+1) == strB.charAt(i)) {
strB.deleteCharAt(i);
i;
count++;
}
else {
strB.insert(i+1, count);
count = 1;
i++;
}
}
return strB.toString();
}

arsragavan
April 01, 2014 meetings will have start and end times... This is the classic greedy problem  Inteval scheduling problem
 arsragavan March 30, 2014sort the n meeting according to their end times
Keep assigning the 1...n meetings to the first of the meeting room 1..m which is free
str1.hashCode() == str2.hashCode()
 arsragavan March 29, 2014First ensure the length of two strings are same,
Then, compare each character by its ascii value one by one. This will take care of case automatically.
Are there any other conditions ?
There is no formatting.. How can you understand this thing ?
I guess it's for detecting cycles in a graph
I guess the qn should be moving right or down nor right or left ??
 arsragavan March 28, 2014Same code with minor changes,
public static void printComb(String prefix,String str) {
if (str.length() == 0) {
System.out.println(prefix);
return;
}
if (Character.isAlphabetic(str.charAt(0))) {
printComb(prefix+str.substring(0,1).toLowerCase(),str.substring(1));
printComb(prefix+str.substring(0,1).toUpperCase(),str.substring(1));
}
else
printComb(prefix+str.substring(0,1),str.substring(1));
}

arsragavan
March 26, 2014 You can maintain a hashmap for storing the output. Instead of printing the prefix you can put it into the map and return it. This will avoid duplicates..
Sorting the input and removing duplicates will alter the length of the combination. So, I think this method should be simple..
Is this the right approach. I am keeping track of predecessor value using pre variable. Whenever I reach the given node, I return the tracked predecessor value.
public int inorderPredecessor(BST root, int x, int pre) {
if (root != null) {
pre = inorderPredecessor(root.left, x, pre);
if (root.value == x) {
System.out.println("Predecessor = " + pre);
return pre;
}
pre = inorderPredecessor(root.right, x, root.value);
}
return pre;
}

arsragavan
March 23, 2014 This is same as printing all the permutations of the string..
public void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else
for(int i = 0;i < n;i++)
permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
}

arsragavan
March 23, 2014 No, my solution asks to look for any character of string a in string b..
From your example: characters in string a = {a,b,c}
While traversing string b, it detects character c and then generate two possible combinations  cab, cba and check whether the combinations are present in string b which will be found. So, will return true..
We can maintain the characters of string a in a hashmap so that search will take just O(1) time for each of the characters of string b.
Will this one work...
Search for the occurrence of any character of string a in string b. Let this character be x.
If found, generate all anagrams of string a starting with x and check whether the same pattern is found in string b.
If found return true, else continue finding the next character
Nope, consider a rightskewed tree with node values  5(root), 10, 15, 20.
Now Inorder predecessor(10) = 5. Your code will return null
Should we memoize based on the input string str ?
If yes, which is the best one to maintain a hashmap with str as key or maintain array with length of string ?
To budsiya: Can we use something like a priority queue which maintains the records by time so that we can get the records stored in the last 10 minutes easily.
 arsragavan March 21, 2014Looks like the implementation of Observer design pattern
 arsragavan March 21, 2014If you are going to sort the arrays, you can find the intersection of arrays via 2way merge instead of going for binary search. It's much simpler than the binary search. It doesn't reduce the complexity by any means but it will be much simpler..
 arsragavan March 20, 2014Do the same functionality as palindrome function does with below modifications:
a) you can convert the string to all lowercase
b) consider only ASCII characters within range 97122 (az)
You can solve it in linear time. You need extra space.
Store the elements of array B in hashmap with values as keys.
traverse through array A. If the element is found in the hashmap include it in the output array.
The solution for this is called three way partition or the dutch national flag problem. This can be done using linear time and constant space.. Algorithm is available in wiki page:
 arsragavan March 18, 2014ya sorry.. I will edit it
 arsragavan March 17, 2014HashMap : Insert  O(1), search (by key) O(1)
Array : Insert  O(1), search O(n)
Linked List : Insert  O(n), search O(n)
Queue : Insert (by front pointer)  O(1), search O(n)
public Tree delete(Tree root, int x) {
if (root == null) {
return null;
} else if (x < root.value) {
root.left = delete(root.left, x);
} else if (x > root.value) {
root.right = delete(root.right, x);
} else {
if (root.left == null && root.right == null) {
root = null;
} else if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
Tree temp = find_min(root.right);
root.value = temp.value;
root.right = delete(root.right, temp.value);
}
}
return root;
}

arsragavan
March 12, 2014 Can you expand more.. I guess your technique might disturb the order..
 arsragavan March 09, 2014Maintain two arrays  front [ ] and rear [ ]
front maintains the product before the current index
rear maintains the product after the current index
then the product of current index i = front[i]*rear[i]
int [] product (int [] input) {
int [] front = new int[input.length];
int [] rear = new int[input.length];
int [] output = new int[input.length];
front[0] = 1;
rear[input.length1] =1;
for(int i = 1; i < input.length; i++)
front[i] = front[i1]*input[i1];
for(int i = input.length2; i >=0; i)
rear[i] = rear[i+1]*input[i+1];
for(int i = 0;i<input.length;i++)
output[i] = front[i]*rear[i];
return output;
}

arsragavan
March 07, 2014 I have a doubt.. We cannot heapify a tree unless it maintains the structural property right? Then how can we apply heapify
 arsragavan March 06, 2014Can you provide a better solution ?
 arsragavan March 05, 2014List merge(List head1, List head2) {
List result = null;
if (head1.data < head2.data) {
result = head1;
result.next = merge(head1.next,head2);
}
else {
result = head2;
result.next = merge(head1,head2.next);
}
return result;
}

arsragavan
March 05, 2014 public static int countPath(int m, int n) {
int [] [] count = new int[m][n];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if (i == 0  j == 0)
count[i][j] = 1;
else
count[i][j] = count[i1][j]+count[i][j1]+count[i1][j1];
}
}
return count[m1][n1];
}

arsragavan
March 05, 2014 Answer is stack. Push and Pop is O(1). For find_min, you can maintain a seperate stack which stores the min element so far and you can pop the element from this stack if the element is popped from the main stack..
 arsragavan March 05, 2014
Repleroydperry, Backend Developer at AppNexus
I am from the USA. I am 27 year old. I drive the train for my company Monk Home Funding ...
Repsharonpkarr, None at BT
Hi! My name is Mary. I am a writer for a variety of web and multiplatform applications.I am a ...
Reppaynealiciam, Apple Phone Number available 24/7 for our Customers at Adap.tv
Hello I am Sarah Cote, and I live in Missouri, USA. Last year, Web trailblazer. Passionate entrepreneur. Subtly charming bacon ...
Open Chat in New Window
As ninhnnsoc pointed out, your solution has a worse complexity than O(n^2). Your time complexity is exponential. The code with the memoization technique which produces O(n^2) complexity is,
you have to call the function as,
 arsragavan May 04, 2015