Lazy Caterer's sequence

 Posted on June 10, 2015  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that. Solution The solution to this is very simple, if you know mathematics. :P Number of pieces p p = ( n^2+n+2)/2 p = C(n+1,2) + 1 ``` More on wikipedia - [http://en. [Read More]
kodeknight  Interview Question  mathematics 

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

 Posted on July 30, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Method 1 - Using hashset on str2 and boolean array or hashset on str2 Break down the problem into two tasks. i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose. ii) Finding if all the characters hashed in the first string are available in the second string. [Read More]
kodeknight  String  two-string  Amazon  Interview Question  unique 

Data structure and algorithm interview question for java programmers

 Posted on May 3, 2014  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Question 1 : How to find middle element of linked list in one pass? One of the most popular question from data structures and algorithm, mostly asked on telephonic interview. Since many programmer know that, in order to find length of linked list we need to first traverse through linkedlist till we find last node, which is pointing to null, and then in second pass we can find middle element by traversing only half of length. [Read More]
kodeknight  Interview Question  java 

Amazon Questions - Set 1

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  20 minutes  |  Kinshuk Chandra

Write code to find Nth last node in a linked list. Solution Given a binary tree build a vertical sum array. Solution Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1? Solution Given two lists of strings return a list of strings that is an intersection of both of the lists. Analyze running time and space complexity. Give Test Case scenarios. [Read More]
kodeknight  Amazon  incomplete  Interview Question  interview-set 

Finding an integer that repeats odd number of times in an array of positive integers

 Posted on January 5, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity? Solutions Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. [Read More]
search  Algorithms  ArraySearch  kodeknight  duplicate  Interview Question  array  integer-sort  bits 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

for(int j=arrIndex/2 ; j < arrIndex;j++) …

shanky - Nov 0, 2014

for(int j=arrIndex/2 ; j < arrIndex;j++)
{
if(array[j]==1)
return j;//this is our index
}

This makes the approach O(n)
Do a regular binary search after finding the cap , with range i/2 to i

Hi Shanky, you are right. That’s what I have done :)

search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Find the point of transition from 0 to 1 in an infinite sorted array containings only 0 and 1 .

 Posted on January 2, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Approach 1(bad): Iterating over the array until we find 1, as the array is sort. In worst case it will go till the last element, and hence this is bad approach. Approach 2 : Club binary search approach and array’s random access property Since the array is infinitely increasing i.e. we don’t know array size in advance, so we can’t directly apply traditional BinarySearch (in which we partition the problem size in half in each iteration, kind of top down approach). [Read More]
search  ArraySearch  kodeknight  binary array  Amazon  Interview Question  array  binary search  integer-array  integer-sort  zero 

Longest increasing subsequence

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

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution. Problem Input : Sequence of integers (or any comparable items) Output : Longest increasing subsequence of the sequence, which may not be contiguous. For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. Note that the numbers are non-contiguous. [Read More]
kodeknight  Dynamic Programming  DP  Amazon  incomplete  Interview Question  google 

Vertical Sum of a Binary Tree

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

please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words Added the basic algo for that: 1. Start with the root node and empty double list listNode 2. Add the value of the rootNode to the current listNode 3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively. 4. Similarly for right node Please let me know if I have not explained it properly. [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL 

Vertical Sum of a Binary Tree

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

Question : Find vertical sum of given binary tree. Example: 1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7 We need to output: 4 2 12 3 7 [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL