raghu.aok
BAN USER- 0of 0 votes
AnswersPlease analyze the two slightly obfuscated Tcl procedures below and document the code as it should be. Please change the symbol names to reasonable descriptive names. In addition, an explanation of why these procedures might or might not be useful or suggestions for improvements would be most welcome. This code comes from the application you would be working on. I replaced the names and removed the comments to make the challenge. Feel free to do research and experimentation, but please do not ask anyone else to solve it for you. proc f1 {a} { set n [llength $a] set p {} for {set i 0} {$i < $n} {incr i} { for {set j [expr {$i + 1}]} {$j < $n} {incr j} { lappend p [list [lindex $a $i] [lindex $a $j]] } } return $p }
- raghu.aok in Indiaproc f2 {fn lst {vn {}\}} { set result {} lassign $fn a b n if {$n eq {}} { set n {::} } set cl {} foreach n $vn { upvar 1 $n v set cl "${cl}set $n {$v}\n" } set cfn [list $a "${cl}${b}" $n] foreach item $lst { lappend result [apply $cfn $item] } return $result }
| Report Duplicate | Flag | PURGE
SDE-2 Coding - 0of 0 votes
AnswersThe problem is quite interesting.
- raghu.aok
We have to find the integer solution of the below equation .
n<=sum of(ki*xi)<n+1
such that ki are all constants, xi are integers.
For example : 4<=1.4x1+3.4*x2+1.1*x3<5
solutions (x1,x2,x3) =(1,1,0),(3,0,0),(0,1,1),(0,0,4) ...| Report Duplicate | Flag | PURGE
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <sstream>
using namespace std;
vector<char> vowels = { 'a','e','i','o','u' };
// Find substring that starts with vowel and ends with consonant given a string
void printString(const string& str)
{
stringstream chs;
char ch;
int count = 0;
//map<int ,char> mmap;
vector<int> vecc;
for (auto& x : vowels)
{
count = 0;
vector<int> vec = {};
chs.ignore(100, '\n');
chs.clear();
chs << str;
while (chs.get(ch) && chs.peek())
{
if (ch == x) {
vec.push_back(count);
vecc.push_back(count);
//mmap[count] = ch;
}
count++;
}
}
if (vecc.size() == str.size() || vecc.size()==0) {
cout << "No fucking strings!" << endl;
return;
}
sort(vecc.begin(), vecc.end());
vector<int> vecx;
//vector<int> vecy;
for (int i = 1; i < int(vecc.size()) - 1; i++)
{
if (vecc[i] == vecc[i - 1] + 1 && vecc[i] == vecc[i + 1] - 1) {
vecx.push_back(i - vecx.size());
//vecy.push_back(vecc[i]);
}
}
for (int i = 0; i < int(vecx.size()); i++)
vecc.erase(vecc.begin() + vecx[i]);
count = 0;
map<string, int> xxxx;
if (find(vecc.begin(), vecc.end(), str.size() - 1) == vecc.end())
vecc.push_back(str.size() - 1);
for (int i = 0; i < int(vecc.size()) - 1; i++) {
pair<string, int> p(str.substr(vecc[i], vecc[i + 1] - vecc[i] + 2), vecc[i]);
xxxx.insert(p);
}
auto it = xxxx.begin();
auto et = xxxx.rbegin();
cout << it->first << endl;
if (vecc[vecc.size() - 1] != str.size() - 1)
cout << str.substr(et->second, (vecc[vecc.size() - 1] - et->second)) << endl;
else
cout << str.substr(et->second) << endl;
}
int main()
{
printString("utyrulqaeuouiecodjlmjeaummaoqkexylwaaopnfvlbiiiidyckzfh");
printString("aab");
printString("aaaaa");
printString("nhhhnnn");
return 0;
}
This can be solved by using appropriate data structure linked list may be,
give a matrix of matrixN*matrixN
template <typename T, typename... Args>
T minAll(T a, T b, Args... args)
{
return minAll(a < b ? a : b, args...);
}
template <typename T> T minAll(T t, T x) {
return (t < x ? t : x);
}
Index of (i,j) to index of Linked list is
int MatrixRemove(int i, int j)
{
int depth = minAll(i, j, matrixN - i, matrixN - j);
cout << "Depth " << depth << endl;
int start=0;
if (depth != 0)
{
for (int i=1;i<=depth;i++)
start = start + (matrixN-2*(i-1))*4;
}
cout << "Start " << start << endl;
if (j >= i)
return start + (i - depth) + (j - depth);
else
return start+((matrixN - 2*depth)*4 - (i-depth + j-depth));
}
find the value take O(logn) in sorted list and insertion will also take O(logn) in sorted list.
- raghu.aok June 16, 2016The idea here is to parse the matrix diagnolly
int b[4][4] = { { 1,1,1,0 },{ 0,0,1,0 },{ 0,0,1,0 },{ 0,0,0,0 } };
bool check1(int row,int col)
{
if (col == 0 && row != 0)
{
if (b[row - 1][col] == 1)
return true;
}
else if (row == 0 && col != 0)
{
if (b[row][col-1] == 1 || b[row + 1][col - 1] == 1)
return true;
}
else if (row == 0 && col == 0)
return false;
else if (b[row + 1][col - 1] == 1 || b[row][col - 1] == 1 || b[row - 1][col] == 1)
return true;
return false;
}
int main()
{
int a[] = { 9,3,8,11,12,4,7,0,7,8 };
int islands = 0;
for (int i = 0; i < 7; i++)
{
int j,k,count;
if (i < 4) {
j = 0;
k = i -j;
count = k;
while (j<=count)
{
if (b[j][k] == 1) {
if (!check1(j, k))
{
cout << j << " " << k << endl;
islands++;
}
}
j++;
k = i - j;
}
}
else if(i>=4)
{
k = 3;
j = i - k;
count = j;
while (k>=count)
{
if (b[j][k] == 1) {
if (!check1(j, k))
{
cout << j << " " << k << endl;
islands++;
}
}
j++;
k= i - j;
}
}
}
cout << islands;
return 0;
}
void palindrome(char *str)
{
int i = 1;
int count = 0;
while (str[i] != '\0')
{
if (str[i - 1] == str[i + 1]) {
int j = i, k = i;
while (str[j] == str[k] && j >= 0 && str[k] != '\0')
{
count++;
k++;
j--;
}
j++;
k--;
while (j <= k)
{
cout << str[j];
j++;
}
i = k;
}
else
i++;
cout << endl;
}
}
int main()
{
char *s = "ABCDCBAAA";
char *s1 = "DEFABCBAYT";
palindrome(s);
palindrome(s1);
return 0;
}
Step 1 can be done by tortise heir algorithm. Rest of the steps are evident i guess
FindLeaf()
{
node *temp1=root;
node *temp2=root;
while(temp1!=temp2)
{
temp1=movenext(temp1);
temp2=movenext(temp2);
temp2=movenext(temp2);
}
node *leftnode=temp1;
}
node *movenext(node *temp)
{
if(temp->left!=NULL)
temp=temp->left;
else
temp=temp->right;
return temp;
}
Step2 --> Max of Iterate thru DLL and binary search for the height.
- raghu.aok May 25, 2016The basic solution can be achieved by the below steps ::
1) Find atleast one leaf node
2) Loop thru doing binary search all the leaf nodes as they are all in DLL which will return the level of the node.
3) Find the maximum of the return value which will be the height of the tree
Step 1:: In at max O(n)
Step 2:: No of Leaf nodes*binary search --- O(nlogn)
Step 3 :: No of Leaf Nodes
So order of the above operation is O(nlogn) in worst case
Aerage will be O(logn^2)
Best case will be O(n)
tortise heir algorithm,
You take two pointers pointing to head
slow_ptr and fast_ptr;
slow_ptr moves one step ahead
and fast ptr moves two steps
below is the function in c++
midwaylist(node *head)
{
node *slow_ptr=head;
node *fast_ptr=head;
while(fast_ptr->next!=NULL || fast_ptr!=NULL)
{
slow_ptr=slow_ptr->next;
fast_ptr=fast_ptr->next->next;
}
cout << "Mid value is " << slow_ptr->data << endl;
}
While inserting node maintain horizontal and vertical level of each node as below ::
class node {
private :
int data;
node *left;
node *right;
int level[2];
public :
node(node *rig,node *lef, int d, int vlevel,int hlevel)
{
data=d;
left=lef;
right=rig;
level[0]=vlevel;
level[1]=hlevel;
}
int getData()
{
return data;
}
node *getLeftChild(){
return left;
}
node *getRightChild() {
return right;
}
void setLeftChild(node *n){
left=n;
}
void setRightChild(node *n) {
right=n;
}
void sethLevel(int a)
{
level[1]=a;
}
int gethLevel()
{
return level[1];
}
void setvLevel(int a)
{
level[0]=a;
}
int getvLevel()
{
return level[0];
}
node *getNeighbor()
{
return neighbor;
}
void setNeighbor(node *n)
{
neighbor=n;
}
};
class BST {
private :
node *root;
int _size;
map<int,int> lev;
vector<vector<int> > vec;
int height;
public :
BST() : root(NULL),height(0) {}
BST(int *arr, int siz)
{
_size=siz;
for(int i=0;i<_size;i++)
{
InsertNode(arr[i]);
}
}
void InsertNode(int value)
{
int heit=0;
node *temp=root;
if(temp==NULL)
{
cout << "Adding the root Node" << value << endl;
node *nod=new node(NULL,NULL,value,0,0);
root=nod;
}
while(temp!=NULL)
{
heit++;
if(value>temp->getData())
{
if(temp->getRightChild()==NULL)
{
cout << "Adding the new node" << value << endl;
node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel()+1);
temp->setRightChild(nod);
temp=NULL;
}
else
{
cout << "Moving Right " << temp->getData() << endl;
temp=temp->getRightChild();
}
}
else
{
if(temp->getLeftChild()==NULL)
{
cout << "Adding the new node" << value << endl;
node *nod=new node(NULL,NULL,value,temp->getvLevel()+1,2*temp->gethLevel());
temp->setLeftChild(nod);
temp=NULL;
}
else
{
cout << "Moving Left " << temp->getData() << endl;
temp=temp->getLeftChild();
}
}
}
if(heit>height)
height=heit;
}
Now maintain a map as below ::
map<pair<int,int>,node *>
Now given a node, you can get vertical level and horizontal level.
from that you get the neighbor by incrementing the horizontal level and fetching the node from the map. All the non values are set to NULL.
It is same as saying ::
sum=sum+(b&1)a+(b>>1&1)a*2+(b>>1&1)a*4+(b>>1&1)a*8 ......
For example ::
344*244
is put it in form (344/2)*(244*2)
(172/2)*(244*4)
(86/2)*(244*8)=43*244*8
sum=sum+244*8;
sum=sum+244*16;
sum=sum+244*64;
sum=sum+244*256;
This can be simply put as
while(b!=0)
{
if(b is odd)
sum=sum+a;
b=b/2;
a=a*2;
}
Input is as below ::
START TIME:2015-12-01 04:13:15
END TIME:2015-12-01 04:12:15
START TIME:2015-12-01 04:12:15
END TIME:2015-12-01 04:10:15
I haven't taken exact input as given in the question because i don't want to give the exact answer. Small changes are needed for the above input
#include <iostream>
#include <queue>
using namespace std;
int arr[4][4]={{1,0,0,0},{1,0,0,0},{1,0,0,0},{1,0,0,0}};
int main ()
{
queue<int> myqueue,copyqueue;
int val=0,cnt=0,res;
for (int i=0; i<4; ++i) { myqueue.push(i) ; copyqueue.push(i) ; }
cnt=myqueue.size();
while (!myqueue.empty())
{
if(myqueue.size()==1||val==4){
break;
}
copyqueue=myqueue;
for(int i=0;i<cnt;i++)
{
res=myqueue.front();
if(arr[res][val]==0)
{
myqueue.pop();
}
else
{
myqueue.pop();
myqueue.push(res);
}
}
if(myqueue.empty()){
myqueue=copyqueue;
}
val++;
cnt=myqueue.size();
}
if(myqueue.size()==4){
cout << "All are equal" << endl;
return 0;
}
while(myqueue.size()!=0)
{
res=myqueue.front();
myqueue.pop();
cout << "Final Result : " << res << endl;
}
return 0;
}
Just detailing what you have done
May be we can validate based on the size of legal string
For example ::
size of given string is n.
Assume Legal string size is n -- only one possible
n-1 -- 2 possible
n-2 -- 3 ..
.
.
if we find the legal string we can stop and say it is the largest because we do not have to look for smaller strings.
Worst case would be when we do not find the string :O(n^2) but average case would be lot faster.
- raghu.aok June 22, 2016