Find the maximum distance covered using n bikes

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem There are n bikes and each can cover 100 km when fully fueled. What is the maximum amount of distance you can go using n bikes? You may assume that all bikes are similar and a bike takes 1 litre to cover 1 km. Solution There are couple of ways. Lets find the right solution. Say n = 50. Naive Solution: The most naive solution would be to just make all the bikes go together. [Read More]
kodeknight  Puzzles 

Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

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

Problem Given a binary tree, find out if the tree can be folded or not. A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable. Examples Consider the below trees: (a) and (b) can be folded. (c) and (d) cannot be folded. (a) 10 / \\ 7 15 \\ / 9 11 (b) 10 / \\ 7 15 / \\ 9 11 (c) 10 / \\ 7 15 / / 5 11 (d) 10 / \\ 7 15 / \\ / 9 10 12 Solution Method 1 (Change Left subtree to its Mirror and compare it with Right subtree) [Read More]
Binary Tree  BT  kodeknight 

Given a node in binary tree - Check if left and right subtree are mirror of each other

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

Problem A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples. Example 1 / \ 2 2 ```TRUE 1 / \ 2 2 \ 3 1 / \ 2 2 / \ / \ 4 3 3 4 1 / \ 2 2 / \ / \ [Read More]
Binary Tree  BT  kodeknight  Amazon 

Union and Intersection of two unsorted Linked Lists

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

Problem Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter. Example Input: List1: 10->15->4->20 lsit2: 8->4->2->10 Output: Intersection List: 4->10 Union List: 2->8->20->4->15->10 Solution Method 1 - Simple Following are simple algorithms to get union and intersection lists respectively. Intersection (list1, list2) Initialize result list as NULL. Traverse list1 and look for its each element in list2, if the element is present in list2, then add the element to result. [Read More]
kodeknight  merge  Single Link List  unsorted-array  linked list  two-lists  merge-sort 

Union and Intersection of two sorted arrays

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

Problem Find Union and Intersection of two sorted arrays Example For example, if the input arrays are: arr1[] = {1, 3, 4, 5, 7} arr2[] = {2, 3, 5, 6} Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}. Solution Algorithm Union(arr1[], arr2[]): For union of two arrays, follow the following merge procedure. Use two index variables i and j, initial values i = 0, j = 0 If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i. [Read More]
Adobe  kodeknight  merge  union  two-sorted-arrays  intersection 

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 

Algorithm Interview Questions - Set 1

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

A period of time where users login and logout, given a sets of login and logout time pairs, write a function that can show the number of users online at any given time. Intersection of n sets without using a hash table. Implement a LRU(Least Recently Used) cache Implement a function to compute cubic root what is the time complexity? Given a matrix with 1′s and 0′s, find the number of groups of 1′s. [Read More]
Algorithms  kodeknight  interview-set 

Design Questions - Set 1

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

Design a game of chess Given an ebay site model., you have to deal with auctioning of a particular item. Design the billing & auctioning system of the same. OOPs design of a file system Class diagram of a system to implement Blackjack Class diagram of a parking lot design a furniture module, a furniture could be a couch, chair, etc. each furniture could contain multiple materials, wood, steel, etc. [Read More]
kodeknight  interview-set 

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

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

Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Example Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1 Solution Method 1 (Simple but Inefficient) [Read More]
Algorithms  kodeknight  sorting  array  distance