aditya.eagle059
BAN USER- 0of 0 votes
Answersgiven n-ary tree. zigzag level order traversal.
- aditya.eagle059 in India| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 0of 0 votes
Answersgiven unsorted array and a number K. Find 2 numbers such that sum is K
- aditya.eagle059 in India| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 0of 0 votes
Answersthere are M chocolate packets each packet can have variable number of chocolates in each packet.
- aditya.eagle059 in India
There are N students (N<M).
Distribute chocolate packets to student such that
1) each student gets 1 packet
2) suppose m1,m2,...mn are the packets which are chosen to be distributed in sorted order of number of chocolates in them (nm-n1 must be minimum)
M = 1, 3, 4, 6 (4 packets with specified number of chocolates in them)
N = 2
Ans = 3,4| Report Duplicate | Flag | PURGE
Flipkart SDE-2 - 0of 0 votes
AnswersImplement a hashset of size M for numbers.
- aditya.eagle059 in India
Minimum candidate number will be 1, maximum candidate number can be N. (N>M)
I said simply to initialize an array of size N. when a number X comes in set Arr[X]=1. For lookup return the value of Arr[X].
He was fine with it, but asked me to give a better algorithm where initialization of array is NOT required. In above case we are assuming all elements of arr will be initialized to 0.
How can we do this any ideas ?| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThere is an external array of integers on which you can perform the following operations in O(1) time.
- aditya.eagle059 in United States
1. get(int i) - returns the value at the index 'i' in the external array.
2. reverse( int i, int j) - returns the reverse of the array between index positions i and j (including i and j).
example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return {3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.
Write a code to sort the external array. Mention the time and space complexity for your code.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer
Median(a,b,c)
{
return a+b+c - (Max(a,Max(b,c)) - Min(a,Min(b,c)));
}
Median(a,b,c,max,min)
{
return a^b^c^min^max;
}
suggesting a simple design
we keep N iterators given as input in a doubly linked list
DoublyList<Iterator> list
hasNext() { return list.count>0 }
Next()
{
value = list.First.Next();
Iterator I = list.RemoveFirst();
if(I.hasNext()) { list.Append(I);}
}
even if the root to leave path is 2->3->1 and should be 1 as last node fulfills the condition (i guess)
FindNumberOfNodes(N,max)
{
if(N==null) return 0;
bool isCoditionSatisfied = N<max;
l = FindNumberOfNodes(N.Left, (isCoditionSatisfied) ? N.data : max)
r = FindNumberOfNodes(N.Right, (isCoditionSatisfied) ? N.data : max)
return l + r + ((isCoditionSatisfied) ? 1:0);
}
use sum and carry technique
Sum(string s1, string s2)
{
int [] n1 = new int[s1.Length];
int [] n2 = new int[s2.Length];
int max = s1.Length > s2.Length ? s1.Length:S2.Length;
for(i=0;i<s1.Length;i++) n1[s1.Length - 1 - i] = (s1.charAt(i) == '0') ? 0 : 1;
for(i=0;i<s2.Length;i++) n2[s2.Length - 1 - i] = (s2.charAt(i) == '0') ? 0 : 1;
int carry = new int[((s1.Length > s2.Length) ? s1.Length + 1 : s2.Length + 1) * 2];
int sum = new int[(s1.Length > s2.Length) ? s1.Length + 1 : s2.Length + 1];
bool loop = false;
int i=0;
do
{
loop = false;
if(i==0)
{
for(i=0;i<max;i++)
{
sum[i] = ((i<s1.Length) ? s1[i] : 0) ^ ((i<s2.Length) ? s2[i] : 0);
carry[i+1] = ((i<s1.Length) ? s1[i] : 0) & ((i<s2.Length) ? s2[i] : 0);
loop |= (carry[i+1] == 1) ? true ? false;
}
}
else
{
for(i=0;i<max;i++)
{
sum[i] = (sum[i]) ^ (carry[i]);
carry[i+1] = (sum[i]) & (carry[i]);
loop |= (carry[i+1] == 1) ? true ? false;
}
max = i+1;
}
}while(loop);
StringBuilder sb = new StringBuilder();
for(i=max;i>=0;i--) sb.append(sum[i]);
return sb.ToString();
}
(.8)(K-C)(.2)^(n-1)
here n is the Nth attempt to launch
string GetRandomString(String [] strs, double [] probs)
{
double maxProb = 0.0;
String result=null;
for(int i=0;i<strs.Length.i++)
{
double prob = probs[i] * Random*nextFloat();
if(prob > maxProb)
{
maxProb = prob;
result = strs[i];
}
}
}
My idea is to draw a diagonal and divide the polygon
NonIntersectingDiagonals(N, K)
{
totalSolutions=0;
if(K==1) return N*(N-3)/2;
if(N<4) return 0;
for(int i=3;i<=N-1;i++)
{
for(int j=0;j<=K;j++)
{
totalSolutions += NonIntersectingDiagonals(i,j)*NonIntersectingDiagonals(N-i+2, K-j);
}
}
return totalSolutions*N;
}
Answer should be LRU's tail ?
- aditya.eagle059 March 17, 2015should this work ?
S = Sum(CandleLengths)
let n=number of days
solve the equation n(n+1)/2 = S
N has to be multiple of 2^K?
eg: 123456 does not have a solution if k=2
12345678 has a solution for k=2
the question that makes sense to me is that setup is given with a circle and N points.
Then multiple queries are made with different points outside the above circle. Each query should return closet point from N point set.
well not really O(1) space but recursion can solve this problem without actually we allocating memory
count number of evens
recursively keep storing the numbers, and when recursion is returning position the numbers.
arrange(Arr)
{
int o= -1 // next odd position
int e=Arr.length - CountEvens(Arr) -1 // next even position
int i=0 // current counter position
Arrange(Arr, &o, &e, &i)
}
Arrange(Arr, &o, &e, &i)
{
if(i>=Arr.length) return;
N = Arr[i]; // save the number
if(A[i]%2==0) e++ //even increment
else o++ // odd increment
i++;
Arrange(Arr,&o,&e,&i)
if(N%2==0) {A[e]=N; e--;}
else {A[o] = N; o--;}
}
if at each nanosecond an increment request is coming then it might consume 10^9*3600*24 bytes = 777PB
if interviewer has mentioned that we have nano sec accuracy then we have to serve the accuracy in providing the answer.
one solution i can think of is to write all entries in the file
File F
long counter // using it as string because long cannot hold more than 9 digits
increment()
{
F.Append(Time() + ":" + ++counter)
}
getCountInLastSecond()
{
long currentTime = Time()
long lastcounter = BinarySearchInFile(currentTime - Math.Pow(10, 9))
return this.counter-lastcounter;
}
// similarly we can implement other get methods
recursion is the solution. although recursion uses its own stack but in interviews its considered to be O(1) space
1a 2b 3c 4d 5e
public static void Convert(char [] A, int i)
{
if(i>=A.length/2) return;
char b = A[2*i + 1];
A[i] = A[2*i];
Convert(A,i+1);
A[(A.length/2)+i] = b;
}
M = Given matrix
Queue dequeue = put all the G coordinates in the queue.
Queue queue = empty queue;
while(!dequeue.isEmpty())
{
Pair p = dequeue.Dequeue();
Enqueue all p's neighboring Rooms which are either '0' or less than 'p' value and increase its value by 1;
if(dequeue.isEmpty())
{
temp = queue;
queue = dequeue;
dequeue = temp;
}
}
NextNumber(int number)
{
int numbDigits = numberofdigits(n);
int [] digits = GetDigits(N+1);
if(digits.length >9) return -1;
int default = 123456789;
bool isdefault = false;
for(int i=0;i<digits.length ;i++)
{
if(9-digits[i]<=digits.length-i-1) { isdefault = true; break;}
if(i>0 and digits[i]<digits[i-1]) digits[i] = digits[i-1] + 1;
}
if(isdefault) return default/(10^(numberofdigits+1))
else converttonumber(digits);
}
O(NlogN) solution
1) sort the pairs based on their start time : complexity O(NlogN)
2) iterate over start times: s=startTime, e=corresponding end time
for each (s,e) find s' such that s'<e (using binary search)
number of overlapped timeranges with (s,e) N = index of s' - index is s + 1
return maximum N encountered
1) Create lists for each "NumberOfTall"
2) Sort each list separately
3) Modified-Merge sort two consecutive list at time keeping in mind the conditions for "Height" and "NumberOfTall"
I can come up with a NlogN complexity algo if lengths given are in random order.
Incase the lengths are sorted then complextity would be O(N)
Lengths = Array.Sort(Lengths)
int [] IncrementalLength = new int[Lengths.length + 1]
for(int i=1;i<=Lengths.length;i++)
incrementalLength[i] = incrementalLength[i-1] + Lengths[i-1]
TotalSum = SumArray(incrementalLength)
return TotalSum
int average = AVG(Arr) // length =N
int sum = Sum(arr)
difference = sum - N*average
if(difference ==0) return n
remove X elements from arr such that (Sum(X elements) - average*X = difference)
return N-X
magically in my program below i am observing with few examples that number of outer iterations are limited to just 2. :)
order(Arr[], Seq[])
{
for(int i=0;i<Arr.length;i++)
{
bool requireFurtherIterations = false;
for(int j=0;j<Arr.length;j++)
{
if(j!=Seq[j])
{
Swap(Arr, Seq, j)
requireFurtherIterations = true;
}
}
if(!requireFurtherIterations) break;
}
}
Swar(Arr[], Seq[] , j)
{
int newIndex = Seq[j]
int temp = Arr[j]
Arr[j] = Arr[newIndex]
Arr[newIndex] = temp
temp = Seq[j]
Seq[j] = Seq[newInndex]
Seq[newIndex] = temp
}
magically in my program below i am observing with few examples that number of outer iterations are limited to just 2. :)
order(Arr[], Seq[])
{
for(int i=0;i<Arr.length;i++)
{
bool requireFurtherIterations = false;
for(int j=0;j<Arr.length;j++)
{
if(j!=Seq[j])
{
Swap(Arr, Seq, j)
requireFurtherIterations = true;
}
}
if(!requireFurtherIterations) break;
}
}
Swar(Arr[], Seq[] , j)
{
int newIndex = Seq[j]
int temp = Arr[j]
Arr[j] = Arr[newIndex]
Arr[newIndex] = temp
temp = Seq[j]
Seq[j] = Seq[newInndex]
Seq[newIndex] = temp
}
worst case complexity will N^2 but in general it will be less than that
findminseq(arr, sum)
{
int minsequeence = Integer.Max;
for(int i=0;i<arr.length;i++)
{
minsequence = Minimum(findminseq(arr, sum-arr[i], i+1) - i + 1, minsequence);
}
return minsequeence;
}
findminseq(arr, sum, index)
{
for(int i=index;i<arr.length;i++)
{
if(arr[i]-sum>=0)
return index;
else
return findminsequence(arr, sum-arr[i], i+1);
}
return Integer.Max;
}
hmm nice findings.
minsquares(int N)
{
if(N==0 || N==1) return N;
int squareRoot = sqrt(N);
return Math.Min(1+minsquares(N - squareRoot*squareRoot), 1+minsquares(N - (squareRoot-1)*(squareRoot-1))
}
but there are more corner cases then we might have to take the DP way :)
- aditya.eagle059 February 03, 2015inputing the sorted array.
1) to sort the array complexity would be NlogN
2) choosing A, complexity would be N
3) choosing B, complexity would be again N.
4) choosing C, max number such that c<=d-a-b
overall complexity would be NlogN + N^2logN = N^2logN
sum3([] arr, index, D, nth, List<int>AB)
{
if(nth==1)
{
c=binarySearch(arr, D)
for(int i=c;i>=0;i--) print(AB, arr[i])
}
else
{
List<int> AB = new List<int>();
for(int i=index;i>0; i--)
{
if(D<arr[i]) continue;
sum3(arr, i, nth-1, AB.add(arri[i]));
}
AB.remove(arr[i]);
}
}
inputing the sorted array.
1) to sort the array complexity would be NlogN
2) choosing A, complexity would be N
3) choosing B, complexity would be again N.
4) choosing C, max number such that c<=d-a-b
overall complexity would be NlogN + N^2logN = N^2logN
sum3([] arr, index, D, nth, List<int>AB)
{
if(nth==1)
{
c=binarySearch(arr, D)
for(int i=c;i>=0;i--) print(AB, arr[i])
}
else
{
List<int> AB = new List<int>();
for(int i=index;i>0; i--)
{
if(D<arr[i]) continue;
sum3(arr, i, nth-1, AB.add(arri[i]));
}
AB.remove(arr[i]);
}
}
shouldn't simple inorder work ?
int inorder(Node root)
{
if(root == null) return -1;
int l,r;
if(root.left != null) l = inorder(root.left);
if(root.right != null) r = inorder(root.right);
return Math.max(Math.max(l,r), root.value);
}
it should be simple to implement.
If english alphabets were from 1-99 then solution would have been (2n-1)
Since alphabets are till 25, we need to iterate through the list and figure out how many adjacent digits form a number more than 25 and exclude them from the ans.
number_of_string(int [] arr)
{
int exclude = 0;
for(int i=1;i<arr.length;i++)
{
if(arr[i-1]*10 + arr[i] > 25) exclude++;
}
return 2*arr.length -1 - exclude;
}
Aren't we supposed to use squareroot function ?
If not then we can implement our own.
Algo for current problem
minsquares(int N)
{
if(N==0 || N==1) return N;
int squareRoot = sqrt(N);
return 1+minsquares(N - squareRoot*squareRoot)
}
Below is java program-cum-algo that uses pass by reference or pointer
FindKth(Node Root, k)
{
List<Node> list = new List<Node>();
Inorder(root, k, list);
return (list.size>0)? list.get(0) :null;
}
This function will return -1 if we have already reached the kth element.
Once this function returns "list" (which is supposed to be pass by reference) should have the required element.
Inorder(Node N, int k, List<>list)
{
if(N==null) return 0;
int l = Inorder(N.Left, k ,list);
if(l==-1) return -1;
if(l==k-1) { list.add(N); return -1; } // we found the element
int r = Inorder(N.Right, k-l-1);
if(r==-1) return -1;
return r+l+1;
}
Agreed, but the question is how optimally you can do this.
- aditya.eagle059 May 10, 2015Approach can vary from O(N) to O(1).
You need to come up with best approach :)