Microsoft Interview Question SDETs
Country: India
Interview Type: In-Person
public static void main(String[] args)
{
int[] array = {1,4,5,2,3,4,5,6};
for(int i=0;i<array.length-2;i++)
{
int[] uiarray = {array[i],array[i+1],array[i+2]};
mx(uiarray);
}
int max=0;
}
public static void mx(int [] ab)
{
int max=0;
for(int i=0;i<ab.length;i++)
{
if(max<ab[i])
{
max = ab[i];
}
}
System.out.println(max);
}
import java.util.Arrays;
import java.util.Collections;
public class MaxElefromArr {
public static int findMax(int [] a){
Integer[] intArray = new Integer[a.length];
for(int i=0;i<a.length;i++){
intArray[i] = new Integer(a[i]);
}
Arrays.sort(intArray,Collections.reverseOrder());
return intArray[0];
}
public static void main(String[] args) {
int a[] = {1,4,5,2,3,4,5,6};
int samp[]={5,2,3};
System.out.println(findMax(samp));
}
}
public static void main(String[] args)
{
int[] array = {1,4,5,2,3,4,5,6};
for(int i=0;i<array.length-2;i++)
{
int[] uiarray = {array[i],array[i+1],array[i+2]};
mx(uiarray);
}
int max=0;
}
public static void mx(int [] ab)
{
int max=0;
for(int i=0;i<ab.length;i++)
{
if(max<ab[i])
{
max = ab[i];
}
}
System.out.println(max);
}
public class arraySubSetPrintMax {
public static void printArraySubMax(int[] intArray){
System.out.println(intArray.length);
for (int i=0; i<intArray.length - 2; i++){
int max = Integer.MIN_VALUE;
max = (intArray[i] < intArray[i+1] ? intArray[i+1] : intArray[i]);
max = (max < intArray[i+2] ? intArray[i+2] : max);
System.out.println(max);
}
}
public static void main(String[] args){
int[] intArray = {1,2,3,5,4,6,8,7,9,10,15,12,9,8};
printArraySubMax(intArray);
}
}
public class arraySubSetPrintMax {
public static void printArraySubMax(int[] intArray){
System.out.println(intArray.length);
for (int i=0; i<intArray.length - 2; i++){
int max = Integer.MIN_VALUE;
max = (intArray[i] < intArray[i+1] ? intArray[i+1] : intArray[i]);
max = (max < intArray[i+2] ? intArray[i+2] : max);
System.out.println(max);
}
}
public static void main(String[] args){
int[] intArray = {1,2,3,5,4,6,8,7,9,10,15,12,9,8};
printArraySubMax(intArray);
}
}
So we are interested in only keeping track of max of each tuple of 3 elements -
a) scan through the array, take 3 elements in each iteration, find the max, keep its index in a temp variable. Add this value(index) in a qeue(to keep track of array order).
b) In UI , just show the value at array index, getting index from queue.i.e.
arr[qeueue.dequeue()]. Ofcourse handling edge cases and not making solution only for 3 items, but x items.
public LargerstOutThreeArray ()
{
int[] arr = { 1, 2, 5, 2, 1, 9, 6, 1, 8, 4, 11, 13 };
int largest;
for (int i = 0; i < arr.Length-2 ; i++)
{
Console.WriteLine(" out of " + arr[i] + " " +arr[i+1] +" " + arr[i+2]);
largest = arr[i];
for (int j = i +1; j < i + 3; j++)
{
if (arr[j] > largest)
largest = arr[j];
}
Console.WriteLine(largest);
}
}
much optimized
private static string DoMath2()
{
StringBuilder sb = new StringBuilder();
int[] inputs = Console.ReadLine().Split(',').Select(x => Convert.ToInt32(x)).ToArray();
for (int i = 0; i < inputs.Count()-2; i++)
{
int largest = 0;
for (int j = i; j <= i+2; j++)
{
if(inputs[j]>largest) largest=inputs[j];
}
sb.Append(largest);
}
return sb.ToString();
}
InPlace array replace
output = for each iteration, the element to be shown in UI
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{ if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
} else { if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
} else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
} }
}}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
void UI(int* arr, int len)
{
if (len < 3)
{
std::cout << "ERROR";
return;
}
int prevMaxId = getMaxId(arr, 0, 2); // Get Maximum element's index from 3 elements in constant time
int prevMax = arr[prevMaxId];
arr[0] = prevMax;
for (int i = 1; i< len-2; ++i)
{
if (prevMaxId == i-1)
{
int maxId = getMaxId(arr, i, i+2); // Get Maximum element's index from 3 elements in constant time
prevMaxId = maxId;
prevmax = arr[maxId];
arr[i] = prevMax;
}
else
{
if (prevMax >= arr[i+2])
{
arr[i] = prevMax;
}
else
{
prevMax = arr[i+2];
prevMaxId = i+2;
arr[i] = prevMax;
}
}
}
}
public static void printMaxFromSlidingWindowOfKFromGivenArray(int[] array, int k) {
Deque<Integer> dequeue = new LinkedList<>();
for (int index = 0; index < k; index++) {
while (!dequeue.isEmpty()) {
if (array[dequeue.peekLast()] < array[index]) {
dequeue.removeLast();
}
}
dequeue.addLast(index);
}
for (int index = k; index < array.length; index++) {
while (!dequeue.isEmpty() && dequeue.peek() < index - k) {
dequeue.remove();
}
while (!dequeue.isEmpty() && array[dequeue.peekLast()] < array[index]) {
dequeue.removeLast();
}
dequeue.addLast(index);
}
}
public static void printMaxFromSlidingWindowOfKFromGivenArray(int[] array, int k) {
Deque<Integer> dequeue = new LinkedList<>();
for (int index = 0; index < k; index++) {
while (!dequeue.isEmpty()) {
if (array[dequeue.peekLast()] < array[index]) {
dequeue.removeLast();
}
}
dequeue.addLast(index);
}
for (int index = k; index < array.length; index++) {
while (!dequeue.isEmpty() && dequeue.peek() < index - k) {
dequeue.remove();
}
while (!dequeue.isEmpty() && array[dequeue.peekLast()] < array[index]) {
dequeue.removeLast();
}
dequeue.addLast(index);
}
}
Well, I just chose Python for this
arr = [1,4,5,2,3,4,5,6,6,0,7,3]
temp = 0
i =0
for i in xrange(len(arr)-2):
x = arr[i]
y = arr[i+1]
z = arr[i+2]
temp = x
if x < y:
if y < z:
temp = z
elif y >= z:
temp = y;
else:
print "Shouldn't fall here"
elif x >= y:
if x < z:
temp = z
else:
print "X should still be bigger"
print "Biggest value between value is ",x,"-",y,"-",z,"is ----",temp
public static void main(String[] args) {
int[] sample = {1,4,5,7,6,8,3,9,6};
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0;i<sample.length;i++)
{
if(i==(sample.length)-3)
{
break;
}
for(int j=0;j<3;j++)
{
list.add(sample[i+j]);
}
Integer m = Collections.max(list);
System.out.println(m);
}
}
#include<stdio.h>
#include<stdlib.h>
int arr[15] = {0};
void main(){
int i = 0, j = 0, max = 0;
printf("\nEnter array : \n");
while(i < 10){
scanf("%d", &arr[i]);
i++;
}
i = 0;
printf("\nPrinting max :\n");
while(i < 8){
j = i;
while(j < i + 3){
if(arr[j] > max){
max = arr[j];
}
j++;
}
printf("\n%d\n",max);
i++;
}
getch();
}
#include<stdio.h>
#include<stdlib.h>
int arr[15] = {0};
void main(){
int i = 0, j = 0, max = 0;
printf("\nEnter array : \n");
while(i < 10){
scanf("%d", &arr[i]);
i++;
}
i = 0;
printf("\nPrinting max :\n");
while(i < 8){
j = i;
while(j < i + 3){
if(arr[j] > max){
max = arr[j];
}
j++;
}
printf("\n%d\n",max);
i++;
}
getch();
}
public static List<Integer> maxNumberPrintOnScreen(int[] a)
{
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<a.length-2;i++)
{
int n=findMax(a[i],a[i+1],a[i+2]);
list.add(n);
}
return list;
}
private static int findMax(int i, int j, int k) {
if(i>=j && i>=k)
return i;
else if(j>=i && j>=k)
return j;
else
return k;
}
The idea is to use a queue to keep track of the maximum values/idexes in the window. Every time a new posible maximum value is added all the smaller elements are removed from the queue. Also all the indexes outside the window
- hnatsu February 19, 2016public List<int> GetMaxValues(int[] values, int k) { var result = new List<int>(); var queue = new Queue<int>(); // Stores the indexes queue.Enqueue(0); for (int i = 1; i < values.Length; i++) { int value = values[i]; queue.Enqueue(i); // Remove index outside the window if (queue.Peek() <= i - k) queue.Dequeue(); // Remove elements smaller that the new max value int index = queue.Peek(); while (values[index] < value) { queue.Dequeue(); index = queue.Peek(); } if (i >= k-1) result.Add(values[index]); } return result; }