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 

Stack DS to implement constant time Minimum element lookup

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

Problem: You need to implement a stack data structure that can also report the minimum element in constant-time. Solution Method 1 - Using extra stack This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. [Read More]
kodeknight  O(1)  CrackingTheCodingInterview  stack  min 

Finding the Start of a Loop in a Linked List

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

Problem  Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. DEFINITION Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. EXAMPLE input: A -> B -> C -> D -> E -> C [the same C as earlier] output: C Example head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ | | | +------------------------+ Answer here is 3. [Read More]
kodeknight  link list  java-code  Single Link List  loop  CrackingTheCodingInterview 

Find an element in matrix in which rows and columns are sorted

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

Problem Given a matrix in which each row and each column is sorted, write a method to find an element in it. Example 1 4 7 13 2 5 9 15 3 6 10 16 Solution Here we can have 2 cases - Case when array is sorted such that last element of nth row is less than first element of n+1 th row Generic case - simply put rows and columns CASE 1 - If last element of each row is less than first element of next row [Read More]
kodeknight  2DArray  2DSortedArray  binary search  CrackingTheCodingInterview  sorting-and-searching 

The Ant Collision Problem

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

Problem : There are three ants on different vertices of a equilateral triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.  Solution : Note that equilateral has nothing to do with how they will collide. Also, ants are allowed to move on the sides only. [Read More]
kodeknight  brainteaser  Mathematical  probability  CrackingTheCodingInterview 

Anagram Checker–To check if 2 strings are anagrams

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

An anagram is a type of word, the result of rearra… Unknown - Jul 1, 2014An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. For example: orchestra can be rearranged into carthorse or cat can be rearranged into act. We can find out the anagram strings using below algorithm: [Read More]
kodeknight  String  java-code  anagrams  hashes  CrackingTheCodingInterview 

Anagram Checker–To check if 2 strings are anagrams

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem  Wap to find out if 2 strings are anagrams or not. Anagrams Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive).Similarily, abcd and abdc are anagrams, but abcd and abdce is not. Solution A simple way to check if two strings are anagrams is to find out if the numeric sum of the characters in the strings is equal. [Read More]
kodeknight  String  java-code  anagrams  hashes  CrackingTheCodingInterview 

Sorting a Stack using push,pop,isEmpty and peek

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek. This question is asked in cracking the coding interview. Other ways of asking the question Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you dont pop out the element but peek and see. [Read More]
kodeknight  interview  Data Structures  DS  sorting  CrackingTheCodingInterview  stack 

Implement a Queue using two stacks

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

Problem Implement a Queue using two stacks. Solution Logic :  We’ll implement a FIFO queue using two stacks.Lets call the stacks Instack and Outstack. Enqueue: An element is inserted in the queue by pushing it into the Instack.  ** Dequeue:** An element is extracted from the queue by popping it from the Outstack.  If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order. [Read More]
kodeknight  queue  CrackingTheCodingInterview  stack