Cisco Systems Interview Question
Development Support EngineersCountry: United States
Interview Type: Phone Interview
I wrote the below, but I'm not exactly sure of the complexity because after comparing each of the element in the array, the sorteddictionary does sorting and I'm not sure how to take that into account while calculating the time complexity here.
public static int[] FindTopK(int[] arr, int k)
{
int[] newlist = new int[k];
if (arr.Length < k)
{
Console.WriteLine("Given array has fewer elements than K value, hence returning all 0s");
return newlist;
}
else if (arr.Length == k)
{
for (int i = 0; i < k; i++)
{
newlist[i] = arr[i];
}
return newlist;
}
else
{
SortedDictionary<int, int> topK = new SortedDictionary<int, int>();
for (int i = 0; i < k; i++)
{
topK.Add(arr[i], 1);
}
for (int i = k; i < arr.Length; i++)
{
if (arr[i] > topK.First().Key)
{
topK.Remove(topK.First().Key);
topK.Add(arr[i], 1);
}
else
continue;
}
for (int i = 0; i < k; i++)
{
newlist[i] = topK.ElementAt(i).Key;
}
}
return newlist;
}
Create a min heap of size N. Insert the number in them. Every time before inserting the number check whether it is greater than the min number from heap it is then replace it with current number and call heapify. Complexity : O(count of numbers) Storage O(N)
#input [2,1,20,3,6,5,4,8,11,12]
# N = 3
#output [20,11,12]
# O(n) = (n-x)x
###### create an top_array of n elements from input array,
###### find the minimum of top_array and compare the
###### all the elemnts from n array if the input array
###### elements is bigger than top_array, swap the value
def fill_n_elements(arr,n):
top_arr = []
for i in range(n):
top_arr.append(arr[i])
return top_arr
def find_min(top_arr):
min = top_arr[0]
index = 0
for i in range(1,len(top_arr)):
if min > top_arr[i]:
min = top_arr[i]
index = i
return index
def compare(i,min,arr,top_arr):
if top_arr[min] < arr[i]:
return 1
else:
return -1
def replace(i,min,arr,top_arr):
top_arr[min] = arr[i]
return top_arr
class Top:
def top_n(self,arr, n):
if arr == [] or n == 0:
return arr
top_arr = fill_n_elements(arr,n)
for i in range(n,len(arr)):
min = find_min(top_arr)
flag = compare(i,min,arr,top_arr)
if flag > 0:
top_arr = replace(i,min,arr,top_arr)
return top_arr
top = Top()
arr = [2,1,20,3,6,5,4,8,11,12]
top_arr = top.top_n(arr,3)
print top_arr
int[] arr = new int[] { 1, 2, 3, 30, 10, 11, 12 };
//int max1 = arr[0], max2 = arr[1], max3 = arr[2];
int n = 4;// input max no of element
int[] max = new int[n]; //
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max[0])
{
max[0] = arr[i];
}
for (int j = 0; j < max.Length; j++)
{
bool flag = false;
for (int k = 0; k < j; k++)
{
if (arr[i] < max[k])
flag = true;
else
{
flag = false;
break;
}
}
if (flag && (arr[i] > max[j]))
{
//max[j + 1] = max[j];
//algo to swap all the elments after j such that swap[j+1,j)
for (int l = max.Length -1; l > 0; l--)
{
if (l >= 1)
max[l] = max[l-1];
}
max[j] = arr[i];
//one more loop to replace max array ;
}
}
}
Console.WriteLine(string.Format("max1 : {0}, max2 :{1},max3 : {2},{3}", max[0], max[1], max[2], max[3]));
Console.ReadLine();
int[] arr = new int[] { 1, 2, 3, 30, 10, 11, 12 };
//int max1 = arr[0], max2 = arr[1], max3 = arr[2];
int n = 4;// input max no of element
int[] max = new int[n]; //
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] > max[0])
{
max[0] = arr[i];
}
for (int j = 0; j < max.Length; j++)
{
bool flag = false;
for (int k = 0; k < j; k++)
{
if (arr[i] < max[k])
flag = true;
else
{
flag = false;
break;
}
}
if (flag && (arr[i] > max[j]))
{
//max[j + 1] = max[j];
//algo to swap all the elments after j such that swap[j+1,j)
for (int l = max.Length -1; l > 0; l--)
{
if (l >= 1)
max[l] = max[l-1];
}
max[j] = arr[i];
//one more loop to replace max array ;
}
}
}
Console.WriteLine(string.Format("max1 : {0}, max2 :{1},max3 : {2},{3}", max[0], max[1], max[2], max[3]));
Console.ReadLine();
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
public static void main(String...args){
Test test = new Test();
test.searchInts(new int[]{2,1,20,3,6,5,4,8,11,12}, 3);
for(int i=0; i<test.result.size(); i++){
System.out.println(test.result.get(i));
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
public static void main(String...args){
Test test = new Test();
test.searchInts(new int[]{2,1,20,3,6,5,4,8,11,12}, 3);
for(int i=0; i<test.result.size(); i++){
System.out.println(test.result.get(i));
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
public static void main(String...args){
Test test = new Test();
test.searchInts(new int[]{2,1,20,3,6,5,4,8,11,12}, 3);
for(int i=0; i<test.result.size(); i++){
System.out.println(test.result.get(i));
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
public static void main(String...args){
Test test = new Test();
test.searchInts(new int[]{2,1,20,3,6,5,4,8,11,12}, 3);
for(int i=0; i<test.result.size(); i++){
System.out.println(test.result.get(i));
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
private void searchInts(int[] data, int N){
result = new LinkedList<Integer>();
for(int i=0; i <data.length;i++){
add(data[i], N);
}
}
private void add(int data, int N) {
// If result already has the data or result's least index has higher data, then
// the param data can be ignored.
if(result.contains(data) || (result.size() == N && result.get(N-1) > data)){
return;
}
if (result.size() > 0) {
for(int i=0; i<result.size(); i++){
if(result.get(i) < data){
result.add(i, data);
break;
}
}
} else {
result.add(data);
}
// Remove the extra (above N) data.
if (result.size() > N) {
result.remove(N);
}
}
NOTE: This solution is for if all the elements in the array are positive. It can be solved in O(n)
class SolutionFindTopNMaximum {
private int getMaximum(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public void solution(int[] arr, int n) {
int posSize = getMaximum(arr);
boolean[] posArr = new boolean[posSize];
for (int i = 0; i < arr.length; i++) {
posArr[arr[i] - 1] = true;
}
int counter = n;
while (counter > 0 && posSize >= 0) {
if (posArr[posSize - 1]) {
System.out.println(posSize);
counter--;
}
posSize--;
}
}
}
public class FindTopNMaximum {
public static void main(String[] args) {
SolutionFindTopNMaximum mSol = new SolutionFindTopNMaximum();
mSol.solution(new int[] {
2, 1, 20, 3, 6, 5, 4, 8, 11, 12
}, 3);
}
}
import java.util.ArrayList;
import java.util.List;
public class TopNIntegers {
public static List<Integer> getTopNIntegersWithOutSorting(int[] array,
int count) {
if (count <= 0) {
throw new IllegalArgumentException(
"N value has to be greater than 0");
}
if (count > array.length) {
throw new IllegalArgumentException(
"N value cannot be greater than the array size of "
+ array.length);
}
if (array.length < count) {
throw new IllegalArgumentException(
"The array size should be greater than or equal to "
+ count);
}
final List<Integer> topNIntegers = createAListWithNelements(array,
count);
for (int i = 0; i < array.length; i++) {
for (Integer integer : topNIntegers) {
if (array[i] > integer && topNIntegers.size() < count) {
topNIntegers.remove(integer);
topNIntegers.add(array[i]);
}
}
}
return topNIntegers;
}
private static List<Integer> createAListWithNelements(int[] array, int count) {
final List<Integer> topNIntegers = new ArrayList<Integer>();
for (int i = 0; i < array.length; i++) {
if (topNIntegers.size() == count) {
break;
}
topNIntegers.add(array[i]);
}
return topNIntegers;
}
public static void main(String args[]) {
int[] unsortedArray = { 2, 1, 20, 3, 6, 5, 4, 8, 11, 12 };
System.out.println("Top N integers");
for (int i : getTopNIntegersWithOutSorting(unsortedArray, 10)) {
System.out.print(i + " ");
}
}
}
So like in your example
{2 1 20 3 6 5 4 8 11 12} and we are asked for the top 3 integers.
In a min heap insert the first 4. Pop the minimum and insert the next.Keep on doing so till the numbers get exhausted.
Complexity:
Space : O(N)
Time: O(No of numbers to inspect). Obviously, We can't do better .
public void givenInfiniteNumbersInArrayPrintTopK(int[] a, int k){
MinHeap minHeap = new MinHeap(k);
for (int i = 0; i < a.length; i++) {
minHeap.add(a[i]);
}
for (int i = 0; i < k; i++) {
System.out.println(minHeap.remove());
}
}
public class MinHeap {
/*
* Returns the minimum to maximum numbers from heap
*/
private static final int DEFAULT_SIZE = 10;
int[] heap = null;
int index = -1;
public MinHeap(int size){
heap = new int[size];
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(5);
minHeap.add(321);
minHeap.add(32);
minHeap.add(341);
minHeap.add(10);
minHeap.add(97);
minHeap.add(23);
System.out.println(minHeap.remove());
System.out.println(minHeap.remove());
System.out.println(minHeap.remove());
System.out.println(minHeap.remove());
System.out.println(minHeap.remove());
}
public MinHeap(){
this(DEFAULT_SIZE);
}
//add
//siftup
//remove
//siftdown
public void add(int data){
if(isFull()){
if(peek() < data){
remove();
}else{
return;
}
}
heap[++index] = data;
siftup(index);
}
private void siftup(int index) {
/*
* calculate parent..
* is index left child or right child..
* we can know this by index number..
* from parent children are
* l -> 2k + 1
* r -> 2k + 2
*
*
* similarly parent from left would be..
* l -1/ 2
* r -2/2
*
*/
int parent = index;
while(index > 0){
if(index % 2 == 0){
parent = (index -2)/2;
}else{
parent = (index -1)/2;
}
if(parent < 0){
break;
}
if(heap[index] < heap[parent]){
//then swap..
int temp = heap[index];
heap[index] = heap[parent];
heap[parent] = temp;
index = parent;
}else{
//done.. we have completed siftup as there is nothing left..
break;
}
}
}
public boolean isFull(){
return index >= heap.length -1;
}
public int peek(){
return heap[0];
}
public int remove(){
if(isEmpty()){
return -1;
}
int data = heap[0];
heap[0] = heap[index --];
siftdown();
return data;
}
private void siftdown() {
int currentIndex = 0;
while(currentIndex < index){
//calculate left and right child..
int leftIndex = 2 * currentIndex + 1;
int rightIndex = 2 * currentIndex + 2;
int indexToCompare = leftIndex;
if(rightIndex <= index){
if(heap[leftIndex] > heap[rightIndex]){
indexToCompare = rightIndex;
}
}
if(indexToCompare > index){
break;
}
if(heap[indexToCompare] < heap[currentIndex]){
int temp = heap[currentIndex];
heap[currentIndex] = heap[indexToCompare];
heap[indexToCompare] = temp;
currentIndex = indexToCompare;
}else{
break;
}
}
}
private boolean isEmpty() {
return index < 0;
}
}
package test;
public class testcc150 {
public static int[] MinTop(int Min[] ){
int min = Min[0];
int pos =0;
int size = Min.length;
int re[]=new int[2];
for(int i = 0; i< size; i++){
if (min>Min[i]){
min = Min[i];
pos =i;
}
}
re[0]=min;
re[1]=pos;
return re;
}
public static int[] Top(int allNum[],int topnum){
int Max[] = new int[topnum] ;
int min ;
int pos;
for(int i =0 ;i< topnum; i++){
//System.out.println(allNum[i]);
Max[0]=allNum[0];
//System.out.println(Max);
Max[i] = allNum[i];
//System.out.println("this"+Max[topnum-1]);
}
min = MinTop(Max)[0];
pos = MinTop(Max)[1];
for(int i = topnum; i<allNum.length; i++){
if(min<allNum[i]){
Max[pos] = allNum[i];
min = MinTop(Max)[0];
pos = MinTop(Max)[1];
}
}
return Max;
}
public static void main(String args[]){
int[] nums2 = {1,100,3,4,5,6,7,8,9,15,11,99,32};
System.out.println(Top(nums2,3)[0]);
System.out.println(Top(nums2,3)[1]);
System.out.println(Top(nums2,3)[2]);
}
}
package test;
public class testcc150 {
public static int[] MinTop(int Min[] ){
int min = Min[0];
int pos =0;
int size = Min.length;
int re[]=new int[2];
for(int i = 0; i< size; i++){
if (min>Min[i]){
min = Min[i];
pos =i;
}
}
re[0]=min;
re[1]=pos;
return re;
}
public static int[] Top(int allNum[],int topnum){
int Max[] = new int[topnum] ;
int min ;
int pos;
for(int i =0 ;i< topnum; i++){
//System.out.println(allNum[i]);
Max[0]=allNum[0];
//System.out.println(Max);
Max[i] = allNum[i];
//System.out.println("this"+Max[topnum-1]);
}
min = MinTop(Max)[0];
pos = MinTop(Max)[1];
for(int i = topnum; i<allNum.length; i++){
if(min<allNum[i]){
Max[pos] = allNum[i];
min = MinTop(Max)[0];
pos = MinTop(Max)[1];
}
}
return Max;
}
public static void main(String args[]){
int[] nums2 = {1,100,3,4,5,6,7,8,9,15,11,99,32};
System.out.println(Top(nums2,3)[0]);
System.out.println(Top(nums2,3)[1]);
System.out.println(Top(nums2,3)[2]);
}
}
public class TopThreeArray {
public static void main(String[] args) {
int arr[]={3,7,13,6,36,24,56,26,35,75,35};
int n=3;
printtopthree(arr,n);
}
public static void printtopthree(int arr[],int n){
PriorityQueue<Integer> pq=new PriorityQueue<Integer>(n);
for(int i=0;i<arr.length;i++){
while(pq.size()<=n){
pq.offer(arr[i]);
}
pq.poll();
}
System.out.println(pq);
}
}
public class TopThreeArray {
public static void main(String[] args) {
int arr[]={3,7,13,6,36,24,56,26,35,75,35};
int n=3;
printtopthree(arr,n);
}
public static void printtopthree(int arr[],int n){
PriorityQueue<Integer> pq=new PriorityQueue<Integer>(n);
for(int i=0;i<arr.length;i++){
while(pq.size()<=n){
pq.offer(arr[i]);
}
pq.poll();
}
System.out.println(pq);
}
}}
We can use the Linear Order selection algorithm using Quick sort partition method
1. Divide array into elems of 5
2. Find median of each sub arrays
3. Create another array of all the medians and recursively find medians (go to step 1) till we get one single median.
4. Use this as the pivot and partition the array.
5. If N(input) is less than pivot index then recursively apply same algo on left half array else on right half.
Note: Same thing can be done by randomly selecting a pivot as well.
Complexity: For large no. of elements, it has a complexity of O(num elems) with a rather big constant value (which is ok compared to nlogn complexity obtained due to sorting).
public static void main(String[] args)
{
int list[] = {3,26,56,34,26,56,78,99,31,44,27};
List<Integer> pushlist = new ArrayList<Integer>();
System.out.println("Initial Size "+list.length);
for(int count = 0; count< list.length; count++ )
{
push(list[count],pushlist);
System.out.println("Push List Size:: "+pushlist.size());
}
for(int topCounter = 0;topCounter<5; topCounter++)
{
System.out.println(pushlist.get(topCounter));
}
System.out.println("Final Length "+pushlist.size());
}
private static void push(int value,List<Integer> pushlist)
{
if(pushlist.isEmpty())
{
System.out.println("Empty .. Add First "+value);
pushlist.add(value);
}else if(pushlist.get(pushlist.size()-1)>=value)
{
System.out.println("Simply Add "+value);
pushlist.add(value);
}else{
System.out.println("Pop Add "+value);
pop(value,pushlist);
}
}
private static boolean pop(int value,List<Integer> pushlist)
{
boolean isadded = false;
int index = pushlist.size()-1;
int delete = pushlist.get(index);
pushlist.remove(index);
if(pushlist.isEmpty())
{
pushlist.add(value);
}else{
if(pushlist.get(pushlist.size()-1)<value)
{
isadded = pop(value,pushlist);
}
System.out.println("RE-Add :: "+delete);
if(!isadded)
{
pushlist.add(value);
}
}
pushlist.add(delete);
return true;
}
public static void main(String[] args)
{
int list[] = {3,26,56,34,26,56,78,99,31,44,27};
List<Integer> pushlist = new ArrayList<Integer>();
System.out.println("Initial Size "+list.length);
for(int count = 0; count< list.length; count++ )
{
push(list[count],pushlist);
System.out.println("Push List Size:: "+pushlist.size());
}
for(int topCounter = 0;topCounter<5; topCounter++)
{
System.out.println(pushlist.get(topCounter));
}
System.out.println("Final Length "+pushlist.size());
}
private static void push(int value,List<Integer> pushlist)
{
if(pushlist.isEmpty())
{
System.out.println("Empty .. Add First "+value);
pushlist.add(value);
}else if(pushlist.get(pushlist.size()-1)>=value)
{
System.out.println("Simply Add "+value);
pushlist.add(value);
}else{
System.out.println("Pop Add "+value);
pop(value,pushlist);
}
}
private static boolean pop(int value,List<Integer> pushlist)
{
boolean isadded = false;
int index = pushlist.size()-1;
int delete = pushlist.get(index);
pushlist.remove(index);
if(pushlist.isEmpty())
{
pushlist.add(value);
}else{
if(pushlist.get(pushlist.size()-1)<value)
{
isadded = pop(value,pushlist);
}
System.out.println("RE-Add :: "+delete);
if(!isadded)
{
pushlist.add(value);
}
}
pushlist.add(delete);
return true;
}
This can be achieved using basic stack operations Push and Pop. Sudo Code as follows:
1) Create an empty stack.
2) Iterate over the Array. Current element n (say).
3) if stack isEmpty or n >= k (top element of Stack) then Push(n)
4) Else Pop All elements from Stack till n>=K, then Push(n) and Re-push all the pop-ed elements.
To get the max N element, perform N Pop operations on the Stack
import java.util.Scanner;
import java.util.Arrays;
class Cisco
{
public static void main(String[] args)
{
Scanner s=new Scanner(System.in);
int a[]={2,1,20,3,6,5,4,8,11,12};
System.out.println("Enter no to display max number:");
int n=s.nextInt();
Arrays.sort(a);
for(int i=0;i<n;i++)
{
System.out.println(a[a.length-1-i]);
}
}
}
Create a heap of arr[N]
- Michael Bom April 26, 2015-Anytime insert new number, compare each with min(arr[N]) and max[arr[N])
-Sort arr[N]
-O(N.n)