Symantec Interview Question for Senior Software Development Engineers


Country: United States




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

Here is my version. complexity is O(n). coded in java.

public static void searchBestTrade( int[] price ) {
        int lowest = price[0];
        int highest = price[0];
        int buy = price[0];
        int sell = price[0];
        for(int i = 1; i < price.length; i ++) {
            if(price[i] > highest) {
                highest = price[i];
            } else if (price[i] < lowest) {
                lowest = price[i];
                highest = price[i]; 
            }
            // update trade record
            if(sell - buy < highest - lowest) {
                buy = lowest;
                sell = highest;
            }
        }
        System.out.println("Buy: " + buy + " / Sell: " + sell);
    }

- Henry J Law April 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It wont work if highest no is the first no.. just take the stock price as 1000 on the first day. So you also have to assume that you have to buy first and than sell

- chittresh November 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its simply maximum single sell profit algorithm,
Steps:
1) maxDiff = 0, currentMinimum = a[0]
2) for i in [0,n-1] do: 
curMinimum = min(curMinimum, a[i])
maxDiff = max(maxDiff, a[i] - curMinimum) 

3) maxDiff is the answer
Complexity = O(n)
working code:
public int[] getIndexIandJ(int[] integers){
        if(integers == null || integers.length == 1){
            return integers;
        }
        int maxDiff = 0;
        int curMin = integers[0];
        int startIndex = 0;
        int endIndex = 0;
        int tempStart = 0;
        for(int i = 1; i<integers.length; i++){
            if(curMin > integers[i]){
                curMin = integers[i];
                tempStart = i;
            }

            if (maxDiff < (integers[i] - curMin)){
                maxDiff = (integers[i] - curMin);
                startIndex = tempStart;
                endIndex = i;
            }
        }
        int[] indices = new int[2];
        indices[0] = startIndex;
        indices[1] = endIndex;
        return indices;
}

- m3th0d.itbhu April 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void find_max_profit(int array[], int n, int* min, int* max)
{
	int diff = 0;
	int m = array[n-1];
 	for(int i = n-2; i >= 0; i--)
	{
		if(array[i] >= m)
		{
			m = array[i];
		}
		else
		{
			if((m - array[i]) > diff)
			{
                 diff = m - array[i];
				*min = array[i];
				*max = m;
			}
		}
	}
}

- aasshishh April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess the easy way is to first sort the array (O(nlogn)), then pick the corresponding max and min elements (of course you need to make sure the max happens after the min) (O(n)). Consequently, the time complexity is still O(nlogn).

- zy April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you sort it you will loose the sequence, sequence has to be maintained. U can;t even use any data structure.

- PCB April 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

possible solution in O(n) complexity, without taking extra memory (just ~12 bytes).

void fund_better_points(unsigned* points, unsigned pointsLen, unsigned& p1, unsigned& p2)
{
unsigned currP1 = 0, currP2 = 0;
if(pointsLen) {
currP1 = currP2 = points[0];
}
p1 = p2 = currP1;
for(unsigned i=1; i<pointsLen; ++i) {
if(currP2 < points[i]) {
currP2 = points[i];
}
if(points[i] < currP1) {
if(((currP2 - currP1) > (p2 - p1)) ||
(((currP2 - currP1) == (p2 - p1)) && (currP1 < p1))) {
p2 = currP2;
p1 = currP1;
}
currP1 = currP2 = points[i];
}
}
if(((currP2 - currP1) > (p2 - p1)) ||
(((currP2 - currP1) == (p2 - p1)) && (currP1 < p1))) {
p2 = currP2;
p1 = currP1;
}
}

- Nerses April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool findMinMax(int *array, int len, int * min, int * max)
{
int minIndex = 0, maxIndex = 0, curIndex = 0;
if (len > 0)
{
for (; curIndex < len; curIndex++)
{
if (array[curIndex] < array[minIndex])
{ // found a new minimum, so old max isnt valid anymore
minIndex = maxIndex = curIndex;
}
if (array[curIndex] > array[maxIndex])
{ // found new max
maxIndex = curIndex;
}
}
if (minIndex < maxIndex)
{ // return min & max
*min = array[minIndex];
*max = array[maxIndex];
return true;
}
}

return false;
}

- TimeForAChange April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;
class share
{
public static void main(String args[])
{
int in[] = new int[15];
int i,n,buy,sell;
Scanner s  = new Scanner(System.in);
System.out.println("Enter No of Inputs");
n = s.nextInt();
for(i=0;i<n;i++)
{
in[i] = s.nextInt();
}
buy = in[0];
sell = in[0];
for(i=1;i<n;i++)
{
if(in[i]>sell)
{sell=in[i];}
if(in[i]<buy)
{buy=in[i];}
} 
System.out.println("Buy:" + buy);
System.out.println("Sell:" + sell);
}
}

- shekhawat.amit1019 April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int find_Max_Profit(int array[], int n) {
  int minNum, maxProfit, curMax;
  minNum = INT_MAX;
  curMax = INT_MIN;
  for (int i = 0; i < n; i++ ) {
     if( array[i] > minNum) {
         minNum = array[i];
     }
     maxProfit = array[i] - minNum;
     if(maxProfit > curMax) {
          curMax = maxProfit;
     }
   }
   return curMax;
}

- abrahm April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple one,
--> find the largest element in array after the current element
--> now do largest element minus current element.
--> do this for all array elements.

for eg1,
    given array        		[30, 12,  15,  10,  40,  30,  60, 100]
    next_max_elt    		[100, 100,  100,  100, 100,  100,  100, 0    ]

    difference array		[70,    88,    85,    90,    60,    70,    40,   -100]
-> here the maximum difference is 90.
-> so when we buy at 10 and sell at 100 , we get more profit.

example 2:

    price_array			[8,	22,	12,	9,	6,	10,	11,	13,	20,	18,	4,	19]
    next_max_elt		[22,  0,	20,	20,	20,	20,	20,	13,	0,	19,	19,	0]

    difference_array         [14,	-22,	8,	11,	14,	10,	9,	7,	-20,	1,	15,	-19]
-> maximum value is 15,
-> so we have to buy at 4 and sell at  	19.

- yKumar April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

solution :
for ex : a[]={30, 12, 15, 10, 40, 30, 60, 100} (given prices of share)
prepare an auxillary array aux[i]=a[i+1]-a[i]
aux[]={-18,3,-5,30,-10,30,40}
and find start and end index for max sum sub vector in aux[]....(a[start] , a[end+1] ) is required solution(apply kadane's algorithms on aux[])

and code for this is

#include<stdio.h>



/*-----------------------------maximum sum subarray(Kadane's algorithm)-------------------------------*/

void maxsum(int *a,int n){

int max_so_far=a[0],max_end_here=a[0];
int start,end,temp_start,i;

for(i=0;i<n;i++){
	if(max_end_here<0){
		max_end_here=a[i];
		temp_start=i;	

	}
	else
		max_end_here += a[i];

	if(max_end_here>max_so_far){
		max_so_far=max_end_here;
		start=temp_start;
		end=i;
		
	}

}

printf("( %d , %d )  %d",start,end+1,max_so_far);

return;
}


/*-----------------------------max profit share problem-------------*/


void share(int *a,int n){

int aux[n-1],i;

for(i=0;i<n-1;i++)
	aux[i]=a[i+1]-a[i];

maxsum(aux,n-1);

}



void main(){

int a[10]={30,12,15,5,40,30,60,130,2,110 };
share(a,10);

}

- Anonymous April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

complexity should not be n2.

- PCB April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not O(n2)..its O(n)

- Anonymous April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check out the Kim-Shan Algorithm.

- Anonymous April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

algo: subtract all the elements with next elements as shown below and once you get that then basically what we are looking for is a maximum subarray which can be find out using kadence algorithm.
//int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
int a[] = {-18, 3, -5, 30, -10, 30, 40};

static int l_index = 0, h_index = 0;

int maximum_subarray(int* nums, int start_index, int end_index)
{
        int max_sum = 0;
        int cur_index, cur_sum = 0, max_ending_here, max_so_far;

        for(cur_index = 0; cur_index < end_index; cur_index++) {
                cur_sum = cur_sum + nums[cur_index];
                if(cur_sum < 0) {
                        cur_sum = 0;
                        l_index = cur_index;
                }
                if(cur_sum > max_sum) {
                        max_sum = cur_sum;
                        h_index = cur_index;
                }
        }
        return max_sum;
}

int main()
{
        //int a[] = {30, 12, 15, 10, 40, 30, 60, 100};
        int a[] = {-18, 3, -5, 30, -10, 30, 40};
        printf("sum %d\n", maximum_subarray(a, 0, sizeof(a)/sizeof(a[0])));
        printf("left %d right %d\n", l_index, h_index);
        return 0;
}

- aka April 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When I run this program with a[] = {30, 12, 15, 10, 40, 30, 60, 100}

The output is pointing to 30 and 100. its wrong
It should be 12 and 100

- PCB April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@PCB: please re-read my post again.
It is clearly mentioned you have to first diff it before finding out maximum subarray.
a[] = {30, 12, 15, 10, 40, 30, 60, 100}
try this a[] = {-18, 3, -5, 30, -10, 30, 40}

- aka April 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my version. complexity is O(n). coded in java.

{{
public static void searchBestTrade( int[] price ) {
int lowest = price[0];
int highest = price[0];
int buy = price[0];
int sell = price[0];
for(int i = 1; i < price.length; i ++) {
if(price[i] > highest) {
highest = price[i];
} else if (price[i] < lowest) {
lowest = price[i];
highest = price[i];
}
// update trade record
if(sell - buy < highest - lowest) {
buy = lowest;
sell = highest;
}
}
System.out.println("Buy: " + buy + " / Sell: " + sell);
}
}}

- Henry J Law April 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstdio>

using namespace std;
void getMax(int& _buy, int& _sell, int n, int price[])
{
    int buy = price[0];
    int sell = price[1] - price[0];
    for(int i = 2; i < n; i++)
    {
        buy = price[i - 1] < buy ? price[i - 1] : buy;
        if(price[i] - buy > sell)
        {
            _buy = buy;
            _sell = price[i];
            sell = price[i] - buy;
        }
    }
}

int main()
{
    int n = 0;
    int a[100];
    int buy = 0, sell = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    getMax(buy, sell, n, a);
    printf("%d %d\n", buy, sell);
    return 0;
}

- Gabriel April 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int temp[5]={2,7,66,9,3};
int i=0;
int curmin,curmax;
curmin=curmax=temp[0];
for(;i<5;i++)
{
if(curmin>temp[i])
curmin=temp[i];
if(curmax<temp[i])
curmax=temp[i];
}
printf("%d\n",curmax);
printf("%d\n",curmin);




getch();
}

- Anonymous May 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void bestTrade(int[] prices)
	{
		if (prices == null || prices.length < 2)
		{
			return;
		}
		int min = prices[0];
		int buy = min;
		int sell = buy;
		for(int price : prices)
		{
			if (price < min)		
			{
				min = price;
			}
			else if (price > sell)	
			{
				sell = price;
				buy = min;
			}			
		}
		System.out.println("Buy: " + buy + "\nSell: " + sell);
	}

- Pravin September 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java code::
public static void searchBestTrade( int[] price ) {
Arrays.sort(price);
System.out.println("Buy: " + price[0]+ " / Sell: " + price[price.length - 1]);
}

- Ramu September 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple way here in perl.

#########################
#!/usr/bin/perl
my $input = “30,12,15,10,40,30,60,100”;

my @array = split (/\,/, $input);

my @sort_array = sort {$a <=> $b} @array;

print “Best BUY : $sort_array[0] and Best SELL: $sort_array[$#sort_array] \n”;

#####################################

- Srilakshmi Vallalar October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findMaxProfit(){
                int[] share= new int[]{30, 12, 15, 5, 40, 30, 60, 130, 2, 110 };
		int maxProfit=0;
		int buy=share[0];
		int sell=share[0];
		int lowest=share[0],heighest=share[0];
		boolean isLowestPriceChanged=false;
		
		for (int i = 1; i < share.length; i++) {
			if(lowest>share[i]){
				lowest=share[i];
				isLowestPriceChanged=true;
			}
			
			 if(heighest<share[i] || isLowestPriceChanged){
				heighest=share[i];
				isLowestPriceChanged=false;
			}
			
			if(heighest-lowest>maxProfit){
				maxProfit=heighest-lowest;
				buy=lowest; sell=heighest;
				System.out.println("buy "+ buy +" sell "+sell);
				
			}
			
		}
		
		System.out.println("buy "+ buy +" sell "+sell);

	}

- BA November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String string = br.readLine();
String[] integers = string.split(",");
int[] input = new int[integers.length];
for (int count = 0; count < integers.length; count++) {
input[count] = Integer.parseInt(integers[count]);
}
HashMap<Integer, Integer> positionMap = new HashMap<Integer, Integer>();
for (int count = 0; count < integers.length; count++) {
if (positionMap.get(input[count]) == null) {
positionMap.put(input[count], count);
}
}
int maxProfit = Integer.MIN_VALUE;
Arrays.sort(input);
int buyValue = 0;
int saleValue = 0;
int i = 0;
int j = input.length - 1;
while (i <= j) {
if (positionMap.get(input[j]) > positionMap.get(input[i])
&& ((input[j] - input[i]) > maxProfit)) {
buyValue = input[i];
saleValue = input[j];
maxProfit = input[j] - input[i];
}
if (positionMap.get(input[j - 1]) > positionMap.get(input[i])
&& ((input[j - 1] - input[i]) > maxProfit)) {
buyValue = input[i];
saleValue = input[j - 1];
maxProfit = input[j - 1] - input[i];
}
if (positionMap.get(input[j]) > positionMap.get(input[i + 1])
&& ((input[j] - input[i + 1]) > maxProfit)) {
buyValue = input[i + 1];
saleValue = input[j];
maxProfit = input[j] - input[i + 1];
}
j--;
i++;
}
// System.out.println("StockPrize By value : " + buyValue
// + " StockPrice sale value : " + saleValue
// + " Maximum Profit : " + maxProfit);
System.out.println(buyValue + "," + saleValue);

}

- Darkhorse March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String string = br.readLine();
		String[] integers = string.split(",");
		int[] input = new int[integers.length];
		for (int count = 0; count < integers.length; count++) {
			input[count] = Integer.parseInt(integers[count]);
		}
		HashMap<Integer, Integer> positionMap = new HashMap<Integer, Integer>();
		for (int count = 0; count < integers.length; count++) {
			if (positionMap.get(input[count]) == null) {
				positionMap.put(input[count], count);
			}
		}
		int maxProfit = Integer.MIN_VALUE;
		Arrays.sort(input);
		int buyValue = 0;
		int saleValue = 0;
		int i = 0;
		int j = input.length - 1;
		while (i <= j) {
			if (positionMap.get(input[j]) > positionMap.get(input[i])
					&& ((input[j] - input[i]) > maxProfit)) {
				buyValue = input[i];
				saleValue = input[j];
				maxProfit = input[j] - input[i];
			}
			if (positionMap.get(input[j - 1]) > positionMap.get(input[i])
					&& ((input[j - 1] - input[i]) > maxProfit)) {
				buyValue = input[i];
				saleValue = input[j - 1];
				maxProfit = input[j - 1] - input[i];
			}
			if (positionMap.get(input[j]) > positionMap.get(input[i + 1])
					&& ((input[j] - input[i + 1]) > maxProfit)) {
				buyValue = input[i + 1];
				saleValue = input[j];
				maxProfit = input[j] - input[i + 1];
			}
			j--;
			i++;
		}
//		System.out.println("StockPrize By value : " + buyValue
//				+ " StockPrice sale value : " + saleValue
//				+ " Maximum Profit : " + maxProfit);
		System.out.println(buyValue + "," + saleValue);
		
	}

- Darkhorse March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Scanner;


public class ShareMarket {
public static void main(String a[])
{
Scanner sc = new Scanner(System.in);
String[] ins = sc.nextLine().split(" ");
int numEles = ins.length;
int[] in = new int[numEles];
int i = 0;
for(String s:ins)
{
in[i++] = Integer.parseInt(s);
}

int buy = in[0], sell = in[0], hp = 0;
int b = 0, s = 0;
for(i = 0 ; i < numEles; i++)
{
b = in[i];
for(int j = i + 1; j < numEles; j++)
{
s = in[j];
if( (s - b) > hp )
{
hp = s-b;
buy = b;
sell = s;
}
}
}
System.out.println(buy + " " + sell + " " + hp);
}
}

- enigma2006.kishore February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This solution follows this approach: -
- Since the highest price of the stock will be towards the end, parse the array from the right and mark the highest prices.
- Also, we need the max difference between the buying price (lower value, towards the beginning of the array) with the selling price.

- Create another array (diff) with same length as the prices array
- Parse the prices array from behind,
- If price is larger than the previous largest price
- Store -1 in the diff array.
- Change the largest price to this price.
- If price is lower than the largest price
- Store the diff between the 2 prices in the diff array

- Now parse the diff array from beginning to find the largest diff
- Once the largest diff is found, this is your buying price. Start a loop from this price to the end of the diff array
- As soon as you encounter a -1 in the diff array, this is your selling price

private static void printStockPrices(int[] prices) {
		long start = System.currentTimeMillis();
		int[] diff = new int[prices.length];
		int max_index = -1;
		int max_diff_index = 0;
		
		for (int j = prices.length - 1; j >= 0; j--) {
			if (j == prices.length - 1) {
				diff[j] = -1;
				max_index = j;
			} else if (prices[j] >= prices[max_index]) {
				diff[j] = -1;
				max_index = j;
			} else {
				diff[j] = prices[max_index] - prices[j];
			}
		}
		
		for (int j = 0; j < diff.length; j++) {
			if (diff[j] > diff[max_diff_index]) {
				max_diff_index = j;
			}
		}
		
		for (int j = max_diff_index + 1; j < diff.length; j++) {
			if (diff[j] == -1) {
				System.out.println ("(" + prices[max_diff_index] + ", " + prices[j] + ")");
				break;
			}
		}
		
		long end = System.currentTimeMillis();
		System.out.println ("Time taken (in sec): " + ((end - start)/1000));
	}

- Anonymous April 05, 2013 | 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