Implement 3 stacks in 1 array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem - Implement 3 stacks in 1 array Solutions Method 1 - Create 3 stacks with fixed max size Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[” means inclusive, while “(” means exclusive of the end point). for stack 1, we will use [0, n/3) for stack 2, we will use [n/3, 2n/3) for stack 3, we will use [2n/3, n) Here is the code : [Read More]
kodeknight  array  CrackingTheCodingInterview  stack 

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]. See here for the full implementation. Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one. [Read More]
kodeknight  queue  stack 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

def findMin(arr): print(“Finding min in a…

Anonymous - Sep 4, 2014

def findMin(arr):
print(“Finding min in a rotated sorted array of integers”)

low = 0
high = len(arr) - 1
while low < high:
mid = int((low + high)/2)
left = mid - 1
right = high

if arr[mid] > arr[left] and arr[mid] > arr[right]:
low = mid
elif arr[mid] > arr[left] and arr[mid] < arr[right]:
high = mid
else:
return arr[mid]

search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Find the minimum element in the rotated sorted sorted array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question : Find the minimum element in the rotated sorted array. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer - The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B, [Read More]
search  ArraySearch  kodeknight  recursion  array  binary search  rotated array  min  sorted-array 

Search an element in the sorted rotated array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable. So for example we have sorted array as - 2,3,6,12, 15, 18. Now suppose the array is rotated k times ( we don’t know k), such that array becomes 15, 18,2,3,6,12 Answer: We can do a binary search with some modified checks. So lets take arr as array, start be start of the array, end be arr. [Read More]
ArraySearch  kodeknight  Amazon  recursion  array  binary search  rotated array  CrackingTheCodingInterview  sorted-array  sorting-and-searching  java 

Reverse a String using bits

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Question: Reverse a string in C using as little additional memory as possible. Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code. Method 1 - Normal Reversal of String void reverseString(char\* str) { int i, j; char temp; i\=j\=temp\=0; j\=strlen(str)\-1; for (i\=0; i<j; i++, j\-\-) { temp\=str\[i\]; str\[i\]\=str\[j\]; str\[j\]\=temp; } } Method 2 - Using xor to swap 2 characters [Read More]
kodeknight  String  reverse  string-udf  bits 

Pick a Random Byte

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem**:** You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Solution**:**  Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. [Read More]
kodeknight  brainteaser 

Three Switches and Three Blub Problem

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem:  You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which bulb. Solution:  Stumped? The issue lies in the fact that there are only two possible positions for each switch (on or off), but three bulbs to identify. [Read More]
kodeknight  brainteaser 

Deleting a node from a singly linked link list

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C. Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. [Read More]
kodeknight  link list  Single Link List  delete 

Link list ADT

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

What is linked list? Linked List consists of a sequence of nodes. These nodes are made-up of the following: A Data Field for housing the data item One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s. In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible. [Read More]
kodeknight  link list  Single Link List  abstract-data-type  ADT  incomplete  Data Structure  linked list