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 

Finding IP Address from hostname in Windows Linux and Unix

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

IP Address from hostname in Windows and Linux How many times in a day you have a hostname and you want to know the IP address? Host name to IP address and IP address to hostname conversion is one of frequent thing which we need to do for many things when dealing with networking command in unix. For one command we need IP address for other we need hostname even from bash script some time we require hostname and some time we look for IP address. [Read More]
kodeknight 

Skiplist vs Binary tree

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

Here are some of the differences Skiplist Binary tree Concurrency - Skip lists are more amenable to concurrent access/modification. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked. pressure. The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. [Read More]
differences  kodeknight  linux  unix  skip-list 

Skiplists

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

Goal To understand skiplist. Definition Skiplist is a dynamic search structure, as it is dynamic when it comes to insertion and deletion, which supports search). Other dynamic search structure: Treaps Red black tree B-Trees (2-3 trees etc) Operations on skiplist Search - O(log n) Insert - O(log n) Delete - O(log n) These operations are with high probability, 1/polynomial depending on polynomial number of operation. [Read More]
kodeknight  incomplete  Data Structure  linux  unix  concurrency  skip-list