Point inside a triangle or NOT

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

Problem Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not. Example For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15) B(10,30) / \\ / \\ / \\ / P \\ P' / \\ A(0,0) ----------- C(20,0) Solution Method 1 - Area of triangles made by point and other 2 vertices of triangle [Read More]
coordinate geometry  kodeknight  Microsoft  maths 

Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0

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

Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0 Example **Input : ** 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution [Read More]
kodeknight  Microsoft  2DArray  java-code  binary array  boolean  matrix  CrackingTheCodingInterview  zero 

Given a dictionary of word - Group all words into set of anagrams of each other

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

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets. input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ] 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). Approach The simpler logic would be to : [Read More]
kodeknight  Microsoft  String  Amazon  anagrams 

K – Reverse a linked list

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

This is one of the questions asked in Microsoft Interview. Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list. The following are the constraints given: If the no. of nodes in a link list is not a multiple of k then left-out nodes in the end should remain as it is You have to retain the memory address of the nodes without modifying it i. [Read More]
kodeknight  Microsoft  link list  reverse  Amazon  Single Link List  incomplete 

Globe Walker

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

Problem : How many points are there on the globe where, by walking one mile south, then one mile east and then one mile north, you would reach the place where you started? Solution :  The trivial answer to this question is one point, namely, the North Pole. But if you think that answer should suffice, you might want to think again! Let’s think this through methodically. If we consider the southern hemisphere, there is a ring near the South Pole that has a circumference of one mile. [Read More]
kodeknight  Microsoft  brainteaser 

Spiral printing of a two dimensional array

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

Given a 2D array, print it in spiral form. Examples See the following examples. Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is : [Read More]
kodeknight  Microsoft  2DArray  Interview Question  array  matrix 

Median of 2 sorted arrays of equal size n

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

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]
Adobe  kodeknight  Microsoft  yahoo  divide and conquer  Amazon  array  two-sorted-arrays  median  incomplete  two-arrays  sorted-array 

Important ds question

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

a) Write a function that validates whether a tree is a BST or not. b) Write a function to find the common ancestor of two given nodes of binary tree. c) In a BST, value of two of the nodes got exchanged by mistake. Write a function to correct the BST. d) In a array, there exists a majority element(a no. repeated atleast n/2 + 1 times) and rest of the no. [Read More]
kodeknight  Microsoft  Amazon  Data Structures  DS  sorting  binary-search-tree  BST