teli.vaibhav
BAN USER- 0of 0 votes
AnswersSearch for a sorted integer in an integer array that has been rotated multiple times.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Samsung Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersGiven an alphabet where we do not know the order of the letters also do not know the number of letters.
- teli.vaibhav in United States
We are give an input list of tuples where each entry in the list gives an ordering between the 2 letters
Determine the alphabet order.
Ex-
<A, B>
<C, D>
<C, E>
<D, E>
<A, C>
<B, C>
Order is A, B, C, D, E| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 2 votes
AnswersHow would you design Amazon Lockers?
- teli.vaibhav in United States
Amazon Lockers - Customers can use these lockers to have their products delivered. These lockers are physically available to customers at the same or several nearby zip codes.| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersThe amazon site was working just fine until yesterday. But in the past 24 hours processing the customer orders is taking a really long time.
- teli.vaibhav in United States
How would you debug and fix the issue?
When I asked if anything had changed in the past 24 hours, I was told several new products had been added after which the performance issues were noticed.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Debugging - 3of 3 votes
AnswersGiven the root of a Binary Tree along with two integer values. Assume that both integers are present in the tree.
- teli.vaibhav in United States
Find the LCA (Least Common Ancestor) of the two nodes with values of the given integers.
2 pass solution is easy. You must solve this in a single pass.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersYou are given 2 lists -
List 1: List<Demand> is a list of Demand objects.
List 2: List<Supply> is a list of Supply objects.
Return a result fulfillment List<Demand,List<Supply>>.
This means each demand could be satisfied by more than one supplies.class Demand { Date startDate; Date expirationDate; int quantity; } class Supply { Date startDate; Date expirationDate; int quantity; }
The Demand and Supply refers to that of groceries. You must map supplies to a demand only if the supply still has at least 3 days remaining to its expiration before the demand can be fulfilled.
- teli.vaibhav in United States
A demand is said to be fulfilled 24 hours after all demands have been mapped to correspondingly available supplies.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - -1of 1 vote
AnswerWrite code for the partition subroutine in Quicksort.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswerHow would you Design a HashTable?
- teli.vaibhav in United States
In what ways would you attempt to address collisions?| Report Duplicate | Flag | PURGE
Amazon SDE-2 design - 0of 0 votes
AnswersFor this problem, we would like you to think of a single line of text, and justify that text into a buffer,where the first character of the line of text is in the first spot in the buffer and the last character of textis in the specified slot in the buffer.
In ruby, you might define this function as follows:def justify(line, length)
It might be called like this:
puts justify("The quick brown fox jumps over the lazy dog.", 52)
It produces a string that looks like this:
- teli.vaibhav in United StatesThe quick brown fox jumps over the lazy dog. 1234567890123456789012345678901234567890123456789012 (You have 7 characters remaining in the buffer)
| Report Duplicate | Flag | PURGE
RealSelf Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is indexing in a database?
- teli.vaibhav in United States
What are the underlying data structures you think are involved in indexing of a database?
What are some upsides and downsides of using indexing?| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an array of integers. Find the surpasser count of each element of the array.
- teli.vaibhav in United States
"A surpasser of an element of an array is a greater element to its right"
ex -
Input: [2, 7, 5, 3, 0, 8, 1]
Output: [4, 1, 1, 1, 2, 0, 0]| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of integers and a sum 'S'. Find 2 integers in the array that add up to S.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFind the first unrepeated character in a given string. Solve this in a single pass.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a list of sorted arrays, like List<int[]>. Prepare and return a single sorted list.
- teli.vaibhav in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
- teli.vaibhav in United States
ex-
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersGiven a string which may contain parenthesis. We must verify the validity of the string.
- teli.vaibhav in United States
ex-
1) "<ad675+-fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question -
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex - <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm
- 1 Answer Printing all permutations of a String with repeated characters
I wanna print all permutations of lets say a char[] array for simplicity. This array contains a few repeated characters.
- teli.vaibhav December 17, 2013
I need to get the result without going into any previous results.
ex- say we have ['a','c','a','b']
I will print "aacb" when I encounter is the first time and I must not print it the second time, neither can I look into the previous result.| Flag | PURGE - 0 Answers Time and Space complexity
Could someone tell me what the time and space complexity of an iterative + recursive algorithm would be?
- teli.vaibhav December 15, 2013
ex:-
The following code snippet prints binary sequences. i.e if n=2,
The output is
00
01
10
11
public static void printBinarySequence(int n)
{
if(n<0)
return;
int[] temp = new int[n];
printBinarySequenceAux(n,0,temp);
}
private static void printBinarySequenceAux(int n, int d, int[] temp) {
if(d==n)
{
printArray(temp);
return;
}
for(int i=0;i<=1;++i)
{
temp[d]=i;
printBinarySequenceAux(n,d+1,temp);
}
}| Flag | PURGE - 7 Answers Space complexity for Recursive Binary Search
Space complexity for Iterative Binary Search would obviously be O(1) but with the recursive algorithm I believe the stack would use O(log n) space. However, everywhere I read I see the worst case complexity for BS O(1). Could someone please help me understand.
- teli.vaibhav November 07, 2013| Flag | PURGE
public boolean swapKthFromFirstAndLast(int k)
{
ListNode current=head,slow=head,temp;
int count=1;
while(count<k-1)
{
if(current==null)
return false;
current=current.next;
count++;
}
temp=current;
current=current.next;
while(current.next.next!=null)
{
current=current.next;
slow=slow.next;
}
if(temp.next==slow.next)
return false;
swap(temp,slow);
return true;
}
private void swap(ListNode a, ListNode b) {
ListNode tmp=a.next;
a.next=b.next;
b.next=tmp;
ListNode tmp1=tmp.next;
tmp.next=a.next.next;
a.next.next=tmp1;
}
Of course in the code here my ListNode head is an instance variable of my LinkedList class.
- teli.vaibhav April 18, 2013Even though 'A'^' A' is 0. Please help me understand how it would fail. The swap still happens correctly, doest it?
- teli.vaibhav April 05, 2013Hashtable would take up a lot of space. The question says the size is not known, that itself shows the input is very large. Moreover, you say the space is O(1). The space is O(n).
- teli.vaibhav March 30, 2013This is a nice solution. To make it clearer, we can say that we XOR the index of each slot with the value in the slot of the array. Finally we XOR with 'n', the size of the array. The result would be the missing one.
- teli.vaibhav March 29, 2013A B-Tree is not a binary tree, its a Bayer's Tree.
- teli.vaibhav March 28, 2013Though the question suggests that we just need to iterate in a for loop and print it, saying that it would almost be the same in either case and that the difference would be at the assembly level like prem has suggested would probably be correct. But pointing out that if we are allowed only a Singly Linked list and we are to iterate from the last element to the first then Array would be faster, would fetch additional points from the interviewer I suppose.
- teli.vaibhav March 15, 2013I've always heard Serializable is a marker interface. Does that mean that this interface has no declared methods?
- teli.vaibhav February 10, 2013Is there any empty class in the java library.. ? curious..
- teli.vaibhav February 10, 2013I think the scenario boils down to when one would use a BT over a BST..
- teli.vaibhav February 10, 2013Using hash is not allowed whether your write your own hash function or you use the one available in the java collections.
Sorting seems fine but it gives you O(n* log n) complexity.
A better means would be to declare a 256-bit BitSet. The index of each of the slots of this bit array would represent the Ascii code.
Now we just traverse through the given string and change the bit value in the BitSet(givenString.charAt(i)) from 0 to 1.
If we confront a 1 instead of a 0 for a character then we return false.
If we successfully traverse the whole string it implies the string has all unique characters.
O(n) would be the time complexity for this.
A Binary Tree is a tree in which each node can have maximum of 2 children.
Uses could be like a folder structure or the organizational hierarchy. It is used when there are no specific rules as to which node should be where, unlike in the case of a BST or a balanced tree which follow a set f rules.
An AVL tree is a balanced BST,it basically assures that the height of your tree is k*log n where k is a constant and n is the number of nodes in the tree. This in turn reduces the time complexity of an add, delete or a search operation to O(log n) which would normally be O(n) in a binary tree and O(h) in a BST.
I guess this answers the question for which is most efficient.
I do not know much about RB trees, but it too is a balanced BST like AVL trees and I believe that the implementation of operations in an RB tree are a lot more complex than that of an AVL tree but RB trees are apparently more secure and are used by several java libraries.
Please correct me if I'm wrong.
Oh look Mr. Wise Ass poops in.. if you have some technical wisdom then please preach else go fart elsewhere..
- teli.vaibhav January 29, 2013The question is vague.. What do you mean by an array of 0s and 1s of UNKNOWN size? If I am to write a method to implement the required functionality, I would have to pass the given array as argument and if I am a java coder array.length should simply give me the size.
I am guessing a stream on 0s and 1s would make more sense here, in which case even using a Vector may not be the best of solutions as the size of the data stream could eat up all the main memory crashing our program..
Yes.. I happened to miss that condition out..
Here is the code after incorporating the condition for equality:
package com.career.cup;
class MergeWithoutDuplicates {
static int[] getMergedArrayWithoutDuplicates(int[] firstArray, int[] secondArray)
{
int firstArraySize=firstArray.length;
int secondArraySize=secondArray.length;
int i=0,j=0,k=0;
int[] resArray=new int[firstArraySize+secondArraySize];
while(i<firstArraySize && j<secondArraySize)
{
if(firstArray[i]==secondArray[j])
{
resArray[k++]=firstArray[i++];
j++;
}
else if(firstArray[i]<secondArray[j])
resArray[k++]=firstArray[i++];
else
resArray[k++]=secondArray[j++];
}
while(i<firstArraySize)
resArray[k++]=firstArray[i++];
while(j<secondArraySize)
resArray[k++]=secondArray[j++];
return resArray;
}
public static void main(String[] args)
{
int[] firstArray={1,2,6,9,10,27};
int[] secondArray={2,8,10,89};
for(int resIndividualElement: getMergedArrayWithoutDuplicates(firstArray,secondArray))
{
System.out.println(resIndividualElement);
}
}
}
This solution works fine but since we created an array of size (m+n) and when there are duplicates, we dont use some of these slots in the result array we are returning which are initialized to 0. Can someone please suggest how we could avoid this without having to create a whole new array only to accommodate the size.
- teli.vaibhav January 27, 2013By doing that someone into java but not C can probably follow an idea or vice versa.
- teli.vaibhav July 11, 2012Could someone please explain an algorithm of what they have implemented. Figuring from code is exceedingly difficult.
- teli.vaibhav July 11, 2012That would be absolutely correct if the provided tree was a binary search tree. Which I assume it must have been as this is a question asked in a phone interview.
- teli.vaibhav July 11, 2012But the given input is a string. If we make a StringBuffer and make changes to get the result and again convert to a string using the toString() method in the StringBuffer. The string that we finally obtain and the string that was given as input would still be different strings due to their immutable nature. Can we still call such a computation an in-place one?
- teli.vaibhav July 10, 2012I have come up with a code in java which involves character by character computation in the same string. But String being immutable I am doubtful whether it is in place reversal or not. Can someone please verify this:
public class ReverseWordsInStringInPlace {
public static void revInPlace(String s)
{
int sLength=s.length();
int j=0;
int beginIndex=0;
for(int i=0;i<(sLength)/2;i++)
{
s=inPlaceSwap(s,i);
}
while(j<s.length())
{
if(s.charAt(j)==' ')
{
s=indexSwap(s,beginIndex, j-1);
beginIndex=j+1;
}
if(j==s.length()-1)
{
s=indexSwap(s,beginIndex, j);
}
j++;
}
System.out.println(s);
}
public static String indexSwap(String s,int beginIndex,int endIndex)
{
System.out.println(s);
char temp;
StringBuilder sb=new StringBuilder(s);
for(int i=beginIndex;i<=(endIndex+beginIndex)/2;i++)
{
temp=s.charAt(endIndex);
System.out.println(temp);
sb.setCharAt(endIndex,s.charAt(i));
sb.setCharAt(i, temp);
endIndex--;
}
s=sb.toString();
System.out.println(s);
return s;
}
public static String inPlaceSwap(String s,int index)
{
char temp;
int sLength=s.length();
temp=s.charAt(s.length()-1-index);
StringBuilder sb=new StringBuilder(s);
sb.setCharAt(s.length()-1-index, s.charAt(index));
sb.setCharAt(index, temp);
s=sb.toString();
return s;
}
public static void main(String[] args)
{
revInPlace("where are you");
}
}
I took the liberty to implement your algorithm:
package com.careercup;
public class Max1sIn2dArray {
public static int getMax1sIn2dArray(int[][] array,int m,int n)
{
int numberOf1s=0;
int maxIndex=0;
for(int i=0;i<m;i++)
{
System.out.println(array[i][1]);
maxIndex=getIndexOfLast1BinarySearch(array[i],1,0,n-1)+1;
System.out.println(maxIndex);
if(maxIndex>numberOf1s)
{
numberOf1s=maxIndex;
}
}
return numberOf1s;
}
public static int getIndexOfLast1BinarySearch(int[] array,int key,int startIndex,int lastIndex)
{
int middleIndex=(startIndex+lastIndex)/2;
if(array[middleIndex]==key && (middleIndex==lastIndex || array[middleIndex+1]==0))
{
return middleIndex;
}
else if(array[middleIndex]==key)
{
startIndex=middleIndex+1;
return getIndexOfLast1BinarySearch(array,key,startIndex,lastIndex);
}
else if(array[middleIndex]==0 && middleIndex!=lastIndex)
{
lastIndex=middleIndex-1;
return getIndexOfLast1BinarySearch(array,key,startIndex,lastIndex);
}
return -1;
}
public static void main(String[] args)
{
int noOfRows=4;
int noOfColumns=4;
int[][] inputArray={{1,1,0,0},{1,0,0,0},{0,0,0,0},{1,1,1,1}};
System.out.println(getMax1sIn2dArray(inputArray,noOfRows,noOfColumns));
}
}
With your logic i think the time complexity narrows down to O(m*log(n)) where m is the number of rows and n is the number of columns.
- teli.vaibhav July 08, 2012Its just the implementation of the first suggested algorithm where you reverse the entire string in the first scan and then reverse each word individually.
Can someone please tell me if using the split() method of the string class would be inappropriate or something in an interview?
code in java:
public class StringReverse {
public static String strRev(String s)
{
String reversedString="";
for(int i=(s.length()-1);i>=0;i--)
{
reversedString+=s.charAt(i);
}
return reversedString;
}
public static void reverseWordByWord(String s)
{
String wordFormed="";
String requiredString="";
for(int i=0;i<=s.length();i++)
{
if(i==s.length() || s.charAt(i)==' ')
{
wordFormed=strRev(wordFormed);
requiredString+=wordFormed+" ";
System.out.println(requiredString);
wordFormed="";
}
else
wordFormed+=s.charAt(i);
}
System.out.println(requiredString);
}
public static void main(String[] args)
{
String s="What is this";
String reversedString=strRev(s);
reverseWordByWord(reversedString);
}
}
No where close to linear time complexity..
- teli.vaibhav July 05, 2012using min heap would only complicate the comparison. Using max heap makes more sense.
- teli.vaibhav July 05, 2012@subrata: well.. I had the definition of a complete binary tree and that of a full binary tree mixed up.. your sarcasm helped clarify a basic concept for me.. thanx.. :)
- teli.vaibhav July 04, 2012This need not be the case, if we have even number of elements in the given inorder then it would not make a complete binary tree. We simply convert the array into a max heap.
- teli.vaibhav July 04, 2012yes. It just says inorder traversal of a tree not BST. And yes, the given condition is a waste, its as good as an arbitrary array given.
- teli.vaibhav July 03, 2012The time complexity for the above code would be O(n). This would be achieved in the case where a binary tree would have all nodes on its left or all nodes on its right.
The space complexity is Theta(n).
Apologies for the ugly look of the code. I suppose writing separate methods for swapping elements and for adjusting heap would make the code more readable.
The time complexity for the above code would be Theta(n) as all elements are traversed atleast once and less than twice.
And space complexity would be O(1), as we are doing all the manipulations on the same given array.
:-O
- teli.vaibhav July 03, 2012Here is the code in java taking the given inorder in an array:
class BuildMaxHeap {
public static void convertToMaxHeap(int[] array)
{
int temp;
int n=array.length;
for(int i=(n-1)/2;i>=0;i--)
{
int parentIndex=i;
while(getLeftChildIndex(array,parentIndex)<n)
{
Integer leftChildIndex=getLeftChildIndex(array,parentIndex);
Integer rightChildIndex=getRightChildIndex(array,parentIndex);
int maxChildIndex=leftChildIndex;
if(rightChildIndex!=null && array[rightChildIndex]>array[leftChildIndex])
{
maxChildIndex=rightChildIndex;
}
if(array[parentIndex]<array[maxChildIndex])
{
temp=array[parentIndex];
array[parentIndex]=array[maxChildIndex];
array[maxChildIndex]=temp;
parentIndex=maxChildIndex;
}
else
break;
}
}
for(int m:array)
{
System.out.println(m);
}
}
public static Integer getLeftChildIndex(int[] a,int parentIndex)
{
return (2*parentIndex+1);
}
public static Integer getRightChildIndex(int[] a,int parentIndex)
{
if(2*parentIndex+2<a.length)
return (2*parentIndex+2);
return null;
}
public static void main(String[] args)
{
int[] inorder={1,2,3,4,5,6};
convertToMaxHeap(inorder);
}
}
I am guessing the number of pairs involved in the overlapping are asked. Correct me if I'm wrong.
- teli.vaibhav July 01, 2012We can take 2 arrays of size n, assuming n pairs of events exist.
Sort the first array consisting of start times.
Sort the second array consisting of end times.
Now, just like in the case of merge sort we merge the 2 arrays. But in addition to the merging we maintain a count variable. During the merging if the element is being picked from the first array, it is a start point, so we increment the count as count++. Whenever we pick the from the second array of end points, we decrement the count as count--. At the end of the merging. The count value eventually will be the number of overlaps.
The time complexity is O(nlog)+O(nlogn)+O(n+n) =>O(nlogn)
nlogn for each sort and O(n+n) for the merging.
This gives us a better overall time complexity but I cannot retrieve the pairs with this procedure. Can someone come up with an idea for that.
public class Print1To500WithoutLoop {
public static boolean printNums(int n)
{
System.out.println(n);
n++;
boolean a=n!=501 && printNums(n);
return true;
}
public static void main(String[] args)
{
printNums(1);
}
}
I suppose the condition should have said, the seed is smaller than the number. That makes more sense as far as I understand.
- teli.vaibhav June 27, 2012I understood why a0 * a1 * a2 * ... * ai <= n/(10^i + ... + 1000 + 100 + 10 +1) but can someone please explain how the space above is narrowed down to log n?
- teli.vaibhav June 27, 2012There is no need to sort the mobile number strings. We make an array of TrieNodes of size 10. The indices of this array would represent numbers from 0-9. Now each of these 9 slots in the array would have another array of TrieNodes of size 10 and so on.
So if 6 is entered then everything under the first array[5] would be displayed.
Because that would result in unnecessary space wastage.
- teli.vaibhav June 25, 2012I suppose a Ternary Search Tree would give a fitting solution, but I am not confident about its implementation.
- teli.vaibhav June 25, 2012Were you asked to implement the datastructure or just name it?
- teli.vaibhav June 25, 2012Trie is the datastructure to be used.
- teli.vaibhav June 25, 2012
RepSandyBMartinez, iOS Developer
Searching for a simple and delicious homemade treats for dogs?Visit Healthy Dog treats online store and shop the best ...
RepWilliamDGiles, Cloud Support Associate at ADP
Spent 2001-2006 creating marketing channels for tar worldwide. Was quite successful at building tobacco for farmers. Won several awards for ...
Here is an in-place solution:
Efficiency suggestions are invited. :)
- teli.vaibhav April 18, 2013