words&lyrics
BAN USER 0of 0 votes
AnswersGiven a dictionary of words, two APIs
 words&lyrics in India
Is_word(string)
Is_prefix(string)
And a NxN matrix with each postion consisting of a character. If from any position (i,j) you can move
in any of the four directions, find out the all the valid words that can be formed in the matrix.
(looping is not allowed, i.e. for forming a word position if you start from (i,j) and move to (i1,j) then
from this position you cannot go back to (i,j)) Report Duplicate  Flag  PURGE
Amazon Applications Developer  0of 0 votes
AnswersQ1) Given that there are n players and each one of them has played exactly one game with every
 words&lyrics in India
other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and
‘b’ could be any of the players. Arrange the n players in a length n array such that player at position
‘i’ has won from player at ‘i+1’ and lost to player at ‘i1’
Interested in linear time solution
PS: Its not a sorting problem. Please notice that problem is not asking for ranking in decreasing order.. Report Duplicate  Flag  PURGE
Amazon Applications Developer Algorithm
Can somebody explain the recursion?? Why it's working?
 words&lyrics August 04, 2012@I am not here to get votes on my answer. It's a public forum , where people contribute and get their doubts cleared. A healthy discussion is always a good thing. But This is not the way. Tail recursion is the first thing I suggested please see my post. But i didn't claimed O(1) space complexity.
 words&lyrics August 04, 2012Mathematics is wrong. But correct code!
 words&lyrics August 02, 2012+1
 words&lyrics July 31, 2012It's not mirror image.
 words&lyrics July 31, 2012When we merge two lists , we compare the smallest not inserted element of the the two list two decide which will be the new element of the new list. This is done till one gets empty. In this case empty for circular list would mean when iterator becomes equal to head again.
 words&lyrics July 31, 2012Push every thing in stack. And pop and swap one by one. Another is recursive approach which uses internal stack. I doubt this can be solved without using extra memory. Recursion also uses stack.
A recursive function
void rotate(int a[], int n, int *left,int right)
{
if(right==n)
return ;
rotate(a,n,left,right+1);
swap(a[*left],a[right]);
(*left)++;
return;
}
Call this as
int left =0,right =0;
rotate(a,n,&left,right);
Corrected!
See this
codepad.org/tKbYOpCE
I don't think they are asking answer for comparison sort. Option doesn't make sense in that case. Even worst of comparison sorts in worst of cases will give less number of comparison than the given option
 words&lyrics July 30, 2012Well I don't have the book.
Think in this way
My buckets will be link lists in an array say,
buck[10]
when I need to push a digit say i, in its corresponding bucket
the bucket will be buck[i]. What comparison I did?? ith bucket is mapped to ith location.
You don't need to compare with each bucket. 1 will go in bucket 1 , 2 will go in bucket 2 .....
 words&lyrics July 30, 2012Number of buckets will be 10.
 words&lyrics July 29, 2012counting +radix sort
answer is 40
First MSB will be sorted using counting or bucket sort (both are stable sorts) total number of buckets will be 10 (decimal base 10) so 10 comparisons. similarly for other digit positions.
Total comparison 4*10 =40
Inplace (Working code!)
ideone.com/u1oS4
#include<stdio.h>
#define n 3
void printm(int (*a)[n])
{
int i,j;
for(i=0; i<n; i++)
{
for(j=0;j<n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
}
void rotate(int (*a)[n])
{
int i,j,temp,l;
for(i=0; i<n/2;i++)
{
l=n2*i;
for(j=0;j<l1; j++)
{
temp = a[i+j][i];
a[i+j][i] = a[n1i][i+j];
a[n1i][i+j] = a[n1ij][n1i];
a[n1ij][n1i] = a[i][n1ij];
a[i][n1ij] = temp;
}
}
}
int main()
{
int a[][3]={{1,2,3},{4,5,6},{7,8,9}};
printm(a);
printf("\n\n\nAfter Rotation\n");
rotate(a);
printm(a);
return 0;
}
 words&lyrics July 28, 2012Breaking in sub problems can give better run time. To decide how to break, we need DP
 words&lyrics July 28, 2012Have one more pass to store the number as they were in original array. This would be something like this.
if(ceil(a[i])==floor(a[i]))
a[i]= int(a[i]);
This won't work if there are numbers like 2.0 , 3.0 in the original array.
You can do one more thing. Sort the number by any method . For all comparison do something like this
if((float)a >float(b)
..
Make all other operations (swapping) with original values
Nklog(N) not Nklog(NK) in this case
as lists will be atleast of k size
For binary tree This is true. But BST has some properties of it's own and its not just any binary tree. For BST we can build with either post or pre order alone. But not with inorder alone
 words&lyrics July 26, 2012This is in place Array transpose.
Working code!
http://codepad.org/GzIUMLjy
#include <stdio.h>
int get_index(int idx, int N) {
return (idx % 3) * N + (idx / 3);
}
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void transform_array2(int *s, int len) {
int N = len / 3,i;
for(i = 0; i < len; i++) {
int new_idx = get_index(i, N);
while(new_idx < i) {
new_idx = get_index(new_idx, N);
}
printf("i: %d; new_idx: %d\n", i, new_idx);
swap(&s[i], &s[new_idx]);
}
for(i = 0; i < len; i++) {
printf("%d ", s[i]);
}
printf("\n");
}
int main()
{
int arr[]={1,2,3,4,5,6,7,8,9,10,11,12};
transform_array2(arr,12);
return 0;
}
 words&lyrics July 26, 2012Good!
Few points:
This is sufficient!
static int r[]={0,0,1,1,1};
static int c[]={1,1,1,0,1},k;
in total five adjacent points. This is because,
outer loop for countImage ensures for any point with x coordinate i , ( (0..i1), j) have been already visited.j can have any value here
Secondly why are vectors r anc c static??
Third:
You are modifying the original input . You can use an auxiliary array for marking visited. And use stacks for DFS you can avoid recursion.
This can be done non recursively
for(i=0 i<n; i++)
for(j=0; j<n ; j++)
if(a[i][j])
{
count ++; //one image found
point tmp = point(i,j);
while(!queue_empty(&s))
{
//enqueue all previously not visited neighbors of tmp (which are 1) in the queue
tmp = dequeu(s);
}
// This image finished now search other
}
Correct!
Just build the tree!
Got it!
Never mind!
Make a binary tree with a node having an extra field for counting number of elements
in it's right sub tree.
Now insertion will be like this:
Say root is (Xr,Yr) and element to be inserted is x,y
if x>Xr and y>yr , (x,y) will go to right sub tree and count for root node will be incremented
In all other cases coming node will be inserted in left subtree
Traverse the tree too get the sum of count
logic??
 words&lyrics July 22, 2012@niraj: Recursion internally uses stack to function so this is again not avoiding memory constraint!
 words&lyrics July 22, 2012I missed a return after the success check (in case where sucess has already been achieved )
 words&lyrics July 22, 2012search for extreme set of points on the three axes that is with minimum and maximum x coordinate andd similarly for other two axes. (can be multiple points on a plane)
These points will be in 6 different planes each having multiple points ( at faces of cuboid)
Now same problem reduces to finding minimum points in a 2d plane which will enclose all the points in that plane . Now again do similar step that is forming pair of extreme along x and y coordinate . These points will be included . For left over points they may or may not be included . They will be included if they don't lie in the existing figure .
This can be checked as follows.
Consider A,B,C,D points (three are already included so check for 4th one if this is already in the figure or not)
D is within ABC if
Area (ABC)= Area(ABD)+AREA(BCD) +AREA(ACD)
If true no need to include . Otherwise include
This can be extended for any number of points
gcc test.c &; ls >txt &; uname a;
This will compile test.c in background and ''ls" will run while with it's
output being redirected to txt so again everything in background on screen
you will get output of third command (program)
This should do I guess!
recurse(&success_flag, args....)
{
if(!(*success_flag))
recurse(sucess_flag, args...);
if(success)
*success_flag = 1;
}
@Selme... What is not true?? Better try the code and see for your self!
 words&lyrics July 19, 2012O(n)
1. Make all zeros 1
2. change array such that a[i] = a[i] + a[i1] (cumulative sum)
3.Now look for two location i,j such that a[i]=a[j] and choose
such that ji is maximum possible. Same numbers at two location means cumulative sum of numbers between them is zero. For largest such sub array this range should be maximum . This step can be done by hashing with key as number and storing first and last occurrence of that number
But there can be one more possibility, i.e cumulative sum itself zero up to some point (a[k] =0). Choose maximum k , i.e farthest location where 0 is stored
Return MAX( (ji) , k)
If for SISC than no written just interview
for SEL there will be written for under 3 years of experience .It will focus on
basic knowledge of c
There are some very good examples in geeksforgeeks.org archives .
Search under dynamic programming tag
I have considered that case!
When the numbers of negative numbers are odd you will discard the number with minimum absolute value and use max instead
@incognitosj
I think we need to do some more modification to above approach!
1. We need to maintain number of negative nodes inserted.
2. We need to keep track of greatest positive number from those inserted or deleted from the heap at any point of time.
say max.
In the final heap if number of ve numbers is odd use the max from above along with other two positive nuumber
else you have the solution.
Note: Original numbers will be inserted in the heap with proper sign just comparison while inserting will be based on absolute values
In the above example:
Number of odd numbers in final heap is odd so we will discard the negative number and calculate product using other two and max (42)
Please comment if any error!
This is the right approach!
Just when lengths are equal you need to check for both first and last nodes!
Consider a tree structure for the directory.
Read the input and while input string is not over do following for
each element after 'cd '
switch(ch)
current directory will be root.
when command is
case 1. cd a
two possibilities
a) There is a child directory a, you need to go to this node
b) No child directory called a stop and print error
case 2 cd .
Do nothing. '.' means current directory
case 3 cd ..
Go to parent
@log... Thanks for pin pointing. Sorting on the basis of rank can give one solution. But ranking itself will be O(n2)
 words&lyrics July 18, 2012You will get linker error!
Compiler only looked for names for binding not the type so int *a was binded to int a[] (basically that means both a have same address). If you try to print '&a' in file 1 and '&a' in file 2 you will get same address. so both the pointers are at same location.
So basically binding is some what like this
&a = &a; instead of a = a
Although the pointer addresses are same the content at the addresses ('a ' not *a )) is not. In first case it was the addresses of first element of array (const int*) , in second case it is NULL. Why it is happening is something , that can be attributed solely to compiler architecture . Here what is happening is , a const int* cannot be converted into int* so the compiler decides to Make it NIL.
This will work;
file 1: char* a =&('a')
fil2 2; extern int *a;
print *a; //off course with %c to avoid memory infringement
because char* can be type casted to int*
In your example even access to *a is in valid as it is essentially Null.
My final conclusion is may be on different compiler the results will be diffrent as it is clearly upto compiler how to handle.
This is O(n)
I just need to make list of element greater and less than root for both and then compare corresponding lists for equality!
I got this!
Thanks for pointing
Sorry I mean j can be b/w 0 and maxmin
so j+min is between 0 and max
Please look at the solution again! Either I don't understand you or you missed something. Can you explain how I have assumed that?? I didn't intended
so please pinpoint it.
I didn't understand what you mean! My only assumption was that they are of same sign. Can you
be more clear??
Please look again j can be between min and maxmin
so j+min is between min to max, where min and max are minimum and maximum in the array
@eugene: I agree, but I specified them. And I guess interviewer was looking for this approach as well as
otherwise it seems is not possible to come up with a solution for this!
Sorry I missed one condition!
After forming the heap once, If incoming element is larger than root replace!
In your example! Below is the heap formation and you need to compare only absolute values . 100 is converted to 100

12
100 42

42
100 89

89
100 103


words&lyrics
July 18, 2012 O(n) time O(1) Space
1. Find max and min
2. Traverse the array and for each a[i] change sign of a[[a[i] min]]
Each time a element is found sign of location corresponding to that
(mapped to a[i]min) changes sign. So same sign after this traversal means
even number of occurrences, different sign means odd no. of occurrences
3.Finally traverse the array from i =0 to i = maxmin
and look for ve element at location 'j'.
4. Return j+min
This algorithm will work only if all elements are of same sign initially
No need to the element to be in any range!
See my comment below for the approach!
???
 words&lyrics September 22, 2012