Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].

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

Given an integer array of which both first half and second half are sorted. Write a function to merge the two parts to create one single sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to: [-5,-2,1,3,3,6,8,8]

http://stackoverflow.com/questions/6153915/merging-of-two-sorted-halfs-without-extra-memory

kodeknight  merge  incomplete  array  bitonic  sorted-array 

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 

k-way merge - Merging k sorted arrays of n elements

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

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr\[\]\[\] = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]
kodeknight  merge  divide and conquer  sorting  array  two-sorted-arrays  min-heap  sorted-array 

Find the maximum repeating number in array where all the elements are in range 0 to k-1, k ∈ [0,N]

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

Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). [Read More]
kodeknight  duplicate  array 

Finding the max repeated element in an array

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

Problem : Find the element which occurs maximum number of times. METHOD 1 : Sorting the array and scanning the array The simple solution is to Sort the array Scan the array such that keep the track of the elements which occurred max number of times METHOD 2 : Using Binary Search Tree We can have a binary search tree with an extra field count, which indicates the number of times an element appeared in the input. [Read More]
max  kodeknight  duplicate  array 

Print letters followed by their frequency (Run Length Encoding)

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

Given a string ,Write a program to print letter followed by it’s frequency.This is also knows as Run Length Encoding. Example: Input aaabcc Output a3b1c2 Algorithm: 1.Pick the first character from the string and print it. 2.Count the number of subsequent occurrences of the picked character and then print the count. 3.Pick the next character and repeat step 2 till we reach end of the String. #include <iostream> #include<string> using namespace std; int main() { string str = "aaabcc"; int count=0; int i=0,j; int l = str. [Read More]
kodeknight  String  frequency  encoding 

Remove duplicate characters in a string

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

Problem Given a string, Write a program to remove duplcate characters from the string. Input String : kodeknight Output String : kodenight Solution Method 1 : Brute force void removeDuplicates(char \*str) { if (!str) return; int len = strlen(str); if (len < 2) return; int tail = 1; for (int i = 1; i < len; ++i) { int j; for (j = 0; j < tail; ++j) if (str\[i\] == str\[j\]) break; if (j == tail) { str\[tail\] = str\[i\]; ++tail; } } str\[tail\] = '\\0'; } Time Complexity : O(N^2) [Read More]
kodeknight  String  java-code  duplicate  CrackingTheCodingInterview  remove-duplicates 

Find first non repeating character in a string

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

You are given a string, find its first non-repeating character?

Algorithm:

  1. Scan the string from left to right and construct the count array.
  2. Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it.

Code :

#include<stdlib.h>  
#include<stdio.h>  
#define NO\_OF\_CHARS 256  
  
/\* The function returns index of first non-repeating  
   character in a string \*/  
int getFirstNonRepeating(char \*str)  
{  
 int \*count = (int \*)calloc(sizeof(int), NO\_OF\_CHARS);  
 int i;  
 for (i = 0; \*(str+i);  i++)  
   count\[\*(str+i)\]++;  
 int index = -1;  
  
 for (i = 0; \*(str+i);  i++)  
 {  
  if(count\[\*(str+i)\] == 1)  
  {  
    index = i;  
    break;  
  }  
 }  
 return index;  
}

Time complexity: O(N)

kodeknight  String  duplicate 

Reverse a c-style string

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

For example if a user enters a string “kodeknight” then on reversing the string will be “thginkedok“. The basic approach here is to swap the first half of the string, with the next half. Method 1 - Iterative using string length #include<stdio.h> int string\_length(char\*); void reverse(char\*); int main() { char string\[100\]; printf("Enter a string\\n"); gets(string); reverse(string); printf("Reverse of entered string is \\"%s\\".\\n", string); return 0; } void reverse(char \*string) { int length, i; char \*begin, \*end, temp; length = string\_length(string); begin = string; end = string; for ( i = 0 ; i < ( length - 1 ) ; i++ ) end++; // swap the chars till half of the length of the string //begin with the end char and so on for ( i = 0 ; i < length/2 ; i++ ) { temp = \*end; \*end = \*begin; \*begin = temp; begin++; end--; } } int string\_length(char \*ptr) { int len = 0; while( \*(ptr+len) ! [Read More]
kodeknight  String  reverse  CrackingTheCodingInterview 

Eliminate the pairs (two same chars adjacent to each other) in string

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

Problem: You are given a string. You have to eliminate the pairs (two same chars adjacent to each other). eg. input string RGBBGBGR –> RGGBGR–> RBGR (output) Solution: We should check if we have character pair then cancel it. and then check for next character and previous character. Keep canceling the character until we either reach start of the array or end of the array or not find a pair. [Read More]
kodeknight  String