Array implementation of stack

 Posted on October 20, 2010  (Last modified on August 12, 2020)  |  3 minutes  |  Kinshuk Chandra

Here will discuss the array implementation of stack. Problems with array implementation Underflow - Array may be empty but people may try to pop the element Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html Null items - Can nulls be added - Yes in this case, nulls can be added in stack [Read More]
kodeknight  array  cppimpl  stack  java 

Array implementation of stack

 Posted on October 20, 2010  (Last modified on August 12, 2020)  |  3 minutes  |  Kinshuk Chandra

Here will discuss the array implementation of stack. Problems with array implementation Underflow - Array may be empty but people may try to pop the element Overflow - Array is full. To over come we have to use re-szing of array. We can see how we can solve this problem here - http://k2code.blogspot.com/2013/09/resizing-array-implementation-of-stack.html Null items - Can nulls be added - Yes in this case, nulls can be added in stack [Read More]
kodeknight  array  cppimpl  stack  java 

Arrays tip : Ignoring the zeroth row

 Posted on October 18, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

This trick can be used in any language but is shown in java right now. Sometimes you want to use natural input values as an index, the real values that that data has instead of starting with zero. Let’s take the case of data that starts with the value 1, like the day of the month. The standard approach is to subtract one from every day value that’s used as an index. [Read More]
kodeknight  Java Arrays  array 

How to bound check arrays in cpp / c

 Posted on August 31, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Bound checking in cpp /c is headache…. char \*strcpy(char \*dest, const char \*src) { char \*save \= dest; while(\*dest++ \= \*src++); return save; } //main func char *src = “hello to c programming language”; char dest[12]; strcpy(dest,src); //calling function Here we have no bound check on dest size or src size. When we pass it to function it is perfectly alright but problem is dest is array which is just 12 bytes long…but src is larger string… [Read More]
cleaner code  kodeknight  vectors  cpp  array  dynamic arrays 

maximum index of an array

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Space for 200,000,000 integers : 800MB 256,000,000 integers : 1024MB Integer.MAX_VALUE (2,147,483,647) : ~8600MB Integer.MAX_VALUE/2 (1,073,741,823) : ~4300MB //arrayindextest.java class arrayindextest { public static void main(String[] args) { int[] a = new int[256000000]; //or 200000000 System.out.println(a.length); } } -Xmx set max heap size flag -Xms set min heap size flag 200,000,000 integers : 800MB With new int[200000000]: java -Xms32m -Xmx1024m arrayindextest 200000000 256,000,000 integers : 1024MB With new int[256000000]: [Read More]
Algorithms  kodeknight  array 

Remove duplicates from the sorted array

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

**Problem **  Remove duplicates from the sorted array Example [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5] Method 1- using 3 pointers //using 3 pointers fixDuplicatesInSortedArray(Integer\[\] a): start = 0 end = 0 destination = 0 while(start < a.length): while(end < a.length && a\[end\] == a\[start\]): end++ end-- //copy the distinct element a\[destination\] = a\[start\] destination++ start = end + 1 end = start //null out the rest while destination < a. [Read More]
Algorithms  kodeknight  duplicate  array  remove-duplicates  sorted-array 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

in your Pseudocode, the if condition should be if …

RM - May 3, 2014

in your Pseudocode, the if condition should be if (low < high).

Thanks Rish. I have made the change a[low] > a[high] rather than low < low. :). Thanks for correcting me.

kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

 Posted on April 26, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort. Example Input - Binary unsorted array A = {0,1,1,0,0,1}; Output - binary sorted array B = {0,0,0,1,1,1} Solution This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). [Read More]
kodeknight  interview  quicksort  binary array  sorting  Interview Question  array  programCPP  integer-sort  zero 

Find the median in a continous stream of numbers

 Posted on January 18, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated. OR You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream(in say O(1) time) **OR ** [Read More]
median  Algorithms  kodeknight  hard  array  binary-search-tree  BST  CrackingTheCodingInterview 

Bubble sort

 Posted on January 14, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

The sorting problem Input: Array of numbers , unsorted. Eg. Output : Same numbers sorted in some order, say increasing order. Eg. What is Bubble Sort? The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). [Read More]
cpp  kodeknight  Data Structures  DS  c  array  Sorting Algorithm  bubble sort  sorting arrays  programming  sorting  incomplete  programCPP  Data Structure  java