Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
awesome!my code is basically common with yours, the only difference is I had not used recursive。
it was not complete code.
Now it is complete. I have not run many test cases, let me know the ones which fails ...
It fails for {5, 4, 0, 3, 1, 6, 2} : your code gives 5 as output but the correct answer is 4 for S[2] = {0,5,6,2}.
thanks buddy,
it should be return 0 in place of return S[i] in breaking condition.
if (S[i] != 0)
return 0;
corrected !!! :)
#include<iostream>
using namespace std;
int main(int argc, char **argv)
{
int N;
int max, result;
int i, j;
cin >> N;
int *visit_num = new int[N];
int *data = new int[N];
int *st = new int[N];
int top;
bool *is_visited = new bool[N];
for (i = 0; i < N; i++) {
cin >> data[i];
}
for (i = 0; i < N; i++) {
visit_num[i] = 0;
is_visited[i] = false;
}
result = -1;
for (i = 0; i < N; i++) {
if (visit_num[i] != 0) {
continue;
}
j = i;
top = -1;
do {
st[++top] = j;
is_visited[j] = true;
j = data[j];
} while (is_visited[j] == false);
max = top + 1;
if (visit_num[j] != 0) {
max += visit_num[j];
}
if (max > result) {
result = max;
}
for (j = 0; j <= top; j++, max--) {
visit_num[st[j]] = max;
}
}
cout << result << endl;
return 0;
}
// Keeps a count of the depth (number of rucursive calls)
int count;
// Stores the visited elements' INDEX
int* done;
// Returns the number of calls possible without going
// beyond bounds and makes sure it does not visit
// already visited elements
void get_depth_for(int *i, int m, int size)
{
// We continue only if the index is within bounds
if(m < size)
{
// To know if the node has been visited aleady
int found = 0;
for(int x=0; x<count; x++)
{
if(done[x] == m)
{
found = 1;
break;
}
}
if(0 == found)
{
// If we are here, that means
// the index has not been visited
// AND
// the index is within bounds
done[count++] = m;
// MOST IMPORTANT PART!
// Call the function recursively with
// the element at index m as the index
// of the next element
get_depth_for(i, i[m], size);
}
}
}
int main()
{
int i[4] = {3, 1, 2, 0};
int m;
int highest = 0;
done = malloc(sizeof(i));
for(m=0; m<4; m++)
{
count = 0;
get_depth_for(i, m, sizeof(i));
if ( highest < count )
{
highest = count;
}
}
printf("%d\n", highest);
return 0;
}
How about this?
for (i = 0; i < N; i++) B[i] = 0;
for (i = 0; i < N; i++) {
if (B[i]) continue;
S = {}
k = i;
while (!B[k]) {
B[k] = 1;
k = A[k];
S = S + {k}
}
print S;
}
for (i = 0; i < N; i++) {
if (A[i] < 0) continue;
S = {}
k = i;
while (A[k] >= 0) {
k = A[k];
A[k] = -A[k] - 1;
S = S + {k}
}
print S;
}
for (i = 0; i < N; i++) {
A[i] = -A[i] - 1;
solution in Ruby.
To avoid array search, use 2 hashes to
1. detect duplicate set, determined by the a[i]
2. detect duplicate number in a set.
The computation complexity is O(n)
a = ARGV[0].split(",").map {|x| x.to_i}
n = a.size
h = {} #store the a[i]
total_loop = 0 #count the compute complexity
puts "input:" + a.to_s
puts "output:"
#a[0] to a[n-1]
(0..n-1).each do |i|
total_loop = total_loop + 1
v = i
k = a[v]
next if !h[k].nil? #a[i] already stored? if yes, the same set already found, ignore
h.merge! k=>i #remember a[i]
new_h = {} #hash to store the new set
lp = 0
# stop the loop while find duplicate value and exceed the array boundry
while (new_h[k].nil? and v < n) do
lp=lp+1 #count the inner loop
new_h.merge!(k=>v)
v = k
k = a[v]
end
total_loop=total_loop+lp
puts i.to_s+" loop:"+lp.to_s + "\t" + new_h.keys.to_s
end
puts "n = " + n.to_s + ", total loop= " + total_loop.to_s
ruby largest_set.rb 5,4,0,3,1,6,2
input:[5, 4, 0, 3, 1, 6, 2]
output:
0 loop:4 [5, 6, 2, 0]
1 loop:2 [4, 1]
2 loop:4 [0, 5, 6, 2]
3 loop:1 [3]
4 loop:2 [1, 4]
5 loop:4 [6, 2, 0, 5]
6 loop:4 [2, 0, 5, 6]
n = 7, total loop= 28
Recursive Version
#include <stdio.h>
#include <string.h>
#include "ctype.h"
int max = 0;
int count =0;
void findSet(int a[],int n,int first,bool isFirst)
{
if(!isFirst && (a[n] == n || a[n] == first))
{
printf("]\n");
return;
}
printf("%d ",a[n]);
count ++;
findSet(a,a[n],first,false);
}
void main()
{
int a[8] = { 5,4,7,0,3,1,6,2};
for (int i = 0; i<8 ; i++)
{
printf("[");
findSet(a,i,a[i],true);
if(count > max)
max = count;
count = 0;
}
printf(" max size %d",max);
}
As per question, input array will have numbers from 0 to n-1 only for array size n with probability of duplicates.
Based on that
1) Initialise array S of size n with 0
2) iterate through array and increment S[i] by 1 each time a[i] is accessed.
3) recursively call index a[i] and add return value to S[i] and do as step 2.
4) breakpoint: if i and a[i] is equal return 0, else if S[i] is non-zero then return S[i];
Complexity : O(n) as each index will be accessed once only
- SK January 27, 2014