Socialcam Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

## python code
#for longest subsequence with asending order

data = [3,5,8,9,3,-1,-2, -4,-5,-6]

# 0-index for size, 1-index for index in the array where subsequence starts
best = [1, -1]  
curr = [1, -1]

#data.reverse()  #uncomment for descending

#start from the end
for i in range(len(data)-2, -1, -1):
    #if less then add to the current state
    if data[i] <= data[curr[1]]: 
        curr[0] = curr[0]+1
        curr[1] = i
    else:
        #if the run breaks..then compare with the current best
        if(best[0] < curr[0]): 
            best[0] = curr[0]
            best[1] = curr[1]
        #resetting the current run
        curr[0] = 1
        curr[1] = i

if(best[0] > curr[0]):
    print best
else:
    print curr

- bluesky September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

have 2 counters, 1 for DSC, 1 for ASC. Traverse the array, keeping track of both counters and update them while traversing.

O(n)

- pandit September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Run the longest increasing subsequence algorithm twice. The second time, you reverse the compare function.

- Anonymous September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it better with recursion, split the sequence, determine the longest increasing/decreasing sub-sequence and remember if the longest sub-sequence was at the beginning or ending of the sequence. And when "merging" the result just add the "longests" (ending of 1st+starting of 2nd forms a consequtive sub-sequence) or choose the max of them (otherwise).

- Selmeczy, Péter September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

logic::
while traversing array,
use 2 bool variables,
bprev => relation [ascending/descending] between current & prev elements i.e.a[i-1] & a[i]
bcur => relation [ascending/descending] between current & next elements i.e.a[i-1] & a[i]

if bprev == bcur
increment counter
else
there is change, so prevcounter = max of curcounter and prev counter
curcounter ++

return max counter +1
code

#include "iostream"
using namespace std;

int maxAscDeslength(int a[],int n)
{
	int prevcounter =0 ,curcounter = 0;
	bool bprev = true;
	if(a[0] > a[1])
		bprev = false;
	bool bcur;
	for(int i =0; i< n-1; ++i)
	{
		if(a[i] < a[i+1])
			bcur = true;
		else 
			bcur = false;

		if(bprev != bcur)
		{
			prevcounter = max(prevcounter,curcounter);
			curcounter = 1;
		}
		else
			curcounter++;
		bprev = bcur;
	}
	
return (max(curcounter,prevcounter)+1);
}
int main (){
	int a[] = {3, 5, 8 , 9, 3, -1, -4, -5, -6};
	cout << maxAscDeslength(a,9);
	return 0;
}

- mahadev September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Q's is confusing..either ways the sequence should be the same..?

- Anonymous September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain what does sub-sequence mean..I didn't understand the q?

- Anonymous September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sub sequence is just a part of a sequence. So the question is to determine the length of a part of the given sequence, that contains the longest sub-sequence in ascending or descending order. It has o be found in a single traversal.

--- Hope this might help. Good luck

- prabu September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

okay..longest subsequence...inwhat sense

- Anonymous September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int longestAscendingSub(int A[], int m)
{
int startAsc = 0;
int endAsc = 0;
int startDec = 0;
int endDec = 0;
int longest = 0;

for (int i = 1; i < m; ++i)
{
if (A[i] > A[i - 1])
{
startDec = i;
endAsc = i;
}
else if(A[i] < A[i - 1]){
endDec = i;
longest = longest < (endAsc - startAsc + 1) ? (endAsc - startAsc + 1) : longest;
longest = longest < (endDec - startDec + 1) ? (endDec - startDec + 1) : longest;
startAsc = i;

}
}
return longest;
}

- dafeilei November 01, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More